1、精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)求解二次規(guī)劃問(wèn)題的拉格朗求解二次規(guī)劃問(wèn)題的拉格朗日及有效集方法日及有效集方法最優(yōu)化方法課程實(shí)驗(yàn)報(bào)告學(xué)院：數(shù)學(xué)與統(tǒng)計(jì)學(xué)院班級(jí)：碩 2041 班姓名：王彭學(xué)號(hào)：指導(dǎo)教師：阮小娥同 組 人：錢東東精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)求解二次規(guī)劃問(wèn)題的拉格朗日及有效集方法摘要摘要二次規(guī)劃師非線性優(yōu)化中的一種特殊情形，它的目標(biāo)函數(shù)是二次實(shí)函數(shù)，約束函數(shù)都是線性函數(shù)。由于二次規(guī)劃比較簡(jiǎn)單，便于求解（僅次于線性規(guī)劃） ，并且一些非線性優(yōu)化問(wèn)題可以轉(zhuǎn)化為求解一些列的二次規(guī)劃問(wèn)題， 因此二次規(guī)劃的求解方法較早引起人們的重視，稱為求解非線性優(yōu)化的一個(gè)重要途徑。二次規(guī)

2、劃的算法較多， 本文僅介紹求解等式約束凸二尺規(guī)劃的拉格朗日方法以及求解一般約束凸二次規(guī)劃的有效集方法。關(guān)鍵字：關(guān)鍵字：二次規(guī)劃，拉格朗日方法，有效集方法。精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)【目錄】【目錄】精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)1 等式約束凸二次規(guī)劃的解法等式約束凸二次規(guī)劃的解法1.1 問(wèn)題描述問(wèn)題描述我們考慮如下的二次規(guī)劃問(wèn)題bAxtsxcHxxTT. .,21min(1.1)其中nnRH對(duì)稱正定，nmRA行滿秩，nRxc,，mRb。1.2 拉格朗日方法求解等式約束二次規(guī)劃問(wèn)題拉格朗日方法求解等式約束二次規(guī)劃問(wèn)題1.2.1 拉格朗日方法的推導(dǎo)拉格朗日方法的推導(dǎo)首先寫

3、出拉格朗日函數(shù)：)(21)L(x,bAxxcHxxTTT，(1.2)令0),(, 0),(xLxLx，得到方程組.,A-HxTbAxc將上述方程組寫成分塊矩陣形式：.0HbcxAAT(1.3)我們稱傷處方程組的系數(shù)矩陣0A-A-HT為拉格朗日矩陣。下面的定理給出了線性方程組(1.1)有唯一解的充分條件。定理定理 1 1 設(shè)nmRH對(duì)稱正定，nmRA行滿秩。若在問(wèn)題(1.1)的解*x處滿足二階充分條件，即, 0, 0, 0dTAddRdHdn則線性方程組(1.4)的系數(shù)矩陣非奇異，即方程組（1.4）有唯一解。其中，方程組(1.4)為（1.1）對(duì)應(yīng)的齊次方程組：精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注

4、-專業(yè)00A-HTvdA（1.4）.下面，我們來(lái)推導(dǎo)方程(1.3)的求解公式。根據(jù)定理 1，拉格朗日矩陣必然是非奇異的，故可設(shè)其逆為CBBGT0A-A-HT.由恒等式mnmmnnTIICBBG000A-A-HT可得.,0,0,AHGTmTnmmnTTnIABAGCAHBIB于是由上述四個(gè)等式得到矩陣CB,G,的表達(dá)式)7 . 1 (.)()6 . 1 (,)()5 . 1 (,)(HG111111111-1TTTTAAHCAHAAHBAHAAHAH因此，由(1.3)可得解得表達(dá)式)8 . 1 (,xCbBcbBGcbcCBBGTT其中，CB,G,分別由(1.5),(1.6),(1.7)給出。下

5、面給出x和的另一種等價(jià)表達(dá)式。設(shè)kx是問(wèn)題(1.1)的任一可行點(diǎn)，即kx滿足bkAx。而在此點(diǎn)處目標(biāo)函數(shù)的梯度為cHxxfkk)(gk，利用kx和kg，可將(1.8)改寫為)9 . 1 (.xkkkBgGgx1.2.2 拉格朗日方法的應(yīng)用拉格朗日方法的應(yīng)用（1）拉格朗日方法的 Matlab 程序見附錄。（2）利用拉格朗日方法求解下列問(wèn)題：精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè). 22, 4. .,22min321321321232221xxxxxxtsxxxxxx解解 容易寫出.24,112111,100,200042022HbAc利用 Matlab 程序求解該問(wèn)題可以結(jié)果如下：2 一般凸

