二次規劃二次規劃問題求解 _生活百科

大家好,小編來為大家解答以上的問題。二次規劃問題求解，二次規劃這個很多人還不知道,現在讓我們一起來看看吧！

文章插圖
1、二次規劃（Quadraticprogramming），在運籌學當中，是一種特殊類型的最佳化問題。
2、[編輯]簡介二次規劃問題可以以下形式來描述：f(x)=(1/2)xTQx+cTx受到一個或更多如下型式的限制條件：Ex=dvT是v的轉置。
3、如果Q是半正定矩陣，那么f(x)是一個凸函數。
4、如果有至少一個向量x滿足約束而且f(x)在可行域有下界，二次規劃問題就有一個全局最小值x 。
5、如果Q是正定矩陣，那么全局最小值就是唯一的。
6、如果Q=0，二次規劃問題就變成線性規劃問題。
7、根據優化理論，一個點x成為全局最小值的必要條件是滿足Karush-Kuhn-Tucker(KKT)條件。
8、當f(x)是凸函數時，KKT條件也是充分條件。
9、當二次規劃問題只有等式約束時，二次規劃可以用線性方程求解。
10、否則的話，常用的二次規劃解法有：內點法(interiorpoint)、activeset和共軛梯度法等。
11、凸集二次規劃問題是凸優化問題的一個特例。
12、[編輯]對偶每個二次規劃問題的對偶問題也是二次規劃問題。
13、我們以正定矩陣Q為例：L(x,λ)=(1/2)xTQx+λT(Ax?b)+cTx對偶問題g(λ)，可定義為我們可用:得到L的極小x*=?Q?1(ATλ+c),對偶函數：g(λ)=?(1/2)λTAQ?1ATλ?cTQ?1ATλ?bTλ對偶問題為：maximize:?(1/2)λTAQ?1ATλ?(ctQ?1AT+bT)λsubjectto:計算復雜性當Q正定時，用橢圓法可在多項式時間內解二次規劃問題。
【二次規劃二次規劃問題求解】14、當Q負定時，二次規劃問題是NP困難的(NP-Hard) 。
15、即使Q存在一個負特征值時，二次規劃問題就是NP困難的。
本文到此分享完畢，希望對大家有所幫助。

二次規劃 二次規劃問題求解

二次規劃二次規劃問題求解