求解二次規(guī)劃方案問題的拉格朗日及有效集方法

學院：數(shù)學與記錄學院班級：碩2041班學院：數(shù)學與記錄學院班級：碩2041班姓名：王彭學號：指引教師：阮小娥同組人：錢東東——最優(yōu)化辦法課程實驗報告求解二次規(guī)劃問題拉格朗日及有效集辦法求解二次規(guī)劃問題拉格朗日及有效集辦法摘要二次規(guī)劃師非線性優(yōu)化中一種特殊情形，它目的函數(shù)是二次實函數(shù)，約束函數(shù)都是線性函數(shù)。由于二次規(guī)劃比較簡樸，便于求解（僅次于線性規(guī)劃），并且某些非線性優(yōu)化問題可以轉化為求解某些列二次規(guī)劃問題，因而二次規(guī)劃求解辦法較早引起人們注重，稱為求解非線性優(yōu)化一種重要途徑。二次規(guī)劃算法較多，本文僅簡介求解等式約束凸二尺規(guī)劃拉格朗日辦法以及求解普通約束凸二次規(guī)劃有效集辦法。核心字：二次規(guī)劃，拉格朗日辦法，有效集辦法。

【目錄】摘要 -1-1等式約束凸二次規(guī)劃解法 -3-1.1問題描述 -3-1.2拉格朗日辦法求解等式約束二次規(guī)劃問題 -3-1.2.1拉格朗日辦法推導 -3-1.2.2拉格朗日辦法應用 -4-2普通凸二次規(guī)劃問題解法 -5-2.1問題描述 -5-2.2有效集法求解普通凸二次規(guī)劃問題 -6-2.2.1有效集辦法理論推導 -6-2.2.2有效集辦法算法環(huán)節(jié) -9-2.2.3有效集辦法應用 -10-3總結與體會 -11-4附錄 -11-4.1拉格朗日辦法matlab程序 -11-4.2有效集辦法Matlab程序 -11-

