Sức mạnh của quy hoạch tuyến tính không nằm ở chỗ nhiều bài toán được phát biểu sẵn dưới dạng LP, mà ở chỗ rất nhiều bài toán không trông giống LP chút nào lại có thể quy về LP một cách hoàn toàn tự nhiên. Tìm hình tròn lớn nhất nằm trong một đa giác là một bài toán hình học về khoảng cách. Cực tiểu một hàm có góc nhọn là một bài toán không khả vi. Tìm xác suất lớn nhất của một biến cố khi chỉ biết vài thông tin về phân phối là một bài toán xác suất. Cả ba dạng bài này đều chuyển hóa thành LP.

Bài giảng này khảo sát ba mô hình tiêu biểu ấy. Điều quan trọng cần nắm vững không phải là việc ghi nhớ máy móc từng công thức, mà là hai thao tác tư duy cốt lõi lặp lại trong cả ba: Thay một điều kiện "với mọi" bằng giá trị lớn nhất của nó, và tách một giá trị lớn nhất thành nhiều bất đẳng thức tuyến tính.

1. Tâm Chebyshev của một đa diện

Cho đa diện $\mathcal{P}=\{x\in {\mathbb{R}}^n:a_i^{T}x\le b_i,i=1,\dots ,m\}$. Ta muốn tìm hình cầu Euclid lớn nhất nằm trong $\mathcal{P}$. Tâm của hình cầu ấy được gọi là tâm Chebyshev của đa diện: Điểm nằm sâu nhất bên trong, xa biên nhất. Biểu diễn hình cầu bằng tâm $x_c$ và bán kính $r$:

$$\mathcal{B}=\{x_c+u:\parallel u{\parallel }_2\le r\}.$$

Biến của bài toán là $x_c$ và $r$, và ta muốn cực đại $r$ với điều kiện $\mathcal{B}\subseteq \mathcal{P}$.

Điều kiện "hình cầu nằm trong một nửa không gian" là một điều kiện "với mọi": Với mọi $u$ có $\parallel u{\parallel }_2\le r$, ta cần $a_i^T(x_c+u)\le b_i$. Điều kiện này đúng khi và chỉ khi nó đúng với $u$ làm vế trái lớn nhất. Theo bất đẳng thức Cauchy–Schwarz, $a_i^{T}u\le \parallel a_i{\parallel }_2\parallel u{\parallel }_2\le r\parallel a_i{\parallel }_2$, với dấu bằng khi $u$ cùng hướng với $a_i$, nên

$$sup\{a_i^{T}u:\parallel u{\parallel }_2\le r\}=r\parallel a_i{\parallel }_2.$$

Vậy hình cầu nằm trong nửa không gian thứ $i$ khi và chỉ khi $a_i^T{x}_c+r\parallel a_i{\parallel }_2\le b_i$, một bất đẳng thức tuyến tính theo $(x_c,r)$, vì $\parallel a_i{\parallel }_2$ chỉ là một con số tính từ dữ liệu. Tâm Chebyshev là nghiệm của LP

$$\begin{array}{rl}& \text{maximize}r\\ & \text{subject to}{a}_i^T{x}_c+r\parallel a_i{\parallel }_2\le b_i,i=1,\dots ,m.\end{array}$$

Một vô hạn điều kiện, ứng với mọi điểm của hình cầu, đã được thay bằng đúng một bất đẳng thức cho mỗi cạnh. Đây là thao tác thứ nhất của trang này.

Xét ví dụ minh họa: Ngũ giác cho bởi $x_1\ge 0$, $x_2\ge 0$, $x_1+2x_2\le 8$, $3x_1+x_2\le 12$ và $-x_1+x_2\le 3$, có năm đỉnh $(0,0)$, $(4,0)$, $(3.2,2.4)$, $(\frac{2}{3},\frac{11}{3})$ và $(0,3)$. Giải LP, ta được tâm $x_c=(r,r)$ với

$$r=6-2\sqrt{5}\approx 1.528.$$

Hình tròn tiếp xúc với ba cạnh $x_1=0$, $x_2=0$ và $x_1+2x_2=8$. Thật vậy, khoảng cách từ $(r,r)$ tới đường $x_1+2x_2=8$ là $\frac{8-3r}{\sqrt{5}}$, và đặt nó bằng $r$ cho đúng $r=\frac{8}{3+\sqrt{5}}=6-2\sqrt{5}$. Hai ràng buộc còn lại không chặt, nên có thể dịch chúng một chút mà nghiệm không đổi. Trong mặt phẳng, LP có ba biến, nên ở một đỉnh của trong ${\mathbb{R}}^3$ thường có đúng ba ràng buộc chặt: Hình tròn lớn nhất thường chạm đúng ba cạnh.