6、二次規(guī)劃問(wèn)題的解法一般凸二次規(guī)劃問(wèn)題的解法2.1 問(wèn)題描述問(wèn)題描述考慮一般二次規(guī)劃) 1 . 2(, 1, 0, 1, 0. .,21minmlIibxalEibxatsxcHxxiTiiTiTT其中H是n階對(duì)稱陣。記Ii0,b-xa|i)I(xi*Ti*，下面的定理給出了問(wèn)題(2.1)的一個(gè)最優(yōu)性充要條件。定理定理 2 2*x是二次規(guī)劃問(wèn)題(2.1)的局部極小點(diǎn)當(dāng)且僅當(dāng)（1）存在mR*，使得精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè).)(, 0;, 0, 0, 0, 0*xIIiIiIibxaEibxaaacHxiiiTiiTiIiiiEiii(2)記0.)I(xi0,ad);I(xi0,a

7、dE;i0,ad|0RdS*iT*iTiTni且則對(duì)于任意的Sd，均有0dTHd.容易發(fā)現(xiàn)，問(wèn)題(2.1)是凸二次規(guī)劃的充要條件是H半正定。此時(shí)，定理 2的第二部分自然滿足。注意到凸優(yōu)化問(wèn)題的局部極小點(diǎn)也是全局極小點(diǎn)的性質(zhì)，我們有下面的定理：定理定理 3 3*x是凸二次規(guī)劃的全局極小點(diǎn)的充要條件是*x滿足KT條件，即存在mR*，使得).(, 0;, 0, 0, 0, 0Hx*xIIiIiIibxaEibxaaaciiiTiiTiEiIiiiii2.2 有效集法求解一般凸二次規(guī)劃問(wèn)題有效集法求解一般凸二次規(guī)劃問(wèn)題2.2.1 有效集方法的理論推導(dǎo)有效集方法的理論推導(dǎo)首先引入下面的定理，它是有效集方

8、法理論基礎(chǔ)。定理 4 設(shè)*x是一般凸二次規(guī)劃問(wèn)題的全局極小點(diǎn)，且在*x處的有效集為)()(*xIExS，則*x也是下列等式約束凸二次規(guī)劃)2 . 2().(, 0. .,21min*xSibxatsxcHxxiTiTT的全局極小點(diǎn)。從上述定理可以發(fā)現(xiàn)，有效集方法的最大難點(diǎn)是事先一般不知道有效集)(*xS，因此只有想辦法構(gòu)造一個(gè)集合序列去逼近它，即從初始點(diǎn)0 x出發(fā)，計(jì)算有效集)(0 xS，解對(duì)應(yīng)的等式約束子問(wèn)題。重復(fù)這一做法，得到有效集序列精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè), 1 , 0),(kxSk使之)()(*xSxSk，以獲得原問(wèn)題的最優(yōu)解?；谏鲜龆ɡ?，我們分 4 步來(lái)介紹有效

9、集方法的算法原理和實(shí)施步驟。第一步，形成子問(wèn)題并求出搜索方向kd.設(shè)kx是問(wèn)題(2.1)的一個(gè)可行點(diǎn)，據(jù)此確定相應(yīng)的有效集)(kkxIES，其中., 0|)(IibxaixIikTik求解相應(yīng)的子問(wèn)題)3 . 2(., 0. .,21minkiTiTTSibxatsxcHxx上述問(wèn)題等價(jià)于)4 . 2(., 0. .,21)(minkTiTkTkSidatsdgHdddq其中.,cGxgdxxkkk設(shè)求出問(wèn)題(2.4)的全局極小點(diǎn)為kkd,是對(duì)應(yīng)的拉格朗日乘子。第二步，進(jìn)行線性搜索確定步長(zhǎng)因子k.假設(shè)0kd，分兩種情形討論。(1) 若kkdx 是問(wèn)題(2.1)的可行點(diǎn)，即., 0)(, 0)(

10、IibdxaEibdxaikkTiikkTi及則令., 11kkkkdxx(2) 若kkdx 不是問(wèn)題(2.1)的可行點(diǎn)，則通過(guò)線性搜索求出下降最好的可行點(diǎn)。注意到目標(biāo)函數(shù)是凸二次函數(shù)，那么這一點(diǎn)應(yīng)該在可行域的邊界上達(dá)到。因此只要求出滿足可行條件的最大步長(zhǎng)k即可。當(dāng)kSi時(shí)，對(duì)于任意的0k，都有0kTida和ikTikkkTibxadxa)(，此時(shí)，0k不受限制。當(dāng)kSi時(shí)，即第i個(gè)約束是嚴(yán)格的不等式約束，此時(shí)要求k滿足ikkkTibdxa)(，即.,kkTiikTikSixabda注意到上式右端非正，故當(dāng)0kTida時(shí)，上式恒成立。而當(dāng)0kTida時(shí)，由上式可解得精選優(yōu)質(zhì)文檔-傾情為你奉上專

11、心-專注-專業(yè).kTikTiikdaxab 故有.0|minkTikTikTiikkdadaxab合并第(1)(2)可得)5 . 2(, 1minkk.第三步，修正kS.當(dāng)1k時(shí)，有效集不變，即kkSS:1.而當(dāng)1k時(shí)，kTikTiikkdaxabkkk，故kkikkkTibdxa)(， 因 此 在!kx處 增 加 了 一 個(gè) 有 效 約 束 ， 即:1kkkiSS.第四步，考慮0kd的情形。此時(shí)kx是問(wèn)題(2.3)的全局極小點(diǎn)。若這是對(duì)應(yīng)的不等式約束的拉格朗日乘子均為非負(fù)， 則kx也是問(wèn)題(2.1)的全局極小點(diǎn)， 迭代終止。否則，如果對(duì)應(yīng)的不等式約束的拉格朗日乘子有負(fù)的分量，那么需要重新尋找

12、一個(gè)下降可行方向。設(shè))(, 0kkjxIjk，現(xiàn)在要求一個(gè)下降可行方向kd，滿足0kTkdg且)(, 0;, 0kkTjkTjxIjdaEjda，為簡(jiǎn)便計(jì)算，按下述方式選取kd：,)(,)(kkjkkTjjkkTjjjSjbdxabdxakk即)6 . 2(, 0, 0kkkTjkTjjjSjdadak另一方面，注意到kx是子問(wèn)題(2.3)的全局極小點(diǎn)，故有, 0kSiikikacHx即,kkkAg其中精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè).)(,)(kkSikikSiikaA從而，.kTkTkkTkdAdg由(2.6)知,)()(kkkjkTjSjjkTjkTkedaedadA于是有.

13、0)()(kTjkjjkTjTkkTkdaedadgkkk上式表明，由(2.6)確定的kd是一個(gè)下降可行方向。因此，令kkkjSS，則修正后的子問(wèn)題, 0. .,21)(minkTiTkTkSidatsdgHdddq的全局極小點(diǎn)必然是原問(wèn)題的一個(gè)下降可行方向。2.2.2 有效集方法的算法步驟有效集方法的算法步驟經(jīng)過(guò)上面的分析和推導(dǎo)，我們現(xiàn)在可寫出有效集方法的算法步驟：（1）選取初值。給定初始可行點(diǎn)nRx 0，令0:k.（2）解子問(wèn)題。確定相應(yīng)的有效集)(kkxIES.求解子問(wèn)題, 0. .,21)(minkTiTkTkSidatsdgHdddq得極小點(diǎn)kd和拉格朗日乘子向量k.若0kd轉(zhuǎn)步驟（

14、4） ；否則，轉(zhuǎn)步驟（3） 。（3）檢驗(yàn)終止準(zhǔn)則。計(jì)算拉格朗日乘子,kkkgB其中.)(,)(,111kSiikkTkkkkkaAHAAHABcHxg令.)(min)()(ikxIitkk若0)(tk，則kx是全局極小點(diǎn)，停算。否則，若0)(tk，則令:tSSkk，轉(zhuǎn)步驟（2） 。（4）確定步長(zhǎng)k.令, 1minkk，其中精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè).0|minkTikTikTiiSikdadaxabk令.:1kkkkdxx（5）若1k，則令kkSS:1；否則，若1k，則令1kkkjSS，其中kj滿足.kTjkTjjkdaxabkkk（6）令1: kk，轉(zhuǎn)步驟(1)。2.2.3

