Quy hoạch nửa xác định (SDP)

SDP cực tiểu một hàm tuyến tính với ràng buộc bất đẳng thức tuyến tính, tức một ma trận đối xứng phụ thuộc affine vào x phải hoặc nửa xác định âm. lồi nhưng có thể có biên cong. SDP chứa LP, QP và như trường hợp riêng.

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

Dạng chuẩn. Tương tự LP, SDP dạng chuẩn cực tiểu $\mathrm{tr}(CX)$ với $\mathrm{tr}(A_{i}X)=b_i$ và $X⪰0$. Nhiều LMI và bất đẳng thức tuyến tính gộp được thành một LMI khối chéo. Một LMI chéo là một hệ bất đẳng thức tuyến tính.

Ví dụ. tương quan của ba biến phải . Giữ ${\rho }_{23}=c$, tập các cặp $({\rho }_{12},{\rho }_{13})$ hợp lệ là ellipse ${\rho }_{12}^2+{\rho }_{13}^2-2c{\rho }_{12}{\rho }_{13}\le 1-c^2$. Cực tiểu lớn nhất ${\lambda }_{max}(A(x))$ là SDP: Cực tiểu $t$ với $tI-A(x)⪰0$. Nguồn: Convex Optimization, §4.6.

Ví dụ

Với ${\rho }_{12}={\rho }_{23}=0.8$, điều kiện tương quan buộc ${\rho }_{13}\in [0.28,1]$.

Khi nào cần dùng?

Cực tiểu lớn nhất hay chuẩn phổ của , ma trận tương quan hợp lệ, điều khiển, .

Câu hỏi ôn lại

Ràng buộc $X⪰0$ có nghĩa là mọi phần tử của X không âm không?

Xem đáp án

Không. Nó nghĩa là $v^{T}Xv\ge 0$ với mọi v. Một có phần tử âm vẫn có thể , và ngược lại.

Thuật ngữ liên quan

• Ma trận nửa xác định dương
• Phần bù Schur
• Bất đẳng thức tổng quát