外点法求约束最优化问题

数学规划课程设计题目外点法求约束最优化问题姓名 学号 成绩 摘要罚函数是应用最广泛的一种求解式的数值解法，基本思路是通过目标函数加上惩罚项，将原约束非线性规划问题转化为求解一系列无约束的极值问题。（这种惩罚体现在求解过程中，对于企图违反约束的那些迭代点，给予很大的目标函数值，迫使这一系列无约束问题的极小值或者无限地向可行解（域）逼近，或者一直保持在可行集（域）内移动，直到收敛于原来约束问题的极小值点。）本文 外点法可用于求解不等式约束优化问题，又可用于求解等式约束优化问题，主要特点是惩罚函数定义在可行域的外部，从而在求解系列无约束优化问题的过程中，从可行域外部逐渐逼近原约束优化问题最优解。关键词：罚函数法、约束最优化问题、外点法一、预备知识(基本理论)看下是否还有定理、定义等等，可以加一些外点惩罚函数法的一般形式考虑不等式约束优化设计时：对minf(X), xeRn s.t.g(X)>0,(u=1,2,m)u构造一般形式的外点惩罚函数为：P(X,rk)=f(X)+rk£{minb,g(X)『uu=1其中：(1)当满足所有约束条件时惩罚项为0，即rk区｛minb,g(X)»二0uu=1(2)当X违反某一约束条件，即g(X)v0时urk瓦｛minb,g(X)»=rk[g(X)1>0表明X在可行域外，惩罚项起作用，且若uuu=1X离开约束边界越远，惩罚力度越大。这样用惩罚的方法迫使迭代点回到可行域。(3)惩罚因子rk是一递增的正数数列，即rovr1vr2<•••<rk<…且limrk=g一般rk=1kTa考虑等式约束的优化问题：minf(X), XeRns.t. .h(X)=0 (v=1,2,…，p)v构造外点罚函数：P(X,rk)=f(X)+rk才bi(X)1vv=1同样，若x满足所有等式约束则惩罚项为0；若不能满足，则rkfbl(X)T>0且vv=q随着惩罚因子的增大而增大；综合等式约束和不等式约束情况，可以得到一般约束优化问题的外点罚函数公式为：p(X,rk)=f(X)+rkmin(0,g(X))2+fh(X)uv2>1u=1v=1实际计算中，因为惩罚因子rk不可能达到无穷大，故所得的最优点也不可能收敛到原问题的最优点，而是落在它的外面，显然，这就不能严格满足约束条件。为了克服外点惩罚函数法的这一缺点，对那些必须严格满足的约束(如强度、刚度等性能约束)引入约束裕度5，即将这些约束边界向可行域内紧缩，移动u一个微量，得到g(X)=g(X)-5>0 (u=1,2,…,m)u u u这样用重新定义的约束函数来构造惩罚函数，得到最优设计方案。外点惩罚函数法的迭代步骤：1•给定初始点X0，初始惩罚因子r1，维数n迭代精度£和递增系数C>1；构造外点惩罚函数P(Xk,rk)；选用无约束优化方法来求解惩罚函数极小点，即P(Xk,rk)二minP(X,rk)检验是否满足迭代终止条件||Xk-Xk-^|<e或f(Xk)-f(Xk一1)<e若满足转6,若不满足转5；5.令Cr5.令CrkTrk+i，转2；6.输出最优解，迭代终止。二、解问题1问题重述用外点法求解约束最优化问题min(x26.输出最优解，迭代终止。二、解问题1问题重述用外点法求解约束最优化问题min(x2+2x2)12s・t・x+x>1122问题求解解：构造罚函数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 为最优点坐标，fO为最优点函数值，flf2最优点梯度。symsx1x2e; %e 为罚因子。m(l)=l;c=lO;a(l)=O;b(l)=O; %c 为递增系数。赋初值。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');%求偏导、海森元素。fork=1:100 % 外点法e迭代循环.xl=a(k);x2=b(k);e=m(k);forn=l:lOO % 梯度法求最优值。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)%最优值收敛条件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) %输出最优点坐标，罚因子迭代次数，最优值b(k+1)kf0(k+1)break;elsem(k+1)=c*m(k);endend得结果：ans=0.6666ans=0.3333k=5ans=0.6666即min()的最优结果为0.6666写一些总结性内容三、参考文献范玉妹，徐尔，赵金玲，胡毅庆•数学规划及其应用[M].北京：冶金工业出版社，2009姜启源，