约束优化方法精选课件.ppt

《约束优化方法精选课件.ppt》由会员分享，可在线阅读，更多相关《约束优化方法精选课件.ppt（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于约束优化方法第一页，本课件共有77页 第五章第五章第五章第五章 约束优化方法约束优化方法约束优化方法约束优化方法根据求解方式的不同，可分为根据求解方式的不同，可分为直接解法和间接解法直接解法和间接解法两类。两类。机械优化设计的问题，大多属于约束优化设计问题，其数机械优化设计的问题，大多属于约束优化设计问题，其数学模型为：学模型为：直接解法直接解法是在满足不等式约束的可行设计区域内直接求是在满足不等式约束的可行设计区域内直接求出问题的约束最优解。出问题的约束最优解。间接解法间接解法是将约束优化问题转化为一系列无约束优化问题来解的是将约束优化问题转化为一系列无约束优化问题来解的一种方法。一种方

2、法。第二页，本课件共有77页 第五章第五章第五章第五章 约束优化方法约束优化方法约束优化方法约束优化方法直接解法直接解法是在满足不等式约束的可行设计区域内直接求是在满足不等式约束的可行设计区域内直接求出问题的约束最优解。出问题的约束最优解。属于直接解法的有：随机实验法、属于直接解法的有：随机实验法、随机方向搜索法、随机方向搜索法、复合形法复合形法、可行方向法等。、可行方向法等。间接解法间接解法是将约束优化问题转化为一系列无约束优化问题来是将约束优化问题转化为一系列无约束优化问题来解的一种方法。解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，由于间接解法可以选用已研究比较成熟的

3、无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。机械优化设计得到广泛的应用。间接解法中具有代表性的是间接解法中具有代表性的是惩罚函数法惩罚函数法。第三页，本课件共有77页直接解法的基本思想：直接解法的基本思想：在由在由m个不等式约束条件个不等式约束条件gu(x)0所确定的可行域所确定的可行域内，选择内，选择一个初始点一个初始点x(0)，然后确定一个可行搜索方向，然后确定一个可行搜索方向S，且以适当的步，且以适当的步长沿长沿S方向进行搜索，取得一个目标函数有所改善的可行的新点方向进行搜索，取得

4、一个目标函数有所改善的可行的新点x(1)，即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均，即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算：按如下的基本迭代格式进行计算：x(k+1)x(k)+(k)S(k)(k=0,1,2,)逐步趋向最优解，逐步趋向最优解，直到满足终止准则才停止迭代。直到满足终止准则才停止迭代。第四页，本课件共有77页直接解法的原理简单，方法实用，其特点是：直接解法的原理简单，方法实用，其特点是：1 1）由于整个过程在可行域内进行，因此，迭代计算不论）由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好的设

5、计点。何时终止，都可以获得比初始点好的设计点。2 2）若目标函数为凸函数，可行域为凸集，则可获得全域）若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局部最优解，当选择的初始最优解，否则，可能存在多个局部最优解，当选择的初始点不同，而搜索到不同的局部最优解。点不同，而搜索到不同的局部最优解。3 3）要求可行域有界的非空集。）要求可行域有界的非空集。直接解法的特点：直接解法的特点：第五页，本课件共有77页a)a)可行域是凸集；可行域是凸集；b)b)可行域是非凸集可行域是非凸集第六页，本课件共有77页间接解法的基本思路：间接解法的基本思路：将约束函数进行特殊的加权处理后，和

6、目标函数结合起来，将约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，构成一个新的目标函数，即将原约束优化问题转化为一个即将原约束优化问题转化为一个或一系列的无约束优化问题或一系列的无约束优化问题。新目标函数新目标函数加权因子加权因子然后对新目标函数进行无约束极小化计算。然后对新目标函数进行无约束极小化计算。第七页，本课件共有77页间接解法的基本思路间接解法的基本思路 第八页，本课件共有77页2.1 2.1 随机方向法的基本思路随机方向法的基本思路 1 1、在可行域内选择一个初始点；、在可行域内选择一个初始点；2 2、利用随机数的概率特性，产生若干个随机方向；、利用随机数

