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

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

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

1等式約束凸二次規(guī)劃解法1.1問題描述咱們考慮如下二次規(guī)劃問題(1.1)其中對(duì)稱正定，行滿秩，，。1.2拉格朗日辦法求解等式約束二次規(guī)劃問題1.2.1拉格朗日辦法推導(dǎo)一方面寫出拉格朗日函數(shù)：，(1.2)令，得到方程組將上述方程組寫成分塊矩陣形式：(1.3)咱們稱傷處方程組系數(shù)矩陣為拉格朗日矩陣。下面定理給出了線性方程組(1.1)有唯一解充分條件。定理1設(shè)對(duì)稱正定，行滿秩。若在問題(1.1)解處滿足二階充分條件，即則線性方程組(1.4)系數(shù)矩陣非奇異，即方程組（1.4）有唯一解。其中，方程組(1.4)為（1.1）相應(yīng)齊次方程組：（1.4）.下面，咱們來推導(dǎo)方程(1.3)求解公式。依照定理1，拉格朗日矩陣必然是非奇異，故可設(shè)其逆為.由恒等式可得于是由上述四個(gè)等式得到矩陣表達(dá)式因而，由(1.3)可得解得表達(dá)式其中，分別由(1.5),(1.6),(1.7)給出。下面給出和另一種等價(jià)表達(dá)式。設(shè)是問題(1.1)任一可行點(diǎn)，即滿足。而在此點(diǎn)處目的函數(shù)梯度為，運(yùn)用和，可將(1.8)改寫為1.2.2拉格朗日辦法應(yīng)用（1）拉格朗日辦法Matlab程序見附錄。（2）運(yùn)用拉格朗日辦法求解下列問題：解容易寫出運(yùn)用Matlab程序求解該問題可以成果如下：2普通凸二次規(guī)劃問題解法2.1問題描述考慮普通二次規(guī)劃其中是階對(duì)稱陣。記，下面定理給出了問題(2.1)一種最優(yōu)性充要條件。定理2是二次規(guī)劃問題(2.1)局部極小點(diǎn)當(dāng)且僅當(dāng)（1）存在，使得(2)記則對(duì)于任意，均有.容易發(fā)現(xiàn)，問題(2.1)是凸二次規(guī)劃充要條件是半正定。此時(shí)，定理2第二某些自然滿足。注意到凸優(yōu)化問題局部極小點(diǎn)也是全局極小點(diǎn)性質(zhì)，咱們有下面定理：定理3是凸二次規(guī)劃全局極小點(diǎn)充要條件是滿足條件，即存在，使得2.2有效集法求解普通凸二次規(guī)劃問題2.2.1有效集辦法理論推導(dǎo)一方面引入下面定理，它是有效集辦法理論基本。定理4設(shè)是普通凸二次規(guī)劃問題全局極小點(diǎn)，且在處有效集為，則也是下列等式約束凸二次規(guī)劃全局極小點(diǎn)。從上述定理可以發(fā)現(xiàn)，有效集辦法最大難點(diǎn)是事先普通不懂得有效集，因而只有想辦法構(gòu)造一種集合序列去逼近它，即從初始點(diǎn)出發(fā)，計(jì)算有效集，解相應(yīng)等式約束子問題。重復(fù)這一做法，得到有效集序列使之，以獲得原問題最優(yōu)解?；谏鲜龆ɡ?，咱們分4步來簡(jiǎn)介有效集辦法算法原理和實(shí)行環(huán)節(jié)。第一步，形成子問題并求出搜索方向.設(shè)是問題(2.1)一種可行點(diǎn)，據(jù)此擬定相應(yīng)有效集，其中求解相應(yīng)子問題上述問題等價(jià)于其中設(shè)求出問題(2.4)全局極小點(diǎn)為是相應(yīng)拉格朗日乘子。第二步，進(jìn)行線性搜索擬定步長(zhǎng)因子.假設(shè)，分兩種情形討論。(1)若是問題(2.1)可行點(diǎn)，即則令(2)若不是問題(2.1)可行點(diǎn)，則通過線性搜索求出下降最佳可行點(diǎn)。注意到目的函數(shù)是凸二次函數(shù)，那么這一點(diǎn)應(yīng)當(dāng)在可行域邊界上達(dá)到。因而只規(guī)定出滿足可行條件最大步長(zhǎng)即可。當(dāng)時(shí)，對(duì)于任意，均有和，此時(shí)，不受限制。當(dāng)時(shí)，即第個(gè)約束是嚴(yán)格不等式約束，此時(shí)規(guī)定滿足，即注意到上式右端非正，故當(dāng)時(shí)，上式恒成立。而當(dāng)時(shí)，由上式可解得故有合并第(1)(2)可得.第三步，修正.當(dāng)時(shí)，有效集不變，即.而當(dāng)時(shí)，，故，因而在處增長(zhǎng)了一種有效約束，即.第四步，考慮情形。此時(shí)是問題(2.3)全局極小點(diǎn)。若這是相應(yīng)不等式約束拉格朗日乘子均為非負(fù)，則也是問題(2.1)全局極小點(diǎn)，迭代終結(jié)。否則，如果相應(yīng)不等式約束拉格朗日乘子有負(fù)分量，那么需要重新尋找一種下降可行方向。設(shè)，當(dāng)前規(guī)定一種下降可行方向，滿足且，為簡(jiǎn)便計(jì)算，按下述方式選用：即另一方面，注意到是子問題(2.3)全局極小點(diǎn)，故有即其中從而，由(2.6)知于是有上式表白，由(2.6)擬定是一種下降可行方向。因而，令，則修正后子問題全局極小點(diǎn)必然是原問題一種下降可行方向。2.2.2有效集辦法算法環(huán)節(jié)通過上面分析和推導(dǎo)，咱們當(dāng)前可寫出有效集辦法算法環(huán)節(jié)：（1）選用初值。給定初始可行點(diǎn)，令.（2）解子問題。擬定相應(yīng)有效集.求解子問題得極小點(diǎn)和拉格朗日乘子向量.若轉(zhuǎn)環(huán)節(jié)（4）；否則，轉(zhuǎn)環(huán)節(jié)（3）。（3）檢查終結(jié)準(zhǔn)則。計(jì)算拉格朗日乘子其中令若，則是全局極小點(diǎn)，停算。否則，若，則令，轉(zhuǎn)環(huán)節(jié)（2）。（4）擬定步長(zhǎng).令，其中令（5）若，則令；否則，若，則令，其中滿足（6）令，轉(zhuǎn)環(huán)節(jié)(1)。2.2.3有效集辦法應(yīng)用（1）有效集法Matlab程序見附錄。（2）用有效集辦法求解下列二次規(guī)劃問題：解一方面擬定關(guān)于數(shù)據(jù)：運(yùn)用Matlab計(jì)算可得成果如下：3總結(jié)與體會(huì)通過本次實(shí)驗(yàn)，筆者對(duì)求解等式約束凸二次規(guī)劃問題拉格朗日辦法及普通約束條件下凸二次規(guī)劃問題有效集辦法有了較深結(jié)識(shí)和理解。感謝阮教師悉心教誨和指引，使得筆者對(duì)最優(yōu)化課程中理論推導(dǎo)、算法環(huán)節(jié)及編程都比較熟悉，對(duì)后來科研工作有較好指引和借鑒意義。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點(diǎn)，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是初始點(diǎn)，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是相應(yīng)乘子向量；output是構(gòu)造變量%輸出極小值f(x),迭代次數(shù)k等信息，exitflag是算法終結(jié)類型%初始化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;%求步長(zhǎng)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;