求解二次規劃問題的拉格朗]日及有效集方法——最優化方法課程實驗報告學院:數學與統計學院班級:碩2041班姓名：王彭學號：28指導教師：阮小娥同組人：錢東東求解二次規劃問題的拉格朗日及有效集方法摘要二次規劃師非線性優化中的一種特殊情形，它的目標函數是二次實函數，約束函數都是線性函數。由于二次規劃比較簡單，便于求解（僅次于線性規劃），并且一些非線性優化問題可以轉化為求解一些列的二次規劃問題，因此二次規劃的求解方法較早引起人們的重視，稱為求解非線性優化的一個重要途徑。二次規劃的算法較多，本文僅介紹求解等式約束凸二尺規劃的拉格朗日方法以及求解一般約束凸二次規劃的有效集方法。關鍵字：二次規劃，拉格朗日方法，有效集方法。【目錄】摘要錯誤!未定義書簽。1等式約束凸二次規劃的解法錯誤!未定義書簽。問題描述錯誤!未定義書簽。拉格朗日方法求解等式約束二次規劃問題錯誤!未定義書簽。拉格朗日方法的推導錯誤!未定義書簽。拉格朗日方法的應用錯誤!未定義書簽。2一般凸二次規劃問題的解法錯誤!未定義書簽。問題描述錯誤!未定義書簽。有效集法求解一般凸二次規劃問題錯誤!未定義書簽。有效集方法的理論推導錯誤!未定義書簽。有效集方法的算法步驟錯誤!未定義書簽。有效集方法的應用錯誤!未定義書簽。3總結與體會錯誤!未定義書簽。4附錄錯誤!未定義書簽。拉格朗日方法的matlab程序錯誤!未定義書簽。有效集方法的Matlab程序錯誤!未定義書簽。1等式約束凸二次規劃的解法問題描述min—xtHx+ctx,min—xtHx+ctx,s.t.Ax=b其中HeRnxn對稱正定，AeRmxn行滿秩，c,XGRn，beRm。拉格朗日方法求解等式約束二次規劃問題拉格朗日方法的推導首先寫出拉格朗日函數：L(x,人)=xtHx+ctx-Xt(Ax-b)VL(x,X)=0,V/(x,X)=0得到方程組Hx-ATX=-c一Ax=-b.將上述方程組寫成分塊矩陣形式:-At-a0_||_X「|_-b我們稱傷處方程組的系數矩陣H-A-At0為拉格朗日矩陣。卜面的定理給出了線性方程組有唯一解的充分條件。定理1設HeRmxn對稱正定，AeRmxn行滿秩。若在問題的解X*處滿足二階充分條件，即dTHd>0,VdeRn,d。0,Ad=0,則線性方程組的系數矩陣非奇異，即方程組（）有唯一解。其中，方程組為（）對應的齊次方程組：[H-Atd-A0_LvJ=0（）.&下面，我們來推導方程的求解公式。根據定理1，拉格朗日矩陣必然是非奇異的，故可設其逆為一H-At=一G-Bt--A0JL-Bc由恒等式\H-At]]G-Bt-=-1n0一nxm-A0JL-bCJL0mxnIm可得HG+AtBHG+AtB=I-HBt-AtC=0nxm-AG=0mxnABt=Im于是由上述四個等式得到矩陣G,B,C的表達式G=H-1-H-1At(AH-1At)-iAH-1,(1.5)B=(AH-1At)-1AH-1,(1.6)(1.7)C=-(AH-1At)-1.(1.7)因此，由可得解得表達式X=一Bt[-c]X=一Bt[-c]="-Gc+BTb—力-Bc_-bjBc-Cb(1.8)下面給出X和廠的另一種等價表達式。設xk是問題的任一可行點，即xk滿足Axk=b。而在此點處目標函數的梯度為gk=W（七）=叫+c，利用xk和gk，氣一Gg(1.9)可將改寫為氣一Gg(1.9)拉格朗日方法的應用（1）拉格朗日方法的Matlab程序見附錄。（2）利用拉格朗日方法求解下列問題：minx2+2x2+x2—2xx+x,st.x+x+x=4,2x-x+x=2.解容易寫出一2-20「「11「「4「H=-240,c=0,A=,b=2-11」2_002」1_1」1—」—,利用Matlab程序求解該問題可以結果如下:1.9000909090909091.9545454545454550.136363636363637Lam=2.636363636363636-1.363636363036363￡val=3.9772727272727282一般凸二次規劃問題的解法問題描述考慮一般二次規劃I1Tmin—xtHx+ctx,2s.t.aTx一b=0,ieE={1,???,/},,(2.1)iiaTx-b>0,ieI={l+1,…,m}ii其中H是n階對稱陣。記I(x*)={iIaTx*-b=0,ieI}，下面的定理給出了問題的一個最優性充要條件。定理2x*是二次規劃問題的局部極小點當且僅當(1)存在人*eRm，使得‘Hx+c-&a-&a=0,ieEiel‘HxaTx*-b=0,ieE,aTx*-b>0,ieI,X*>0,ieI;X*=0,ieI\I(x*)ii⑵記