7、的概率特性，产生若干个随机方向；3 3、从中选一个能使目标函数值下降最快的方向作为搜索方向、从中选一个能使目标函数值下降最快的方向作为搜索方向d d；4 4、从初始点、从初始点x0 x0出发，沿出发，沿d d 方向以一定步长进行搜索，得到新点方向以一定步长进行搜索，得到新点X X，新点，新点X X应满足约束条件且应满足约束条件且f(x)f(x0)f(x)f(x0)，至此完成一次迭代。，至此完成一次迭代。基本思路如图所示。基本思路如图所示。随机方向法程序设计简单，搜索速度快，是解决小型机械优随机方向法程序设计简单，搜索速度快，是解决小型机械优化问题的十分有效的算法。化问题的十分有效的算法。第二节

8、第二节 约束随机方向法约束随机方向法第九页，本课件共有77页随机方向法的基本思路随机方向法的基本思路 第十页，本课件共有77页2.2 2.2 随机方向的构成随机方向的构成1.用用RND(X)RND(X)产生产生n n个随机数个随机数2.将将(0,1)中的随机数中的随机数变换到变换到(-1,1)中去中去(归一化归一化);3.构成随机方向构成随机方向变换得变换得:于是于是例例:对于三维问题对于三维问题第二节第二节 约束随机方向法约束随机方向法第十一页，本课件共有77页从从k个随机方向中，个随机方向中，选取一个较好的方向。选取一个较好的方向。2.3 2.3 可行搜索方向的产生可行搜索方向的产生第二节

