Một ràng buộc tuyến tính $a^{T}x\le b$ giả định rằng ta biết chính xác vector $a$. Trong thực tế, $a$ thường là một ước lượng: Hàm lượng dinh dưỡng của thực phẩm, năng suất của một máy, hệ số của một mô hình học từ dữ liệu. Nếu muốn ràng buộc đúng với mọi giá trị có thể của $a$ trong một vùng bất định hình ellipsoid, ràng buộc tuyến tính ấy biến thành một ràng buộc có chứa . Họ bài toán chứa những ràng buộc như thế được gọi là quy hoạch nón bậc hai (second-order cone program, SOCP).

Bài giảng này định nghĩa chuẩn mực về SOCP, phân tích vị trí bao hàm giữa nó với LP và QCQP, rồi đi sâu vào hai nguồn gốc nảy sinh tự nhiên trong thực tế: Quy hoạch tuyến tính bền vững (Robust LP) và ràng buộc theo xác suất (Chance constraints).

1. Ràng buộc nón bậc hai

Một ràng buộc có dạng

$$\parallel Ax+b{\parallel }_2\le c^{T}x+d,$$

với $A\in {\mathbb{R}}^{k\times n}$, được gọi là ràng buộc nón bậc hai. Tên gọi đến từ việc nó đòi hỏi vector $(Ax+b,c^{T}x+d)\in {\mathbb{R}}^{k+1}$ nằm trong nón bậc hai

$$\mathcal{K}=\{(y,t)\in {\mathbb{R}}^{k+1}:\parallel y{\parallel }_2\le t\},$$

chính là nón chuẩn của . Vì $\mathcal{K}$ là và ánh xạ $x\mapsto (Ax+b,c^{T}x+d)$ là affine, tập các $x$ thỏa ràng buộc là ảnh ngược của một tập lồi qua ánh xạ affine, nên lồi. Một bài toán SOCP cực tiểu một hàm tuyến tính với các ràng buộc như vậy:

$$\begin{array}{rl}& \text{minimize}{f}^{T}x\\ & \text{subject to}\parallel A_{i}x+b_i{\parallel }_2\le c_i^{T}x+d_i,i=1,\dots ,m,\\ & \phantom{\text{subject to}}Fx=g.\end{array}$$

Hai trường hợp riêng cho thấy SOCP chứa những dạng bài toán đã biết. Khi mọi $A_i=0$, vế trái là một hằng số không âm $\parallel b_i{\parallel }_2$, và ràng buộc trở thành một bất đẳng thức tuyến tính: SOCP thành LP. Khi mọi $c_i=0$, vế phải là hằng số $d_i$, và bình phương hai vế cho một ràng buộc toàn phương lồi: SOCP thành QCQP. SOCP còn tổng quát hơn cả hai.

Đừng bình phương một cách vô tư. Bình phương hai vế của $\parallel Ax+b{\parallel }_2\le c^{T}x+d$ cho $\parallel Ax+b{\parallel }_2^2\le (c^{T}x+d{)}^2$, nhưng hai ràng buộc không tương đương. Ràng buộc gốc buộc ngầm $c^{T}x+d\ge 0$, còn ràng buộc bình phương thì không. Ví dụ một biến: Bất phương trình $|x|\le -1$ vô nghiệm, nhưng $x^2\le 1$ lại có cả đoạn nghiệm $[-1,1]$. Hơn nữa, $(c^{T}x+d{)}^2$ là , nên ràng buộc bình phương có dạng "lồi ≤ lồi", không phải dạng chuẩn lồi. Cách viết nón bậc hai giữ được cả tính lồi lẫn điều kiện dấu.

2. LP bền vững

Xét một LP dạng bất đẳng thức, cực tiểu $c^{T}x$ với $a_i^{T}x\le b_i$, nhưng mỗi vector $a_i$ chỉ được biết là nằm trong một ellipsoid

$${\mathcal{E}}_i=\{{\overline{a}}_i+P_{i}u:\parallel u{\parallel }_2\le 1\},$$

với tâm ${\overline{a}}_i$ là giá trị danh nghĩa và $P_i$ mô tả độ bất định. Ta đòi hỏi mỗi ràng buộc đúng với mọi $a_i\in {\mathcal{E}}_i$. Đây là một điều kiện "với mọi", và cũng như với tâm Chebyshev, ta thay nó bằng giá trị lớn nhất:

$$sup\{a_i^{T}x:A_i\in {\mathcal{E}}_i\}={\overline{a}}_i^{T}x+sup\{u^T{P}_i^{T}x:\parallel u{\parallel }_2\le 1\}={\overline{a}}_i^{T}x+\parallel P_i^{T}x{\parallel }_2,$$

trong đó đẳng thức cuối là bất đẳng thức Cauchy–Schwarz, đạt khi $u$ cùng hướng với $P_i^{T}x$. Vậy LP bền vững là SOCP

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

Số hạng $\parallel P_i^{T}x{\parallel }_2$ có một cách hiểu đáng nhớ: Nó đóng vai một số hạng điều chuẩn, ngăn $x$ lớn theo những hướng mà hệ số còn nhiều bất định. Một nghiệm bền vững là một nghiệm thận trọng: Nó chấp nhận giá trị mục tiêu kém hơn một chút để đổi lấy sự an toàn trước sai số của dữ liệu.

Ví dụ tự đặt: Cực đại $x_1+2x_2$ với năm ràng buộc $x_1\le 3$, $x_2\le 2$, $x_1+x_2\le 4$, $-x_1\le 1$, $-x_2\le 1$. Nghiệm danh nghĩa là $(2,2)$ với giá trị 6. Bây giờ giả sử mỗi vector hệ số chỉ biết nằm trong hình tròn bán kính $\rho$ quanh giá trị danh nghĩa, tức $P_i=\rho I$, và ràng buộc bền vững là ${\overline{a}}_i^{T}x+\rho \parallel x{\parallel }_2\le b_i$. Với $\rho =0.2$, nghiệm bền vững là $(2,1.5)$ với giá trị 5. Kiểm tra trực tiếp: $\parallel (2,1.5){\parallel }_2=2.5$, nên hai ràng buộc $x_2\le 2$ và $x_1+x_2\le 4$ trở thành $1.5+0.5=2$ và $3.5+0.5=4$, cùng chặt. Còn nghiệm danh nghĩa $(2,2)$ có $\rho \parallel x{\parallel }_2\approx 0.566$, nên trong trường hợp xấu nhất nó vượt cả hai ràng buộc ấy khoảng 0.566.

Cái giá của việc an toàn với mọi hệ số

Miền nhạt là miền khả thi khi các hệ số aᵢ được biết chính xác. Khi mỗi aᵢ chỉ biết nằm trong một hình tròn bán kính ρ, các điểm phải thỏa ràng buộc với mọi hệ số có thể, và miền khả thi co lại thành miền tô đậm có biên cong.

miền bền vững, hướng cnghiệm bền vữngmiền danh nghĩa (nhạt)

Bán kính bất định ρ = 0.20

Nghiệm danh nghĩa (ρ = 0): (2, 2), giá trị x₁ + 2x₂ = 6.

Nghiệm bền vững: x = (2.000, 1.500), giá trị 5.000, thấp hơn 1.000 so với danh nghĩa. Ràng buộc chặt: x₂ ≤ 2, x₁ + x₂ ≤ 4.

Nếu vẫn dùng nghiệm danh nghĩa (2, 2), trong trường hợp xấu nhất có ràng buộc bị vượt 0.566, vì số hạng ρ‖x‖₂ = 0.566.

Gợi ý thao tác

1. Tăng ρ từ 0. Miền bền vững co lại về phía nào nhiều nhất, và vì sao các điểm gần gốc tọa độ ít bị ảnh hưởng?
2. Đặt ρ = 0.2 và kiểm tra nghiệm (2, 1.5) bằng tay: hai ràng buộc chặt cho phương trình nào?
3. Biên của miền bền vững cong. Vì sao một ràng buộc vốn tuyến tính lại cho biên cong?
4. Giá trị tối ưu giảm khi ρ tăng. Đó là cái giá của sự an toàn. Với ρ = 0.5, cái giá ấy là bao nhiêu phần trăm?

3. Ràng buộc xác suất

Có thể nhìn LP bền vững từ góc độ thống kê. Giả sử $a_i$ là vector ngẫu nhiên Gauss với trung bình ${\overline{a}}_i$ và hiệp phương sai ${\mathrm{\Sigma }}_i$, và ta chỉ đòi hỏi ràng buộc đúng với xác suất ít nhất $\eta$:

$$\mathrm{prob}(a_i^{T}x\le b_i)\ge \eta .$$

Với $x$ cố định, $u=a_i^{T}x$ là biến Gauss với trung bình $\overline{u}={\overline{a}}_i^{T}x$ và độ lệch chuẩn $\sigma =\parallel {\mathrm{\Sigma }}_i^{1/2}x{\parallel }_2$. Gọi $\mathrm{\Phi }$ là hàm phân phối của Gauss chuẩn, ràng buộc trở thành $\mathrm{\Phi }((b_i-\overline{u})/\sigma )\ge \eta$, tức

$${\overline{a}}_i^{T}x+{\mathrm{\Phi }}^{-1}(\eta )\parallel {\mathrm{\Sigma }}_i^{1/2}x{\parallel }_2\le b_i.$$

Khi $\eta \ge \frac{1}{2}$, hệ số ${\mathrm{\Phi }}^{-1}(\eta )\ge 0$, và đây là một ràng buộc nón bậc hai. Khi $\eta <\frac{1}{2}$, hệ số âm, vế trái là một hàm affine trừ đi một chuẩn, hàm lõm, và ràng buộc không còn lồi. Đòi hỏi độ tin cậy cao lại cho bài toán dễ, còn đòi hỏi độ tin cậy thấp lại cho bài toán khó, một điều thoạt nghe rất ngược đời.

Ví dụ một biến: Hàm lượng một chất trong mỗi đơn vị nguyên liệu là biến Gauss với trung bình 2 và độ lệch chuẩn 0.3, và tổng hàm lượng trong $x$ đơn vị không được vượt quá 10 với xác suất ít nhất 95%. Với ${\mathrm{\Phi }}^{-1}(0.95)\approx 1.645$, ràng buộc là $2x+1.645\times 0.3x\le 10$, tức $x\le 4.01$. Nếu bỏ qua bất định và dùng giá trị trung bình, ta cho phép $x$ tới 5, nhưng khi đó xác suất vi phạm là đúng 50%. Một mô phỏng Monte Carlo với hai triệu mẫu xác nhận xác suất thỏa ràng buộc tại $x=4.01$ là khoảng 0.95.

4. Ràng buộc hyperbolic và những biểu thức khác

Nhiều ràng buộc không trông giống nón bậc hai vẫn viết lại được thành nón bậc hai. Một đồng nhất thức hữu ích thường dùng để biến đổi: Với $y,z\ge 0$,

$$x^{T}x\le yz⟺{\Vert \left[\begin{array}{c}2x\\ y-z\end{array}\right]\Vert }_2\le y+z.$$

Chứng minh chỉ là khai triển. Bình phương vế phải trừ bình phương vế trái là $(y+z{)}^2-(y-z{)}^2-4x^{T}x$, rút gọn thành $4(yz-x^{T}x)$, và cả hai vế đều không âm khi $y,z\ge 0$. Nhờ đó, ràng buộc $\frac{\parallel x{\parallel }_2^2}{y}\le t$ với $y>0$, chẳng hạn khi một hàm mục tiêu chứa tỉ số giữa bình phương sai số và một phương sai cần ước lượng, là một ràng buộc nón bậc hai.

Một số bài toán quen thuộc khác cũng là SOCP. Cực tiểu $\parallel Ax-b{\parallel }_2$ là cực tiểu $t$ với $\parallel Ax-b{\parallel }_2\le t$. Cực tiểu tổng các chuẩn $\sum _i\parallel A_{i}x+b_i{\parallel }_2$ là cực tiểu $\sum _i{t}_i$ với $\parallel A_{i}x+b_i{\parallel }_2\le t_i$. Một ứng dụng hình học kinh điển khác là bài toán mặt cực tiểu (minimal surface problem): Tìm mặt cong có diện tích nhỏ nhất căng trên một khung biên không gian cho trước. Sau khi rời rạc hóa, diện tích là tổng các của những vector gradient xấp xỉ, nên bài toán cũng là SOCP.

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

