第五章+约束优化计算方法讲解课件.ppt

1、机械优化设计机械优化设计第五章 约束优化计算方法5.1 引言5.2 随机方向搜索法5.3 复合形法5.4 惩罚函数法机械优化设计机械优化设计5.1 引言引言 机械优化设计中的问题，大多数属于约束优化设机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为计问题，其数学模型为12min(),.()0(1,2,)()0(1,2,)Tnijfx xxst gimhjpxxxx机械优化设计机械优化设计 上一章讨论的都是无约束条件下非线性函数的寻上一章讨论的都是无约束条件下非线性函数的寻优方法，但在实际工程中大部分问题的变量取值都有优方法，但在实际工程中大部分问题的变量取值都有一定的限制，也就是

2、属于有约束条件的寻优问题。一定的限制，也就是属于有约束条件的寻优问题。与无约束问题不同，约束问题目标函数的最小值与无约束问题不同，约束问题目标函数的最小值是满足约束条件下的最小值，即是由约束条件所限定是满足约束条件下的最小值，即是由约束条件所限定的可行域内的最小值。只要由约束条件所决定的可行的可行域内的最小值。只要由约束条件所决定的可行域必是一个凸集，目标函数是凸函数，其约束最优解域必是一个凸集，目标函数是凸函数，其约束最优解就是全域最优解。否则，将由于所选择的初始点的不就是全域最优解。否则，将由于所选择的初始点的不同，而探索到不同的局部最优解上。在这种情况下，同，而探索到不同的局部最优解上。

3、在这种情况下，探索结果经常与初始点的选择有关。为了能得到全局探索结果经常与初始点的选择有关。为了能得到全局最优解，在探索过程中最好能改变初始点，有时甚至最优解，在探索过程中最好能改变初始点，有时甚至要改换几次。要改换几次。机械优化设计机械优化设计（1）直接法）直接法 直接法包括：网格法、复合形法、随机试验法、直接法包括：网格法、复合形法、随机试验法、随机方向法、可变容差法和可行方向法。随机方向法、可变容差法和可行方向法。（2）间接法）间接法 间接法包括：罚函数法、内点罚函数法、外点罚间接法包括：罚函数法、内点罚函数法、外点罚函数法、混合罚函数法、广义乘子法、广义简约梯度函数法、混合罚函数法、广

4、义乘子法、广义简约梯度法和约束变尺度法等。法和约束变尺度法等。根据求解方式的不同，约束优化设计问题可分为根据求解方式的不同，约束优化设计问题可分为:直直接解法、间接解法。接解法、间接解法。机械优化设计机械优化设计 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。间接解法中具有代表性的是惩罚函数法。直接解法的基本思想：在由m个不等式约束条件gu(x)0所确定的可行域内，选择一个初始点x(0)，然后确定一个可行搜索方向S，且以适当的步长沿S方向进行

5、搜索，取得一个目标函数有所改善的可行的新点x(1)，即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算：机械优化设计机械优化设计 x(k+1)x(k)+(k)S(k)(k=0,1,2,)逐步趋向最优解，直到满足终止准则才停止迭代。机械优化设计机械优化设计 直接解法通常适用于仅含不等式约束的问题，思路是在直接解法通常适用于仅含不等式约束的问题，思路是在m个不个不等式约束条件所确定的可行域内，选择一个初始点，然后决定可行等式约束条件所确定的可行域内，选择一个初始点，然后决定可行搜索方向搜索方向 S且以适当的步长且以适当的步长 ，进行搜索，得到一个使目标函数，进行搜

6、索，得到一个使目标函数值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上述搜索过程，直至满足收敛条件。述搜索过程，直至满足收敛条件。(1)()()()(0,1,2,)kkkkSkxxk()ks-步长步长-可行搜索方向可行搜索方向 可行搜索方向可行搜索方向:当设计点沿该方向作微量移动时，目标函数当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域。值将下降，且不会越出可行域。机械优化设计机械优化设计直接解法的原理简单，方法实用，其特点是：1）由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好的

7、设计点。2）若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局部最优解，当选择的初始点不同，而搜索到不同的局部最优解。3）要求可行域有界的非空集。机械优化设计机械优化设计a)可行域是凸集；b)可行域是非凸集机械优化设计机械优化设计间接解法的求解思路：将约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优化问题。121211,mljkjkxf xG gxH hx 新目标函数加权因子然后对新目标函数进行无约束极小化计算。机械优化设计机械优化设计机械优化设计机械优化设计5.2 随机方向法随机方向法 机械优化设计

