懲罰函數(shù)的外點法

1、2013-2014（1）專業(yè)課程實踐論文懲罰函數(shù)的外點法一、算法理論基本原理 設(shè)原目標函數(shù)為，在不等式約束條件下外點懲罰函數(shù)法求極小，外點法常采用如下形式的泛函： （1）由此，外點法所構(gòu)造的相應(yīng)的懲罰函數(shù)形式為： （2）式中，懲罰因子是一個遞增的正值數(shù)列，即： 懲罰項中： （3）由此可見，當?shù)c位于可行域內(nèi)滿足約束條件時，懲罰項為零，這時不管取多大，新目標函數(shù)就是原目標函數(shù)，亦即滿足約束條件時不受“懲罰”，此時求式（2）的無約束極小，等價于求原目標函數(shù)在已滿足全部約束條件下的極??；而當點位于可行域外不滿足約束條件時，懲罰項為正值，懲罰函數(shù)的值較原目標函數(shù)的值增大了，這就構(gòu)成對不滿足約束條件的

2、一種“懲罰”。由式（2）可知,每一次對罰函數(shù)求無約束的極值，其結(jié)果將隨該次所給定的罰因子值而異。在可行域外，離約束邊界越近的地方，約束函數(shù)的值越大，的值也就越小，懲罰項的作用也就越弱，隨著罰因子逐次調(diào)整增大，有增大懲罰項的趨勢，但一般說來泛函值下降得更快一些。此時盡管但泛函值亦趨于零，滿足式（3）。最后當，泛函值和懲罰項值均趨近于零。外點法在尋優(yōu)過程中，隨著罰因子的逐次調(diào)整增大，即取，所得的最優(yōu)點序列可以看作是以為參數(shù)的一條軌跡，當時，最優(yōu)點點列從可行域的外部一步一步地沿著這條軌跡接近可行域，所得的最優(yōu)點列逼近原問題的約束最優(yōu)點。這樣，將原約束最優(yōu)化問題轉(zhuǎn)換成為序列無約束最優(yōu)化問題。外點法就是

3、因從可行域的外部逼近最優(yōu)解而得名。外點懲罰函數(shù)法的具體迭代步驟如下：(1) 給定初始點，初始懲罰因子，迭代精度，遞增系數(shù), 維數(shù)。置。(2) 以為初始點，用無約束最優(yōu)化方法求解懲罰函數(shù)的極小點，即： (3) 檢驗是否滿足迭代終止條件：或 若不滿足，則進行第(4)步;否則轉(zhuǎn)第(5)步。 （4）令，置，返回進行第(2)步。 （5） 輸出最優(yōu)解：，停止迭代。 二、算法框圖給定, c ,k=0i=0求與Hessian矩陣輸出和YNi=i+1k=k+1YN結(jié)束三、算法程序clcm=zeros(1,50);a=zeros(1,50);b=zeros(1,50);f0=zeros(1,50);%a b為最優(yōu)

4、點坐標，f0為最優(yōu)點函數(shù)值，f1 f2最優(yōu)點梯度。syms x1 x2 e; %e為罰因子。m(1)=1;c=10;a(1)=0;b(1)=0; %c為遞增系數(shù)。賦初值。f=(x1-1)2+x22+e*(x2-1)2;f0(1)=1;fx1=diff(f,x1);fx2=diff(f,x2);fx1x1=diff(fx1,x1);fx1x2=diff(fx1,x2);fx2x1=diff(fx2,x1);fx2x2=diff(fx2,x2);%求偏導(dǎo)、海森元素。for k=1:100 %外點法e迭代循環(huán).x1=a(k);x2=b(k);e=m(k);for n=1:100 %梯度法求最優(yōu)值。f

5、1=subs(fx1); %求解梯度值和海森矩陣f2=subs(fx2);f11=subs(fx1x1);f12=subs(fx1x2);f21=subs(fx2x1);f22=subs(fx2x2);if(double(sqrt(f12+f22)=0.001) %最優(yōu)值收斂條件a(k+1)=double(x1);b(k+1)=double(x2);f0(k+1)=double(subs(f);break;elseX=x1 x2-inv(f11 f12;f21 f22)*f1 f2;x1=X(1,1);x2=X(2,1);endendif(double(sqrt(a(k+1)-a(k)2+(b(k+1)-b(k)2)=0.001)&(double(abs(f0(k+1)-f0(k)/f0(k)=0.001) %罰因子迭代收斂條件a(k+1) %輸出最優(yōu)點坐標，罰因子迭代次數(shù)，最優(yōu)值b(k+1)kf0(k+1)break;elsem(k+1)=c*m(k);endend四、算法實現(xiàn)例1.利用