Câu 1. Nếu thay vùng bất định hình ellipsoid bằng một hình hộp, tức mỗi thành phần $a_{ij}$ nằm trong $[{\overline{a}}_{ij}-\delta ,{\overline{a}}_{ij}+\delta ]$, thì LP bền vững trở thành bài toán gì?

Xem lời giải thích

Giá trị lớn nhất của $a^{T}x$ trên hình hộp là ${\overline{a}}^{T}x+\delta \parallel x{\parallel }_1$, đạt khi mỗi $a_j$ lệch về phía cùng dấu với $x_j$. Chẳng hạn với $\overline{a}=(1,2)$, $\delta =0.1$ và $x=(3,-1)$, giá trị lớn nhất là $1+0.1\times 4=1.4$. Ràng buộc bền vững ${\overline{a}}^{T}x+\delta \parallel x{\parallel }_1\le b$ chứa chuẩn ${\ell }_1$, và viết được thành các bất đẳng thức tuyến tính bằng biến phụ $|x_j|\le s_j$. Vậy LP bền vững với hộp bất định vẫn là một LP. Hình dạng của vùng bất định quyết định dạng bài toán: Hộp cho LP, ellipsoid cho SOCP. Đây là một ví dụ của nguyên tắc chung: Giá trị lớn nhất của $a^{T}x$ trên một hình cầu chuẩn là chuẩn đối ngẫu của $x$.

Câu 2. Trong ví dụ ràng buộc xác suất, nếu chỉ đòi hỏi xác suất thỏa ràng buộc là 10% thì sao? Vì sao bài toán lại trở nên không lồi?

Xem lời giải thích

Với $\eta =0.1$, ${\mathrm{\Phi }}^{-1}(0.1)\approx -1.28<0$, và ràng buộc là ${\overline{a}}^{T}x-1.28\parallel {\mathrm{\Sigma }}^{1/2}x{\parallel }_2\le b$. Vế trái là affine trừ một chuẩn, nên lõm, và tập các $x$ thỏa ràng buộc nói chung không lồi. Trực giác như sau. Với độ tin cậy thấp, ta được phép "đánh cược" rằng sai số sẽ có lợi cho mình, và có nhiều cách đặt cược rời rạc nhau: Đi theo một hướng mà sai số có thể kéo $a^{T}x$ xuống, hoặc theo một hướng khác. Hợp của những lựa chọn ấy không lồi. Với độ tin cậy cao, ta phải phòng thủ theo mọi hướng, và yêu cầu phòng thủ là một giao, một . Trong một chiều, như ví dụ nguyên liệu với $x\ge 0$, ràng buộc vẫn chỉ là một đoạn, nên điều này chỉ lộ ra từ hai chiều trở lên.

Câu 3. LP bền vững cho nghiệm $(2,1.5)$ với giá trị 5, thấp hơn nghiệm danh nghĩa 6. Có phải lúc nào cũng nên dùng nghiệm bền vững không?

Xem lời giải thích

Không hẳn. Nghiệm bền vững tối ưu cho trường hợp xấu nhất trong vùng bất định, và cái giá là giá trị kém đi 1 đơn vị, tức khoảng 17%, ngay cả khi hệ số thật đúng bằng giá trị danh nghĩa. Nếu vùng bất định được chọn quá rộng, nghiệm sẽ quá thận trọng. Nếu vi phạm ràng buộc chỉ gây thiệt hại nhỏ, ràng buộc xác suất với $\eta$ vừa phải có thể hợp lý hơn. Lựa chọn giữa danh nghĩa, bền vững và xác suất là một quyết định mô hình hóa, phụ thuộc vào hậu quả của việc vi phạm, không phải một câu hỏi toán học có đáp án duy nhất.

Câu 4. Trong mô phỏng, mỗi ràng buộc ban đầu là một đường thẳng, nhưng biên của bền vững lại cong. Độ cong ấy đến từ đâu?

Xem lời giải thích

Biên của ràng buộc bền vững thứ $i$ là tập $\{x:{\overline{a}}_i^{T}x+\rho \parallel x{\parallel }_2=b_i\}$. Chuyển vế và bình phương cho thấy đó là một đường conic, một nhánh của hyperbol, parabol hay ellipse tùy theo $\rho$ so với $\parallel {\overline{a}}_i{\parallel }_2$. Về hình học, miền bền vững là giao của vô số nửa mặt phẳng $\{a^{T}x\le b_i\}$, mỗi nửa ứng với một vector $a$ trong hình tròn bất định. Giao của vô số nửa mặt phẳng với pháp tuyến biến thiên liên tục cho một biên cong, giống như hình tròn là giao của vô số nửa mặt phẳng tiếp xúc với nó.

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

