Bài giảng 29: Tối ưu hóa có ràng buộc

Các kỹ sư, nhà kinh tế học, nhà khoa học và toán học thường cần tìm giá trị lớn nhất hoặc nhỏ nhất của một dạng toàn phương $Q(\mathbf{x})$ khi $\mathbf{x}$ nằm trong một tập hợp xác định. Thông thường, bài toán có thể được sắp xếp sao cho $\mathbf{x}$ biến thiên trong tập các vector đơn vị. Bài toán tối ưu hóa có ràng buộc này có một lời giải rất thú vị và tao nhã. Ví dụ 6 sẽ minh họa cách các bài toán như vậy phát sinh trong thực tế.

Yêu cầu rằng một vector $\mathbf{x}$ trong ℝⁿ là một vector đơn vị có thể được phát biểu theo nhiều cách tương đương nhau:

$\|\mathbf{x}\|=1,\quad\|\mathbf{x}\|^{2}=1,\quad\mathbf{x}^{T}\mathbf{x}=1$

và

(1) $\begin{equation*}x_{1}^{2}+x_{2}^{2}+\cdots+x_{n}^{2}=1\end{equation*}$

Dạng triển khai đầy đủ (1) của phương trình $\mathbf{x}^{T}\mathbf{x}=1$ thường được sử dụng trong các ứng dụng thực tế. Khi một dạng toàn phương $Q$ không có các hạng tử tích chéo, thì việc tìm giá trị lớn nhất và nhỏ nhất của $Q(\mathbf{x})$ với điều kiện $\mathbf{x}^{T}\mathbf{x}=1$ trở nên dễ dàng hơn.

Ví dụ 1: Tìm giá trị lớn nhất và nhỏ nhất của $Q(\mathbf{x})=9x_1^2+4x_2^2+3x_3^2$ với điều kiện ràng buộc $\mathbf{x}^{T}\mathbf{x}=1$ .

Giải: Vì $x_2^2$ và $x_3^2$ là không âm, ta có

$4x_2^2\leq 9x_2^2$ và $3x_3^2\leq 9x_3^2$

Do đó:

$\begin{matrix}Q(\mathbf{x})=&9x_1^2+4x_2^2+3x_3^2\\\leq&9x_1^2+9x_2^2+9x_3^2\\=&9(x_1^2+x_2^2+x_3^2)=9\\\end{matrix}$

khi $x_1^2+x_2^2+x_3^2=1$ . Vì vậy, giá trị lớn nhất của $Q(\mathbf{x})$ không vượt quá 9 khi $\mathbf{x}$ là một vector đơn vị. Hơn nữa, $Q(\mathbf{x})=9$ khi $\mathbf{x}=(1,0,0)$ . Do đó, 9 là giá trị lớn nhất của $Q(\mathbf{x})$ khi $\mathbf{x}^{T}\mathbf{x}=1$ .

Để tìm giá trị nhỏ nhất của $Q(\mathbf{x})$ , ta nhận thấy:

$9x_1^2\geq 3x_1^2;\quad 4x_2^2\geq 3x_2^2$

nên:

$Q(\mathbf{x})\geq 3x_1^2+3x_2^2+3x_3^2=3(x_1^2+x_2^2+x_3^2)=3$

khi $x_1^2+x_2^2+x_3^2=1$ . Ngoài ra, $Q(\mathbf{x})=3$ khi $x_1=0,x_2=0$ và $x_3=1$ . Vậy 3 là giá trị nhỏ nhất của $Q(\mathbf{x})$ khi $\mathbf{x}^{T}\mathbf{x}=1$ .

Dễ thấy trong ví dụ 1, ma trận của dạng toàn phương $Q$ có các giá trị riêng là 9, 4 và 3, và giá trị riêng lớn nhất và nhỏ nhất chính là giá trị lớn nhất và nhỏ nhất (có ràng buộc) của $Q(\mathbf{x})$ . Điều này cũng đúng với mọi dạng toàn phương, như ta sẽ thấy sau.