9、第二节 约束随机方向法约束随机方向法1.1.检验检验k k个随机点是否为可行点，除去非可行点，计算余下个随机点是否为可行点，除去非可行点，计算余下的可行点的目标函数值，比较其大小，选出目标函数最小的的可行点的目标函数值，比较其大小，选出目标函数最小的点点X XL 。2.2.比较比较X XL L 和和X X0 0两点的目标函数值，两点的目标函数值，若若f(Xf(XL L)f(X)f(X)f(X0 0)，则步长，则步长0 0 缩小，转步骤缩小，转步骤1 1）重新计算，直）重新计算，直至至f(Xf(XL L)f(X)f(X0 0)为止。为止。如果如果0 0 缩小到很小，仍然找不到一个缩小到很小，仍然

10、找不到一个X XL L，使，使f(Xf(XL L)f(X)f(X0 0)则则说明说明X X0 0是一个局部极小点，此时可更换初始点，转步骤是一个局部极小点，此时可更换初始点，转步骤1 1）。）。第十二页，本课件共有77页产生可行搜索方向的条件为：产生可行搜索方向的条件为：则可行搜索方向为：则可行搜索方向为：2.3 2.3 可行搜索方向的产生可行搜索方向的产生第二节第二节 约束随机方向法约束随机方向法第十三页，本课件共有77页2.4 2.4 初始点的选择初始点的选择随机方向法的初始点随机方向法的初始点x0必须是一个可行点，既满足全部不等式约必须是一个可行点，既满足全部不等式约束条件。束条件。初始

11、点可以通过随机选择的方法产生。初始点可以通过随机选择的方法产生。1 1）输入设计变量的下限值和上限值，即）输入设计变量的下限值和上限值，即2 2）在区间（）在区间（0 0，1 1）内产生）内产生 n n 个伪随机数个伪随机数3 3）计算随机点）计算随机点x x的各分量的各分量第二节第二节 约束随机方向法约束随机方向法4 4）判别随机点）判别随机点x x是否可行，若随机点可行，用是否可行，若随机点可行，用x x代替代替x0 x0为为初始点；若非可行点，转到步骤初始点；若非可行点，转到步骤 2 2）重新产生随机点，只）重新产生随机点，只到可行为止。到可行为止。第十四页，本课件共有77页2.5.2.

12、5.迭代过程迭代过程在初始点处产生一随机方向，在初始点处产生一随机方向，若该方向适用、可行，则以定若该方向适用、可行，则以定步长前进；步长前进；若该方向不适用、可行，则若该方向不适用、可行，则产生另一方向；产生另一方向；若在某处产生的方向足够多若在某处产生的方向足够多(50-100)(50-100)，仍无一适用、可行，仍无一适用、可行，则采用收缩步长；则采用收缩步长；若步长小于预先给定的误若步长小于预先给定的误差限则终止迭代。差限则终止迭代。第二节第二节 约束随机方向法约束随机方向法第十五页，本课件共有77页2.6.2.6.流程图流程图X0=X,F0=F给定内点给定内点X0,0 0,m,m,=

13、0,F0=F(X0)F=F（X）j=1K=K+1是是K=0,j=0产生随机方向产生随机方向=0.5否否FF0j=0K=0 while max(gx)=0 dir0=rand(N,1);dir0=rand(N,1);x0=xl+dir0.*xu;x0=xl+dir0.*xu;gx=feval(g_cons,x0);gx=feval(g_cons,x0);%feval()%feval()执行由串指定的函数执行由串指定的函数endend%=%=fx0=feval(f,x0);fx0=feval(f,x0);xk=x0+1;xk=x0+1;fxk=feval(f,xk);fxk=feval(f,xk)

14、;xmin=x0;xmin=x0;alpha=1.3;alpha=1.3;k1=0;k1=0;flag1=1;flag1=1;while norm(xk-x0)TolX|abs(fxk-fx0)TolFunwhile norm(xk-x0)TolX|abs(fxk-fx0)TolFunk1=k1+1;k1=k1+1;x0=xmin;x0=xmin;fx0=feval(f,x0);fx0=feval(f,x0);2.7 2.7 随机方向法的随机方向法的MatlabMatlab程序程序第十七页，本课件共有77页dir0=rand(N,1)*2-1;dir0=rand(N,1)*2-1;dir0=d

15、ir0/norm(dir0);dir0=dir0/norm(dir0);xk=x0+alpha*dir0;xk=x0+alpha*dir0;gx=feval(g_cons,xk);gx=feval(g_cons,xk);if max(gx)0 if max(gx)0 alpha=alpha*0.7;alpha=alpha*0.7;elseelsefxk=feval(f,xk);fxk=feval(f,xk);if fxkfx0if fxkfx0if norm(xk-x0)TolX&abs(fxk-fx0)TolFunif norm(xk-x0)TolX&abs(fxk-fx0)TolFunbr

16、eakbreakelseelsexmin=xk;xmin=xk;alpha=1.3;alpha=1.3;endendx0,xk,fx0,fxkx0,xk,fx0,fxkelseelsealpha=-alpha;alpha=-alpha;end end endendendendx1=x0;x1=x0;fx1=feval(f,x1);fx1=feval(f,x1);gx=feval(g_cons,x1);gx=feval(g_cons,x1);k1k1endend第十八页，本课件共有77页例例:求求2.7 2.7 随机方向法的随机方向法的MatlabMatlab程序程序function opt_r

17、andom1_test1%opt_random1_test1.mclc;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第十九页，本课件共有77页第三节第三节 复合形法复合形法复合形法是求解约束优化问

18、题的一种重要的直接解法。复合形法是求解约束优化问题的一种重要的直接解法。基本思路：基本思路：1、在可行域内构造一个具有、在可行域内构造一个具有k个顶点的初始复合形；个顶点的初始复合形；2、对该复合形各顶点的目标函数值进行比较，找到目标函、对该复合形各顶点的目标函数值进行比较，找到目标函数最大的顶点（最坏点）；数最大的顶点（最坏点）；3、然后按一定的法则求出目标函数值有所下降的可行的新点，并、然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形的形状每改变一次，就用此点代替最坏点，构成新的复合形，复合形的形状每改变一次，就向最优点移动一步，直至逼近最优点

19、。向最优点移动一步，直至逼近最优点。由于复合形的形状不必保持规则的图形，对目标函数和约由于复合形的形状不必保持规则的图形，对目标函数和约束函数无特殊要求，因此这种方法适应性强，在机械优化设计束函数无特殊要求，因此这种方法适应性强，在机械优化设计中应用广泛。中应用广泛。第二十页，本课件共有77页3.1基本思路基本思路在可行域内选取若干初始点并以之为顶点构成一个在可行域内选取若干初始点并以之为顶点构成一个多面体多面体(复合形复合形),),然后比较各顶点的函数值然后比较各顶点的函数值,去掉最坏点去掉最坏点,代之以好的新点代之以好的新点,并构成新的复合形并构成新的复合形,以逼近最优点以逼近最优点.第三

20、节第三节 复合形法复合形法第二十一页，本课件共有77页3.2 3.2 初始复合形生成的方法：初始复合形生成的方法：（1）由设计者决定）由设计者决定k个可行点，构成初始复合形。设计变量少时适个可行点，构成初始复合形。设计变量少时适用。用。（2）由设计者选定一个可行点，其余的）由设计者选定一个可行点，其余的k-1个可形点用随机法个可形点用随机法产生。产生。（3）由计算机自动生成初始复合形的所有顶点。）由计算机自动生成初始复合形的所有顶点。第三节第三节 复合形法复合形法*初始复合形的构成初始复合形的构成*复合形的移动和收缩复合形的移动和收缩第二十二页，本课件共有77页第二十三页，本课件共有77页3.

21、2.1 3.2.1 初始复合形的构成初始复合形的构成(1)(1)复合形顶点数复合形顶点数K K的选择的选择建议建议:小取大值小取大值,大取小值大取小值(2)(2)初始复合形顶点的确定初始复合形顶点的确定用试凑方法产生用试凑方法产生-适于低维情况适于低维情况;用随机方法产生用随机方法产生3.2 3.2 初始复合形生成的方法：初始复合形生成的方法：第三节第三节 复合形法复合形法第二十四页，本课件共有77页 将非可行点调入可行域内将非可行点调入可行域内 K K个顶点中要求无一在可行域内。重新产生。个顶点中要求无一在可行域内。重新产生。K K个顶点中有可行点个顶点中有可行点，重新排列，将可行点依次排在

22、前面，重新排列，将可行点依次排在前面，如有如有q q个顶点个顶点X(1)、X(2)、X(q)是可行点，其它是可行点，其它K-qK-q个为非个为非可行点。对可行点。对X(q+1)，将其调入可行域的步骤是：，将其调入可行域的步骤是：先用随机函数产生先用随机函数产生 个随机数个随机数 ,然后变换到预定的区间然后变换到预定的区间 中去中去.用随机方法产生用随机方法产生K K个顶点个顶点第二十五页，本课件共有77页(1)(1)计算计算q q个点集的中心个点集的中心X(s)；(2)(2)将第将第q+1q+1点朝着点点朝着点X(s)的的方向移动，按下式产生新的方向移动，按下式产生新的X(q+1)，即，即 若

23、仍不可行，则重复此步骤，直至进入若仍不可行，则重复此步骤，直至进入可行域为止。可行域为止。按按照照这这个个方方法法，同同样样使使X(q+2)、X(q+3)、X(K)都都变变为为可可行点，这行点，这K K个点就构成了初始复合形。个点就构成了初始复合形。第二十六页，本课件共有77页有两种基本运算有两种基本运算:1)映射映射-在坏点的对侧试探在坏点的对侧试探新点新点:先计算除最坏点外各先计算除最坏点外各顶点的几何中心顶点的几何中心,然后再作然后再作映射计算映射计算.2)收缩收缩-保证映射点的保证映射点的“可行可行”与与“下降下降”X1为最坏点为最坏点-映射系数映射系数常取常取若发现映射点不适用、可行