Bài tập 1: Viết thành SOCP

Viết bài toán cực tiểu $\parallel Ax-b{\parallel }_2+\lambda \parallel x{\parallel }_2$, với $\lambda >0$, thành một SOCP.

Lời giải

Thêm hai biến $t_1,t_2$ và viết: Cực tiểu $t_1+\lambda t_2$ với $\parallel Ax-b{\parallel }_2\le t_1$ và $\parallel x{\parallel }_2\le t_2$. Hai ràng buộc là ràng buộc nón bậc hai theo $(x,t_1,t_2)$, hàm mục tiêu tuyến tính. Bài toán tương đương bài toán gốc vì tại nghiệm, cả hai ràng buộc đều chặt: Nếu $t_1>\parallel Ax-b{\parallel }_2$, giảm $t_1$ sẽ giảm hàm mục tiêu.

Bài tập 2: Ràng buộc xác suất

Một xe tải chở $x$ thùng hàng, mỗi thùng nặng trung bình 50 kg với độ lệch chuẩn 4 kg, các thùng độc lập và phân phối Gauss. Tải trọng tối đa là 2000 kg. Tìm $x$ lớn nhất để xác suất quá tải không quá 5%, bỏ qua yêu cầu $x$ nguyên.

Gợi ý

Tổng khối lượng có trung bình $50x$ và độ lệch chuẩn $4\sqrt{x}$, không phải $4x$, vì các thùng độc lập.

Lời giải

Ràng buộc là $50x+1.645\times 4\sqrt{x}\le 2000$. Đặt $s=\sqrt{x}$, ta có $50s^2+6.58s-2000\le 0$, cho $s\le \frac{-6.58+\sqrt{{6.58}^2+400000}}{100}\approx 6.259$, tức $x$ không vượt quá khoảng $39.18$. Nếu bỏ qua bất định, ta cho phép 40 thùng, và khi đó xác suất quá tải là 50%. Lưu ý độ lệch chuẩn của tổng tăng theo $\sqrt{x}$ vì các thùng độc lập, khác với ví dụ nguyên liệu ở mục 3, nơi cả $x$ đơn vị dùng chung một hệ số ngẫu nhiên.

Bài tập 3: Kiểm tra đồng nhất thức

Với $x=(1,2)$, $y=2$, $z=3$, kiểm tra cả hai vế của đồng nhất thức hyperbolic ở mục 4.

Lời giải

Vế trái: $x^{T}x=5\le yz=6$, đúng. Vế phải: Vector $(2x,y-z)=(2,4,-1)$ có chuẩn $\sqrt{21}\approx 4.583$, không vượt quá $y+z=5$, cũng đúng. Hai vế cùng đúng, và hiệu bình phương $25-21=4=4(yz-x^{T}x)$, khớp với chứng minh.

Tóm tắt

Ràng buộc nón bậc hai $\parallel Ax+b{\parallel }_2\le c^{T}x+d$ lồi vì nó là ảnh ngược của nón qua một ánh xạ affine. SOCP cực tiểu hàm tuyến tính với các ràng buộc như vậy, và chứa LP cùng QCQP như trường hợp riêng. Không được bình phương hai vế khi chưa giữ điều kiện vế phải không âm.

SOCP xuất hiện tự nhiên khi dữ liệu bất định. Đòi một ràng buộc tuyến tính đúng với mọi hệ số trong một ellipsoid cho thêm một số hạng chuẩn $\parallel P^{T}x{\parallel }_2$, đóng vai điều chuẩn và làm co lại thành một miền có biên cong. Đòi ràng buộc đúng với xác suất $\eta \ge \frac{1}{2}$ khi hệ số là Gauss cho một ràng buộc cùng dạng với hệ số ${\mathrm{\Phi }}^{-1}(\eta )$. Đồng nhất thức hyperbolic cho phép viết thêm nhiều biểu thức khác thành nón bậc hai.

Tài liệu tham khảo

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