外點(diǎn)法求約束最優(yōu)化問題

數(shù)學(xué)規(guī)劃課程設(shè)計(jì)題目外點(diǎn)法求約束最優(yōu)化問題姓名 學(xué)號 成績 摘要罰函數(shù)是應(yīng)用最廣泛的一種求解式的數(shù)值解法，基本思路是通過目標(biāo)函數(shù)加上懲罰項(xiàng)，將原約束非線性規(guī)劃問題轉(zhuǎn)化為求解一系列無約束的極值問題。（這種懲罰體現(xiàn)在求解過程中，對于企圖違反約束的那些迭代點(diǎn)，給予很大的目標(biāo)函數(shù)值，迫使這一系列無約束問題的極小值或者無限地向可行解（域）逼近，或者一直保持在可行集（域）內(nèi)移動(dòng)，直到收斂于原來約束問題的極小值點(diǎn)。）本文 外點(diǎn)法可用于求解不等式約束優(yōu)化問題，又可用于求解等式約束優(yōu)化問題，主要特點(diǎn)是懲罰函數(shù)定義在可行域的外部，從而在求解系列無約束優(yōu)化問題的過程中，從可行域外部逐漸逼近原約束優(yōu)化問題最優(yōu)解。關(guān)鍵詞：罰函數(shù)法、約束最優(yōu)化問題、外點(diǎn)法一、預(yù)備知識(基本理論)看下是否還有定理、定義等等，可以加一些外點(diǎn)懲罰函數(shù)法的一般形式考慮不等式約束優(yōu)化設(shè)計(jì)時(shí)：對minf(X), xeRn s.t.g(X)>0,(u=1,2,m)u構(gòu)造一般形式的外點(diǎn)懲罰函數(shù)為：P(X,rk)=f(X)+rk￡{minb,g(X)『uu=1其中：(1)當(dāng)滿足所有約束條件時(shí)懲罰項(xiàng)為0，即rk區(qū)｛minb,g(X)?二0uu=1(2)當(dāng)X違反某一約束條件，即g(X)v0時(shí)urk瓦｛minb,g(X)?=rk[g(X)1>0表明X在可行域外，懲罰項(xiàng)起作用，且若uuu=1X離開約束邊界越遠(yuǎn)，懲罰力度越大。這樣用懲罰的方法迫使迭代點(diǎn)回到可行域。(3)懲罰因子rk是一遞增的正數(shù)數(shù)列，即rovr1vr2<???<rk<…且limrk=g一般rk=1kTa考慮等式約束的優(yōu)化問題：minf(X), XeRns.t. .h(X)=0 (v=1,2,…，p)v構(gòu)造外點(diǎn)罰函數(shù)：P(X,rk)=f(X)+rk才bi(X)1vv=1同樣，若x滿足所有等式約束則懲罰項(xiàng)為0；若不能滿足，則rkfbl(X)T>0且vv=q隨著懲罰因子的增大而增大；綜合等式約束和不等式約束情況，可以得到一般約束優(yōu)化問題的外點(diǎn)罰函數(shù)公式為：p(X,rk)=f(X)+rkmin(0,g(X))2+fh(X)uv2>1u=1v=1實(shí)際計(jì)算中，因?yàn)閼土P因子rk不可能達(dá)到無窮大，故所得的最優(yōu)點(diǎn)也不可能收斂到原問題的最優(yōu)點(diǎn)，而是落在它的外面，顯然，這就不能嚴(yán)格滿足約束條件。為了克服外點(diǎn)懲罰函數(shù)法的這一缺點(diǎn)，對那些必須嚴(yán)格滿足的約束(如強(qiáng)度、剛度等性能約束)引入約束裕度5，即將這些約束邊界向可行域內(nèi)緊縮，移動(dòng)u一個(gè)微量，得到g(X)=g(X)-5>0 (u=1,2,…,m)u u u這樣用重新定義的約束函數(shù)來構(gòu)造懲罰函數(shù)，得到最優(yōu)設(shè)計(jì)方案。外點(diǎn)懲罰函數(shù)法的迭代步驟：1?給定初始點(diǎn)X0，初始懲罰因子r1，維數(shù)n迭代精度￡和遞增系數(shù)C>1；構(gòu)造外點(diǎn)懲罰函數(shù)P(Xk,rk)；選用無約束優(yōu)化方法來求解懲罰函數(shù)極小點(diǎn)，即P(Xk,rk)二minP(X,rk)檢驗(yàn)是否滿足迭代終止條件||Xk-Xk-^|<e或f(Xk)-f(Xk一1)<e若滿足轉(zhuǎn)6,若不滿足轉(zhuǎn)5；5.令Cr5.令CrkTrk+i，轉(zhuǎn)2；6.輸出最優(yōu)解，迭代終止。二、解問題1問題重述用外點(diǎn)法求解約束最優(yōu)化問題min(x26.輸出最優(yōu)解，迭代終止。二、解問題1問題重述用外點(diǎn)法求解約束最優(yōu)化問題min(x2+2x2)12s?t?x+x>1122問題求解解：構(gòu)造罰函數(shù)0(X,M)二x+x+MIminG,x+x-1)11212用解析法求解理=2x+2M[min(0,x+x-1)]dx 1 1 21=4x+2Mtnin(0,x+x-1)]Ox 2 1 22別帥o0OxOx12陽 I2x+2M(x+x—1)=0即，<1 1 2丨4x+2M(x+x—1)=0

