二次規劃

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

簡介

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

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

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

${\displaystyle Ax\leq b}$

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

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

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

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

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

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

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

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

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

對偶

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

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

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

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

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

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

對偶函數：

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

對偶問題為：

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

subject to :${\displaystyle \lambda \geq 0}$

計算複雜性

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