8、机械优化设计随机方向法的基本思路：随机方向法的基本思路：在可行域内选择一个初始点，利用随机数的概率特性，产生若干个随机方向，并从中选择一个能使目标函数值下降最快的随机方向作为搜索方向s。从初始点x0出发，沿s 方向以一定步长进行搜索，得到新点X，新点x应满足约束条件且f(x)f(x0)，至此完成一次迭代。基本思路如图所示。随机方向法程序设计简单，搜索速度快，是解决小型机械优化问题的十分有效的算法。机械优化设计机械优化设计机械优化设计机械优化设计 机械优化设计机械优化设计5.3 复合形法复合形法机械优化设计机械优化设计 它的基本思路是在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的

9、目标函数值进行比较，找到目标函数最大的顶点（最坏点），然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形的形状没改变一次，就向最优点移动一步，直至逼近最优点。由于复合形的形状不必保持规则的图形，对目标函数和约束函数无特殊要求，因此这种方法适应性强，在机械优化设计中应用广泛。机械优化设计机械优化设计机械优化设计机械优化设计二二.初始复合形的构成初始复合形的构成1.复合形顶点数复合形顶点数K K的选择的选择建议建议:nKn21 小取大值小取大值,大取小值大取小值nn2)为避免降维为避免降维,K K应取大些应取大些;但过大但过大,计算量也大计算量也大.*1

