第五章 约束优化方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 约束优化方法,2026/1/16 周五,1,2),约束随机方向法,;,3),复合形法,;,5),罚函数法,;,约束优化直接解法,约束优化间接解法,（,1,）,内点罚函数法,;,（,2,）,外点罚函数法,;,1),约束坐标轮换法；,4),可行方向法,;,（自学）,第五章 约束优化方法,根据求解方式的不同，可分为,直接解法和间接解法,两类。,机械优化设计的问题，大多属于约束优化设计问题，其数学模型为：,直接解法,是,将迭代点限制在可行域内,(,可行性,),，步步降低目标函数值,(,下降性,),，直至到达最优点，,求出问题的约束最优解。,间接解法,是将约束优化问题转化为一系列无约束优化问题来解的一种方法。,常用方法有,:,约束坐标轮换法,约束随机方向法,复合形法,可行方向法,线性逼近法等,.,常用方法有,:,罚函数法,拉格朗日乘子法等,.,第五章 约束优化方法,直接解法,是在满足不等式约束的可行设计区域内直接求,出问题的约束最优解。,属于直接解法的有：随机实验法、,随机方向搜索法、,复合形法,、可行方向法等。,间接解法,是将约束优化问题转化为一系列无约束优化问题来,解的一种方法。,由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。,间接解法中具有代表性的是,惩罚函数法,。,直接解法的基本思想：,在由,m,个不等式约束条件,g,u,(,x,)0,所确定的可行域,内，选择一个初始点,x,(0),，然后确定一个可行搜索方向,S,，且以适当的步长沿,S,方向进行搜索，取得一个目标函数有所改善的可行的新点,x,(1),，即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算：,x,(,k,+1),x,(,k,),+,(,k,),S,(,k,),(k=0,1,2,),逐步趋向最优解，,直到满足终止准则才停止迭代。,直接解法的原理简单，方法实用，其特点是：,1,）由于整个过程在可行域内进行，因此，迭代计算不论,何时终止，都可以获得比初始点好的设计点。,2,）若目标函数为凸函数，可行域为凸集，则可获得全域,最优解，否则，可能存在多个局部最优解，当选择的初始,点不同，而搜索到不同的局部最优解。,3,）要求可行域有界的非空集。,直接解法的特点：,a),可行域是凸集；,b),可行域是非凸集,间接解法的基本思路：,将约束函数进行特殊的加权处理后，和目标函数结合起来，,构成一个新的目标函数，,即将原约束优化问题转化为一个,或一系列的无约束优化问题,。,新目标函数,加权因子,然后对新目标函数进行无约束极小化计算。,间接解法的基本思路,2026/1/16 周五,9,第二节 约束坐标轮换法,一,.,基本思路,可取定步长、加速步长和收缩步长,但不能取最优步长,;,1.,依次沿各坐标轴方向,-e,1,e,2,e,n,方向搜索,;,2.,将迭代点限制在可行域内,.,对每一迭代点均需进行可行性和下降性检查,.,2026/1/16 周五,10,二,.,迭代步骤,2026/1/16 周五,11,三,.,存在问题,有时会出现死点,导致输出,“,伪最优点,”,.,*,为辨别真伪,要用,K-T,条件,进行检查,.,3.1,随机方向法的基本思路,1,、在可行域内选择一个初始点；,2,、利用随机数的概率特性，产生若干个随机方向；,3,、从中选一个能使目标函数值下降最快的方向作为搜索方向,d,；,4,、从初始点,x0,出发，沿,d,方向以一定步长进行搜索，得到新点,X,，新点,X,应满足约束条件且,f(x)f(x0),，至此完成一次迭代。,基本思路如图所示。,随机方向法程序设计简单，搜索速度快，是解决小型机械优,化问题的十分有效的算法。,第三节 约束随机方向法,坐标轮换法有时会输出,“,伪最优点,”,用随机方向法可克服这一缺点,.,随机方向法的基本思路,3.2,随机方向的构成,1.,用,RND(X),产生,n,个随机数,2.,将,(0,1),中的随机数,变换到,(-1,1),中去,(,归一化,),;,3.,构成随机方向,变换得,:,于是,例,:,对于三维问题,第二节 约束随机方向法,从,k,个随机方向中，选取一个较好的方向。,3.3,可行搜索方向的产生,第二节 约束随机方向法,1.,检验,k,个随机点是否为可行点，除去非可行点，计算余下的可行点的目标函数值，比较其大小，选出目标函数最小的点,X,L,。,2.,比较,X,L,和,X,0,两点的目标函数值，,若,f(X,L,)f(X,0,),，则步长,0,缩小，转步骤,1,）重新计算，直至,f(X,L,)f(X,0,),为止。,如果,0,缩小到很小，仍然找不到一个,X,L,，使,f(X,L,)f(X,0,),则说明,X,0,是一个局部极小点，此时可更换初始点，转步骤,1,）。,产生可行搜索方向的条件为：,则可行搜索方向为：,3.3,可行搜索方向的产生,第二节 约束随机方向法,3.4,初始点的选择,随机方向法的初始点,x0,必须是一个可行点，既满足全部不等式约束条件。,初始点可以通过随机选择的方法产生。,1,）输入设计变量的下限值和上限值，即,2,）在区间（,0,，,1,）内产生,n,个伪随机数,3,）计算随机点,x,的各分量,第二节 约束随机方向法,4,）判别随机点,x,是否可行，若随机点可行，用,x,代替,x0,为,初始点；若非可行点，转到步骤,2,）重新产生随机点，只,到可行为止。,3.5.,迭代过程,在初始点处产生一随机方向，若该方向适用、可行，则以定步长前进；,若该方向不适用、可行，则产生另一方向；,若在某处产生的方向足够多,(50-100),，仍无一适用、可行，则采用收缩步长；,若步长小于预先给定的误差限则终止迭代。,第二节 约束随机方向法,3.6.,流程图,X,0,=X,F,0,=F,给定内点,X,0,0,m,=,0,F,0,=F(X,0,),F=F,（,X,）,j=1,K=K+1,是,K=0,j=0,产生随机方向,=,0.5,否,FF,0,j=0,K=0,dir0=rand(N,1);,x0=xl+dir0.*xu;,gx=feval(g_cons,x0);,%feval(),执行由串指定的函数,end,%=,fx0=feval(f,x0);,xk=x0+1;,fxk=feval(f,xk);,xmin=x0;,alpha=1.3;,k1=0;,flag1=1;,while norm(xk-x0)TolX|abs(fxk-fx0)TolFun,k1=k1+1;,x0=xmin;,fx0=feval(f,x0);,3.7,随机方向法的,Matlab,程序,dir0=rand(N,1)*2-1;,dir0=dir0/norm(dir0);,xk=x0+alpha*dir0;,gx=feval(g_cons,xk);,if max(gx)0,alpha=alpha*0.7;,else,fxk=feval(f,xk);,if fxkfx0,if norm(xk-x0)TolX&abs(fxk-fx0)TolFun,break,else,xmin=xk;,alpha=1.3;,end,x0,xk,fx0,fxk,else,alpha=-alpha;,end,end,end,x1=x0;,fx1=feval(f,x1);,gx=feval(g_cons,x1);,k1,end,例,:,求,3.7,随机方向法的,Matlab,程序,function opt_random1_test1,%opt_random1_test1.m,clc;,clear all;,f=inline(x(1)2+x(2),x);,xl=-3-3;,xu=3 3;,TolX=1e-8;,TolFun=1e-8;,x1,fx1,g=,opt_random1,(f,fun_cons,xl,xu,TolX,TolFun),function g=fun_cons(x),g=x(1)2+x(2)2-9,x(1)+x(2)-1;,计算结果：,x1=-0.0076-3.0000,f=-2.9999,g=-0.0000-4.0076,第四节 复合形法,复合形法是求解约束优化问题的一种重要的直接解法。,基本思路：,1,、在可行域内构造一个具有,k,个顶点的初始复合形；,2,、对该复合形各顶点的目标函数值进行比较，找到目标函数最大的顶点（最坏点）；,3,、然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形的形状每改变一次，就向最优点移动一步，直至逼近最优点。,由于复合形的形状不必保持规则的图形，对目标函数和约束函数无特殊要求，因此这种方法适应性强，在机械优化设计中应用广泛。,4.1,基本思路,在可行域内选取若干初始点并以之为顶点构成一个多面体,(,复合形,),然后比较各顶点的函数值,去掉最坏点,代之以好的新点,并构成新的复合形,以逼近最优点,.,第四节 复合形法,4.2,初始复合形生成的方法：,（,1,）由设计者决定,k,个可行点，构成初始复合形。设计变量少时适用。,（,2,）由设计者选定一个可行点，其余的,k-1,个可形点用随机法,产生。,（,3,）由计算机自动生成初始复合形的所有顶点。,第四节 复合形法,*,初始复合形的构成,*,复合形的移动和收缩,4.2.1,初始复合形的构成,(1),复合形顶点数,K,的选择,建议,:,小取大值,大取小值,(2),初始复合形顶点的确定,用试凑方法产生,-,适于低维情况,;,用随机方法产生,4.2,初始复合形生成的方法：,第四节 复合形法,将非可行点调入可行域内,K,个顶点中要求无一在可行域内。重新产生。,K,个顶点中有可行点,，,重新排列，将可行点依次排在前面，如有,q,个顶点,X,(1),、,X,(2),、,X,(q),是可行点，其它,K-q,个为非可行点。对,X,(q+1),，将其调入可行域的步骤是：,先用随机函数产生,个随机数,然后变换到预定的区间,中去,.,用随机方法产生,K,个顶点,(1),计算,q,个点集的中心,X,(,s,),；,(2),将第,q+1,点朝着点,X,(s),的方向移动，按下式产生新的,X,(q+1),，即,若仍不可行，则重复此步骤，直至进入可行域为止。,按照这个方法，同样使,X,(q+2),、,X,(q+3),、,X,(K),都变为可行点，这,K,个点就构成了初始复合形。,有两种基本运算,:,1),映射,-,在坏点的对侧试探新点,:,先计算除最坏点外各顶点的几何中心,然后再作映射计算,.,2),收缩,-,保证映射点的,“,可行,”,与,“,下降,”,X,1,为最坏点,-,映射系数,常取,若发现映射点不适用、可行,则将 减半后重新映射,.,4.3,复合形法的搜索方法,4.4,复合形法的迭代步骤,(1),构造初始复合形；,(2),计算各顶点的函数值,F(X,(j),),，,j=1,2,.,K,。,选出好点,X,(L),和坏点,X,(H),；,(3),计算坏点外的其余各顶点的中心点,X,(0),。,(4),计算映射点,X,(R),检查,X,(R),是否在可行域内。若,X,(R),为非可行点，将映射系数减半后再按上式改变映射点，直到,X,(R),进入可行域内为止。,(5),构造新的复合形,计算映射点的函数值,F(,X,(R),),，并与坏点的函数值,F(X,(H),),比较，可能存在两种情况：,1,）映射点优于坏点,F(X,(R),)F(X,(H),),这种情况由于映射点过远引起的，减半映射系数，若有,F(X,(R),)F(X,(H),),，这又转化为第一种情况。,4.5,判断终止条件,1),各顶点与好点函数值之差的均方根,值小于误差限，即,2,）,各顶点与好点的函数值之差的平方和,小于误差限，即,3,）各,顶点与好点函数值差的绝对值之和,小于误差限，即,如果不满足终止迭代条件，则返回步骤,2,继续进行下一次迭代；否则，可将最后复合形的好点,X,(L),及其函数值,F(X,(L),),作为最优解输出。,比较复合形各顶点的函数值，找出好点,X,L,，坏点,X,H,X,H,=X,R,=0,.,5,找出次坏点,X,SH,，,X,H,=X,SH,满足终止条件？,X*=X,L,F*=F(X,L,),结 束,4.6,流程图,是,否,给定,K,，,，,，,，,a,i,b,i,i=1,2,n,产生初始复合形顶点,X,j,j=1,2,K,计算复合形各顶点的函数值,F(X,j,),j=1,2,K,是,是,是,否,否,否,X,R,D,F,R,0,x0=xl+rand(N,1).*xu;,gx=feval(g_cons,x0);,end,x1,fx=gen_complex(x0,k,f,g_cons);,flag1=1;flag2=1;flag3=1;,k1=0,fx,x1,fprintf(,此处暂停，请按下任意键继续,n),pause,while k1MaxIter,flag1=1;flag2=1;flag3=1;,k1=k1+1,fx,I=sort(fx);,for i=1:k,x2(:,i)=x1(:,I(i);,end,x1=x2;,fmax1=fx(k);,imax1=I(k);,fmin=fx(1);,imin=I(1);,fmax2=fx(k-1);,imax2=I(k-1);,%,计算形心,xc=zeros(N,1);,for i=1:k,xc=xc+x1(:,i);,end,xc=xc-x1(:,imax1);,xc=xc/(k-1);,gxc=feval(g_cons,xc);,alpha=1.31;,%,反射,xr=xc+alpha*(xc-x1(:,imax1);,gxr=feval(g_cons,xr),if max(gxr)0,fxr=feval(f,xr);,if fxrfmax1,fprintf(,反射成功,n),fmax1,fxr,fmax1=fxr;,fx(imax1)=fxr;,x1(:,imax1)=xr;,flag1=-1;,else,%,反射失败,flgg1=1;,end,else,%,反射失败,flag1=1;,end,gama=0.7;,if flag1=-1,fprintf(,延伸,n),xe=xr+gama*(xr-xc);,gxe=feval(g_cons,xe),if max(gxe)0,fxe=feval(f,xe);,if fxefmax1,fprintf(,延伸成功,n),fxe,fmax1,fx(imax1)=fxe;,fmax1=fxe;,x1(:,imax1)=xe;,flag2=-1;,else,%,延伸失败,flag2=1;,end,else,%,延伸失败,flag2=1;,end,end,beta=0.7;,if flag1=-1&flag2=-1,fprintf(,收缩,n),xk=x1(:,imax1)+beta*(xc-x1(:,imax1);,gxk=feval(g_cons,xk),if max(gxk)0,fxk=feval(f,xk);,if fxkfmax1,fprintf(,收缩成功,n),fxk,fmax1,fmax1=fxk;,fx(imax1)=fxk;,x1(:,imax1)=xk;,flag3=-1;,else,%,收缩失败,flag3=1;,end,else,%,收缩失败,flag3=1;,end,end,if flag1,=-1&flag2,=-1&flag3,=-1,fprintf(flag1,flag2,flag3n%d%d%dn,flag1,flag2,flag3),fprintf(,重新生成单纯形,n),fx,I=sort(fx);,imin=I(1);,x0=x1(:,imin);,x1,fx=gen_complex(x0,k,f,g_cons),end,end,xo=x1(:,imin);,fo=feval(f,xo);,go=feval(g_cons,xo);,k1,function,x1,fx=gen_complex(x0,k,f,g_cons),N=length(x0);,M=size(g_cons);,M=length(M(:,1);,x1(:,1)=x0;,fx(1)=feval(f,x0);,a=1.3;,s=rand(N,k)*2-ones(N,k);,s=s/norm(s);,k2=1;,while,k2k,x0=x1(:,1)+a*s(:,k2);,gx=feval(g_cons,x0);,if,max(gx)0,k2=k2+1;,x1(:,k2)=x0;,fx(k2)=feval(f,x0);,else,a=0.7*a;,end,end,4.7,应用复合形法,Matlab,程序求约束优化问题的最优解,function opt_complex_test1,%opt_complex_test1.m,clc;,clear all;,f=inline(x(1)-5)2+4*(x(2)-6)2,x);,TolX=1e-6;,TolFun=1e-6;,x0=8,14;,xl=2 2;,xu=7 9;,MaxIter=65;,options=optimset(LargeScale,off);,xo,fxo,g=,opt_complex,(f,fun_cons,x0,xl,xu,TolX,TolFun,MaxIter),%,用,复合形法,求目标函数最优解和最优值,xo,fo=,fmincon,(f,x0,xl,xu,fun_cons,options),%,通过使用,函数,fmincon,解决有约束的非线性优化问题,function c ceq=,fun_cons,(x),c=64-x(1)2-x(2)2,-x(1)+x(2)-10,x(1)-10;,ceq=;,应用,opt_complex,函数计算结果,:,xo=5.2186 6.0635,fo=0.0639,g=-0.0000,-9.1551,-4.7814,应用,fmincon,函数计算结果：,xo=5.2186 6.0635,fo=0.0639,。,MATLAB,中,options=,optimset(LargeScale,off,Simplex,on,display,iter),这是对,寻优函数搜索方式,的设定，,LargeScale,指大规模搜索，,off,表示在规模搜索模式关闭，,Simplex,指单纯形算法，,on,表示该算法打开。,display,指结果方式，有四种,off|iter|notify|final,，,iter,是指中间结果每步都显示，一般选择,final,显示最终结果。,在,MATLAB,运行窗口直接输入,optimset,可显示所有可设置的参数及对应的可选择的参数值。,约束优化问题的间接解法,约束优化问题的间接解法是将约束优化问题转化为一系列无约束优化问题来进行求解的方法。,约束优化问题的间接解法除拉格朗日乘子法外，常用的方法还有,罚函数法及增广乘子法,。,虽然约束优化问题的间接解法可利用无约束优化问题的求解方法进行求解，但由于增加了拉格朗日乘子或罚因子，其求解过程与常规无约束优化问题有所不同。,4.1,概述,1.,基本思想,将约束问题,转化成,无约束问题,求解,惩罚函数,可调参数,*,构造惩罚函数,的基本要求,:,惩罚项用约束条件构造,;,到达最优点时,惩罚项的值为,0,;,当约束不满足或未到达最优点时,惩罚项,的值,大于,0,.,第四节 惩罚函数法,惩罚函数法是一种很广泛、很有效的间接解法。它的基本原理是将约束优化问题中的不等式和等式约束函数经加权后，和原目标函数结合为新的目标函数,惩罚函数。,将约束优化问题转换为无约束优化问题。求解无约束优化问题的极小值，从而得到原约束优化问题的最优解。,加权转化项,第四节 惩罚函数法,惩罚函数法,是按一定的法则改变加权因子的值，构成一系列的无约束优化问题，求一系列无约束最优解，并不断地逼近原约束优化问题的最优解。因此,又称序列无约束极小化方法。常称,SUMT,方法。,根据它们在惩罚函数中的作用，分别称障碍项和惩罚,项。,障碍项的作用是当迭代点在可行域内时，在迭代过程中将阻止迭代点越出可形域。,惩罚项的作用是当迭代点在非可行域或不满足等式约束条件时，在迭代过程中将迫使迭代点逼近约束边界或等式约束曲面。,4.2,分类,内点法,-,将迭代点限制在可行域内,;,外点法,-,迭代点一般在可行域外,;,混合法,-,将外点法和内点法结合起来解,GP,型问题,.,按照惩罚函数在优化过程中迭代点是否可行，分为：内点法、外点法 及 混合法。,第四节 惩罚函数法,4.3 SUMT,内点法,(,内点惩罚函数法、障碍函数法,),1.,惩罚函数的构造,原问题,:,s.t.,可取,式中,1),当,X,趋于,D,的边界时,中间函数,B(X),趋于无穷大,故又称为,障碍,(,围墙,),函数,;,r,称为罚因子,，在逐次迭代中越来越小,4.3.1,基本思想：,内点法将新目标函数,(x,r),构筑在,可行域,D,内,，随着惩罚因子,r,(k),的不断,递减,，生成一系列新目标函数,(x,k,r,(k),),，在可行域,内,逐步迭代，产生的极值点,x,k,*(r,(k),),序列从可行域,内,部趋向原目标函数的约束最优点,x*,。,例,：求下述约束优化问题的最优点。,min.f(x)=x x R,1,s.t g(x)=1-x 0,X,1,*,X,2,*,X,*,4.3 SUMT,内点法,(,内点惩罚函数法、障碍函数法,),4.3.2,惩罚函数的形式,：,其中：惩罚（加权）因子,罚因子降低系数（罚因子递减速率）,c,：,0 c 1,4.3 SUMT,内点法,(,内点惩罚函数法、障碍函数法,),4.3.3,迭代步骤：,选取合适的初始点,x,(0),，以及,r,(0),、,c,、,计算精度,1,、,2,，令,k=0,；,2.,构造惩罚（新目标）函数；,3.,调用无约束优化方法，求新目标函数的最优解,x,k,*,和,(x,k,r,(k),),；,4.,判断是否收敛：运用终止准则,前后两次无约束极小点之间的距离,相邻两点罚函数的相对误差,若均满足，停止迭代，有约束优化问题的最优点为,x*=x,k,*,；,若有一个准则不满足，则令,并转入第,3,步，继续计算。,4.3 SUMT,内点法,(,内点惩罚函数法、障碍函数法,),下面介绍内点法中的初始点、惩罚因子初值及其缩减系数的选取和收敛条件的确定。,1.,初始点的选取,初始点应选离约束边界较远的可行点。,程序设计时，一般，考虑具有人工输入和计算机自动生成可行初始点的两种功能。,4.3 SUMT,内点法,1.,初始点,x,(0),的选择方法,人工估算，需要校核可行性；计算机随机产生，也需校核可行性；搜索方法：,任意给出一个初始点；,判断其可行性，若违反了,S,个约束，求出不满足约束中的最大值：,应用优化方法减少违反约束：,以求得的设计点作为新初始点，继续其判断可行性，若仍有不满足的约束，则重复上述过程，直至初始点可行。,4.3 SUMT,内点法,(,内点惩罚函数法、障碍函数法,),2.,惩罚因子的初值的选取,惩罚因子的初值选取应适当，否则会影响迭代计算的正常进行。太大会影响迭代次数，太小会使惩罚函数的形态变坏，难以收敛到极值点。,1,）取,r,0,=1,，根据试算的结果，再决定增加或减少,r,0,值。,2,）按经验公式,计算,r,0,值。这样选取的,r,0,，可以是,惩罚函数中的障碍项和原目标函数的值大致相等，不会因障碍项的值太大则起支配作用，也不会因障碍项的值太小而被忽略掉,。,3.,惩罚因子的缩减系数,c,的选取,在构造序列惩罚函数时，惩罚因子,r,是一个逐次递减到,0,的数列，相邻两次迭代的惩罚因子的关系为：,惩罚因子的缩减系数,通常的取值范围：,0.1-0.7,之间,。,罚因子,为使,与原问题同解,应使,*,对于一个,求解一个无约束优化问题,.,前一问题的结果为后一问题的初值,故为,系列无约束极小化方法,(Sequential Unconstrained Minimization Technique).,4.,收敛条件,前后两次无约束极小点之间的距离,相邻两点罚函数的相对误差,5.,几个参数选择小结：,惩罚因子初始值,r,(0),的选择：,过大、过小均不好，,建议考虑选择：,2.,降低系数,c,的选择：,c,的典型值为,0.1,0.7,。建议先试算。,3.,初始点,x,(0),的选择,：,要求：,在可行域内；,不要离约束边界太近。,方法：,人工估算，需要校核可行性；,计算机随机产生，也需校核可行性。,4.3 SUMT,内点法,(,内点惩罚函数法、障碍函数法,),6.,方法评价：,用于目标函数比较复杂，或在可行域外无定义的场合下；,由于优化过程是在可行域内逐步改进设计方案，故在解决工程问题时，只要满足工程要求，即使未达最优解，接近的过程解也是可行的；,初始点和序列极值点均需严格满足所有约束条件；,不能解决等式约束问题,。,4.3 SUMT,内点法,(,内点惩罚函数法、障碍函数法,),输出,X*,，,F*=F,（,X*,）,结束,是,4.3 SUMT,内点罚函数法迭代步骤,用无约束方法求,的极小点,X*,输入,X,0,，,r,0,c,否,k=k+1,X,k,=X*,，,r,k,=cr,k,K=0,X,k,=X,0,例,:,解,:,惩罚函数,在,D,内,对于固定,的,令,得,r,(k),x,*,f(x,*,),B(x,*,),1/2,2,1,1,1.5,1/10,1.4472,0.7236,2.2361,0.9472,1/50,1.2,0.6,5,0.7,1/6250,1.0179,0.5089,55.9017,0.5179,0,1,0.5,0.5,4.3 SUMT,内点法,(,内点惩罚函数法、障碍函数法,),r,(k),x,*,f(x,*,),B(x,*,),1/2,2,1,1,1.5,1/10,1.4472,0.7236,2.2361,0.9472,1/50,1.2,0.6,5,0.7,1/6250,1.0179,0.5089,55.9017,0.5179,0,1,0.5,0.5,内点法是将惩罚因数定义于可行域内，而外点法与内点法不同，是将惩罚项函数定义于可行区域的外部。序列迭代点从可行域外部逐渐逼近约束边界上的最优点。,4.4,外点惩罚函数法（衰减函数法）,外点法可以用来求解含不等式和等式约束的优化问题。,对于约束优化问题,惩罚因子，它是由小到大。,惩罚项,由惩罚项可知，当迭代点不可行时，惩罚项的值大于零。,当迭代点离约束边界越远时，惩罚项愈大，这可看成是对迭代点不满足约束条件的一种惩罚。,转化后的外点惩罚函数的形式为：,1.,基本思想：,外点法将新目标函数,(x,r),构筑在,可行域,D,外,，随着惩罚因子,r,(k),的不断,递增,，生成一系列新目标函数,(x,k,r,(k),),，在可行域,外,逐步迭代，产生的极值点,x,k,*(r,(k),),序列从可行域,外,部趋向原目标函数的约束最优点,x*,。,例：求下述约束优化问题的最优点。,min.f(x)=x x R,1,s.t g(x)=1-x 0,新目标函数：,4,4.4,外点惩罚函数法（衰减函数法）,惩罚项是罚因子和中间函数的乘积；,内点法中随着设计变量移向约束函数的边界，中间函数值不断增加，罚因子不断减小，在迭代过程中惩罚项最终趋于零。,外点法，即在迭代过程中随着设计变量移向约束函数的边界，使中间函数逐步减小，而使罚因子逐步增大。如此构造出的罚函数称为外点罚函数，外点罚函数的具体形式如下。,4.4,外点惩罚函数法（衰减函数法）,2.,惩罚函数的构造,2.,惩罚函数的构造,4.4,外点惩罚函数法（衰减函数法）,2.,惩罚函数的构造,4.4,外点惩罚函数法（衰减函数法）,2.,惩罚函数的构造,考虑非线性规划问题,:,s.t.,惩罚函数可取为,2),罚因子,*1),时,惩罚项为,0,不惩罚,;,时,惩罚项大于,0,有惩罚作用,.,因,边界时,惩罚项中大括号中的值趋于,0,为保证惩罚作用,应取,4.4,外点惩罚函数法（衰减函数法）,3.,几个参数的选择,r,(0),的选择,:,r,(0),过大，会使惩罚函数的等值线变形或偏心，求极值困难。,r,(0),过小，迭代次数太多。,x,(0),的选择：,基本上可以在可行域内外，任意选择。,递增系数,c,的选择,：,通常选择,5,10,，可根据具体题目，进行试算调整。,4.4,外点惩罚函数法（衰减函数法）,4.,终止准则和约束裕量：,终止准则：,约束裕量：,当必须严格满足约束条件时，选用约束裕量,。,g=g+,g,0,0,4.4,外点惩罚函数法（衰减函数法）,5.,外点法迭代步骤,2.,构造惩罚（新目标）函数，调用无约束优化方法，求新目标函数 的最优解,x,k,*,和,(x,k,r,(k),),；,3.,4.,判断是否收敛：运用终止准则,若均满足，停止迭代，有约束优化问题的最优点为,x*=x,k,*,；,若有一个准则不满足，则令,并转入第,2,步，继续计算。,1.,选择合适的初始点,x,(0),，并选择,r,(0),a,1,2,0,，令,k=0,；,4.4,外点惩罚函数法（衰减函数法）,2.,SUMT,外点法的迭代步骤,给定,X,0,，,c,r,0,1,2,3,k=0,r,(k),=r,0,X,(K),=X,0,输出,X*,，,F*=F,（,X*,）,结束,是,是,是,否,否,否,求解,得极小点,X*,k=k+1,r,(k),=cr,(k),X,(k),=X*,-,初始点,对凸规划可任意给定,;,*,-,外点法点距精度,;,-,等式约束允许的误差限,;,-,不等式约束允许的误差限,;,-,罚因子的放大系数,;,*,为使迭代点进入可行域,可设,约束容差带,:,6.,外点法方法评价,：,初始点原则上可任意选择,;,能解决等式约束问题,;,由于优化过程是在可行域外进行，故在解决工程问题时，过程解均不可行。,4.4,外点惩罚函数法（衰减函数法）,例,:,解,:,惩罚函数,在,D,外,对于固定的,令,得,r,(k),x,*,f(x,*,),1,1.5,0.25,0.5,10,1.90909,0.82654,0.90909,100,1.99099,0.980296,0.990099,1000,1.999001,0.998003,0.999001,2,1,1,内点法和外点法的简单比较,内点法的特点：,（,1,）始点必须为严格内点,（,2,）不适于具有等式约束的数学模型,（,3,）迭代过程中各个点均为可行设计方案,（,4,）一般收敛较慢,（,5,）初始罚因子要选择得当,（,6,）罚因子为递减，递减率,c,有,0c1,一,.,基本思想,：,采用内点法和外点法相结合的混合惩罚函数法，以发挥内点法和外点法的特点，处理既有等式约束，又有不等式约束的优化设计问题。,4.5,混合惩罚函数法,二,.,惩罚函数的形式：,一般既包括障碍项，也包括衰减项。,4.5,混合惩罚函数法,4.5,混合惩罚函数法,4.5,混合惩罚函数法,