第4章 优化设计(约束优化)

1、 约束优化 解析法解析法 这类方法这类方法是需要利用函数的一阶偏导数甚至二阶偏导数是需要利用函数的一阶偏导数甚至二阶偏导数构造搜构造搜索方向索方向，如梯度法、共轭梯度法、牛顿法和变尺度法等。，如梯度法、共轭梯度法、牛顿法和变尺度法等。由于需要计算偏导数，故这类方法计算量大，但收敛较快。由于需要计算偏导数，故这类方法计算量大，但收敛较快。 直接法直接法 这类方法这类方法是仅利用迭代点的函数值来是仅利用迭代点的函数值来构造搜索方向构造搜索方向，如坐标轮换，如坐标轮换法、法、powell 共轭方向法和单纯形法等。共轭方向法和单纯形法等。由于只需要由于只需要计算函数值计算函数值，对于无法求导或求导困难

2、的函数，则这，对于无法求导或求导困难的函数，则这类方法就有突出的优越性，但是其收敛速度较慢。类方法就有突出的优越性，但是其收敛速度较慢。无约束优化无约束优化牛顿法与变尺度法的迭代公式(1)( )( )( )1( )()()kkkkkXXH Xf X(1)( )( )( )( )( )( )( )()kkkkkkkkXXSXAf X4.5 约束优化方法约束优化方法 工程中的大量优化设计问题，都是工程中的大量优化设计问题，都是，这类问题的一般这类问题的一般为：为： min (), . .()01, 2, , ()01, 2, , nuvf XXRstgXumhXvpn 求解这类问题的方法称求解这类

3、问题的方法称，所求得的所求得的称为称为。大致可归纳为大致可归纳为两大类两大类：（4-44） 直接解法直接解法间接解法间接解法这类方法的基本思想这类方法的基本思想：在约束的在约束的可行域内可行域内直接搜索出它的直接搜索出它的约束最优解约束最优解。属于这类方法的主要有属于这类方法的主要有：网格法，可行方向法，网格法，可行方向法，复合形法等。复合形法等。这类方法这类方法对于只有对于只有不等式约束不等式约束的优化的优化问题是有效的。问题是有效的。直接解法直接解法：这类方法这类方法的基本思想的基本思想：将复杂的将复杂的约束问题约束问题转化为一系列转化为一系列无约束优化问题无约束优化问题，即按一定原则即按

4、一定原则构造构造一个一个新的目标函数新的目标函数，并以它的，并以它的最最优解优解去逐步逼近去逐步逼近原约束问题原约束问题的的最优解最优解。约束问题通。约束问题通过这种方法的处理，就可以采用无约束优化方法求过这种方法的处理，就可以采用无约束优化方法求解。解。主要介绍：主要介绍：属于这类方法的主要有属于这类方法的主要有：消元法、简约梯度法、拉格消元法、简约梯度法、拉格朗日乘子法、惩罚函数法等。朗日乘子法、惩罚函数法等。 这类方法这类方法对于解决具有对于解决具有不等式约束不等式约束和和等式约束条件等式约束条件的的优化问题都有效。优化问题都有效。间接解法间接解法：4.5.1 复合形法复合形法 是适用于

5、求解具有不等式约束优化问题的一种是适用于求解具有不等式约束优化问题的一种直接算法直接算法在在 n 维优化设计空间的维优化设计空间的可行域可行域 D 内，内，构造构造具有具有 k 个顶点个顶点 的的多边形多边形(或或多面体多面体)称作称作复合形复合形。复合形复合形的的每个顶点每个顶点都代表一个都代表一个设计方案设计方案。然后然后计算复合形计算复合形各顶点的目标函数值并逐一进行比各顶点的目标函数值并逐一进行比较，取函数值最大者为较，取函数值最大者为最坏点最坏点，最小者为，最小者为最好点最好点。再以去掉再以去掉最坏点最坏点的其余各点的的其余各点的中心点中心点为为映射轴心映射轴心，在在最坏点最坏点和其

6、余各点的和其余各点的中心点中心点的连线上，的连线上，寻找寻找一个既满一个既满足约束条件，又使目标函数值有所改善的足约束条件，又使目标函数值有所改善的坏点映射点坏点映射点，并以并以该映射点该映射点替换替换坏点坏点而构成而构成新的复合形新的复合形。按照按照上述步骤上述步骤重复多次，不断地去掉重复多次，不断地去掉最坏点最坏点，这样不断，这样不断调整调整复合形的复合形的顶点，使顶点，使复合形复合形不断向不断向最优点最优点靠拢，最后搜索到靠拢，最后搜索到。(12 )nkn 该法的该法的基本思路：基本思路：对于对于二维问题二维问题，复合形法复合形法的搜索原理，如的搜索原理，如图图4-24所示。所示。图图4