10、)为保证迭代点能逼近极小点为保证迭代点能逼近极小点,应使应使1 nK机械优化设计机械优化设计2.初始复合形顶点的确定初始复合形顶点的确定 1)用试凑方法产生用试凑方法产生-适于低维情况适于低维情况;2)用随机方法产生用随机方法产生用随机方法产生用随机方法产生K K个顶点个顶点 先用随机函数产生先用随机函数产生 个随机数个随机数 ,然后变换到预定的区间然后变换到预定的区间 中去中去.n)10(iiiiibxaniiiiiiaabx,.,2,1,)(这便得到了一个顶点这便得到了一个顶点,要连续产生要连续产生K K个顶点个顶点.机械优化设计机械优化设计初始复合形生成的方法：1）由设计者决定k个可形点

11、，构成初始复合形。设计变量少时适用。2）由设计者选定一个可形点，其余的k-1个可形点用随机法产生。()iixar ba11LcjjxxL110.5LcLcxxxx机械优化设计机械优化设计3）由计算机自动生成初始复合形的所有顶点。二、复合形法的搜索方法1.反射1）计算复合形各顶点的目标函数值，并比较其大小，求出最好点XL、最坏点XH 及 次坏点XG，即:min1,2,.,:max1,2,.,:max1,2,.,jLLjHHjGGxf xf xjkxf xf xjkxf xf xjk jH机械优化设计机械优化设计2）计算除去最坏点XH 外的（k-1）个顶点的中心XC 111Lcjjxxk3）从统计

12、的观点来看，一般情况下，最坏点XH和中心点XC的连线方向为目标函数的下降方向。机械优化设计机械优化设计RCCHxxa xx4）判别反射点XR的位置 若XR 为可行点，则比较XR 和XH 两点的目标函数值，如果f(XR)=f(XH),则将缩小0.7倍，重新计算新的反射点，若仍不行，继续缩小，直至f(XR)f(XH)为止。若为非可行点，则将缩小0.7倍，直至可行为止。然后再重复可行点的步骤。2.扩张机械优化设计机械优化设计机械优化设计机械优化设计3.收缩机械优化设计机械优化设计机械优化设计机械优化设计三三.终止判别条件终止判别条件各顶点与好点函数值之差的均方根应不大于误差限各顶点与好点函数值之差的

13、均方根应不大于误差限2112)()()(1kjLjXFXFk机械优化设计机械优化设计比较复合形各顶点的函数值比较复合形各顶点的函数值，找出好点找出好点XL，坏点坏点XHXH=XR=0.5找出次坏点找出次坏点XSH，XH=XSH满足终止条件满足终止条件？X*=XL,F*=F(XL)结结 束束四四.复合形法的复合形法的 迭代步骤迭代步骤是是否否 KjjCHjXKX1,11)(),(RRHCCRXFFXXXX 给定给定K，ai,bi i=1,2,n产生初始复合形顶点产生初始复合形顶点Xj,j=1,2,K计算复合形各顶点的函数值计算复合形各顶点的函数值F(Xj),j=1,2,K是是是是是是否否否否否否

14、XRDDFRF(XH)机械优化设计机械优化设计方法特点方法特点机械优化设计机械优化设计 惩罚函数法是一种很广泛、很有效的间接解法。它的基本原理是将约束优化问题中的不等式和不等式约束函数经加权后，和原目标函数结合为新的目标函数惩罚函数。将约束优化问题转换为无约束优化问题。求解无约束优化问题的极小值，从而得到原约束优化问题的最优解。121211,mljkjkx r rf xrG gxrH hx加权转化项机械优化设计机械优化设计 将有约束的优化问题转化为无约束优化问题来求解。将有约束的优化问题转化为无约束优化问题来求解。前提：一是不能破坏约束问题的约束条件，二是使它归结前提：一是不能破坏约束问题的约

15、束条件，二是使它归结到原约束问题的同一最优解上去。到原约束问题的同一最优解上去。min(),.()01,2,()01,2,njkfRst gjmhklxxxx 构成一个新的目标函数，称为惩罚函数构成一个新的目标函数，称为惩罚函数()()()()121211(,)()()()mlkkkkjkijrrfrG grH hxxxx机械优化设计机械优化设计 从而有从而有()11lim()0mkikirG gx()21lim()0lkjkjrH hx()()()12lim(,)()0kkkkrrfxx惩罚项必须具有以下极限性质：惩罚项必须具有以下极限性质：求解该新目标函数的无约束极小值，以期得到原问题求解

16、该新目标函数的无约束极小值，以期得到原问题的约束最优解。按一定的法则改变罚因子的约束最优解。按一定的法则改变罚因子r1 和和r2的值，的值，求得一序列的无约束最优解，不断地逼近原约束优化问求得一序列的无约束最优解，不断地逼近原约束优化问题的最优解。题的最优解。机械优化设计机械优化设计 根据约束形式和定义的泛函及罚因子的递推方法根据约束形式和定义的泛函及罚因子的递推方法等不同，罚函数法可分为内点法、外点法和混合罚等不同，罚函数法可分为内点法、外点法和混合罚函数法三种。这种方法是函数法三种。这种方法是1968年由美国学者年由美国学者AVFiacco和和GPMcormick提出的，把不等式约束引提出

17、的，把不等式约束引入数学模型中，为求多维有约束非线性规划问题开入数学模型中，为求多维有约束非线性规划问题开创了一个新局面。创了一个新局面。机械优化设计机械优化设计1.内点法内点法 这种方法将新目标函数定义于可行域内，序列迭代点在这种方法将新目标函数定义于可行域内，序列迭代点在可行域内逐步逼近约束边界上的最优点。内点法只能用来求解可行域内逐步逼近约束边界上的最优点。内点法只能用来求解具有不等式约束的优化问题。具有不等式约束的优化问题。min()s.t.()0(1,2,)jfgjmxx对于只具有不等式约束的优化问题：对于只具有不等式约束的优化问题：转化后的惩罚函数形式为：转化后的惩罚函数形式为：(

18、)11(,)()()mkiirfrgxxx()1(,)()ln()mkiirfrgxxx或：或：机械优化设计机械优化设计rk是惩罚因子，它是一个由大到小且趋近于是惩罚因子，它是一个由大到小且趋近于0的正数列，的正数列，即即:01210kkrrrrr 由于内点法的迭代过程在可行域内进行，由于内点法的迭代过程在可行域内进行，“障碍项障碍项”的作用是阻止迭代点越出可行域。由的作用是阻止迭代点越出可行域。由“障碍项障碍项”的的函数形式可知，当迭代点靠近某一约束边界时，其值函数形式可知，当迭代点靠近某一约束边界时，其值趋近于趋近于0，而，而“障碍项障碍项”的值陡然增加，并趋近于无的值陡然增加，并趋近于无

19、穷大，好像在可行域的边界上筑起了一道穷大，好像在可行域的边界上筑起了一道“高墙高墙”，使迭代点始终不能越出可行域。显然，只有当惩罚因使迭代点始终不能越出可行域。显然，只有当惩罚因子子 时，才能求得在约束边界上的最优解。时，才能求得在约束边界上的最优解。0kr 机械优化设计机械优化设计 是：由于内点法只能在可行域是：由于内点法只能在可行域内迭代，而最优解很可能在可行域内靠近边界处或内迭代，而最优解很可能在可行域内靠近边界处或就在边界上，此时尽管泛函的值很大，但罚因子是就在边界上，此时尽管泛函的值很大，但罚因子是不断递减的正值，经多次迭代，接近最优解时，惩不断递减的正值，经多次迭代，接近最优解时，

20、惩罚项已是很小的正值。罚项已是很小的正值。机械优化设计机械优化设计例例5-2 用内点法求用内点法求2212min()fxxx1s.t.()10gx x的约束最优解。的约束最优解。解解:用内点法求解该问题时，首先构造内点惩罚函数用内点法求解该问题时，首先构造内点惩罚函数:22121(,)ln(1)krxxrxx用解析法求函数的极小值，运用极值条件：用解析法求函数的极小值，运用极值条件：1112220120krxxxxx 联立求解得：联立求解得：12112()2()0kkkrx rx r机械优化设计机械优化设计1112()2rx r时不满足约束条件时不满足约束条件 1()10g xx 应舍去应舍去

21、。无约束极值点为无约束极值点为*1*2112()2()0kkkrx rx r当当04r*0()2 0Tx r*0()4f x r01.2r*0()1.422 0Tx r*0()2.022f x r00.36r*0()1.156 0Tx r*0()1.336f x r00r*0()1 0Tx r*0()1f x r机械优化设计机械优化设计机械优化设计机械优化设计 1）初始点初始点x0的选取的选取 使用内点法时，初始点应选择一个离约束边界较远的可行点使用内点法时，初始点应选择一个离约束边界较远的可行点。如太靠近某一约束边界，构造的惩罚函数可能由于障碍项的。如太靠近某一约束边界，构造的惩罚函数可能由

22、于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难值很大而变得畸形，使求解无约束优化问题发生困难.2）惩罚因子初值惩罚因子初值r0的选取的选取 惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。无一般性的有效方法。对于不同的坏，甚至难以收敛到极值点。无一般性的有效方法。对于不同的问题，都要经过多次试算，才能决定一个适当问题，都要经过多次试算，才能决定一个适当 r0 3)惩罚因子的缩减系数惩罚因子

