《第五章 约束优化方法.ppt》由会员分享，可在线阅读，更多相关《第五章 约束优化方法.ppt（81页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章第五章第五章 约束优化方法约束优化方法约束优化方法约束优化方法2023/3/1312)2)约束随机方向法约束随机方向法;3)3)复合形法复合形法;5)5)罚函数法罚函数法;约束优化直接解法约束优化直接解法约束优化间接解法约束优化间接解法（1 1）内点罚函数法内点罚函数法;（2 2）外点罚函数法外点罚函数法;1)1)约束坐标轮换法；约束坐标轮换法；4)4)可行方向法可行方向法;（自学）（自学）第五章第五章第五章第五章 约束优化方法约束优化方法约束优化方法约束优化方法根据求解方式的不同，可分为根据求解方式的不同，可分为直接解法和间接解法直接解法和间接解法两类。两类。机械优化设计的问题，
2、大多属于约束优化设计问题，机械优化设计的问题，大多属于约束优化设计问题，其数学模型为：其数学模型为：直接解法直接解法是是将迭代点限制在可行域内将迭代点限制在可行域内(可行性可行性)，步步降低目标，步步降低目标函数值函数值(下降性下降性)，直至到达最优点，直至到达最优点，求出问题的约束最优解。求出问题的约束最优解。间接解法间接解法是将约束优化问题转化为一系列无约束优化问题来是将约束优化问题转化为一系列无约束优化问题来解的一种方法。解的一种方法。常用方法有常用方法有:约束坐标轮换法约束坐标轮换法,约束随机方向法约束随机方向法,复合形法复合形法,可行方向法可行方向法,线性逼近法等线性逼近法等.常用方
3、法有常用方法有:罚函数法罚函数法,拉格朗日乘子法等拉格朗日乘子法等.第五章第五章第五章第五章 约束优化方法约束优化方法约束优化方法约束优化方法直接解法直接解法是在满足不等式约束的可行设计区域内直接求是在满足不等式约束的可行设计区域内直接求出问题的约束最优解。出问题的约束最优解。属于直接解法的有：随机实验法、属于直接解法的有：随机实验法、随机方向搜索法、随机方向搜索法、复合形法复合形法、可行方向法等。、可行方向法等。间接解法间接解法是将约束优化问题转化为一系列无约束优化问题来是将约束优化问题转化为一系列无约束优化问题来解的一种方法。解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法
4、，由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。在机械优化设计得到广泛的应用。间接解法中具有代表性的是间接解法中具有代表性的是惩罚函数法惩罚函数法。直接解法的基本思想：直接解法的基本思想：在由在由m个不等式约束条件个不等式约束条件gu(x)0所确定的可行域所确定的可行域内，内，选择一个初始点选择一个初始点x(0)，然后确定一个可行搜索方向，然后确定一个可行搜索方向S，且以适，且以适当的步长沿当的步长沿S方向进行搜索，取得一个目标函数有所改善的方向进行搜索，
5、取得一个目标函数有所改善的可行的新点可行的新点x(1)，即完成了一次迭代。以新点为起始点重复，即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算：上述搜索过程，每次均按如下的基本迭代格式进行计算：x(k+1)x(k)+(k)S(k)(k=0,1,2,)逐步趋向最优解，逐步趋向最优解，直到满足终止准则才停止迭代。直到满足终止准则才停止迭代。直接解法的原理简单，方法实用，其特点是：直接解法的原理简单，方法实用，其特点是：1 1）由于整个过程在可行域内进行，因此，迭代计算不论）由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好的设计点。何时
6、终止，都可以获得比初始点好的设计点。2 2）若目标函数为凸函数，可行域为凸集，则可获得全域）若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局部最优解，当选择的初始最优解，否则，可能存在多个局部最优解，当选择的初始点不同，而搜索到不同的局部最优解。点不同，而搜索到不同的局部最优解。3 3）要求可行域有界的非空集。）要求可行域有界的非空集。直接解法的特点：直接解法的特点：a)a)可行域是凸集；可行域是凸集；b)b)可行域是非凸集可行域是非凸集间接解法的基本思路：间接解法的基本思路：将约束函数进行特殊的加权处理后，和目标函数结合起来，将约束函数进行特殊的加权处理后，和目标函
7、数结合起来，构成一个新的目标函数，构成一个新的目标函数，即将原约束优化问题转化为一个即将原约束优化问题转化为一个或一系列的无约束优化问题或一系列的无约束优化问题。新目标函数新目标函数加权因子加权因子然后对新目标函数进行无约束极小化计算。然后对新目标函数进行无约束极小化计算。间接解法的基本思路间接解法的基本思路 2023/3/139第二节第二节第二节第二节 约束坐标轮换法约束坐标轮换法约束坐标轮换法约束坐标轮换法一一.基本思路基本思路 可取定步长、加速步长和收缩步长可取定步长、加速步长和收缩步长,但不能取最但不能取最优步长优步长;1.1.依次沿各坐标轴方向依次沿各坐标轴方向-e-e1 1,e,e
8、2 2,e,en n方向搜索方向搜索;2.2.将迭代点限制在可行域内将迭代点限制在可行域内.对每一迭代点均需进行可行性和下降性检查对每一迭代点均需进行可行性和下降性检查.2023/3/1310二二.迭代步骤迭代步骤2023/3/1311三三.存在问题存在问题有时会出现死点有时会出现死点,导致输出导致输出“伪最优点伪最优点”.*为辨别真伪为辨别真伪,要用要用K-TK-T条件条件进行检查进行检查.3.1 3.1 随机方向法的基本思路随机方向法的基本思路 1 1、在可行域内选择一个初始点；、在可行域内选择一个初始点；2 2、利用随机数的概率特性，产生若干个随机方向；、利用随机数的概率特性，产生若干个
9、随机方向；3 3、从中选一个能使目标函数值下降最快的方向作为搜索方向、从中选一个能使目标函数值下降最快的方向作为搜索方向d d；4 4、从初始点、从初始点x0 x0出发，沿出发，沿d d 方向以一定步长进行搜索，得到新点方向以一定步长进行搜索，得到新点X X，新点，新点X X应满足约束条件且应满足约束条件且f(x)f(x0)f(x)f(x0)，至此完成一次迭代。，至此完成一次迭代。基本思路如图所示。基本思路如图所示。随机方向法程序设计简单，搜索速度快，是解决小型机械优随机方向法程序设计简单，搜索速度快，是解决小型机械优化问题的十分有效的算法。化问题的十分有效的算法。第三节第三节 约束随机方向法
10、约束随机方向法坐标轮换法有时会输出坐标轮换法有时会输出“伪最优点伪最优点”,用随机方向法可克服这一缺点用随机方向法可克服这一缺点.随机方向法的基本思路随机方向法的基本思路 3.2 3.2 随机方向的构成随机方向的构成1.用用RND(X)RND(X)产生产生n n个随机数个随机数2.将将(0,1)中的随机数中的随机数变换到变换到(-1,1)中去中去(归一化归一化);3.构成随机方向构成随机方向变换得变换得:于是于是例例:对于三维问题对于三维问题第二节第二节 约束随机方向法约束随机方向法从从k个随机方向中，个随机方向中，选取一个较好的方向。选取一个较好的方向。3.3 3.3 可行搜索方向的产生可行
11、搜索方向的产生第二节第二节 约束随机方向法约束随机方向法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 缩小到很小，仍然找不到
12、一个缩小到很小，仍然找不到一个X XL L，使，使f(Xf(XL L)f(Xf(X0 0)则说明则说明X X0 0是一个局部极小点，此时可更换初始点，转步是一个局部极小点，此时可更换初始点，转步骤骤1 1）。）。产生可行搜索方向的条件为：产生可行搜索方向的条件为：则可行搜索方向为：则可行搜索方向为：3.3 3.3 可行搜索方向的产生可行搜索方向的产生第二节第二节 约束随机方向法约束随机方向法3.4 3.4 初始点的选择初始点的选择随机方向法的初始点随机方向法的初始点x0必须是一个可行点，既满足全部不等必须是一个可行点，既满足全部不等式约束条件。式约束条件。初始点可以通过随机选择的方法产生。初始
13、点可以通过随机选择的方法产生。1 1）输入设计变量的下限值和上限值，即）输入设计变量的下限值和上限值，即2 2）在区间（）在区间（0 0，1 1）内产生）内产生 n n 个伪随机数个伪随机数3 3）计算随机点）计算随机点x x的各分量的各分量第二节第二节 约束随机方向法约束随机方向法4 4）判别随机点）判别随机点x x是否可行，若随机点可行，用是否可行，若随机点可行，用x x代替代替x0 x0为为初始点；若非可行点，转到步骤初始点；若非可行点，转到步骤 2 2）重新产生随机点，只）重新产生随机点，只到可行为止。到可行为止。3.5.3.5.迭代过程迭代过程在初始点处产生一随机方在初始点处产生一随
14、机方向，若该方向适用、可行，向，若该方向适用、可行，则以定步长前进；则以定步长前进；若该方向不适用、可行，若该方向不适用、可行，则产生另一方向；则产生另一方向；若在某处产生的方向足够若在某处产生的方向足够多多(50-100)(50-100)，仍无一适用、，仍无一适用、可行，则采用收缩步长；可行，则采用收缩步长；若步长小于预先给定的误若步长小于预先给定的误差限则终止迭代。差限则终止迭代。第二节第二节 约束随机方向法约束随机方向法3.6.3.6.流程图流程图X0=X,F0=F给定内点给定内点X0,0 0,m,m,=0,F0=F(X0)F=F（X）j=1K=K+1是是K=0,j=0产生随机方向产生随
15、机方向=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);xmin=x0;xmin=x0;alpha=1.3;alpha=1.3;k1=0;
16、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);3.7 3.7 随机方向法的随机方向法的MatlabMatlab程序程序dir0=rand(N,1)*2-1;dir0=rand(N,1)*2-1;dir0=dir0/norm(dir0);dir0=dir0/norm(dir0);xk=x0+alpha*dir0;xk
17、=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)TolFunbreakbreakelseelsexmin=xk;xmin=xk;alpha=1.3;alpha=1.3;end
18、endx0,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例例:求求3.7 3.7 随机方向法的随机方向法的MatlabMatlab程序程序function opt_random1_test1%opt_random1_test1.mclc;clear all;f=inline(x(1)2+x(2),x)
19、;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个顶点的初始复合形
20、；个顶点的初始复合形；2、对该复合形各顶点的目标函数值进行比较，找到目标、对该复合形各顶点的目标函数值进行比较，找到目标函数最大的顶点（最坏点）；函数最大的顶点（最坏点）；3、然后按一定的法则求出目标函数值有所下降的可行的、然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形的形状新点，并用此点代替最坏点，构成新的复合形，复合形的形状每改变一次，就向最优点移动一步，直至逼近最优点。每改变一次，就向最优点移动一步，直至逼近最优点。由于复合形的形状不必保持规则的图形，对目标函数和约由于复合形的形状不必保持规则的图形，对目标函数和约束函数无特殊要求，因此这种
21、方法适应性强，在机械优化设束函数无特殊要求，因此这种方法适应性强，在机械优化设计中应用广泛。计中应用广泛。4.1基本思路基本思路在可行域内选取若干初始点并以之为顶点构成在可行域内选取若干初始点并以之为顶点构成一个多面体一个多面体(复合形复合形),),然后比较各顶点的函数值然后比较各顶点的函数值,去去掉最坏点掉最坏点,代之以好的新点代之以好的新点,并构成新的复合形并构成新的复合形,以逼以逼近最优点近最优点.第四节第四节 复合形法复合形法4.2 4.2 初始复合形生成的方法：初始复合形生成的方法：（1）由设计者决定）由设计者决定k个可行点，构成初始复合形。设计变量个可行点，构成初始复合形。设计变量
22、少时适用。少时适用。（2）由设计者选定一个可行点，其余的）由设计者选定一个可行点，其余的k-1个可形点用随机法个可形点用随机法产生。产生。（3）由计算机自动生成初始复合形的所有顶点。）由计算机自动生成初始复合形的所有顶点。第四节第四节 复合形法复合形法*初始复合形的构成初始复合形的构成*复合形的移动和收缩复合形的移动和收缩4.2.1 4.2.1 初始复合形的构成初始复合形的构成(1)(1)复合形顶点数复合形顶点数K K的选择的选择建议建议:小取大值小取大值,大取小值大取小值(2)(2)初始复合形顶点的确定初始复合形顶点的确定用试凑方法产生用试凑方法产生-适于低维情况适于低维情况;用随机方法产生
23、用随机方法产生4.2 4.2 初始复合形生成的方法：初始复合形生成的方法：第四节第四节 复合形法复合形法 将非可行点调入可行域内将非可行点调入可行域内 K K个顶点中要求无一在可行域内。重新产生。个顶点中要求无一在可行域内。重新产生。K K个顶点中有可行点个顶点中有可行点，重新排列，将可行点依次排在前重新排列，将可行点依次排在前面，如有面，如有q q个顶点个顶点X(1)、X(2)、X(q)是可行点，其它是可行点，其它K-qK-q个个为非可行点。对为非可行点。对X(q+1)，将其调入可行域的步骤是：，将其调入可行域的步骤是：先用随机函数产生先用随机函数产生 个随机数个随机数 ,然后变换到预定的区
24、间然后变换到预定的区间 中去中去.用随机方法产生用随机方法产生K K个顶点个顶点(1)(1)计算计算q q个点集的中心个点集的中心X(s)；(2)(2)将第将第q+1q+1点朝着点点朝着点X(s)的的方向移动，按下式产生新方向移动，按下式产生新的的X(q+1)，即，即 若仍不可行，则重复此步骤，直至进若仍不可行，则重复此步骤，直至进入可行域为止。入可行域为止。按按照照这这个个方方法法，同同样样使使X(q+2)、X(q+3)、X(K)都都变变为可行点，这为可行点，这K K个点就构成了初始复合形。个点就构成了初始复合形。有两种基本运算有两种基本运算:1)映射映射-在坏点的对侧试探在坏点的对侧试探新
25、点新点:先计算除最坏点外各先计算除最坏点外各顶点的几何中心顶点的几何中心,然后再作然后再作映射计算映射计算.2)收缩收缩-保证映射点的保证映射点的“可行可行”与与“下降下降”X1为最坏点为最坏点-映射系数映射系数常取常取若发现映射点不适用、可行若发现映射点不适用、可行,则将则将 减半后重新映射减半后重新映射.4.3 4.3 复合形法的搜索方法复合形法的搜索方法4.4 4.4 复合形法的迭代步骤复合形法的迭代步骤(1)(1)构造初始复合形；构造初始复合形；(2)(2)计算各顶点的函数值计算各顶点的函数值F(X(j)，j=1,2,j=1,2,.,K.,K。选出好点选出好点X(L)和坏点和坏点X(H
26、)；(3)(3)计算坏点外的其余各顶点的中心点计算坏点外的其余各顶点的中心点X(0)。(4)(4)计算映射点计算映射点X(R)检查检查X(R)是否在可行域内。若是否在可行域内。若X(R)为非可行点，将映射为非可行点，将映射系数减半后再按上式改变映射点，直到系数减半后再按上式改变映射点，直到X(R)进入可行域内进入可行域内为止。为止。(5)(5)构造新的复合形构造新的复合形 计算映射点的函数值计算映射点的函数值F(X(R)，并与坏点的函数值，并与坏点的函数值F(X(H)比较，可能存在两种情况：比较，可能存在两种情况：1 1）映射点优于坏点）映射点优于坏点 F(X(R)F(X(H)这这种种情情况况
27、由由于于映映射射点点过过远远引引起起的的，减减半半映映射射系系数数，若有若有F(X(R)F(X(H)，这又转化为第一种情况。，这又转化为第一种情况。4.5 4.5 判断终止条件判断终止条件1)1)各顶点与好点函数值之差的均方根各顶点与好点函数值之差的均方根值小于误差限，即值小于误差限，即2 2）各顶点与好点的函数值之差的平方和各顶点与好点的函数值之差的平方和小于误差限，即小于误差限，即 3 3）各）各顶点与好点函数值差的绝对值之和顶点与好点函数值差的绝对值之和小于误差限，即小于误差限，即 如果不满足终止迭代条件，则返回步骤如果不满足终止迭代条件，则返回步骤2 2继续进行下继续进行下一次迭代；否
28、则，可将最后复合形的好点一次迭代；否则，可将最后复合形的好点X X(L)(L)及其函数值及其函数值F F(X(X(L)(L)作为最优解输出。作为最优解输出。比比较较复复合合形形各各顶顶点点的的函函数数值值，找出好点找出好点XL，坏点，坏点XHXH=XR=0.5找出次坏点找出次坏点XSH，XH=XSH满足终止条件？满足终止条件？X*=XL,F*=F(XL)结结束束4.6 4.6 流程图流程图是是否否给定给定K，ai,bii=1,2,n产生初始复合形顶点产生初始复合形顶点Xj,j=1,2,K计算复合形各顶点的函数值计算复合形各顶点的函数值F(Xj),j=1,2,K是是是是是是否否否否否否XRDFR
29、0 while max(gx)0 x0=xl+rand(N,1).*xu;x0=xl+rand(N,1).*xu;gx=feval(g_cons,x0);gx=feval(g_cons,x0);endendx1,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 k1Max
30、Iterwhile k1MaxIterflag1=1;flag2=1;flag3=1;flag1=1;flag2=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);ima
31、x2=I(k-1);imax2=I(k-1);%计算形心计算形心xc=zeros(N,1);xc=zeros(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
32、=feval(g_cons,xr)gxr=feval(g_cons,xr)if max(gxr)0if max(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;endendelse
33、else%反射失反射失败败flag1=1;flag1=1;end end gama=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,
34、fmax1fx(imax1)=fxe;fx(imax1)=fxe;fmax1=fxe;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(:,imax
35、1);xk=x1(:,imax1)+beta*(xc-x1(:,imax1);gxk=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;e
36、lseelse%收缩失败收缩失败flag3=1;flag3=1;endendelseelse%收缩失败收缩失败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=
37、sort(fx);imin=I(1);imin=I(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);k1k1functionfunction x1,fx=gen_complex(x0,k,f,g_cons)x1,fx=gen_comple
38、x(x0,k,f,g_cons)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
39、(:,1)+a*s(:,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 4.7 4.7 应用复合形法应用复合形法MatlabMatlab程序求约束优化问题的最优解程序求约束优化问题的最优解function opt_complex_test1%opt_complex_test1.mclc
40、;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解决有约束的非解决有
41、约束的非线性优化问题线性优化问题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)这是对这是对寻优函数搜索方式寻优
42、函数搜索方式的设定，的设定，LargeScale指大规指大规模搜索，模搜索，off表示在规模搜索模式关闭，表示在规模搜索模式关闭，Simplex指单指单纯形算法，纯形算法，on表示该算法打开。表示该算法打开。display指结果方式，指结果方式，有四种有四种off|iter|notify|final，iter是指中间结果每是指中间结果每步都显示，一般选择步都显示，一般选择final显示最终结果。显示最终结果。在在MATLAB运行窗口直接输入运行窗口直接输入optimset可显示所有可可显示所有可设置的参数及对应的可选择的参数值。设置的参数及对应的可选择的参数值。约束优化问题的间接解法约束优化问
43、题的间接解法约束优化问题的间接解法约束优化问题的间接解法 约束优化问题的间接解法是将约束优化问题转化为约束优化问题的间接解法是将约束优化问题转化为一系列无约束优化问题来进行求解的方法。一系列无约束优化问题来进行求解的方法。约束优化问约束优化问题的间接解法除拉格朗日乘子法外，常用的方法还有题的间接解法除拉格朗日乘子法外，常用的方法还有罚罚函数法及增广乘子法函数法及增广乘子法。虽然约束优化问题的间接解法可利用无约束优化问虽然约束优化问题的间接解法可利用无约束优化问题的求解方法进行求解，但由于增加了拉格朗日乘子或题的求解方法进行求解，但由于增加了拉格朗日乘子或罚因子，其求解过程与常规无约束优化问题有
44、所不同。罚因子，其求解过程与常规无约束优化问题有所不同。4.1概述概述1.基本思想基本思想将约束问题将约束问题 转化成转化成无约束问题无约束问题 求解求解惩罚函数惩罚函数可调参数可调参数*构造惩罚函数构造惩罚函数的基本要求的基本要求:惩罚项用约束条件构造惩罚项用约束条件构造;到达最优点时到达最优点时,惩罚项的值为惩罚项的值为0 0;当约束不满足或未到达最优点时当约束不满足或未到达最优点时,惩罚项惩罚项的值的值大于大于0 0.第四节第四节 惩罚函数法惩罚函数法惩罚函数法是一种很广泛、很有效的间接解法。它惩罚函数法是一种很广泛、很有效的间接解法。它的基本原理是将约束优化问题中的不等式和等式约束的基
45、本原理是将约束优化问题中的不等式和等式约束函数经加权后，和原目标函数结合为新的目标函数函数经加权后，和原目标函数结合为新的目标函数惩罚函数。惩罚函数。将约束优化问题转换为无约束优化问题。求解无约将约束优化问题转换为无约束优化问题。求解无约束优化问题的极小值，从而得到原约束优化问题的最束优化问题的极小值，从而得到原约束优化问题的最优解。优解。加权转化项加权转化项第四节第四节 惩罚函数法惩罚函数法惩罚函数法惩罚函数法是按一定的法则改变加权因子的值，构是按一定的法则改变加权因子的值，构成一系列的无约束优化问题，求一系列无约束最优解，成一系列的无约束优化问题，求一系列无约束最优解，并不断地逼近原约束优
46、化问题的最优解。因此并不断地逼近原约束优化问题的最优解。因此又称序又称序列无约束极小化方法。常称列无约束极小化方法。常称SUMT方法。方法。根据它们在惩罚函数中的作用，分别称障碍项和惩罚根据它们在惩罚函数中的作用，分别称障碍项和惩罚项。项。障碍项的作用是当迭代点在可行域内时，在迭代过程障碍项的作用是当迭代点在可行域内时，在迭代过程中将阻止迭代点越出可形域。中将阻止迭代点越出可形域。惩罚项的作用是当迭代点在非可行域或不满足等式约惩罚项的作用是当迭代点在非可行域或不满足等式约束条件时，在迭代过程中将迫使迭代点逼近约束边界或束条件时，在迭代过程中将迫使迭代点逼近约束边界或等式约束曲面。等式约束曲面。
47、4.2分类分类内点法内点法-将迭代点限制在可行域内将迭代点限制在可行域内;外点法外点法-迭代点一般在可行域外迭代点一般在可行域外;混合法混合法-将外点法和内点法结合起来解将外点法和内点法结合起来解GPGP型问题型问题.按照惩罚函数在优化过程中迭代点是否可行，分为：按照惩罚函数在优化过程中迭代点是否可行，分为：内点法、外点法内点法、外点法及及混合法。混合法。第四节第四节 惩罚函数法惩罚函数法4.3 SUMT4.3 SUMT内点法内点法(内点惩罚函数法、障碍函数法内点惩罚函数法、障碍函数法)1.1.惩罚函数的构造惩罚函数的构造原问题原问题:s.t.可取可取式中式中,1)当当X X趋于趋于D D的边
48、界时的边界时,中间函数中间函数B(X)趋于无穷大趋于无穷大,故又称为故又称为障碍障碍(围墙围墙)函数函数;r称为罚因子称为罚因子，在逐次迭代中越来越小，在逐次迭代中越来越小4.3.1 4.3.1 基本思想：基本思想：内点法将新目标函数内点法将新目标函数(x,r)构筑在构筑在可行域可行域 D D 内内，随着惩罚因子，随着惩罚因子 r r(k)(k)的不断的不断递减递减，生成一系列新目，生成一系列新目标函数标函数 (x(xk k,r,r(k)(k)，在可行域，在可行域内内逐步迭代，产生的极值点逐步迭代，产生的极值点 x xk k*(r*(r(k)(k)序列从可行域序列从可行域内内部趋向原目标函数部
49、趋向原目标函数的约束最优点的约束最优点 x*x*。例例：求下述约束优化问题的最优点。：求下述约束优化问题的最优点。min.f(x)=xxR1s.tg(x)=1-x0X1*X2*X*4.3 SUMT4.3 SUMT内点法内点法(内点惩罚函数法、障碍函数法内点惩罚函数法、障碍函数法)4.3.2 4.3.2 惩罚函数的形式惩罚函数的形式：其中：惩罚（加权）因子其中：惩罚（加权）因子罚因子降低系数罚因子降低系数（罚因子递减速率）（罚因子递减速率）c：0c14.3 SUMT4.3 SUMT内点法内点法(内点惩罚函数法、障碍函数法内点惩罚函数法、障碍函数法)4.3.3 4.3.3 迭代步骤：迭代步骤：1.
50、选取合适的初始点选取合适的初始点x(0)，以及，以及r(0)、c、计算精度计算精度1、2，令，令k=0；2.构造惩罚（新目标）函数；构造惩罚（新目标）函数；3.调用无约束优化方法，求新目标函数的最优解调用无约束优化方法，求新目标函数的最优解xk*和和(xk,r(k)；4.判断是否收敛：运用终止准则判断是否收敛：运用终止准则前后两次无约束极小点之间的距离前后两次无约束极小点之间的距离相邻两点罚函数的相对误差相邻两点罚函数的相对误差若均满足，停止迭代，有约束优化问题的最优点为若均满足，停止迭代，有约束优化问题的最优点为x*=xk*；若有一个准则不满足，则令若有一个准则不满足，则令并转入第并转入第3