惩罚函数的外点法

2013-2014（1）专业课程实践论文惩罚函数的外点法一、算法理论基本原理设原目标函数为(X)f，在不等式约束(X)0(1,2,,)ugum条件下外点惩罚函数法求极小，外点法常采用如下形式的泛函：2(X)min0,(X)uuGgg（1）由此，外点法所构造的相应的惩罚函数形式为：2(k)(k)1(X,)(X)min0,(X)muurfrg（2）式中，惩罚因子(k)r是一个递增的正值数列，即：(1)(2)(k)0rrr(k)limkr惩罚项中：(X),(X)0(X)(X)min0,(X)20,(X)0uuuuuugggggg若若（3）由此可见，当迭代点X位于可行域内满足约束条件时，惩罚项为零，这时不管(k)r取多大，新目标函数就是原目标函数，亦即满足约束条件时不受“惩罚”，此时求式（2）的无约束极小，等价于求原目标函数(X)f在已满足全部约束条件下的极小；而当点X位于可行域外不满足约束条件时，惩罚项2(k)1min0,(X)muurg为正值，惩罚函数的值较原目标函数的值增大了，这就构成对不满足约束条件的一种“惩罚”。由式（2）可知,每一次对罚函数(k)(X,)r求无约束的极值，其结果将随该次所给定的罚因子(k)r值而异。在可行域外，离约束边界越近的地方，约束函数(X)ug的值越大，(X)uGg的值也就越小，惩罚项的作用也就越弱，随着罚因子(k)r逐次调整增大，有增大惩罚项的趋势，但一般说来泛函值下降得更快一些。此时尽管(k)r但泛函值亦趋于零，满足式（3）。最后当k，(k)r，泛函值和惩罚项值均趋近于零。外点法在寻优过程中，随着罚因子的逐次调整增大，即取(1)(2)(k)0rrr，所得的最优点序列可以看作是以为参数的一条轨迹，当时，最优点点列*()X(1,2,)k从可行域的外部一步一步地沿着这条轨迹接近可行域，所得的最优点列*()Xk逼近原问题的约束最优点*X。这样，将原约束最优化问题转换成为序列无约束最优化问题。外点法就是因从可行域的外部逼近最优解而得名。外点惩罚函数法的具体迭代步骤如下：(1)给定初始点(0)XnR，初始惩罚因子(1)0r，迭代精度，递增系数1c,维数n。置1k。(2)以(1)Xk为初始点，用无约束最优化方法求解惩罚函数(k)(X,)r的极小点(k)X，即：(k)(k)(X,)min(X,)rr(3)检验是否满足迭代终止条件：(k)(k-1)XX()(1)()(X)(X)((X)1)kkkfff若或()(1)()()(X)(X)((X)1)(X)kkkkffff若若不满足，则进行第(4)步;否则转第(5)步。（4）令(k)(k+1)crr，置1kk，返回进行第(2)步。（5）输出最优解：(k)*XX，()*(X)(X)kff，停止迭代。二、算法框图给定)0(x,,)0(Mc,k=0i=0求)()(iX与Hessian矩阵)()(iXH||)(||)(iX)()(*)(ikXMX||)()(||)1()(*kkMXMX|)]([)]([)]([|)1(*)1(*)(*kkkMXfMXfMXf输出*X和)(*XfYN)()]([)(1)()()1(iiiiXXHXXi=i+1)()(*)0(kMXX)()1(kkcMMk=k+1YN结束三、算法程序clcm=zeros(1,50);a=zeros(1,50);b=zeros(1,50);f0=zeros(1,50);%ab为最优点坐标，f0为最优点函数值，f1f2最优点梯度。symsx1x2e;%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');%求偏导、海森元素。fork=1:100%外点法e迭代循环.x1=a(k);x2=b(k);e=m(k);forn=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=[x1x2]'-inv([f11f12;f21f22])*[f1f2]';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.利用外点法解非线性规划min2221)1()(xxxfdefts.01)(2xxg解：运行结果：例2.利用外点法解非线性规划min2221)(xxxfdefts.12()10gxxx解：运行结果：例3.利用外点法解非线性规划min2212()(1)deffxxxts.1()10gxx解：运行结果：例4.利用外点法解非线性规划min2212()(1)(1)deffxxxts.12()10gxxx解：运行结果：