✨Quy hoạch toàn phương

Quy hoạch toàn phương là một dạng đặc biệt của tối ưu hóa toán học. Đó là vấn đề tối ưu hóa (cực tiểu hóa hoặc cực đại hóa) một hàm số mục tiêu dạng bậc 2 với nhiều biến dưới những hàm số ràng buộc tuyến tính.

Một bài toán quy hoạch toàn phương có thể được viết dưới dạng:

Cho x thuộc $\backslash mathbb\{R\}^\{n\}$. Cực tiểu hóa hàm số mục tiêu sau: :$f(x\_1,\backslash cdots,x$n)=\sum{i=1}^{n}\sum{j=1}^{n}q{ij}x_i xj +\sum{j=1}^{n}c_j x_j dưới các ràng buộc: :$g$i(\mathbf{x})=\sum{j=1}^{n}a_{ij}x_j-b_i\le 0 \qquad i\in 1,\ldots, m

Bài toán ở trên có thể được viết dưới dạng ma trận với ma trận Q n×n đối xứng, và c là một vector n×1 bất kì.

Cực tiểu hóa (với x) :$f(\backslash mathbf\{x\})\; =\; \backslash tfrac\{1\}\{2\}\; \backslash mathbf\{x\}^T\; Q\backslash mathbf\{x\}\; +\; \backslash mathbf\{c\}^T\; \backslash mathbf\{x\}$

dưới các ràng buộc sau: :$A\backslash mathbf\{x\}\; \backslash leq\; \backslash mathbf\; b$ :$E\backslash mathbf\{x\}\; =\; \backslash mathbf\; d$

với $\backslash mathbf\{x\}^T$ là vector chuyển vị của $\backslash mathbf\{x\}$. Ký hiệu $Ax\; \backslash leq\; b$ có nghĩa là mỗi thành phần của vector Ax nhỏ hơn hoặc bằng thành phần tương ứng của vector $\backslash mathbf\; b$.