23、的缩减系数c的选取的选取 在构造序列惩罚函数时，惩罚因子在构造序列惩罚函数时，惩罚因子r是一个逐次递减到是一个逐次递减到0的的数列，相邻两次迭代的惩罚因子的关系为数列，相邻两次迭代的惩罚因子的关系为:机械优化设计机械优化设计1(1,2,.)rkrcrk 式中的式中的c称为惩罚因子的缩减系数，称为惩罚因子的缩减系数，c为小于为小于1的正数。的正数。一般的看法是，一般的看法是，c值的大小在迭代过程中不起决定性作值的大小在迭代过程中不起决定性作用，通常的取值范围在用，通常的取值范围在0.10.7之间。之间。4)收敛条件收敛条件*111*11(),(),(),kkkkkkrrrrrrxxx*12()(

24、)kkrrxx机械优化设计机械优化设计1）选择可行域内初始点）选择可行域内初始点X(0);2）选取初始罚因子）选取初始罚因子r(0)与罚因子降低系数与罚因子降低系数c，并置，并置K0；3）求）求min(x(K),r(K)解出最优点解出最优点xK*；4）当）当K=0转步骤转步骤5），否则转步骤），否则转步骤6）；）；5）KK+1，r(K+1)r(K)，xK+10 xK*，并转步骤，并转步骤3）；）；6）按终止准则判别，若满足转步骤）按终止准则判别，若满足转步骤7），否则转步骤），否则转步骤5）；）；7）输出最优解（）输出最优解（X*，F*），停止计算），停止计算。机械优化设计机械优化设计机械优化

25、设计机械优化设计2.外点法外点法 外点法是从可行域的外部构造一个点序列去逼外点法是从可行域的外部构造一个点序列去逼近原约束问题的最优解。外点法可以用来求解含近原约束问题的最优解。外点法可以用来求解含不等式和等式约束的优化问题。不等式和等式约束的优化问题。外点惩罚函数的形式为：外点惩罚函数的形式为：2211(,)()max0,()()pmijijrfrgrhxxxxr是惩罚因子是惩罚因子,012rrr 外点法的迭代过程在可行域之外进行，惩罚项的作用外点法的迭代过程在可行域之外进行，惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面。由惩罚项是迫使迭代点逼近约束边界或等式约束曲面。由惩罚项的形式可

26、知，当迭代点的形式可知，当迭代点x 不可行时，惩罚项的值大于不可行时，惩罚项的值大于0。机械优化设计机械优化设计 2211,max 0,mljkjkx rf xrgxrhx惩罚因子，它是由小到大。惩罚项 由惩罚项可知，当迭代点不可行时，惩罚项的值大于零。当迭代点离约束边界越远时，惩罚项愈大，这可看成是对迭代点不满足约束条件的一种惩罚。转化后的外点惩罚函数的形式为：机械优化设计机械优化设计 例例 用外点法求解下列有约束优化问题用外点法求解下列有约束优化问题3121min()(1)3fxxx1122s.t.()10()0gxgx xx解：惩罚函数为：解：惩罚函数为：32212121(,)(1)ma

27、x(0,1)max(0,)3rxxrxrxx312123221212121(1)()0,()0)31(1)(1)()()0,()0)3xxggxxrxrxggxxxx对上式求偏导，得对上式求偏导，得 机械优化设计机械优化设计212111(1)(1)2(1)xxxrx22112()rxx无约束目标函数极小化问题的最优解系列为：无约束目标函数极小化问题的最优解系列为：*21*2()141()0.5x rrrrx rr 当惩罚因子渐增时，由下表可看出收敛情况。当惩罚因子渐增时，由下表可看出收敛情况。机械优化设计机械优化设计*1x*2x*()r*()frr0.01-0.80975-50.00000-2