2 1 2I 2Mx= I1 2+3MMx= 、2 2+3Mmin(X,M)的解為Ymin(X,M)的解為Y=K(2M K—I2+3MK——2+3M(21)2^33，min(x2+2x2)=2即解為：罰年+2x2）二-程序解法：利用MATLAB編寫程序如下：m=zeros(1,50);a=zeros(1,50);b二zeros(l,50);f0二zeros(l,50);%ab 為最優(yōu)點(diǎn)坐標(biāo)，fO為最優(yōu)點(diǎn)函數(shù)值，flf2最優(yōu)點(diǎn)梯度。symsx1x2e; %e 為罰因子。m(l)=l;c=lO;a(l)=O;b(l)=O; %c 為遞增系數(shù)。賦初值。f=x「2+2*x2辺+e*(1-x1-x2廠2;f0(1)=1;fxl=diff(f,'xl');fx2=diff(f,'x2');fxlxl=diff(fxl,'xl');fxlx2=diff(fxl,'x2');fx2xl=diff(fx2,'xl');fx2x2=diff(fx2,'x2');%求偏導(dǎo)、海森元素。fork=1:100 % 外點(diǎn)法e迭代循環(huán).xl=a(k);x2=b(k);e=m(k);forn=l:lOO % 梯度法求最優(yōu)值。fl=subs(fxl);%求解梯度值和海森矩陣f2=subs(fx2);fll=subs(fxlxl);fl2=subs(fxlx2);f2l=subs(fx2xl);f22=subs(fx2x2);if(double(sqrt(f「2+f2“2))<=0.001)%最優(yōu)值收斂條件a(k+1)=double(x1);b(k+1)=double(x2);f0(k+1)=double(subs(f));break;elseX=[x1x2]'-inv([f11f12;f21f22])*[f1f2]';x1=X(1,1);x2=X(2,1);endendif(double(sqrt((a(k+l)—a(k)廠2+(b(k+l)—b(k)廠2))<=0.001)&&(double(abs((f0(k+1)-f0(k))/f0(k)))<=0.001) %罰因子迭代收斂條件a(k+1) %輸出最優(yōu)點(diǎn)坐標(biāo)，罰因子迭代次數(shù)，最優(yōu)值b(k+1)kf0(k+1)break;elsem(k+1)=c*m(k);endend得結(jié)果：ans=0.6666ans=0.3333k=5ans=0.6666即min()的最優(yōu)結(jié)果為0.6666寫一些總結(jié)性內(nèi)容三、參考文獻(xiàn)范玉妹，徐爾，趙金玲，胡毅慶?數(shù)學(xué)規(guī)劃及其應(yīng)用[M].北京：冶金工業(yè)出版社，2009姜啟源，