Ví dụ 2: Cho $A=\begin{bmatrix}3&0\\0&7\end{bmatrix}$ , và $Q(\mathbf{x})=\mathbf{x}^T A\mathbf{x}$ với $\mathbf{x}\in\mathbb{R}^2$ . Hình 1 hiển thị đồ thị của hàm $Q$ . Hình 2 chỉ hiển thị phần của đồ thị nằm bên trong một hình trụ; giao điểm của hình trụ với mặt cong là tập hợp các điểm $(x_1,x_2,z)$ sao cho $z=Q(x_1,x_2)$ và $x_1^2+x_2^2=1$ . “Độ cao” của các điểm này chính là giá trị bị ràng buộc của $Q(\mathbf{x})$ . Về mặt hình học, bài toán tối ưu có ràng buộc là tìm các điểm cao nhất và thấp nhất trên đường giao nhau đó.

Hai điểm cao nhất trên đường cong cách mặt phẳng $x_1x_2$ một khoảng 7 đơn vị, xảy ra tại $x_1=0$ và $x_2=\pm1$ . Những điểm này tương ứng với trị riêng 7 của ma trận $A$ , và các vector riêng tương ứng là $\mathbf{x}=(0,1)$ và $-\mathbf{x}=(0,-1)$ . Tương tự, hai điểm thấp nhất trên đường cong cách mặt phẳng $x_1x_2$ một khoảng 3 đơn vị. Chúng tương ứng với trị riêng 3 và các vector riêng $(1,0)$ và $(-1,0)$ .

Hnh 2 giao tuyến của mặt $z=3x_{1}^{2}+7x_{2}^{2}$ và hình trụ $x_{1}^{2}+x_{2}^{2}=1$ .

Mỗi điểm trên đường giao nhau trong hình 2 có tọa độ $z$ nằm giữa 3 và 7, và với bất kỳ số nào $t$ nằm trong khoảng từ 3 đến 7, đều tồn tại một vector đơn vị $\mathbf{x}$ sao cho $Q(\mathbf{x})=t$ . Nói cách khác, tập hợp tất cả các giá trị có thể có của $\mathbf{x}^T A\mathbf{x}$ , với $\|\mathbf{x}\|=1$ , là đoạn đóng từ 3 đến 7.

Có thể chứng minh rằng, với bất kỳ ma trận đối xứng $A$ , tập hợp tất cả các giá trị của $\mathbf{x}^T A\mathbf{x}$ khi $\|\mathbf{x}\|=1$ là một đoạn đóng trên trục số thực. Gọi điểm đầu bên trái và bên phải của đoạn này lần lượt là $m$ và $M$ . Cụ thể:

(2) $\begin{equation*}m=\min\{\mathbf{x}^T A\mathbf{x}:\|\mathbf{x}\|=1\},\quad M=\max\{\mathbf{x}^T A\mathbf{x}:\|\mathbf{x}\|=1\}\end{equation*}$

Định lý tiếp theo khẳng định rằng chính $m$ và $M$ cũng là các trị riêng của $A$ , giống như trong ví dụ 2.

Định Lý 6
Cho  là một ma trận đối xứng, và định nghĩa  và  như trong biểu thức (2). Khi đó:
•	 là trị riêng lớn nhất  của ,
•	 là trị riêng nhỏ nhất của .
Giá trị của  đạt được là  khi  là một vector riêng đơn vị  tương ứng với .
Tương tự, giá trị của  là  khi  là một vector riêng đơn vị tương ứng với .

Chứng minh: Chúng ta trực giao hóa đường chéo ma trận $A$ dưới dạng $A=P D P^{-1}$ . Ta biết rằng:

(3) $\begin{equation*}\mathbf{x}^T A\mathbf{x}=\mathbf{y}^T D\mathbf{y}\quad\text{khi}\,\mathbf{x}=P\mathbf{y}\end{equation*}$

Ngoài ra,

$\|\mathbf{x}\|=\|P\mathbf{y}\|=\|\mathbf{y}\|,\quad\forall\mathbf{y}$

vì $P^T P=I$ , nên $\|P\mathbf{y}\|^2=(P\mathbf{y})^T(P\mathbf{y})=\mathbf{y}^T P^T P\mathbf{y}=\mathbf{y}^T\mathbf{y}=\|\mathbf{y}\|^2$ . Cụ thể, $\|\mathbf{y}\|=1$ khi và chỉ khi $\|\mathbf{x}\|=1$ . Do đó, $\mathbf{x}^T A\mathbf{x}$ và $\mathbf{y}^T D\mathbf{y}$ nhận cùng một tập giá trị khi $\mathbf{x}$ và $\mathbf{y}$ chạy qua tất cả các vector đơn vị.