1等式約束凸二次規(guī)劃解法1.1問題描述咱們考慮如下二次規(guī)劃問題(1.1)其中對稱正定，行滿秩，，。1.2拉格朗日辦法求解等式約束二次規(guī)劃問題1.2.1拉格朗日辦法推導一方面寫出拉格朗日函數(shù)：，(1.2)令，得到方程組將上述方程組寫成分塊矩陣形式：(1.3)咱們稱傷處方程組系數(shù)矩陣為拉格朗日矩陣。下面定理給出了線性方程組(1.1)有唯一解充分條件。定理1設對稱正定，行滿秩。若在問題(1.1)解處滿足二階充分條件，即則線性方程組(1.4)系數(shù)矩陣非奇異，即方程組（1.4）有唯一解。其中，方程組(1.4)為（1.1）相應齊次方程組：（1.4）.下面，咱們來推導方程(1.3)求解公式。依照定理1，拉格朗日矩陣必然是非奇異，故可設其逆為.由恒等式可得于是由上述四個等式得到矩陣表達式因而，由(1.3)可得解得表達式其中，分別由(1.5),(1.6),(1.7)給出。下面給出和另一種等價表達式。設是問題(1.1)任一可行點，即滿足。而在此點處目的函數(shù)梯度為，運用和，可將(1.8)改寫為1.2.2拉格朗日辦法應用（1）拉格朗日辦法Matlab程序見附錄。（2）運用拉格朗日辦法求解下列問題：解容易寫出運用Matlab程序求解該問題可以成果如下：2普通凸二次規(guī)劃問題解法2.1問題描述考慮普通二次規(guī)劃其中是階對稱陣。記，下面定理給出了問題(2.1)一種最優(yōu)性充要條件。定理2是二次規(guī)劃問題(2.1)局部極小點當且僅當（1）存在，使得(2)記則對于任意，均有.容易發(fā)現(xiàn)，問題(2.1)是凸二次規(guī)劃充要條件是半正定。此時，定理2第二某些自然滿足。注意到凸優(yōu)化問題局部極小點也是全局極小點性質，咱們有下面定理：定理3是凸二次規(guī)劃全局極小點充要條件是滿足條件，即存在，使得2.2有效集法求解普通凸二次規(guī)劃問題2.2.1有效集辦法理論推導一方面引入下面定理，它是有效集辦法理論基本。定理4設是普通凸二次規(guī)劃問題全局極小點，且在處有效集為，則也是下列等式約束凸二次規(guī)劃全局極小點。從上述定理可以發(fā)現(xiàn)，有效集辦法最大難點是事先普通不懂得有效集，因而只有想辦法構造一種集合序列去逼近它，即從初始點出發(fā)，計算有效集，解相應等式約束子問題。重復這一做法，得到有效集序列使之，以獲得原問題最優(yōu)解?；谏鲜龆ɡ?，咱們分4步來簡介有效集辦法算法原理和實行環(huán)節(jié)。第一步，形成子問題并求出搜索方向.設是問題(2.1)一種可行點，據(jù)此擬定相應有效集，其中求解相應子問題上述問題等價于其中設求出問題(2.4)全局極小點為是相應拉格朗日乘子。第二步，進行線性搜索擬定步長因子.假設，分兩種情形討論。(1)若是問題(2.1)可行點，即則令(2)若不是問題(2.1)可行點，則通過線性搜索求出下降最佳可行點。注意到目的函數(shù)是凸二次函數(shù)，那么這一點應當在可行域邊界上達到。因而只規(guī)定出滿足可行條件最大步長即可。當時，對于任意，均有和，此時，不受限制。當時，即第個約束是嚴格不等式約束，此時規(guī)定滿足，即注意到上式右端非正，故當時，上式恒成立。而當時，由上式可解得故有合并第(1)(2)可得.第三步，修正.當時，有效集不變，即.而當時，，故，因而在處增長了一種有效約束，即.第四步，考慮情形。此時是問題(2.3)全局極小點。若這是相應不等式約束拉格朗日乘子均為非負，則也是問題(2.1)全局極小點，迭代終結。否則，如果相應不等式約束拉格朗日乘子有負分量，那么需要重新尋找一種下降可行方向。設，當前規(guī)定一種下降可行方向，滿足且，為簡便計算，按下述方式選用：即另一方面，注意到是子問題(2.3)全局極小點，故有即其中從而，由(2.6)知于是有上式表白，由(2.6)擬定是一種下降可行方向。因而，令，則修正后子問題全局極小點必然是原問題一種下降可行方向。2.2.2有效集辦法算法環(huán)節(jié)通過上面分析和推導，咱們當前可寫出有效集辦法算法環(huán)節(jié)：（1）選用初值。給定初始可行點，令.（2）解子問題。擬定相應有效集.求解子問題得極小點和拉格朗日乘子向量.若轉環(huán)節(jié)（4）；否則，轉環(huán)節(jié)（3）。（3）檢查終結準則。計算拉格朗日乘子其中令若，則是全局極小點，停算。否則，若，則令，轉環(huán)節(jié)（2）。（4）擬定步長.令，其中令（5）若，則令；否則，若，則令，其中滿足（6）令，轉環(huán)節(jié)(1)。2.2.3有效集辦法應用（1）有效集法Matlab程序見附錄。（2）用有效集辦法求解下列二次規(guī)劃問題：解一方面擬定關于數(shù)據(jù)：運用Matlab計算可得成果如下：3總結與體會通過本次實驗，筆者對求解等式約束凸二次規(guī)劃問題拉格朗日辦法及普通約束條件下凸二次規(guī)劃問題有效集辦法有了較深結識和理解。感謝阮教師悉心教誨和指引，使得筆者對最優(yōu)化課程中理論推導、算法環(huán)節(jié)及編程都比較熟悉，對后來科研工作有較好指引和借鑒意義。4附錄4.1拉格朗日辦法matlab程序(1)拉格朗日算法函數(shù)%本程序用拉格朗日辦法求解燈飾約束條件二次規(guī)劃問題。function[x,lam,fval]=qlag(H,A,b,c)%功能：用拉格朗日辦法求解等式約束二次規(guī)劃：%minf(x)=0.5*x'Hx+c'x，s.t.Ax=b%輸入：H,c分別是目的函數(shù)矩陣和向量，A,b分別是約束條件中矩陣和向量%輸出：(x,lam)是KT點，fval是最優(yōu)值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=0.5*x'*H*x+c'*x；(2)拉格朗日算法求解等式約束凸二次規(guī)劃問題主程序：H=[2-20;-240;002];c=[001]';A=[111;2-11];b=[42]';[x,lam,fval]=qlag(H,A,b,c)4.2有效集辦法Matlab程序（1）有效集辦法函數(shù)%本程序重要合用于求解普通約束條件下凸二次規(guī)劃問題function[x,lamk,exitflag,output]=qpact(H,c,Ae,be,Ai,bi,x0)%功能：用有效集辦法解普通約束二次規(guī)劃問題%minf(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是初始點，H,c分別是目的函數(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是相應乘子向量；output是構造變量%輸出極小值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);fori=1:niifAi(i,:)*x>bi(i)+epsilonindex(i)=0;endend%算法主程序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=0.0;iflength(lamk)>ne[y,jk]=min(lamk(ne+1:length(lamk)));endify>=0exitflag=0;elseexitflag=1;fori=1:niifindex(i)&&(ne+sum(index(1:i)))==jkindex(i)=0;break;endendendk=k+1;elseexitflag=1;%求步長alpha=1.0;tm=1.0;fori=1:niif(index(i)==0)&&(Ai(i,:)*dk<0)tm1=(bi(i)-Ai(i,:)*x)/(Ai(i,:)*dk);iftm1<tmtm=tm1;ti=i;endendendalpha=min(alpha,tm);x=x+alpha*dk;%修正有效集iftm<1index(ti)=1;endendifexitflag==0break;endk=k+1;endoutput.fval=0.5*x'*H*x+c'*x;output.iter=k;（2）求解子問題函數(shù)%求解子問題function[x,lambda]=qsubp(H,c,Ae,be)ginvH=pinv(H);[m,n]=size(Ae);ifm>0rb=Ae*ginvH*c+be;