7、-24 复合形法原理复合形法原理 因此，因此，实际就是通过对实际就是通过对复合形复合形各顶点的函数各顶点的函数值计算与比较，反复进行值计算与比较，反复进行点的映射点的映射与与复合形的收缩复合形的收缩，使之逐步逼近约，使之逐步逼近约束问题束问题最优解最优解的。的。 min(), . . ()0, (12,)nuf XXRstgXum， ，根据上述根据上述的的，对于求解，对于求解的优化问题时，采用的优化问题时，采用来求解，需分来求解，需分：第一步：第一步：是在设计空间的是在设计空间的内产生内产生 k个初始顶点构成一个不规则的个初始顶点构成一个不规则的多面体多面体，即生成，即生成初始复合形初始复合形

8、。一般取一般取为：为：。第二步第二步：进行：进行该复合形该复合形的的调优迭代计算调优迭代计算。 通过对通过对各顶点函数值各顶点函数值大小的比较，判断下降方向，不断用新的大小的比较，判断下降方向，不断用新的可可行好点行好点取代取代坏点坏点，构成，构成新的复合形新的复合形，使它逐步向，使它逐步向约束最优点约束最优点移动、收移动、收缩和逼近，直到满足一定的收敛精度为止。缩和逼近，直到满足一定的收敛精度为止。()0,1,2, uDX gXum12nkn 通常，通常，主要采用如下主要采用如下：生成生成，就是确定，就是确定 作为作为初始复合形初始复合形的的顶点顶点。 可由可由设计者设计者预先选择预先选择

