Quy hoạch toàn phương (QP và QCQP)

QP cực tiểu một hàm toàn phương $\frac{1}{2}{x}^{T}Px+q^{T}x+r$ với $P⪰0$ trên một . QCQP cho phép thêm các ràng buộc toàn phương lồi. Khác với LP, nghiệm của QP có thể nằm bên trong hoặc giữa một cạnh của đa diện. Khi thiếu điều kiện $P⪰0$, bài toán không lồi và nói chung rất khó.

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

Lồng nhau. LP là QP với $P=0$, QP là QCQP khi mọi ràng buộc toàn phương suy biến thành tuyến tính. Khi $P\succ 0$, nghiệm nếu có là duy nhất.

Các bài toán thực tế tiêu biểu. có cận cho từng biến, khoảng cách giữa hai , lớn nhất của một khi chỉ biết một phần phân phối, bài toán có chi phí ngẫu nhiên với hàm chi phí tính đến rủi ro ${\overline{c}}^{T}x+\gamma x^T\mathrm{\Sigma }x$, và danh mục đầu tư Markowitz cực tiểu rủi ro $x^T\mathrm{\Sigma }x$ với lợi suất tối thiểu. Nguồn: Convex Optimization, §4.4 và §4.4.1.

Ví dụ

Khoảng cách giữa hai là giá trị tối ưu của một QP cực tiểu $\parallel x_1-x_2{\parallel }_2^2$, với $x_1$ và $x_2$ lần lượt thuộc hai đa diện.

Khi nào cần dùng?

có ràng buộc, danh mục đầu tư Markowitz, phép chiếu lên .

Câu hỏi ôn lại

Kẹp từng thành phần của nghiệm vào một hình hộp có cho nghiệm của QP có ràng buộc hộp không?

Xem đáp án

Nói chung không, trừ khi $A^{T}A$ chéo. Khi các biến tương quan với nhau, phải giải QP.

Thuật ngữ liên quan

• Quy hoạch tuyến tính (LP)
• Ma trận nửa xác định dương
• Bình phương tối thiểu