Để đơn giản ký hiệu, giả sử $A$ là ma trận $3\times 3$ với các giá trị riêng $a\ge b\ge c$ . Sắp xếp các vector riêng làm cột của $P$ sao cho $P=\begin{bmatrix}\mathbf{u}_1&\mathbf{u}_2&\mathbf{u}_3\\\end{bmatrix}$ , và:

$D=\begin{bmatrix}a&0&0\\0&b&0\\0&0&c\end{bmatrix}$

Với bất kỳ vector đơn vị $\mathbf{y}\in\mathbb{R}^3$ có tọa độ $y_1,y_2,y_3$ , ta xét:

$\begin{matrix}a y_1^2=&a y_1^2\\\\b y_2^2\le&a y_2^2\\\\c y_3^2\le&a y_3^2\\\\\end{matrix}$

Và có các bất đẳng thức sau:

$\begin{matrix}\mathbf{y}^T D\mathbf{y}=&a y_1^2+b y_2^2+c y_3^2\\\le&a(y_1^2+y_2^2+y_3^2)\\=&a(y_1^2+y_2^2+y_3^2)\\=&a\|\mathbf{y}\|^2=a\\\end{matrix}$

Do đó, theo định nghĩa, $M\le a$ . Tuy nhiên, $\mathbf{y}^T D\mathbf{y}=a$ khi $\mathbf{y}=\mathbf{e}_1=(1,0,0)$ , nên thật ra $M= a$ . Theo biểu thức ở trên, $\mathbf{x}$ tương ứng với $\mathbf{y}=\mathbf{e}_1$ là eigenvector $\mathbf{u}_1$ của $A$ , vì:

$\mathbf{x}=P\mathbf{e}_1=[\mathbf{u}_1\,\mathbf{u}_2\,\mathbf{u}_3]\begin{bmatrix}1\\0\\0\end{bmatrix}=\mathbf{u}_1$

Vậy nên $M=a=\mathbf{e}_1^T D\mathbf{e}_1=\mathbf{u}_1^T A\mathbf{u}_1$ , điều này chứng minh phát biểu về $M$ . Tương tự, ta cũng chứng minh được rằng $m$ là giá trị riêng nhỏ nhất, $c$ , và giá trị này của $\mathbf{x}^T A\mathbf{x}$ đạt được khi $\mathbf{x}=P\mathbf{e}_3=\mathbf{u}_3$ .

Ví dụ 3: Cho ma trận $A=\begin{bmatrix}3&2&1\\2&3&1\\1&1&4\end{bmatrix}$ . Hãy tìm giá trị lớn nhất của dạng toàn phương $\mathbf{x}^T A\mathbf{x}$ với điều kiện ràng buộc $\mathbf{x}^{T}\mathbf{x}=1$ , và tìm một vector đơn vị tại đó giá trị lớn nhất này đạt được.

Lời giải: Theo định lý 6, giá trị lớn nhất cần tìm chính là giá trị riêng lớn nhất của ma trận $A$ . Phương trình đặc trưng là:

$0=-\lambda^3+10\lambda^2-27\lambda+18=-(\lambda-6)(\lambda-3)(\lambda-1)$

Vậy giá trị riêng lớn nhất là 6.

Giá trị lớn nhất có điều kiện của $\mathbf{x}^T A\mathbf{x}$ đạt được khi $\mathbf{x}$ là vector riêng đơn vị ứng với giá trị riêng $\lambda=6$ . Giải $(A-6I)\mathbf{x}=0$ , ta thu được một vector riêng là $\begin{bmatrix}1/\sqrt{3}\\1/\sqrt{3}\\1/\sqrt{3}\end{bmatrix}$ . tìm một vector riêng là $\begin{bmatrix}1\\1\\1\end{bmatrix}$ . Đặt $\mathbf{u}_1=\begin{bmatrix}1\\1\\1\end{bmatrix}.$

Ở định lý 7 và các ứng dụng sau đó, giá trị của $\mathbf{x}^T A\mathbf{x}$ được tính với các ràng buộc bổ sung lên vector đơn vị $\mathbf{x}$ .

ĐỊNH LÝ 7

Giả sử , , và  được cho như trong Định lý 6. Khi đó, giá trị lớn nhất của  với các ràng buộc:

là giá trị riêng lớn thứ hai, , và giá trị này đạt được khi  là một vector riêng  tương ứng với .

