二次規劃(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]
參考文獻
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.