外点法.docVIP

2012-2013（2）专业课程实践论文 外点法 姓名：洪祥 ，0818180115，R数学08-1班 姓名：毛勇 ，0818180117，R数学08-1班 姓名：秦基超，0818180121，R数学08-1班 一、算法理论 基本原理 设原目标函数为，在不等式约束条件下外点惩罚函数法求极小，外点法常采用如下形式的泛函： （1） 由此，外点法所构造的相应的惩罚函数形式为： （2） 式中，惩罚因子是一个递增的正值数列，即： 惩罚项中： （3） 由此可见，当迭代点位于可行域内满足约束条件时，惩罚项为零，这时不管取多大，新目标函数就是原目标函数，亦即满足约束条件时不受“惩罚”，此时求式（2）的无约束极小，等价于求原目标函数在已满足全部约束条件下的极小；而当点位于可行域外不满足约束条件时，惩罚项为正值，惩罚函数的值较原目标函数的值增大了，这就构成对不满足约束条件的一种“惩罚”。由式（2）可知,每一次对罚函数求无约束的极值，其结果将随该次所给定的罚因子值而异。在可行域外，离约束边界越近的地方，约束函数的值越大，的值也就越小，惩罚项的作用也就越弱，随着罚因子逐次调整增大，有增大惩罚项的趋势，但一般说来泛函值下降得更快一些。此时尽管但泛函值亦趋于零，满足式（3）。最后当，，，泛函值和惩罚项值均趋近于零。外点法在寻优过程中，随着罚因子的逐次调整增大，即取，所得的最优点序列可以看作是以为参数的一条轨迹，当时，最优点点列从可行域的外部一步一步地沿着这条轨迹接近可行域，所得的最优点列逼近原问题的约束最优点。这样，将原约束最优化问题转换成为序列无约束最优化问题。外点法就是因从可行域的外部逼近最优解而得名。 外点惩罚函数法的具体迭代步骤如下： 给定初始点，初始惩罚因子，迭代精度，递增系数, 维数n。置。 以为初始点，用无约束最优化方法求解惩罚函数的极小点，即： 检验是否满足迭代终止条件： 或 若不满足，则进行第(4)步;否则转第(5)步。 （4）令，置，返回进行第(2)步。 （5） 输出最优解：，，停止迭代。 二、算法框图 三、算法程序 clcm=zeros(1,50);a=zeros(1,50);b=zeros(1,50);f0=zeros(1,50);%a b为最优点坐标，f0为最优点函数值，f1 f2最优点梯度。syms x1 x2 e; %e为罚因子。m(1)=1;c=10;a(1)=0;b(1)=0; %c为递增系数。赋初值。f=(x1-1)^2+x2^2+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);%求偏导、海森元素。for k=1:100 %外点法e迭代循环.x1=a(k);x2=b(k);e=m(k);for n=1:100 %梯度法求最优值。f1=subs(fx1); %求解梯度值和海森矩阵f2=subs(fx2);f11=subs(fx1x1);f12=subs(fx1x2);f21=subs(fx2x1);f22=subs(fx2x2);if(double(sqrt(f1^2+f2^2))=0.001) %最优值收敛条件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) %输出最优点坐标，罚因子迭代次数，最优值b(k+1)kf0(k+1)break;elsem(k+1)=c*m(k);endend 四、算法实现 例1.解非线性规划 运行结果： 例2. 解非线性规划