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 $\mathbb{R}^{n}$. Cực tiểu hóa hàm số mục tiêu sau:

$f(x_1,\cdots,x_n)=\sum_{i=1}^{n}\sum_{j=1}^{n}q_{ij}x_i x_j +\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(\mathbf{x}) = \tfrac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x}$

dưới các ràng buộc sau:

$A\mathbf{x} \leq \mathbf b$

$E\mathbf{x} = \mathbf d$

với $\mathbf{x}^T$ là vector chuyển vị của $\mathbf{x}$. Kí hiệu $Ax \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 $\mathbf b$.