Quy hoạch nón bậc hai (SOCP)

SOCP cực tiểu một hàm tuyến tính với các ràng buộc $\parallel A_{i}x+b_i{\parallel }_2\le c_i^{T}x+d_i$, mỗi ràng buộc đòi một phụ thuộc affine vào x nằm trong nón bậc hai. SOCP chứa LP và như trường hợp riêng, và xuất hiện tự nhiên khi dữ liệu bất định, như trong LP bền vững và ràng buộc xác suất với hệ số Gauss.

Lĩnh vực: Tối ưu hóa

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Giải thích kỹ thuật

Từ bất định tới chuẩn. Nếu $a$ chỉ được biết nằm trong $\{\overline{a}+Pu:\parallel u{\parallel }_2\le 1\}$, thì $sup{a}^{T}x={\overline{a}}^{T}x+\parallel P^{T}x{\parallel }_2$ theo bất đẳng thức Cauchy–Schwarz, nên ràng buộc bền vững là một ràng buộc nón bậc hai. Nếu $a$ là Gauss với trung bình $\overline{a}$ và $\mathrm{\Sigma }$, ràng buộc $\mathrm{prob}(a^{T}x\le b)\ge \eta$ tương đương ${\overline{a}}^{T}x+{\mathrm{\Phi }}^{-1}(\eta )\parallel {\mathrm{\Sigma }}^{1/2}x{\parallel }_2\le b$, lồi khi $\eta \ge \frac{1}{2}$.

Ràng buộc hyperbolic. Với $y,z\ge 0$, điều kiện $x^{T}x\le yz$ tương đương $\parallel (2x,y-z){\parallel }_2\le y+z$. Nguồn: Convex Optimization, §4.4.2 và bài tập 4.26.

Ví dụ

Ràng buộc $a^{T}x\le b$ đúng với mọi $a$ trong hình cầu tâm $\overline{a}$ bán kính $\rho$ tương đương với ${\overline{a}}^{T}x+\rho \parallel x{\parallel }_2\le b$.

Khi nào cần dùng?

Tối ưu bền vững, ràng buộc xác suất, các bài toán chứa .

Câu hỏi ôn lại

Có được bình phương hai vế của $\parallel Ax+b{\parallel }_2\le c^{T}x+d$ không?

Xem đáp án

Chỉ khi giữ thêm điều kiện $c^{T}x+d\ge 0$. Bình phương vô điều kiện có thể thêm nghiệm sai và làm mất dạng lồi.

Thuật ngữ liên quan

• Nón lồi
• Quy hoạch toàn phương (QP và QCQP)
• Quy hoạch nửa xác định (SDP)