二次規劃

二次規劃（Quadratic programming），在運籌學當中，是一種特殊類型的最優化問題。

簡介

一個有n個變數與m個限制的二次規劃問題可以用以下的形式描述。首先給定：

• 一個 $n$ 維的向量 $\mathbf {c}$
• 一個 $n\times n$ 維的對稱矩陣 $Q$
• 一個 $m\times n$ 維的矩陣$A$
• 一個 $m$ 維的向量 $\mathbf {b}$

則此二次規劃問題的目標即是在限制條件為

$Ax\leq b$

的條件下，找一個n 維的向量 x ，使得

$f(x)=(1/2)x^{T}Qx+c^{T}x$

為最小。其中$x^{T}$是$x$的轉置。

根據不同的參數特性，可以得到對問題不同的結論

• 如果Q是半正定矩陣，那麼f(x)是一個凸函數。相應的二次規劃為凸二次規劃問題；此時若約束條件定義的可行域不為空，且目標函數在此可行域有下界，則該問題有全局最小值。
• 如果Q是正定矩陣，則該問題有唯一的全局最小值。
• 若Q為非正定矩陣，則目標函數是有多個平穩點和局部極小點的NP問題。
• 如果Q=0，二次規劃問題就變成線性規劃問題。

根據優化理論，一個點x成為全局最小值的必要條件是滿足Karush-Kuhn-Tucker條件（KKT）。當f(x)是凸函數時，KKT條件也是充分條件。

當二次規劃問題只有等式約束時，二次規劃可以用線性方程求解。否則的話，常用的二次規劃解法有：

• 內點法(interior point)
• active set
• 共軛梯度法
• 橢球法 若Q為正定矩陣，則相應的二次規劃問題可由橢球法在多項式時間內求解。
• 增廣拉格朗日法
• 梯度投影法

凸集二次規劃問題是凸優化問題的一個特例。

對偶

每個二次規劃問題的對偶問題也是二次規劃問題。以正定矩陣Q為例：

$L(x,\lambda )=(1/2)x^{T}Qx+\lambda ^{T}(Ax-b)+c^{T}x$

對偶問題$g(\lambda )$，可定義為

$g(\lambda )=\inf _{x}L(x,\lambda )$

可用$\nabla _{x}L(x,\lambda )=0$:得到$L$的極小

$x*=-Q^{-1}(A^{T}\lambda +c)$,

對偶函數：

$g(\lambda )=-(1/2)\lambda ^{T}AQ^{-1}A^{T}\lambda -c^{T}Q^{-1}A^{T}\lambda -b^{T}\lambda$

對偶問題為：

maximize :$-(1/2)\lambda ^{T}AQ^{-1}A^{T}\lambda -(c^{T}Q^{-1}A^{T}+b^{T})\lambda$

subject to :$\lambda \geq 0$

計算複雜性

當Q正定時，用橢圓法可在多項式時間內解二次規劃問題。當Q非正定時，二次規劃問題是NP困難的。即使Q只存在一個負特徵值時，二次規劃問題也是NP困難的。