S={deRn\{0}ldTa.=0,ieE;dTa.>0,ieI(x*);dTa.=0,ieI(x*)且人*>0}.則對于任意的deS，均有dTHd>0.容易發現，問題是凸二次規劃的充要條件是H半正定。此時，定理2的第二部分自然滿足。注意到凸優化問題的局部極小點也是全局極小點的性質，我們有卜面的定理:定理3x*是凸二次規劃的全局極小點的充要條件是x*滿足KT條件，即存在人*eRm，使得"+c-&a=0,ieEieIaTx*-b=0,ieE,iiaTx*-b>0,ieI,iiX*>0,ieI;X*=0,ieI\I(x*).ii有效集法求解一般凸二次規劃問題有效集方法的理論推導首先引入下面的定理，它是有效集方法理論基礎。定理4設x*是一般凸二次規劃問題的全局極小點，且在x*處的有效集為S(x*)=EI(x*)，則x*也是下列等式約束凸二次規劃(2.2)I1丁口,Tmin—xtHx+ctx,2st.aTx-b=0,ieS(x*).(2.2)i的全局極小點。從上述定理可以發現，有效集方法的最大難點是事先一般不知道有效集S(x*)，因此只有想辦法構造一個集合序列去逼近它，即從初始點x0出發，計算有效集S(x0)，解對應的等式約束子問題。重復這一做法，得到有效集序列

{S(七)},k=0,1,…，使之S(七)Ts3*)，以獲得原問題的最優解。基于上述定理，我們分4步來介紹有效集方法的算法原理和實施步驟。第一步，形成子問題并求出搜索方向dk.設七是問題的一個可行點，據此確定相應的有效集sk其中I(x)={iIa定相應的有效集sk其中I(x)={iIaTXk-b=0,ieI}.求解相應的aTx子問題2xtHx+ctx,st.aTx-b=0,ieS.min(2.3)上述問題等價于minq(d)=-2drHd+grd,

s.t.aTd=0,ieS.(2.4)其中k=Gxk+C-設求出問題的全局極小點為dk,人k是對應的拉格朗日乘子。第二步，進行線性搜索確定步長因子a第二步，進行線性搜索確定步長因子ak.假設dk豐0分兩種情形討論。k+dk是問題的可行點，即aT(x+d)-b=0,ieE及aT(x+d)-b>0,ieI.ikkiikki則令a=1,x=x+d.若xk+dk不是問題的可行點，則通過線性搜索求出下降最好的可行點。注意到目標函數是凸二次函數，那么這一點應該在可行域的邊界上達到。因此只要求出滿足可行條件的最大步長a即可。k當ieS時，對于任意的a>0，都有aTd=0和aT(x+ad)=aTx=b，kkikikkkiki此時，ak>0不受限制。當i冬S/寸，即第i個約束是嚴格的不等式約束，此時要求a滿足aT閔+akdk)>b,艮口aa’d>b-aTx,ieS.kikiikk注意到上式右端非正，故當aTdk>0時，上式恒成立。而當aTdk<0時，由上式可解得a<b一件.kaTd故有a=a=min]一aiXk|a’d<0>.k〔E，k〕合并第(1)(2)可得a=min{1,ak}(2.5).第三步，修正S..當ak=1時，有效集不變，即SkH：=Sk.而當ak<1時，故a’(x+ad)=bikkkkik—b-a’xak―以k'kaTdkk，ikk因此在xk+(處增加了一個有效約束，即Sk+i:=Sk{ik}.第四步，考慮dk=0的情形。此時xk是問題的全局極小點。若這是對應的不等式約束的拉格朗日乘子均為非負，則xk也是問題的全局極小點，迭代終止。否則，如果對應的不等式約束的拉格朗日乘子有負的分量，那么需要重新尋找一個下降可行方向。設七廣0,eI亳)，現在要求一個下降可行方向dk，滿足grdk<0且a’dk=0,VjeE;a^d^>0,VjeI(x^)，為簡便計算，按下述方式選取d^:a\(x+d)>b,a(x+d)=b,VjeS,j。j,jkkjkk|ardk>0,。隊=0：月jeSk,j壬j,a*)另一方面，注意到七是子問題的全局極小點，故有"A?:其中A廣("les:"廣。:Les-kk從而，gTd=XtAtd.由知kkkkkATd=Z(aTd)e=(aTd)e,

jeS^Jhh于是有gTd=Xt(aTd)e,=Mk(md)<0.上式表明，由確定的d是一個下降可行方向。因此，令S'=S\{j}，則修正kkkk后的子問題minq(d)=2dTHd+gTd,

