二次規劃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]

參考文獻

編輯
  1. ^ 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). 
  2. ^ 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.