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

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

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

3、因從可行域的外部逼近最優(yōu)解而得名。外點(diǎn)懲罰函數(shù)法的具體迭代步驟如下：(1) 給定初始點(diǎn)，初始懲罰因子，迭代精度，遞增系數(shù), 維數(shù)。置。(2) 以為初始點(diǎn)，用無約束最優(yōu)化方法求解懲罰函數(shù)的極小點(diǎn)，即： (3) 檢驗(yàn)是否滿足迭代終止條件：或 若不滿足，則進(jìn)行第(4)步;否則轉(zhuǎn)第(5)步。 （4）令，置，返回進(jìn)行第(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、點(diǎn)坐標(biāo)，f0為最優(yōu)點(diǎn)函數(shù)值，f1 f2最優(yōu)點(diǎn)梯度。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 %外點(diǎn)法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)點(diǎn)坐標(biāo)，罰因子迭代次數(shù)，最優(yōu)值b(k+1)kf0(k+1)break;elsem(k+1)=c*m(k);endend四、算法實(shí)現(xiàn)例1.利用