s.t.aTd=0,ieS'的全局極小點必然是原問題的一個下降可行方向。有效集方法的算法步驟經過上面的分析和推導，我們現在可寫出有效集方法的算法步驟:選取初值。給定初始可行點x0eRn，令k:=0.解子問題。確定相應的有效集S廣EI(xk).求解子問題

minq(d)=2dTHd+gTd,

s.t.aTd=0,ieS,得極小點dk和拉格朗日乘子向量人?若dk。0轉步驟（4）；否則，轉步驟（3）。（3）檢驗終止準則。計算拉格朗日乘子其中gk=Hx+c,gk=Hx+c,Bk=(AH-iA.t)-iAH-i,=(ai)ieSk(X)=min{(X)}.ktieI(xRk1若(X若(Xk)則xk是全局極小點，停算。否則，若（X）則令S:=Sk\{t}，轉步驟（2）。（4）確定步長a.令a=min{1,ak}，其中a=min]~~七'|aTd<01.kieSk[aTdk令x：=x+ad.（5）若a=1則令S:=S；kk+1否則，（5）若a=1則令S:=S；kk+1否則，若a＜1，則令Ski=Sk{/J，其kaTd

jkk|（6）令k:=k+1，轉步驟（1）。有效集方法的應用（1）有效集法的Matlab程序見附錄。(2)用有效集方法求解下列二次規劃問題:minf(x)=x2—xx+2x2—x一10x,112212<s.t.—3x一2x2-6氣>0,x2>0.解首先確定有關數據：「-3—2—62—1-—1-H=,c=,Ae=[],be=[],Ai=10,bi=0—14—101——1」—1010利用Matlab計算可得結果如下:X=0.50002.250CT=lambda=output-0.750Cfva.1:-13.7500iter:83總結與體會通過本次實驗，筆者對求解等式約束凸二次規劃問題的拉格朗日方法及一般約束條件下凸二次規劃問題的有效集方法有了較深的認識和了解。感謝阮老師的悉心教誨和指導，使得筆者對最優化課程中的理論推導、算法步驟及編程都比較熟悉，對以后的科研工作有很好的指導和借鑒意義。4附錄拉格朗日方法的matlab程序拉格朗日算法函數%本程序用拉格朗日方法求解燈飾約束條件的二次規劃問題。function[x,lam,fval]=qlag(H,A,b,c)%功能：用拉格朗日方法求解等式約束二次規劃：—%minf(x)=*x'Hx+c'x，.Ax=b%輸入：H,c分別是目標函數的矩陣和向量，A,b分別是約束條件中的矩陣和向量%輸出：(x,lam)是KT點，fval是最優值IH=inv(H);AHA=A*IH*A';IAHA=inv(AHA);AIH=A*IH;G=IH-AIH'*IAHA*AIH;B=IAHA*AIH;C=-IAHA;x=B'*b-G*c;lam=B*c-C*b;fval=*x'*H*x+c'*x;⑵拉格朗日算法求解等式約束凸二次規劃問題主程序：H=[2-20;-240;002];c=[001]';A=[111;2-11];b=[42]';[x,lam,fval]=qlag(H,A,b,c)有效集方法的Matlab程序(1)有效集方法函數%本程序主要適用于求解一般約束條件下的凸二次規劃問題function[x,lamk,exitflag,output]=qpact(H,c,Ae,be,Ai,bi,x0)%功能：用有效集方法解一般約束二次規劃問題%minf(x)=*x'*H*x+c'*x,%.a'_i*x-b_i=0,(i=1,...,l),】%a'_i*x-b_i>=0,(i=l+1,...，m)%輸入：x0是初始點，H,c分別是目標函數二次矩陣和向量；%Ae=(a_1,...,a_l)',be=(b_1,...,b_l);%Ai=(a_{l+1},...,a_m),bi=(b_{l+1},...,b_m)'.%輸出：x是最優解，lambda是對應的乘子向量；output是結構變量%輸出極小值f(x),迭代次數k等信息，exitflag是算法終止類型%初始化epsilon=;err=;k=0;x=x0;n=length(x);kmax=;ne=length(be);ni=length(bi);lamk=zeros(ne+ni,1);(index=ones(ni,1);fori=1:niifAi(i,:)*x>bi(i)+epsilonindex(i)=0;end%算法主程序whilek<=kmax%求解子問題Aee=[];(ifne>0Aee=Ae;endforj=1:niifindex(j)>0Aee=[Aee;Ai(j,:)];endendgk=H*x+c;[m1,n1]=size(Aee);{[dk,lamk]=qsubp(H,gk,Aee,zeros(m1,1));ifnorm(dk)<=erry=;iflength(lamk)>ne[y,jk]=min(lamk(ne+1:length(lamk)));endify>=0exitflag=0;elseexitflag=1;fori