9、k 个设计方案个设计方案，即人工构造一个，即人工构造一个初始复合形初始复合形。k 个顶点都个顶点都必须满足必须满足所有的约束条件。所有的约束条件。 ( )( )()jjiiiiiXarba)( jir,iia b在高维且多约束情况下，一般是人为地确定在高维且多约束情况下，一般是人为地确定一个初始可行点一个初始可行点 ，其，其余余 个顶点个顶点 可用可用随机法随机法产生，即产生，即(4-47)式中式中： 复合形顶点的标号复合形顶点的标号 ； 设计变量的标号设计变量的标号 ，表示点的坐标分量；，表示点的坐标分量； 设计变量设计变量 的解域或上下界；的解域或上下界； 0，1区间内服从均匀分布伪随机数

10、。区间内服从均匀分布伪随机数。( )(2,3, )jXjk(1,2, )in(2,3, )jkij(1)X1k (1,2, )iX in( )( )11qcjjXXq)1( qX)(cX(1)( )(1)( )0.5()qcqcXXXX(1)qX(1)qX(2)(3)( ),qqpXXX用上述方法用上述方法随机产生随机产生的的 k-1个顶点，虽然可以满足设计变量的个顶点，虽然可以满足设计变量的边边界约束条件界约束条件，但不一定是，但不一定是可行点可行点，所以还必须，所以还必须逐个检查逐个检查其可行性，并其可行性，并使其成为使其成为可行点可行点。设有设有 q(1qk) 个顶点个顶点满足全部约束条

11、件，满足全部约束条件，第第 q+1点点X(q+1)不是可行不是可行点，则先求出点，则先求出 q 个顶点个顶点的的中心点中心点然后将不满足约束条件的然后将不满足约束条件的点点向向中心点中心点 靠拢，即靠拢，即若新得到的仍在若新得到的仍在可行域外可行域外，则重复上，则重复上式式进行调整，直到点进行调整，直到点成为成为可行点可行点为止。为止。然后，然后，同样处理同样处理其余其余 诸点，使其全部进入诸点，使其全部进入可可行域内行域内，从而构成一个，从而构成一个所有顶点所有顶点均在均在可行域内可行域内的初始复合形。的初始复合形。 初始复合形生成后，其初始复合形生成后，其按按下述步骤下述步骤进行：进行：(

12、1) 计算计算初始复合形各顶点的函数值，初始复合形各顶点的函数值， 选出选出好点、坏点、次坏点：好点、坏点、次坏点： ( )( )( )()()( )()()( ): ()min (), 1,2, : ()max (), 1,2, : ()max (), 1,2, ; LLjHHjGGjXf Xf XjkXf Xf XjkXf Xf XjkjH(2) 计算除计算除坏点坏点X(H) 外其余外其余k-1 个顶点的个顶点的几何中心点几何中心点： 1( )( )11, 1kSjjXXjHk 并并检验检验X(S)点点是否在可行域内。是否在可行域内。 如果如果X(S) 是是可行点可行点，则执行下步，则执行

13、下步(3) ；否则转第；否则转第(4)(4)步。步。 (3) 沿沿X(H) 和和 X(S) 连线方向连线方向求映射点求映射点X(R) ()( )( )()()RSSHXXXX 式中，式中， 称称映射系数映射系数，常取，常取 。 然后，检验然后，检验 X(R) 可行性。可行性。 1.3(4) 若若X(S) 在可行域外在可行域外，此时，此时D可能是可能是非凸集非凸集，如，如图图4-d所示。所示。 此时此时利用利用X(S) 和和X(L) 重复确定一个区间，重复确定一个区间， 在在此区间内此区间内重新随机重新随机产生产生 k 个顶点构成个顶点构成复合形复合形。图图4-d可行域为非凸集可行域为非凸集 重

14、新构成重新构成后，重复第重复第(1)、(2)步，直到成为步，直到成为为止。为止。 )()(LiiSiiXbXa(1,2, )in( )( )( )( )(),LSLSiiXXXX即点在的右边 则取则取 )()(SiiLiiXbXa(1,2, )in)(SX如如所示：所示：( )( )( )( )(),1,2, ,LSLSiiXXXXin即点在的左边 则取则取(5) 计算计算映射点映射点的目标函数值的目标函数值 f(X(R)，若若 f(X(R) f(X(H) ，则将则将映射系数映射系数减半减半，重新计算，重新计算映射点映射点。如果新的如果新的映射点映射点X(R)既为既为可行点可行点，又满足，又满

15、足 f(X(R) c 0；)()1(kkcrr)(1XgGumu为以为以 为函数的复合函数，为函数的复合函数，或称与不等式约束有关的或称与不等式约束有关的。 )(Xgu然后对然后对按按，即，即(k)*(k)min ( , )XrX在求解过程中，针对不同的在求解过程中，针对不同的 ，就有一个与之对应的，就有一个与之对应的极小值极小值点点 ，随着，随着 的减小，使求得的的减小，使求得的 也逐步向原问也逐步向原问题的题的逼近。逼近。所以所以该方法该方法也称为也称为 “序列无约束极小化序列无约束极小化” 方法。方法。( )kr*( )*( )()kkXXr( )kr *( )kX对于对于，要求保证：要

16、求保证： (1)初始点初始点 和所求得的序列最优点和所求得的序列最优点 ，都应是，都应是可行点可行点； (2)求解到最后，求解到最后，序列最优点序列最优点 应逼近应逼近*。)0(X *( )kX *( )kX对于不等式约束优化问题，根据对于不等式约束优化问题，根据罚函数法罚函数法的基本思想，的基本思想， 将将罚函数罚函数定义在可行域内，可构造其定义在可行域内，可构造其内点罚函数内点罚函数的的一般形式一般形式为为( )( )11(,)()()mkkuuX rf XrgX或或 (4-56) (4-55) ( )( )1(,)()ln()mkkuuX rf XrgX式中，式中，惩罚因子惩罚因子 ，是

17、一，是一递减的正数序列递减的正数序列，即，即 (0)(1)(2)( )krrrr( )0krlim0k且且 。 理解 由式(4-55)和式(4-56)可以看出，对于给定的某一惩罚因子h，当点在可行域内时，两种形式的惩罚项的值均大于零，而当点向约束边界靠近时，两种形式的惩罚项的值迅速增大并趋于无穷。这就是说，只要初始点取在可行域内，迭代点就不可能越出可行域的边界。可行性 其次，两种形式的惩罚项的大小也受惩罚因子的影响。当惩罚因子逐渐减小并趋于零时，对应惩罚项的值也逐渐减小并趋子零，惩罚函数的值和目标函数的值逐渐接近并趋于相等，惩罚函数的极小点逼近于约束问题的最优点。可见，惩罚函数的极小点是从可行

18、域内向最优点逼近的。)0(X)0(r( )( )11(,)()()mkkuuX rf XrgX(3) 构造构造惩罚函数惩罚函数( )min (,)kX r*( )()kX r(1)( )kkXX(1)( )( )()()()kkkf Xf Xf X*( )*( )(), ()kkXXrff Xr*, Xf (4) ) 求解求解无约束优化问题无约束优化问题 ，得，得 ； (5) 进行进行收敛判断，若满足收敛判断，若满足或或则令则令 ，停止停止迭代计算，迭代计算，输出输出最优解最优解 ；否则转下步；否则转下步； (1) 在在可行域内可行域内确定确定一个初始点一个初始点 ； (2) 给定给定初始罚因

19、子、惩罚因子初始罚因子、惩罚因子递减系数递减系数C 和和收敛精度收敛精度；置置 k = 0；如下：如下：(6) 取取 ，以，以 ，置置 转步骤转步骤 (3)继续迭代。继续迭代。 (1)( )kkrCr(0)*( )()kXXr1kk，见，见图图2-36。 在在内点法内点法中，中，初始罚因子初始罚因子的选择很重要。的选择很重要。根据经验，一般可取根据经验，一般可取 =1 50，但多数情况是取，但多数情况是取=1。也有建议按初始惩罚项作用与初始目标函数作用相近原则来确定值也有建议按初始惩罚项作用与初始目标函数作用相近原则来确定值，即，即)0(r)0(r)0(r)0(r(0)(0)1()1()muu

20、f XrgX 一般取为：一般取为：C = 0.10.5，常取，常取0.1。 初始罚因子和递减系数的选择初始罚因子和递减系数的选择：图图2-36 内点法程序框图内点法程序框图 内点法例题内点法例题例例4-b 试用试用求解如下优化问题求解如下优化问题：1min ( ), . . ( )10f xxxRstg xx 解解： 此题的此题的为：为： 。根据根据的基本思想，首先构造的基本思想，首先构造，按，按可写出：可写出：*1 , ( ) 1xf x( )( )( )11( ,)( )( )1kkkx rf xrxrg xx可以看出可以看出由由两部分两部分组成，即组成，即 ，其中：其中：( )( ,)k

21、x r( )( )21111kkrrxx1( )f xx12即：是即：是原目标函数原目标函数，为一直线；，为一直线；是一族是一族倒数曲线倒数曲线，当，当 。则则则构成则构成 曲线曲线，如，如下图下图4-26 所示。所示。12( )( ,)kx r21 , x时图图4-26 内点法的求解内点法的求解对对 求导求导并令并令，即，即( )( ,)kx r( )( )( )2( ,)11101(1)kkkdx rdxrrdxdxxx 可求得其可求得其无约束极值点无约束极值点：惩罚函数值惩罚函数值为：为：*( )( )( )(),)12kkkx rrr 当选用不同的当选用不同的惩罚因子惩罚因子 时，可得

22、到不同的时，可得到不同的及及。取递减数列，由上式取递减数列，由上式可得可得序列如下：序列如下：( )kr*( )*( )() (,)kkx rx r和( )*( )*( ) 1, 0.1, 0.01, 0.001, 0 () 2, 1.316, 1.10, 1.0316, 1(,)3, 1.632, 1.20, 1.0630, 1kkkrx rx r表示出取值不同时所得到的表示出取值不同时所得到的 逐步逼逐步逼近近的情形。的情形。( )kr*x( )kr*( ) ()kx r kkrrx1*由由上图上图可以看出，当可以看出，当惩罚因子惩罚因子为一个递减数列时，为一个递减数列时，无约束极值点无约

23、束极值点 离离约束最优解约束最优解愈来愈近，愈来愈近，当即得到了真正的当即得到了真正的约束最优解约束最优解。此时，此时，罚函数罚函数也收敛于也收敛于原目标函数原目标函数的的最优值最优值，即，即*x( )*( )*0 () 1,kkrx rx时,*( )( )*(),)()1kkx rrf x*( ) ()kx r2. 外点外点罚函数罚函数法法 适用于具有适用于具有和和。 搜索策略与搜索策略与内点罚函数法内点罚函数法相似，不同点是将相似，不同点是将惩罚函数惩罚函数的定的定义域为非可行域，即在义域为非可行域，即在可行域外可行域外进行搜索。进行搜索。( )( )2u1(,)()max0, g (X)

24、mkkuX rf Xr()0 (1,2,) ugXum取取外点罚函数外点罚函数的形式为的形式为其其惩罚项的含义惩罚项的含义如下：如下：u2u21u0, g (X)0max0, g ()() g (X) 0 mujXgX当当(4-57) 对于对于不等式约束问题不等式约束问题：上式上式说明说明:当当 X 是是可行点可行点时，时，惩罚项惩罚项为零。为零。 也就是说当极小化惩罚函数也就是说当极小化惩罚函数 时，时，X由不可行点迭代成可由不可行点迭代成可行点，此时，行点，此时，惩罚函数惩罚函数将与将与原目标函数原目标函数 等价等价。 此时惩罚函数的此时惩罚函数的最优可行点最优可行点，也将是原目标函数的，

25、也将是原目标函数的最优点最优点。( )(,)kX r()f X外点罚函数中的外点罚函数中的罚因子罚因子是一递增数列，即是一递增数列，即 (k)()2()1()0(r lim ,kkrrrr对于对于，取，取为为( )( ) 21(,)()()pkkvvX rf Xrh X对于对于同时具有同时具有不等式和等式约束问题不等式和等式约束问题，其，其罚函数的表达式罚函数的表达式为为(4-57b) (4-57a) 在在外点罚函数法外点罚函数法中，为保证中，为保证罚因子罚因子 为递增数列，取为递增数列，取)(kr(1)( )kkrc r式中：式中：c 为递增系数，为递增系数，c 1。的的与与内点法内点法基本相同。基本相同。pvvmuukkXhXgrXfrX1221)()(, 0max()(),(解：构造解