28、4.9650-49.99770.1-0.45969-5.00000-2.2344-4.947410.23607-0.500000.96310.1295100.83216-0.050002.30682.000110000.99800-0.000502.66242.6582108/38/3机械优化设计机械优化设计例6-6 用外点法求问题约束最优解。22121min.10f xxxst g xx 首先构造外点惩罚函数：222121,1x rxxrx11122221020 xrxxxx用解析法求解机械优化设计机械优化设计 1210rx rrxr求解得机械优化设计机械优化设计外点法惩罚因子按下式递增1k

29、krcr递增系数，通常取c=5-10。与内点法相反计算r0 值。选取的r0 太大则会使惩罚函数等值线偏心或变形，难以取得极小值。但r0太小，势必增加迭代次数。经验计算一般取r0=1，c=10常常可以取得满意的效果。机械优化设计机械优化设计内点法和外点法的简单比较内点法和外点法的简单比较 内点法的特点：内点法的特点：（1）始点必须为严格内点）始点必须为严格内点 （2）不适于具有等式约束的数学模型）不适于具有等式约束的数学模型 （3）迭代过程中各个点均为可行设计方案）迭代过程中各个点均为可行设计方案 （4）一般收敛较慢）一般收敛较慢 （5）初始罚因子要选择得当）初始罚因子要选择得当 （6）罚因子为

30、递减，递减率）罚因子为递减，递减率c有有0c1 机械优化设计机械优化设计3.混合法混合法 混合法是用内点法处理不等式约束，用外点法混合法是用内点法处理不等式约束，用外点法处理等式约束。可以用来求解含不等式和等式约处理等式约束。可以用来求解含不等式和等式约束的优化问题。束的优化问题。混合惩罚函数的形式为：混合惩罚函数的形式为：r是惩罚因子是惩罚因子,混合法具有内点法的特点，迭代过程在可行域之内混合法具有内点法的特点，迭代过程在可行域之内进行，参数的选择同内点法。进行，参数的选择同内点法。()()2()1111(,)()()()mlkkjkijirfrhgrxxxx01210kkrrrrr机械优化设计机械优化设计 这种同时处理等式和不等式约束的惩罚函数法称为混合惩罚函数法。混合惩罚函数法与前述内点法和外点法一样，也属于序列无约束极小化(SUMT)方法中的种方法。机械优化设计机械优化设计 惩罚函数法原理简单，算法易行，且惩罚函数法原理简单，算法易行，且分内点法、外点法和混合法三种，各有特点分内点法、外点法和混合法三种，各有特点，适用范围广。需要和有效的无约束优化方，适用范围广。需要和有效的无约束优化方法结合使用。因此该方法也是应用较多的有法结合使用。因此该方法也是应用较多的有约束优化方法。约束优化方法。