Định lý 7 có thể được chứng minh bằng một lập luận tương tự như trong Định lý 6, trong đó bài toán được quy về trường hợp ma trận của dạng toàn phương là ma trận đường chéo. Ví dụ tiếp theo sẽ minh họa cho ý tưởng chứng minh trong trường hợp ma trận là ma trận đường chéo.

Ví dụ 4: Tìm giá trị lớn nhất của biểu thức $9x_1^2+4x_2^2+3x_3^2$ với các ràng buộc $\mathbf{x}^T\mathbf{x}=1$ và $\mathbf{x}^T\mathbf{u}_1=0$ , trong đó $\mathbf{u}_1=(1,0,0)$ . Lưu ý rằng $\mathbf{u}_1$ là một vector riêng đơn vị tương ứng với giá trị riêng lớn nhất $\lambda=9$ của ma trận của dạng toàn phương.

Giải: Nếu các tọa độ của $\mathbf{x}$ là $x_1,x_2,x_3$ , thì ràng buộc $\mathbf{x}^T\mathbf{u}_1=0$ đơn giản có nghĩa là $x_1=0$ . Với một vector đơn vị như vậy, ta có $x_2^2+x_3^2=1$ , và biểu thức cần tối đa hóa trở thành:

$\begin{matrix}9x_1^2+4x_2^2+3x_3^2=&4x_2^2+3x_3^2\\\leq&4x_2^2+4x_3^2\\=&4(x_2^2+x_3^2)\\=&4\\\end{matrix}$

Vậy giá trị lớn nhất theo ràng buộc là 4. Giá trị này đạt được khi $\mathbf{x}=(0,1,0)$ , tức là một vector riêng tương ứng với giá trị riêng lớn thứ hai của ma trận trong dạng toàn phương.

Ví dụ 5: Cho ma trận $A$ như trong ví dụ 3 và $\mathbf{u}_1$ là một vector riêng đơn vị tương ứng với giá trị riêng lớn nhất của $A$ . Hãy tìm giá trị lớn nhất của $\mathbf{x}^T A\mathbf{x}$ với các điều kiện:

(4) $\begin{equation*}\mathbf{x}^T\mathbf{x}=1,\quad\mathbf{x}^T\mathbf{u}_1=0\end{equation*}$

Giải: Từ ví dụ 3, ta biết giá trị riêng lớn thứ hai của $A$ là $\lambda=3$ . Giải phương trình $(A-3I)\mathbf{x}=0$ để tìm một vector riêng, rồi chuẩn hóa nó ta được:

$\mathbf{u}_2=\begin{bmatrix}1/\sqrt{6}\\1/\sqrt{6}\\-2/\sqrt{6}\end{bmatrix}.$

Vector $\mathbf{u}_2$ tự động vuông góc với $\mathbf{u}_1$ vì chúng tương ứng với các giá trị riêng khác nhau. Vậy nên, giá trị lớn nhất của $\mathbf{x}^T A\mathbf{x}$ dưới các ràng buộc đã cho là: $\boxed{3}$ , đạt được khi $\mathbf{x}=\mathbf{u}_2$ .

Định lý tiếp theo là một sự khái quát của định lý 7 và, cùng với định lý 6, cung cấp một cách mô tả hữu ích cho tất cả các giá trị riêng của ma trận $A$ . Phần chứng minh được lược bỏ.

Định lý 8
Giả sử  là một ma trận đối xứng kích thước , có phân tích trực giao , trong đó các phần tử trên đường chéo của ma trận  được sắp xếp theo thứ tự  và các cột của  là các vector riêng đơn vị tương ứng . Khi đó, với mỗi , giá trị lớn nhất của biểu thức  dưới các ràng buộc:


là giá trị riêng thứ , tức là , và giá trị này đạt được khi .

Ví dụ 6: Trong năm tới, chính quyền một quận đang lên kế hoạch sửa chữa $x$ (hàng trăm dặm) đường sá và cầu công cộng, đồng thời cải tạo $y$ (hàng trăm mẫu Anh) công viên và khu vui chơi giải trí. Quận cần quyết định cách phân bổ các nguồn lực (quỹ, thiết bị, nhân công, v.v.) giữa hai dự án này. Nếu việc thực hiện đồng thời cả hai dự án mang lại hiệu quả chi phí cao hơn so với chỉ thực hiện một dự án, thì các giá trị $x$ và $y$ có thể thỏa mãn một ràng buộc như:

$4x^2+9y^2\leq 36$

Xem Hình 3.

**HÌNH 3: Lịch trình công trình công cộng**

Mỗi điểm $(x,y)$ trong vùng bóng mờ khả thi biểu thị một lịch trình công việc công cộng khả thi trong năm. Các điểm nằm trên đường cong ràng buộc $4x^2+9y^2=36$ thể hiện việc sử dụng tối đa nguồn lực sẵn có.

Khi lựa chọn lịch trình công trình công cộng, chính quyền quận muốn xem xét ý kiến của cư dân trong quận. Để đo lường giá trị, hay độ hữu dụng, mà cư dân sẽ gán cho các phương án công việc khác nhau $(x,y)$ , các nhà kinh tế học đôi khi sử dụng một hàm như:

$q(x,y)=xy$

Tập hợp các điểm $(x,y)$ tại đó $q(x,y)$ là một hằng số được gọi là đường bàng quan. Ba đường như vậy được thể hiện trong hình 4. Các điểm nằm trên cùng một đường bàng quan tương ứng với những phương án mà cư dân trong quận, xét trên tổng thể, sẽ thấy có giá trị như nhau. Tìm lịch trình công trình công cộng (tức là giá trị $x,y$ ) sao cho hàm độ hữu dụng $q$ đạt giá trị lớn nhất.

Hình 4: Lịch trình công trình công cộng tối ưu là $(2.1,1.4)$ .

Hình 4: Lịch trình công trình công cộng tối ưu là $(2.1,1.4)$ .

Giải: Phương trình ràng buộc $4x^2+9y^2=36$ không mô tả một tập hợp các vectơ đơn vị, nhưng có thể khắc phục điều này bằng một phép đổi biến. Viết lại phương trình ràng buộc dưới dạng:

$\frac{x^2}{3^2}+\frac{y^2}{2^2}=1$

và định nghĩa

$x_1=\frac{x}{3},\$ và $x_2=\frac{y}{2}$ nghĩa là $x=3x_1$ và $y=2x_2$ .

Khi đó phương trình ràng buộc trở thành:

$x_1^2+x_2^2=1$

và hàm tiện ích trở thành $q(3x_1,2x_2)=(3x_1)(2x_2)=6x_1x_2$ . Gọi $\mathbf{x}=\begin{bmatrix}x_1\\x_2\end{bmatrix}$ , khi đó bài toán trở thành tìm giá trị cực đại của $Q(\mathbf{x})=6x_1x_2$ với điều kiện $\mathbf{x}^T\mathbf{x}=1$ . Lưu ý rằng $Q(\mathbf{x})=\mathbf{x}^T A\mathbf{x}$ , với

$A=\begin{bmatrix}0&3\\3&0\end{bmatrix}$

Các giá trị riêng của $A$ là $\pm3$ , với các vectơ riêng tương ứng là $\begin{bmatrix}1/\sqrt{2}\\1/\sqrt{2}\end{bmatrix}$ cho $\lambda=3$ , và $\begin{bmatrix}-1/\sqrt{2}\\1/\sqrt{2}\end{bmatrix}$ cho $\lambda=-3$ .

Vì vậy, giá trị lớn nhất của $Q(\mathbf{x})=q(x_1,x_2)$ là 3, đạt được khi $x_{1}=1/\sqrt{2}$ và $x_{2}=1/\sqrt{2}$ .

Xét theo các biến ban đầu, lịch trình công trình công cộng tối ưu là:

$x=3x_1=3/\sqrt{2}\approx 2.1$ (tức khoảng 2,1 trăm dặm đường và cầu),
$y=2x_2=\sqrt{2}\approx 1.4$ (tức khoảng 1,4 trăm mẫu công viên và khu vui chơi giải trí).

Lịch trình công trình công cộng tối ưu chính là điểm mà đường ràng buộc và đường bàng quan $q(x,y)=3$ chỉ vừa tiếp xúc nhau. Những điểm $(x,y)$ có mức tiện ích cao hơn nằm trên các đường bàng quan không cắt hoặc không chạm vào đường ràng buộc. Xem hình 4 để hình dung trực quan.

Để lại một bình luận Hủy

Chịu trách nhiệm nội dung

Bản quyền

Ý kiến bạn đọc

Bài giảng 29: Tối ưu hóa có ràng buộc

Lesson Attachments

Để lại một bình luận Hủy