24、若发现映射点不适用、可行,则将则将 减半后重新映射减半后重新映射.3.3 3.3 复合形法的搜索方法复合形法的搜索方法第二十七页，本课件共有77页3.4 3.4 复合形法的迭代步骤复合形法的迭代步骤(1)(1)构造初始复合形；构造初始复合形；(2)(2)计算各顶点的函数值计算各顶点的函数值F(X(j)，j=1,2,j=1,2,.,K.,K。选出好点选出好点X(L)和坏点和坏点X(H)；(3)(3)计算坏点外的其余各顶点的中心点计算坏点外的其余各顶点的中心点X(0)。第二十八页，本课件共有77页(4)(4)计算映射点计算映射点X(R)检查检查X(R)是否在可行域内。若是否在可行域内。若X(R)为

25、非可行点，将映射系为非可行点，将映射系数减半后再按上式改变映射点，直到数减半后再按上式改变映射点，直到X(R)进入可行域内为止。进入可行域内为止。(5)(5)构造新的复合形构造新的复合形 计算映射点的函数值计算映射点的函数值F(X(R)，并与坏点的函数值，并与坏点的函数值F(X(H)比比较，可能存在两种情况：较，可能存在两种情况：1 1）映射点优于坏点）映射点优于坏点 F(X(R)F(X(H)这这种种情情况况由由于于映映射射点点过过远远引引起起的的，减减半半映映射射系系数数，若有若有F(X(R)F(X(H)，这又转化为第一种情况。，这又转化为第一种情况。第三十页，本课件共有77页3.5 3.5

26、 判断终止条件判断终止条件1)1)各顶点与好点函数值之差的均方根各顶点与好点函数值之差的均方根值小于误差限，即值小于误差限，即2 2）各顶点与好点的函数值之差的平方和各顶点与好点的函数值之差的平方和小于误差限，即小于误差限，即 3 3）各）各顶点与好点函数值差的绝对值之和顶点与好点函数值差的绝对值之和小于误差限，即小于误差限，即 如果不满足终止迭代条件，则返回步骤如果不满足终止迭代条件，则返回步骤2 2继续进行下一次继续进行下一次迭代；否则，可将最后复合形的好点迭代；否则，可将最后复合形的好点X X(L)(L)及其函数值及其函数值F(XF(X(L)(L)作为最优解输出。作为最优解输出。第三十一

27、页，本课件共有77页比比较较复复合合形形各各顶顶点点的的函函数数值值，找出好点找出好点XL，坏点，坏点XHXH=XR=0.5找出次坏点找出次坏点XSH，XH=XSH满足终止条件？满足终止条件？X*=XL,F*=F(XL)结结束束3.6 3.6 流程图流程图是是否否给定给定K，ai,bii=1,2,n产生初始复合形顶点产生初始复合形顶点Xj,j=1,2,K计算复合形各顶点的函数值计算复合形各顶点的函数值F(Xj),j=1,2,K是是是是是是否否否否否否XRDFR0 while max(gx)0 x0=xl+rand(N,1).*xu;x0=xl+rand(N,1).*xu;gx=feval(g_

28、cons,x0);gx=feval(g_cons,x0);endend第三十三页，本课件共有77页x1,fx=gen_complex(x0,k,f,g_cons);x1,fx=gen_complex(x0,k,f,g_cons);flag1=1;flag2=1;flag3=1;flag1=1;flag2=1;flag3=1;k1=0k1=0fxfxx1x1fprintf(fprintf(此此处暂处暂停，停，请请按下任意按下任意键继续键继续n)n)pausepausewhile k1MaxIterwhile k1MaxIterflag1=1;flag2=1;flag3=1;flag1=1;fla

29、g2=1;flag3=1;k1=k1+1k1=k1+1fx,I=sort(fx);fx,I=sort(fx);for i=1:kfor i=1:kx2(:,i)=x1(:,I(i);x2(:,i)=x1(:,I(i);endendx1=x2;x1=x2;fmax1=fx(k);fmax1=fx(k);imax1=I(k);imax1=I(k);fmin=fx(1);fmin=fx(1);imin=I(1);imin=I(1);fmax2=fx(k-1);fmax2=fx(k-1);imax2=I(k-1);imax2=I(k-1);%计算形心计算形心xc=zeros(N,1);xc=zeros

30、(N,1);for i=1:kfor i=1:kxc=xc+x1(:,i);xc=xc+x1(:,i);endendxc=xc-x1(:,imax1);xc=xc-x1(:,imax1);xc=xc/(k-1);xc=xc/(k-1);gxc=feval(g_cons,xc);gxc=feval(g_cons,xc);alpha=1.31;alpha=1.31;%反射反射xr=xc+alpha*(xc-x1(:,imax1);xr=xc+alpha*(xc-x1(:,imax1);gxr=feval(g_cons,xr)gxr=feval(g_cons,xr)if max(gxr)0if ma

31、x(gxr)0fxr=feval(f,xr);fxr=feval(f,xr);if fxrfmax1if fxrfmax1fprintf(fprintf(反射成功反射成功n)n)fmax1,fxrfmax1,fxrfmax1=fxr;fmax1=fxr;fx(imax1)=fxr;fx(imax1)=fxr;x1(:,imax1)=xr;x1(:,imax1)=xr;flag1=-1;flag1=-1;elseelse%反射失败反射失败flgg1=1;flgg1=1;endend第三十四页，本课件共有77页elseelse%反射失反射失败败flag1=1;flag1=1;end end gam

32、a=0.7;gama=0.7;if flag1=-1 if flag1=-1 fprintf(fprintf(延伸延伸n)n)xe=xr+gama*(xr-xc);xe=xr+gama*(xr-xc);gxe=feval(g_cons,xe)gxe=feval(g_cons,xe)if max(gxe)0if max(gxe)0fxe=feval(f,xe);fxe=feval(f,xe);if fxefmax1if fxefmax1fprintf(fprintf(延伸成功延伸成功n)n)fxe,fmax1fxe,fmax1fx(imax1)=fxe;fx(imax1)=fxe;fmax1=f

33、xe;fmax1=fxe;x1(:,imax1)=xe;x1(:,imax1)=xe;flag2=-1;flag2=-1;elseelse%延伸失败延伸失败flag2=1;flag2=1;endendelseelse%延伸失延伸失败败flag2=1;flag2=1;endendendendbeta=0.7;beta=0.7;if flag1=-1&flag2=-1if flag1=-1&flag2=-1fprintf(fprintf(收缩收缩n)n)xk=x1(:,imax1)+beta*(xc-x1(:,imax1);xk=x1(:,imax1)+beta*(xc-x1(:,imax1);g

34、xk=feval(g_cons,xk)gxk=feval(g_cons,xk)if max(gxk)0if max(gxk)0fxk=feval(f,xk);fxk=feval(f,xk);if fxkfmax1if fxkfmax1fprintf(fprintf(收缩成功收缩成功n)n)fxk,fmax1fxk,fmax1fmax1=fxk;fmax1=fxk;fx(imax1)=fxk;fx(imax1)=fxk;x1(:,imax1)=xk;x1(:,imax1)=xk;flag3=-1;flag3=-1;elseelse%收缩失败收缩失败flag3=1;flag3=1;endendel

35、seelse第三十五页，本课件共有77页%收缩失败收缩失败flag3=1;flag3=1;endendend end if flag1if flag1=-1&flag2=-1&flag2=-1&flag3=-1&flag3=-1=-1fprintf(flag1,flag2,flag3n%d%d%dn,flag1,flag2,flag3)fprintf(flag1,flag2,flag3n%d%d%dn,flag1,flag2,flag3)fprintf(fprintf(重新生成单纯形重新生成单纯形n)n)fx,I=sort(fx);fx,I=sort(fx);imin=I(1);imin=I(

36、1);x0=x1(:,imin);x0=x1(:,imin);x1,fx=gen_complex(x0,k,f,g_cons)x1,fx=gen_complex(x0,k,f,g_cons)endendendendxo=x1(:,imin);xo=x1(:,imin);fo=feval(f,xo);fo=feval(f,xo);go=feval(g_cons,xo);go=feval(g_cons,xo);k1k1第三十六页，本课件共有77页functionfunction x1,fx=gen_complex(x0,k,f,g_cons)x1,fx=gen_complex(x0,k,f,g_c

37、ons)N=length(x0);N=length(x0);M=size(g_cons);M=size(g_cons);M=length(M(:,1);M=length(M(:,1);x1(:,1)=x0;x1(:,1)=x0;fx(1)=feval(f,x0);fx(1)=feval(f,x0);a=1.3;a=1.3;s=rand(N,k)*2-ones(N,k);s=rand(N,k)*2-ones(N,k);s=s/norm(s);s=s/norm(s);k2=1;k2=1;whilewhile k2k k2kx0=x1(:,1)+a*s(:,k2);x0=x1(:,1)+a*s(:,

38、k2);gx=feval(g_cons,x0);gx=feval(g_cons,x0);ifif max(gx)0 max(gx)0k2=k2+1;k2=k2+1;x1(:,k2)=x0;x1(:,k2)=x0;fx(k2)=feval(f,x0);fx(k2)=feval(f,x0);elseelsea=0.7*a;a=0.7*a;endendendend 第三十七页，本课件共有77页3.7 3.7 应用复合形法应用复合形法MatlabMatlab程序求约束优化问题的最优解程序求约束优化问题的最优解function opt_complex_test1%opt_complex_test1.mc

39、lc;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解决有约束的非线

40、性解决有约束的非线性优化问题优化问题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。第三十八页，本课件共有77页约束优化问题的间接解法约束优化问题的间接解法约束优化问题的间接解法约束优化问题的间接解法 约束优化问题的间接解法是将约束优化问题转化

41、为约束优化问题的间接解法是将约束优化问题转化为一系列无约束优化问题来进行求解的方法。一系列无约束优化问题来进行求解的方法。约束优化问约束优化问题的间接解法除拉格朗日乘子法外，常用的方法还有题的间接解法除拉格朗日乘子法外，常用的方法还有罚函罚函数法及增广乘子法数法及增广乘子法。虽然约束优化问题的间接解法可利用无约束优化问题虽然约束优化问题的间接解法可利用无约束优化问题的求解方法进行求解，但由于增加了拉格朗日乘子或罚因的求解方法进行求解，但由于增加了拉格朗日乘子或罚因子，其求解过程与常规无约束优化问题有所不同。子，其求解过程与常规无约束优化问题有所不同。第三十九页，本课件共有77页4.1概述概述1

42、.基本思想基本思想将约束问题将约束问题 转化成转化成无约束问题无约束问题 求解求解惩罚函数惩罚函数可调参数可调参数*构造惩罚函数构造惩罚函数的基本要求的基本要求:惩罚项用约束条件构造惩罚项用约束条件构造;到达最优点时到达最优点时,惩罚项的值为惩罚项的值为0 0;当约束不满足或未到达最优点时当约束不满足或未到达最优点时,惩罚项惩罚项的值的值大于大于0 0.第四节第四节 惩罚函数法惩罚函数法第四十页，本课件共有77页惩罚函数法是一种很广泛、很有效的间接解法。它的基本惩罚函数法是一种很广泛、很有效的间接解法。它的基本原理是将约束优化问题中的不等式和不等式约束函数经加权原理是将约束优化问题中的不等式和

43、不等式约束函数经加权后，和原目标函数结合为新的目标函数后，和原目标函数结合为新的目标函数惩罚函数。惩罚函数。将约束优化问题转换为无约束优化问题。求解无约束优将约束优化问题转换为无约束优化问题。求解无约束优化问题的极小值，从而得到原约束优化问题的最优解。化问题的极小值，从而得到原约束优化问题的最优解。加权转化项加权转化项第四节第四节 惩罚函数法惩罚函数法第四十一页，本课件共有77页惩罚函数法惩罚函数法是按一定的法则改变加权因子的值，构是按一定的法则改变加权因子的值，构成一系列的无约束优化问题，求一系列无约束最优解，成一系列的无约束优化问题，求一系列无约束最优解，并不断地逼近原约束优化问题的最优解

44、。因此并不断地逼近原约束优化问题的最优解。因此又称序又称序列无约束极小化方法。常称列无约束极小化方法。常称SUMT方法。方法。根据它们在惩罚函数中的作用，分别称障碍项和惩罚根据它们在惩罚函数中的作用，分别称障碍项和惩罚项。项。障碍项的作用是当迭代点在可行域内时，在迭代过程中障碍项的作用是当迭代点在可行域内时，在迭代过程中将阻止迭代点越出可形域。将阻止迭代点越出可形域。惩罚项的作用是当迭代点在非可行域或不满足等式约束条惩罚项的作用是当迭代点在非可行域或不满足等式约束条件时，在迭代过程中将迫使迭代点逼近约束边界或等式约件时，在迭代过程中将迫使迭代点逼近约束边界或等式约束曲面。束曲面。第四十二页，本

45、课件共有77页4.2分类分类内点法内点法-将迭代点限制在可行域内将迭代点限制在可行域内;外点法外点法-迭代点一般在可行域外迭代点一般在可行域外;混合法混合法-将外点法和内点法结合起来解将外点法和内点法结合起来解GPGP型问题型问题.按照惩罚函数在优化过程中迭代点是否可行，分为：按照惩罚函数在优化过程中迭代点是否可行，分为：内点法、外点法内点法、外点法及及混合法。混合法。第四节第四节 惩罚函数法惩罚函数法第四十三页，本课件共有77页4.3 SUMT4.3 SUMT内点法内点法(内点惩罚函数法、障碍函数法内点惩罚函数法、障碍函数法)1.1.惩罚函数的构造惩罚函数的构造原问题原问题:s.t.可取可取

46、式中式中,1)当当X X趋于趋于D D的边界时的边界时,中间函数中间函数B(X)趋于无穷大趋于无穷大,故故又称为又称为障碍障碍(围墙围墙)函数函数;r称为罚因子称为罚因子，在逐次迭代中越来越小，在逐次迭代中越来越小第四十四页，本课件共有77页4.3.1 4.3.1 基本思想：基本思想：内点法将新目标函数内点法将新目标函数(x,r)构筑构筑在在可行域可行域 D D 内内，随着惩罚因子，随着惩罚因子 r r(k)(k)的的不断不断递减递减，生成一系列新目标函数，生成一系列新目标函数 (x(xk k,r,r(k)(k)，在可行域，在可行域内内逐步迭代，产逐步迭代，产生的极值点生的极值点 x xk k

47、*(r*(r(k)(k)序列从可行域序列从可行域内内部趋向原目标函数的约束最优点部趋向原目标函数的约束最优点 x*x*。例例：求下述约束优化问题的最优点。：求下述约束优化问题的最优点。min.f(x)=xxR1s.tg(x)=1-x0X1*X2*X*4.3 SUMT4.3 SUMT内点法内点法(内点惩罚函数法、障碍函数法内点惩罚函数法、障碍函数法)第四十五页，本课件共有77页4.3.2 4.3.2 惩罚函数的形式惩罚函数的形式：其中：惩罚（加权）因子其中：惩罚（加权）因子罚因子降低系数罚因子降低系数（罚因子递减速率）（罚因子递减速率）c：0c14.3 SUMT4.3 SUMT内点法内点法(内点

48、惩罚函数法、障碍函数法内点惩罚函数法、障碍函数法)第四十六页，本课件共有77页4.3.3 4.3.3 迭代步骤：迭代步骤：1.选取合适的初始点选取合适的初始点x(0)，以及，以及r(0)、c、计算精度计算精度1、2，令，令k=0；2.构造惩罚（新目标）函数；构造惩罚（新目标）函数；3.调用无约束优化方法，求新目标函数的最优解调用无约束优化方法，求新目标函数的最优解xk*和和(xk,r(k)；4.判断是否收敛：运用终止准则判断是否收敛：运用终止准则前后两次无约束极小点之间的距离前后两次无约束极小点之间的距离相邻两点罚函数的相对误差相邻两点罚函数的相对误差若均满足，停止迭代，有约束优化问题的最优点

49、为若均满足，停止迭代，有约束优化问题的最优点为x*=xk*；若有一个准则不满足，则令若有一个准则不满足，则令并转入第并转入第3步，继续计算。步，继续计算。4.3 SUMT4.3 SUMT内点法内点法(内点惩罚函数法、障碍函数法内点惩罚函数法、障碍函数法)第四十七页，本课件共有77页下面介绍内点法中的初始点、惩罚因子初值及其缩减下面介绍内点法中的初始点、惩罚因子初值及其缩减系数的选取和收敛条件的确定。系数的选取和收敛条件的确定。1.初始点的选取初始点的选取初始点应选离约束边界较远的可行点。初始点应选离约束边界较远的可行点。程序设计时，程序设计时，一般，考虑具有人工输入和计算机自动生成可行初始一般

50、，考虑具有人工输入和计算机自动生成可行初始点的两种功能。点的两种功能。4.3 SUMT4.3 SUMT内点法内点法第四十八页，本课件共有77页1.初始点初始点x(0)的选择方法的选择方法人工估算，需要校核可行性；人工估算，需要校核可行性；计算机随机产生，也需校核可行计算机随机产生，也需校核可行性；性；搜索方法：搜索方法：任意给出一个初始点；任意给出一个初始点；判断其可行性，若违反了判断其可行性，若违反了S个约束，求出不满足约束中的最大值：个约束，求出不满足约束中的最大值：应用优化方法减少违反约束：应用优化方法减少违反约束：以求得的设计点作为新初始点，继续其判断可行性，若仍有不满以求得的设计点作