Hình tròn lớn nhất nằm trong đa giác

Kéo các chấm tròn để dịch từng cạnh song song với chính nó. Hình tròn lớn nhất nằm trong đa giác là nghiệm của một LP ba biến: hai tọa độ của tâm và bán kính.

đa giác khả thihình tròn lớn nhấtràng buộc chặtràng buộc còn dư

Hiện trọng tâm của đa giác

Tâm Chebyshev x_c = (1.528, 1.528), bán kính r = 1.528.

Ràng buộc chặt: (1) −x₁ ≤ 0.00, (2) −x₂ ≤ 0.00, (3) x₁ + 2x₂ ≤ 8.00. Hình tròn tiếp xúc đúng các cạnh này, còn các cạnh khác có thể dịch mà không đổi nghiệm, chừng nào chúng chưa chạm hình tròn.

Gợi ý thao tác

1. Đếm số cạnh mà hình tròn chạm. Vì sao trong mặt phẳng, thường có đúng ba cạnh chạm?
2. Kéo một cạnh đang màu xám (còn dư) vào trong. Nghiệm có đổi không cho tới khi cạnh ấy chạm hình tròn?
3. Kéo hai cạnh (3) và (4) ra xa. Hình tròn lớn lên tới đâu, và từ lúc nào ràng buộc (5) bắt đầu chặt?
4. Bật trọng tâm. Tìm một hình dạng làm trọng tâm và tâm Chebyshev cách xa nhau.

Tâm Chebyshev có một ý nghĩa thực tế sâu sắc. Nếu đa diện mô tả những thông số thiết kế chấp nhận được, thì tâm Chebyshev là thiết kế chịu được sai lệch tốt nhất (robust design): Mọi sai lệch có độ lớn nhỏ hơn $r$ theo bất kỳ hướng nào đều vẫn giữ thiết kế trong vùng chấp nhận được. Điểm này khác trọng tâm diện tích của đa giác. Với ngũ giác trên, trọng tâm ở khoảng $(1.682,1.501)$, gần cạnh $x_2=0$ hơn tâm Chebyshev.

2. Cực tiểu hàm tuyến tính từng khúc

Một tuyến tính từng khúc luôn viết được thành giá trị lớn nhất của các hàm affine,

$$f(x)=\underset{i=1,\dots ,m}{max}(a_i^{T}x+b_i),$$

như chủ đề về phép toán giữ tính lồi của Lecture 01 đã chỉ ra. Cực tiểu $f$ là bài toán không khả vi, vì hàm có góc tại những nơi hai mảnh gặp nhau. Dạng biến nó thành một LP. Trước hết, bài toán tương đương với cực tiểu $t$ với điều kiện $\underset{i}{max}(a_i^{T}x+b_i)\le t$. Sau đó, tách giá trị lớn nhất thành $m$ điều kiện:

$$\begin{array}{rl}& \text{minimize}t\\ & \text{subject to}{a}_i^{T}x+b_i\le t,i=1,\dots ,m.\end{array}$$

Đây là thao tác thứ hai: "Giá trị lớn nhất không vượt quá $t$" đúng khi và chỉ khi "từng giá trị không vượt quá $t$".

Ví dụ một biến: Xét hàm $f(x)=max\{-x+3,0.5x,2x-5\}$. LP tương ứng là cực tiểu $t$ với $-x+3\le t$, $0.5x\le t$, $2x-5\le t$. Đường giảm $-x+3$ và đường tăng chậm $0.5x$ cắt nhau tại $x=2$ với giá trị 1, còn đường $2x-5$ chỉ vượt lên trên $0.5x$ khi $x>\frac{10}{3}$. Nghiệm là $x^{\star }=2$, $t^{\star }=1$. Tại nghiệm, hai ràng buộc đầu chặt và ràng buộc thứ ba còn dư. Các bài toán khớp dữ liệu theo chuẩn ${\ell }_1$ hay ${\ell }_{\mathrm{\infty }}$ ở Lecture 01 là những trường hợp riêng của mô hình này.

3. Cận chặt cho kỳ vọng khi chỉ biết một phần phân phối

Đây là một bài toán rất thú vị trong xác suất thống kê. Giả sử biến ngẫu nhiên $x$ chỉ nhận các giá trị rời rạc $u_1,\dots ,u_n$ đã biết, nhưng phân phối xác suất $p_i=\mathrm{prob}(x=u_i)$ thì chưa biết cụ thể. Vector phân phối $p$ chỉ cần thỏa mãn $p⪰0$ và điều kiện chuẩn hóa $\sum _{i=1}^n{p}_i=p_1+p_2+\cdots +p_n=1$. Điểm mấu chốt là mọi kỳ vọng:

$$\mathbb{E}[f(x)]=\sum _{i=1}^n{p}_{i}f(u_i)=p_{1}f(u_1)+\cdots +p_{n}f(u_n)$$

và mọi xác suất $\mathrm{prob}(x\in S)=\sum _{u_i\in S}{p}_i$ đều là hàm tuyến tính của vector xác suất $p$. Vì vậy những hiểu biết có sẵn, chẳng hạn cận trên và cận dưới của một vài kỳ vọng, là những ràng buộc tuyến tính trên $p$. Cận nhỏ nhất và lớn nhất có thể của một kỳ vọng khác chính là nghiệm của hai bài toán LP theo biến $p$.

Ví dụ: Xét biến ngẫu nhiên $x$ nhận giá trị trong tập rời rạc $\{0,1,2,3,4\}$, và ta chỉ biết thông tin kỳ vọng $\mathbb{E}[x]=1$. Xác suất $\mathrm{prob}(x\ge 3)$ lớn nhất có thể là bao nhiêu? LP cực đại $p_3+p_4$ với các ràng buộc $\sum _{k=0}^4{p}_k=1$, $\sum _{k=0}^{4}k{p}_k=1$, $p⪰0$ cho giá trị tối ưu $\frac{1}{3}$, đạt tại phân phối dồn $\frac{2}{3}$ khối lượng vào 0 và $\frac{1}{3}$ vào 3. Con số $\frac{1}{3}$ chính là cận của bất đẳng thức Markov, $\mathrm{prob}(x\ge 3)\le \frac{\mathbb{E}[x]}{3}$, và LP cho thấy cận ấy là chặt nhất không thể cải thiện nếu chỉ dùng duy nhất thông tin này.

Bây giờ ta biết thêm thông tin bậc hai $\mathbb{E}[x^2]=2$, nghĩa là phương sai $\mathrm{Var}(x)=\mathbb{E}[x^2]-(\mathbb{E}[x]{)}^2=2-1=1$. Bổ sung thêm một ràng buộc tuyến tính $\sum _{k=0}^4{k}^2{p}_k=2$, bài toán LP cho xác suất lớn nhất là $\frac{1}{6}$, đạt tại phân phối $(\frac{1}{3},\frac{1}{2},0,\frac{1}{6},0)$. Bất đẳng thức Cantelli một phía cho cận $\frac{{\sigma }^2}{{\sigma }^2+2^2}=0.2$, nhưng cận ấy dành cho mọi phân phối bất kỳ trên trục số thực. Muốn đạt được 0.2 thì phân phối phải đặt khối lượng tại điểm 0.5, vốn không thuộc tập giá trị rời rạc cho phép. Khi biết thêm $x$ chỉ nhận giá trị nguyên từ 0 tới 4, LP trả về cận chặt hơn, và đó là cận tối ưu tuyệt đối với thông tin đã có, vì nó đạt được bởi một phân phối cụ thể.

4. Lập kế hoạch qua nhiều giai đoạn

Trong thực tế tối ưu hóa, mô hình quy hoạch tuyến tính còn xử lý rất tự nhiên yếu tố biến thiên theo thời gian (Dynamic LP). Xét bài toán lập kế hoạch kinh tế đa giai đoạn: Một nền kinh tế có $n$ ngành, mức độ hoạt động của ngành $j$ ở giai đoạn $t$ là $x_j(t)\ge 0$. Hoạt động sản xuất vừa tiêu thụ vừa tạo ra hàng hóa theo tỉ lệ với mức hoạt động, và lượng tiêu thụ ở giai đoạn sau không được vượt lượng sản xuất ở giai đoạn trước. Hàng hóa dư ra ở mỗi giai đoạn là một biến bù, và mục tiêu là cực đại tổng giá trị chiết khấu của hàng hóa dư. Mọi quan hệ giữa các biến đều tuyến tính, nên toàn bộ kế hoạch qua $N$ giai đoạn là một bài toán LP dạng chuẩn. Ý tưởng "biến cho từng thời điểm, ràng buộc liên kết các thời điểm liền nhau" sẽ trở lại ở Lecture 07, khi so sánh LP với quy hoạch động.

5. Những câu hỏi để đào sâu

Câu 1. Nếu thay hình cầu Euclid bằng hình vuông song song với các trục, tức hình cầu chuẩn ${\ell }_{\mathrm{\infty }}$, thì bài toán tìm hình vuông lớn nhất nằm trong đa diện còn là LP không?

