二次規劃
![]() | 此條目需要精通或熟悉數學的編者參與及協助編輯。 |
二次規劃(Quadratic programming),在運籌學當中,是一種特殊類型的最優化問題。
簡介
一個有n個變數與m個限制的二次規劃問題可以用以下的形式描述。首先給定:
- 一個 維的向量
- 一個 維的對稱矩陣
- 一個 維的矩陣
- 一個 維的向量
則此二次規劃問題的目標即是在限制條件為
的條件下,找一個n 維的向量 x ,使得
為最小。其中是的轉置。
根據不同的參數特性,可以得到對問題不同的結論
- 如果Q是半正定矩陣,那麼f(x)是一個凸函數。相應的二次規劃為凸二次規劃問題;此時若約束條件定義的可行域不為空,且目標函數在此可行域有下界,則該問題有全局最小值。
- 如果Q是正定矩陣,則該問題有唯一的全局最小值。
- 若Q為非正定矩陣,則目標函數是有多個平穩點和局部極小點的NP問題。
- 如果Q=0,二次規劃問題就變成線性規劃問題。
根據優化理論,一個點x成為全局最小值的必要條件是滿足Karush-Kuhn-Tucker條件(KKT)。當f(x)是凸函數時,KKT條件也是充分條件。
當二次規劃問題只有等式約束時,二次規劃可以用線性方程求解。否則的話,常用的二次規劃解法有:
- 內點法(interior point)
- active set
- 共軛梯度法
- 橢球法 若Q為正定矩陣,則相應的二次規劃問題可由橢球法在多項式時間內求解。
- 增廣拉格朗日法
- 梯度投影法
凸集二次規劃問題是凸優化問題的一個特例。
對偶
每個二次規劃問題的對偶問題也是二次規劃問題。以正定矩陣Q為例:
對偶問題,可定義為
可用:得到的極小
- ,
對偶函數:
對偶問題為:
maximize :
subject to :
計算複雜性
當Q正定時,用橢圓法可在多項式時間內解二次規劃問題。當Q非正定時,二次規劃問題是NP困難的。即使Q只存在一個負特徵值時,二次規劃問題也是NP困難的。 [1] [2]
參考文獻
- ^ Sahni, S. Computationally related problems (PDF). SIAM Journal on Computing. 1974, 3 (4): 262–279 [2022-09-07]. CiteSeerX 10.1.1.145.8685
. doi:10.1137/0203021. (原始內容 (PDF)存檔於2022-04-26).
- ^ Pardalos, Panos M.; Vavasis, Stephen A. Quadratic programming with one negative eigenvalue is (strongly) NP-hard. Journal of Global Optimization. 1991, 1 (1): 15–22. S2CID 12602885. doi:10.1007/bf00120662.