15、有效集方法的應(yīng)用有效集方法的應(yīng)用（1）有效集法的 Matlab 程序見附錄。（2）用有效集方法求解下列二次規(guī)劃問(wèn)題：. 0, 0623. .,102)(min212121222121xxxxtsxxxxxxxf解解 首先確定有關(guān)數(shù)據(jù)：.006,100123,101,4112biAibeAecH利用 Matlab 計(jì)算可得結(jié)果如下：3 總結(jié)與體會(huì)總結(jié)與體會(huì)通過(guò)本次實(shí)驗(yàn)， 筆者對(duì)求解等式約束凸二次規(guī)劃問(wèn)題的拉格朗日方法及一般精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)約束條件下凸二次規(guī)劃問(wèn)題的有效集方法有了較深的認(rèn)識(shí)和了解。感謝阮老師的悉心教誨和指導(dǎo)，使得筆者對(duì)最優(yōu)化課程中的理論推導(dǎo)、算法步驟及編程

16、都比較熟悉，對(duì)以后的科研工作有很好的指導(dǎo)和借鑒意義。4 附錄附錄4.1 拉格朗日方法拉格朗日方法的的 matlab 程序程序(1)(1) 拉格朗日算法函數(shù)拉格朗日算法函數(shù)%本程序用拉格朗日方法求解燈飾約束條件的二次規(guī)劃問(wèn)題。function x,lam,fval=qlag(H,A,b,c)%功能：用拉格朗日方法求解等式約束二次規(guī)劃：% min f(x)=0.5*xHx+cx， s.t. Ax=b%輸入：H,c 分別是目標(biāo)函數(shù)的矩陣和向量，A,b 分別是約束條件中的矩陣和向量%輸出：(x,lam)是 KT 點(diǎn)，fval 是最優(yōu)值IH=inv(H);AHA=A*IH*A;IAHA=inv(AHA)