Xem lời giải thích

Còn. Lập luận giữ nguyên, chỉ thay $sup\{a^{T}u:\parallel u{\parallel }_{\mathrm{\infty }}\le r\}$ bằng $r\parallel a{\parallel }_1$, vì giá trị lớn nhất đạt khi mỗi thành phần $u_j=r\mathrm{sign}(a_j)$. Ràng buộc trở thành $a_i^T{x}_c+r\parallel a_i{\parallel }_1\le b_i$, vẫn tuyến tính. Tổng quát, với một chuẩn bất kỳ, hệ số của $r$ là chuẩn đối ngẫu của $a_i$, nên bài toán luôn là LP, chỉ khác cách tính hệ số từ dữ liệu.

Câu 2. Với hình chữ nhật $[0,4]\times [0,2]$, tâm Chebyshev có duy nhất không? Bán kính thì sao?

Xem lời giải thích

Bán kính lớn nhất là $1$ và duy nhất, vì nó là giá trị tối ưu của LP. Tâm thì không duy nhất: Mọi điểm $(t,1)$ với $1\le t\le 3$ đều là tâm của một hình tròn bán kính 1 nằm trong hình chữ nhật. Tập nghiệm của LP là cả đoạn thẳng ấy, đúng như một LP có thể có cả một cạnh làm tập nghiệm. Nếu cần một tâm duy nhất, chẳng hạn trung điểm $(2,1)$, phải thêm một tiêu chí phụ, ví dụ cực tiểu khoảng cách tới trọng tâm trong số các tâm tối ưu.

Câu 3. Cực tiểu một tuyến tính từng khúc là LP. Còn cực đại nó trên một đa giác thì sao?

Xem lời giải thích

Không còn là LP, và nói chung khó hơn hẳn. Cực đại một trên một đa diện đạt tại một đỉnh, nhưng không có cách nào tránh việc so sánh nhiều đỉnh, vì hàm lồi không cho ta biết đỉnh nào xa hơn chỉ từ thông tin cục bộ. Về hình thức, điều kiện "$\underset{i}{max}(a_i^{T}x+b_i)\ge t$" là một phép "hoặc": Chỉ cần một trong các bất đẳng thức $a_i^{T}x+b_i\ge t$ đúng. Một phép "hoặc" mô tả hợp của các nửa không gian, không phải giao, nên tập khả thi không còn lồi. Sự bất đối xứng giữa cực tiểu và cực đại một hàm lồi là một trong những bài học quan trọng nhất của môn học.

Câu 4. Trong ví dụ phân phối, vì sao có thể nói cận $\frac{1}{6}$ là chặt, trong khi cận Cantelli $0.2$ thì không chặt cho bài toán này?

Xem lời giải thích

Cận $\frac{1}{6}$ đạt được bởi một phân phối cụ thể, $(\frac{1}{3},\frac{1}{2},0,\frac{1}{6},0)$, thỏa mọi thông tin đã biết. Vì vậy không thể chứng minh một cận nhỏ hơn $\frac{1}{6}$ chỉ từ thông tin ấy. Cận Cantelli đúng cho mọi phân phối có cùng trung bình và phương sai trên trục số, và nó đạt được bởi phân phối dồn $0.2$ vào điểm 3 và $0.8$ vào điểm 0.5. Phân phối ấy hợp lệ trên trục số nhưng vi phạm thông tin "$x$ chỉ nhận giá trị nguyên từ 0 tới 4". Mỗi bất đẳng thức xác suất cổ điển là đáp án của một LP như vậy với một tập thông tin nhất định. LP cho phép đưa thêm bất kỳ thông tin tuyến tính nào và luôn trả về cận tốt nhất ứng với thông tin đó.

Câu 5. Thêm cả hai ràng buộc $\mathbb{E}x=1$, $\mathbb{E}{x}^2=2$, xác suất $\mathrm{prob}(x\ge 3)$ nhỏ nhất có thể là bao nhiêu? Kết quả này nói gì?

Xem lời giải thích

LP cực tiểu cho giá trị 0, đạt tại phân phối dồn $\frac{1}{2}$ vào 0 và $\frac{1}{2}$ vào 2, có trung bình 1 và $\mathbb{E}{x}^2=2$. Vậy với thông tin này, xác suất của biến cố có thể nằm bất kỳ đâu trong $[0,\frac{1}{6}]$. Một khoảng rộng như thế là một câu trả lời trung thực: Thông tin đã có không đủ để kết luận chính xác, và mọi con số cụ thể trong khoảng ấy đều cần thêm giả định.

6. Bài tập tự luyện

Bài tập 1: Tâm Chebyshev của tam giác vuông

Tìm tâm Chebyshev và bán kính của tam giác có đỉnh $(0,0)$, $(6,0)$, $(0,8)$. Viết LP trước, rồi giải bằng lập luận hình học.

Gợi ý

Cạnh huyền nằm trên đường $8x_1+6x_2=48$, có pháp tuyến dài $\parallel (8,6){\parallel }_2=10$.

Lời giải

Tam giác là $\{x_1\ge 0,x_2\ge 0,8x_1+6x_2\le 48\}$. LP là cực đại $r$ với $-x_{c,1}+r\le 0$, $-x_{c,2}+r\le 0$ và $8x_{c,1}+6x_{c,2}+10r\le 48$. Hình tròn lớn nhất là đường tròn nội tiếp, tiếp xúc cả ba cạnh. Hai ràng buộc đầu chặt cho $x_c=(r,r)$, và ràng buộc thứ ba chặt cho $8r+6r+10r=48$, tức $r=2$. Tâm là $(2,2)$, khớp với công thức bán kính nội tiếp của tam giác vuông, $\frac{a+b-c}{2}=\frac{6+8-10}{2}=2$.

Bài tập 2: Hàm tuyến tính từng khúc hai biến

Hàm $f$ trên ${\mathbb{R}}^2$ là giá trị lớn nhất của ba hàm $x_1+x_2-2$, $-x_1$ và $-x_2$. Viết LP để cực tiểu $f$ và tìm nghiệm.

Lời giải

LP là cực tiểu $t$ với $x_1+x_2-2\le t$, $-x_1\le t$, $-x_2\le t$. Cộng cả ba ràng buộc, mỗi ràng buộc với hệ số 1, ta được $-2\le 3t$, tức $t\ge -\frac{2}{3}$ với mọi . Cận này đạt khi cả ba ràng buộc chặt: $x_1=x_2=\frac{2}{3}$, và khi đó $x_1+x_2-2=-\frac{2}{3}$. Vậy nghiệm là $x^{\star }=(\frac{2}{3},\frac{2}{3})$ với $f^{\star }=-\frac{2}{3}$. Bộ hệ số $(1,1,1)$ là một chứng nhận tối ưu, cùng loại với chứng nhận của LP ở Lecture 01.

Bài tập 3: Khi thông tin xác định hoàn toàn phân phối

Biến $x$ nhận giá trị trong $\{0,1,2\}$. (a) Chỉ biết $\mathbb{E}x=0.5$, tìm $\mathrm{prob}(x=2)$ lớn nhất có thể. (b) Biết thêm $\mathbb{E}{x}^2=0.7$, xác suất ấy có thể nằm trong khoảng nào?

Lời giải

(a) Cực đại $p_2$ với $p_0+p_1+p_2=1$, $p_1+2p_2=0.5$, $p⪰0$. Để $p_2$ lớn nhất, đặt $p_1=0$, được $p_2=0.25$ và $p_0=0.75$, đúng cận Markov $\frac{\mathbb{E}x}{2}$. (b) Hai phương trình $p_1+2p_2=0.5$ và $p_1+4p_2=0.7$ cho $p_2=0.1$, $p_1=0.3$, rồi $p_0=0.6$. Ba ràng buộc đẳng thức trên ba biến xác định hoàn toàn phân phối, nên cận dưới và cận trên trùng nhau: Xác suất đúng bằng 0.1.

Tóm tắt

Nhiều bài toán không trông giống LP lại là LP nhờ hai thao tác. Thao tác thứ nhất thay một điều kiện "với mọi điểm trong một tập" bằng giá trị lớn nhất trên tập đó, như khi điều kiện hình cầu nằm trong nửa không gian trở thành $a_i^T{x}_c+r\parallel a_i{\parallel }_2\le b_i$. Thao tác thứ hai tách "giá trị lớn nhất không vượt quá $t$" thành nhiều bất đẳng thức, như trong dạng của hàm tuyến tính từng khúc.

Tâm Chebyshev là điểm sâu nhất của đa diện và là nghiệm của một LP. Cực tiểu một tuyến tính từng khúc là LP, nhưng cực đại nó thì không. Khi phân phối của một biến ngẫu nhiên hữu hạn chưa biết, mọi kỳ vọng đều tuyến tính theo phân phối, nên cận chặt nhất cho một kỳ vọng từ những thông tin tuyến tính đã có là nghiệm của một LP, và bất đẳng thức Markov là một trường hợp riêng.

Tài liệu tham khảo

• Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press.