17、;AIH=A*IH;G=IH-AIH*IAHA*AIH;B=IAHA*AIH;C=-IAHA;x=B*b-G*c;lam=B*c-C*b;fval=0.5*x*H*x+c*x;(2) 拉格朗日算法求解等式約束凸二次規(guī)劃問(wèn)題拉格朗日算法求解等式約束凸二次規(guī)劃問(wèn)題主程序：主程序：H=2 -2 0;-2 4 0;0 0 2;c=0 0 1;A=1 1 1;2 -1 1;b=4 2;x,lam,fval=qlag(H,A,b,c)4.2 有效集方法的有效集方法的 Matlab 程序程序（1 1）有效集方法函數(shù)）有效集方法函數(shù)%本程序主要適用于求解一般約束條件下的凸二次規(guī)劃問(wèn)題function x,la

18、mk,exitflag,output=qpact(H,c,Ae,be,Ai,bi,x0)%功能：用有效集方法解一般約束二次規(guī)劃問(wèn)題精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)%min f(x)=0.5*x*H*x+c*x,%s.t.a_i*x-b_i=0,(i=1,l),%a_i*x-b_i=0,(i=l+1,m)%輸入：x0 是初始點(diǎn)，H,c 分別是目標(biāo)函數(shù)二次矩陣和向量；%Ae=（a_1,.,a_l）,be=(b_1,.,b_l);%Ai=(a_l+1,.,a_m),bi=(b_l+1,.,b_m).%輸出：x 是最優(yōu)解，lambda 是對(duì)應(yīng)的乘子向量；output 是結(jié)構(gòu)變量%輸出極小值

19、f(x),迭代次數(shù) k 等信息，exitflag 是算法終止類型%初始化epsilon=1.0e-9;err=1.0e-6;k=0;x=x0;n=length(x);kmax=1.0e3;ne=length(be);ni=length(bi);lamk=zeros(ne+ni,1);index=ones(ni,1);for i=1:niif Ai(i,:)*xbi(i)+epsilonindex(i)=0;endend%算法主程序while k0Aee=Ae;endfor j=1:niif index(j)0Aee=Aee;Ai(j,:);endendgk=H*x+c;m1,n1=size(Aee);dk,lamk=qsubp(H,gk,Aee,zeros(m1,1);if norm(