有约束优化方法

1、第五章 有约束优化方法 5-1 5-1 引言引言5-2 5-2 随机方向法随机方向法5-3 5-3 复合形法复合形法5-4 5-4 可行方向法可行方向法 5-5 5-5 惩罚函数法惩罚函数法5-6 5-6 序列二次规划法序列二次规划法5-1 5-1 引言引言 机械优化设计中的问题，大多数属于约束优化设机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为计问题，其数学模型为min ( ),. .( )01,2,( )01,2,njkfRst gjmhklxxxx 上一章讨论的都是无约束条件下非线性函数的寻上一章讨论的都是无约束条件下非线性函数的寻优方法，但在实际工程中大部分问题的变量取

2、值都有优方法，但在实际工程中大部分问题的变量取值都有一定的限制，也就是属于有约束条件的寻优问题。一定的限制，也就是属于有约束条件的寻优问题。 与无约束问题不同，约束问题目标函数的最小值与无约束问题不同，约束问题目标函数的最小值是满足约束条件下的最小值，即是由约束条件所限定是满足约束条件下的最小值，即是由约束条件所限定的可行域内的最小值。只要由约束条件所决定的可行的可行域内的最小值。只要由约束条件所决定的可行域必是一个凸集，目标函数是凸函数，其约束最优解域必是一个凸集，目标函数是凸函数，其约束最优解就是全域最优解。否则，将由于所选择的初始点的不就是全域最优解。否则，将由于所选择的初始点的不同，而

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

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

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

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

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

8、机方向作为搜索方向d。从初始点x0出发，沿d 方向以一定步长进行搜索，得到新点X，新点x应满足约束条件且f(x)f(x0)，至此完成一次迭代。基本思路如图所示。随机方向法程序设计简单，搜索速度快，是解决小型机械优化问题的十分有效的算法。一、随机数的产生下面介绍一种常用的产生随机数的数学模型3536371232 ,2 ,2rrr首先令取r=2657863，按一下步骤计算：令5rr若3rr则3rrr若则2rrr2rr1rrr1rr若则则1/qr r（0，1）之间的随机数在任意(a,b)区间内的随机数()xaq ba二、初始点的选择 随机方向法的初始点x0必须是一个可行点，既满足全部不等式约束条件。

9、初始点可以通过随机选择的方法产生。1）输入设计变量的下限值和上限值，即iiiaxb2）在区间（0，1）内产生n个伪随机数iq3）计算随机点x的各分量()iiiiixaq ba4）判别随机点x是否可行，若随机点可行，用x代替x0为初始点；若非可行点，转到步骤2）重新产生随机点，只到可行为止。三、可行搜索方向的产生产生可行随机方向的方法：从k个随机方向中， 选取一个较好的方向。其计算步骤为：121211.jjjnjjinirrerr jir1）在(-1,1)区间内产生伪随机数，得随机单位向量je2)取一试验步长a0，按下式计算k个随机点00jjxxa e3）检验k个随机点是否为可行点，除去非可行点

10、，计算余下的可行点的目标函数值，比较其大小，选出目标函数最小的点XL 。4)比较XL 和X0两点的目标函数值，若f(XL) f(X0)，则步长0 缩小，专步骤1）重新计算，直至f(XL) f(X0)为止。如果0 缩小到很小，仍然找不到一个XL，使f(XL) f(X0)则说明X0是一个局部极小点，此时可更换初始点，转步骤1）。产生可行搜索方向的条件为：00min1,2,.,LjLjLgxf xf xjkf xf x则可行搜索方向为：0Ldxx四、搜索步长的确定步长由加速步长法确定。 X0=X, F0=F=0, F0=F(X0)F=F（X）j =1K=K+1三三. .随机方向法随机方向法 的迭代步

11、骤的迭代步骤是是K=0, j=0SXX0产生随机方向产生随机方向=0.5否否FF0j =0K m结结 束束X*=X0 ,F*=F0是是否否是是否否是是否否XDD是是否否,00mX给定内点)(0步长终止误差限的方向数在一迭代点处允许产生初始步长；m；)0, 1()(否则为沿该方向前进过为计数器方向数计数器jK5-3 5-3 复合形法复合形法 它的基本思路是在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，找到目标函数最大的顶点（最坏点），然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形的形状没改变一次，就向最优点移动一

12、步，直至逼近最优点。 由于复合形的形状不必保持规则的图形，对目标函数和约束函数无特殊要求，因此这种方法适应性强，在机械优化设计中应用广泛。二二. .初始复合形的构成初始复合形的构成1. 复合形顶点数复合形顶点数K K的选择的选择建议建议: :nKn21 小取大值小取大值, 大取小值大取小值nn2) 为避免降维为避免降维, K K应取大些应取大些; 但过大但过大, 计算量也大计算量也大.* 1) 为保证迭代点能逼近极小点为保证迭代点能逼近极小点, 应使应使1 nK2. 初始复合形顶点的确定初始复合形顶点的确定 1) 用试凑方法产生用试凑方法产生-适于低维情况适于低维情况; ;2) 用随机方法产生

13、用随机方法产生用随机方法产生用随机方法产生K K个顶点个顶点 先用随机函数产生先用随机函数产生 个随机数个随机数 , ,然后变换到预定的区间然后变换到预定的区间 中去中去. .n) 10(iiiiibxaniiiiiiaabx,.,2,1,)(这便得到了一个顶点这便得到了一个顶点, ,要连续产生要连续产生K K个顶点个顶点. .初始复合形生成的方法：1）由设计者决定k个可形点，构成初始复合形。设计变量少时适用。2）由设计者选定一个可形点，其余的k-1个可形点用随机法产生。()iixar ba11LcjjxxL110.5LcLcxxxx 将非可行点调入可行域内将非可行点调入可行域内) ) 检查已

14、获得的各顶点的可行性检查已获得的各顶点的可行性, ,若无一可行若无一可行, ,则重新产生随机点则重新产生随机点; ;若有若有q q个可行个可行, ,则转下步则转下步. .) ) 计算计算q q个可行点点集的几何中心个可行点点集的几何中心) ) 将非可行点逐一调入可行域内将非可行点逐一调入可行域内. .qjjsXqX1)()(1)(5 . 0)()1()()1(sqsqXXXX 若仍不可行若仍不可行, , 则重则重复此步骤复此步骤, , 直至进入直至进入可行域为止可行域为止. .)(sX) 1( qX3）由计算机自动生成初始复合形的所有顶点。二、复合形法的搜索方法1.反射1）计算复合形各顶点的目

15、标函数值，并比较其大小，求出最好点XL、最坏点XH 及 次坏点XG，即:min1,2,.,:max1,2,.,:max1,2,., ,jLLjHHjGGxf xf xjkxf xf xjkxf xf xjk jH2）计算除去最坏点XH 外的（k-1）个顶点的中心XC 111Lcjjxxk3）从统计的观点来看，一般情况下，最坏点XH和中心点XC的连线方向为目标函数的下降方向。RCCHxxa xx4）判别反射点XR的位置 若XR 为可行点，则比较XR 和XH 两点的目标函数值，如果f(XR) =f(XH),则将缩小0.7倍，重新计算新的反射点，若仍不行，继续缩小，直至f(XR) f(XH)为止。

16、若为非可行点，则将缩小0.7倍，直至可行为止。然后再重复可行点的步骤。2.扩张3.收缩三三. 终止判别条件终止判别条件各顶点与好点函数值之差的均方根应不大于误差限各顶点与好点函数值之差的均方根应不大于误差限2112)()()(1kjLjXFXFk 不是十分可靠不是十分可靠, 可改变可改变 重作重作, 看结果是否相同看结果是否相同.比较复合形各顶点的函数值比较复合形各顶点的函数值，找出好点找出好点XL，坏点坏点XHXH=XR=0. .5找出次坏点找出次坏点XSH ，XH=XSH满足终止条件满足终止条件？X*=XL ,F*=F(XL)结结 束束四四. 复合形法的复合形法的 迭代步骤迭代步骤是是否否

17、 KjjCHjXKX1,11)(),(RRHCCRXFFXXXX 给定给定K，ai , bi i =1,2,n产生初始复合形顶点产生初始复合形顶点Xj , j=1,2,K计算复合形各顶点的函数值计算复合形各顶点的函数值F(Xj), j=1,2,K是是是是是是否否否否否否XRDDFRF(XH)仅具有反射策略的复合形法 令：令：X(4)= X(0)+(X(0)-X(H) 称称X(4)为映射点，记为为映射点，记为X(R)，为映射系数，通常取为映射系数，通常取=1.3，可根据实际情况进行缩减。，可根据实际情况进行缩减。 取次好点和好点连线的中点为取次好点和好点连线的中点为X(0)。 一般情况下，映射点

18、的函数值比坏点的函数值一般情况下，映射点的函数值比坏点的函数值要小，即要小，即F(X(R) F(X(H)。若满足可行域，则用。若满足可行域，则用X(R)代代替替X(H)构成新的复合形。如此反复迭代直到找到最优解构成新的复合形。如此反复迭代直到找到最优解。 在可行域内任选三个初始点在可行域内任选三个初始点X(1)、X(2)、X(3)，连接这，连接这三点形成一个三角形，此三角形称为初始复合形。计算各三点形成一个三角形，此三角形称为初始复合形。计算各个顶点函数值个顶点函数值F(X(1)、 F(X(2)、F(X(3)，找出最大值，记，找出最大值，记为坏点为坏点X(H)。最小值，记为最好点。最小值，记为

19、最好点X(L)。在次好点和好点。在次好点和好点连线与坏点反向一侧的各点应具有较小的目标值。连线与坏点反向一侧的各点应具有较小的目标值。 在迭代过程中，按映射系数在迭代过程中，按映射系数=1.3得到的映射点得到的映射点，不一定满足适用性和可行性，如出现此情况，将，不一定满足适用性和可行性，如出现此情况，将映射系数减半，映射系数减半， 重新取得重新取得X(R)， 使它满足适用性和使它满足适用性和可行性。可行性。一、初始复合形的构成一、初始复合形的构成 复合形的顶点复合形的顶点K通常取通常取n+1K2n个。对于维数较个。对于维数较低的优化问题，由于顶点数目较少，可试凑几个可行点低的优化问题，由于顶点

20、数目较少，可试凑几个可行点作为复合形的顶点。对于维数较高的问题，采用随机方作为复合形的顶点。对于维数较高的问题，采用随机方法，先产生法，先产生K个随机点，然后再把非可行点逐一调入可行个随机点，然后再把非可行点逐一调入可行域内。域内。1、产生、产生K个随机点个随机点 xi= ai +i (bi - ai) i=1,2,.,ni为（为（0，1）区间内产生的均匀分布的随机数，需要）区间内产生的均匀分布的随机数，需要n个个随机数产生一个点随机数产生一个点X (1)。同样，产生其它的随机点。同样，产生其它的随机点X (2)、X (3)、X (K)。2、将非可行点调入可行域、将非可行点调入可行域 将产生的

21、将产生的K个随机点进行判断是否在可行域内，个随机点进行判断是否在可行域内，重新排列，将可行点依次排在前面，如有重新排列，将可行点依次排在前面，如有q个顶点个顶点X (1)、X (2)、X (q)是可行点，其它是可行点，其它K-q个为非可行点。对个为非可行点。对X (q+1)，将其调入可行域的步骤是：，将其调入可行域的步骤是： （1）计算）计算q个点集的中心个点集的中心X (s)； （2）将第）将第q+1点朝着点点朝着点X (s)的方向移动，按下式产的方向移动，按下式产生新的生新的X (q+1)，即，即 X(q+1)= X(s)+0.5 (X(q+1)X(s) 这个新点这个新点X(q+1)实际就

22、是实际就是X(s)与原与原X(q+1)两点连线的中点两点连线的中点，如图。若新的，如图。若新的X(q+1)点仍为非可行点，按上式再产生点仍为非可行点，按上式再产生X(q+1)，使它更向，使它更向X(s)靠拢，最终使其成为可行点。靠拢，最终使其成为可行点。 按照这个方法，同样使按照这个方法，同样使X (q+2)、X (q+3)、X (K)都变为可行点，这都变为可行点，这K个点就构成了初始复合形。个点就构成了初始复合形。二、复合形法的迭代步骤二、复合形法的迭代步骤（1）构造初始复合形；）构造初始复合形；（2）计算各顶点的函数值）计算各顶点的函数值F(X(j)，j=1,2,.,K。选出好点。选出好点

23、X(L)和坏点和坏点X(H)。( )( )( )()()( ):()min (),1,2,:()max (),1,2,LLjHHjXF XF XjKXF XF XjK（3）计算坏点外的其余各顶点的中心点）计算坏点外的其余各顶点的中心点X(0)。( )011,1KjjXXjHk（4）计算映射点）计算映射点X(R) 检查检查X(R)是否在可行域内。若是否在可行域内。若X(R)为非可行点，将映为非可行点，将映射系数减半后再按上式改变映射点，直到射系数减半后再按上式改变映射点，直到X(R)进入可行进入可行域内为止。域内为止。()(0)(0)()()RHXXXX（5）构造新的复合形）构造新的复合形 计算

24、映射点的函数值计算映射点的函数值F(X(R)，并与坏点的函数值，并与坏点的函数值F(X(H)比较，可能存在两种情况：比较，可能存在两种情况： 1）映射点优于坏点）映射点优于坏点 F(X(R) F(X(H) 在此情况，用在此情况，用X(R)代替代替X(H)，构成新的复合形。，构成新的复合形。 若经过多次的映射系数减半，仍不能使映射点由于坏若经过多次的映射系数减半，仍不能使映射点由于坏点，则说明该映射方向不利，此时，应改变映射方向，点，则说明该映射方向不利，此时，应改变映射方向，取对次坏点取对次坏点()()( ):()max (),1,2,SHSHjXF XF XjK jH的映射。的映射。( )0

25、1()(0)(0)()1,1()KjjRSHXXjSHkXXXX再转回本步骤的开始处，直到构成新的复合形。再转回本步骤的开始处，直到构成新的复合形。2）映射点次于坏点）映射点次于坏点 F(X(R) F(X(H) 这种情况由于映射点过远引起的，减半映射系数，这种情况由于映射点过远引起的，减半映射系数，若有若有F(X(R) F(X(H)，这又转化为第一种情况。，这又转化为第一种情况。(6)判断终止条件判断终止条件1)各顶点与好点函数值之差的均方根值小于误差限，即各顶点与好点函数值之差的均方根值小于误差限，即1( )( )2211 ()() KjLjF XF XK2）各顶点与好点的函数值之差的平方和

26、小于误差限，即）各顶点与好点的函数值之差的平方和小于误差限，即 3）各顶点与好点函数值差的绝对值之和小于误差限，即）各顶点与好点函数值差的绝对值之和小于误差限，即 如果不满足终止迭代条件，则返回步骤如果不满足终止迭代条件，则返回步骤2继续进行下继续进行下一次迭代；否则，可将最后复合形的好点一次迭代；否则，可将最后复合形的好点X(L)及其函数值及其函数值F(X(L)作为最优解输出。作为最优解输出。( )( )1()()KjLjF XF X( )( )21 ()()KjLjF XF X方法特点方法特点 可行方向是求解大型不等式约束优化问题的主要方可行方向是求解大型不等式约束优化问题的主要方法之一。

27、法之一。 基本思想：这种方法的基本原理是在可行域内选择基本思想：这种方法的基本原理是在可行域内选择一个初始点一个初始点 ，当确定了一个可行方向，当确定了一个可行方向d和适当的步长和适当的步长后，按式后，按式:0 x5-4 5-4 可行方向法可行方向法1(0,1,2,)kkkkkxxd 进行迭代计算进行迭代计算,迭代点既不超出可行域迭代点既不超出可行域,又使目标函又使目标函数的值有所下降。在不断调整可行方向的过程中，数的值有所下降。在不断调整可行方向的过程中，使迭代点逐步逼近约束最优点。使迭代点逐步逼近约束最优点。可行方向法的搜索策略？可行方向法的搜索策略？即：即：11()0()()kukkgF

28、FxxxOx1x2Ox1x2a) 极值点处于多角形的某一顶点上b) 极值点处于等值线的中心c) 极值点处于约束曲线与等值线的切点上d) 极值点处于两个约束曲线的交点上xg1 (x)0g2 (x)0g3 (x)0 xg2(x)0g3(x)0g4(x)0g1(x)0g2(x)0Ox1x2Ox1x2xg2(x)0 xg1(x)0g1(x)01.可行方向法的搜索策略可行方向法的搜索策略 第一步迭代都是从可行的初始点第一步迭代都是从可行的初始点 出发，沿点的出发，沿点的负梯度负梯度 方向，将初始点移动到某一个约方向，将初始点移动到某一个约束面（只有一个起作用的约束时）上束面（只有一个起作用的约束时）上,

29、 或约束面的交或约束面的交集（有几个起作用的约束时）上。集（有几个起作用的约束时）上。 0 x00()f dx 根据约束函数和目标函数的不同性状，分别采用根据约束函数和目标函数的不同性状，分别采用以下几种策略继续搜索。以下几种策略继续搜索。0 x1x2x0 xkdkxk+1g2(x)=0g1(x)=00()fx1 新点在可行域内的情况新点在可行域内的情况 0 x1x2x0 xkdkxk+1g2(x)=0g1(x)=0g3(x)=00()fx2 新点在可行域外的情况新点在可行域外的情况 0 x1x2x0 xkxk+1g2(x)=0g1(x)=0g3(x)=00()fx 3 沿线性约束面的搜索沿线

30、性约束面的搜索 0 x1x2x0 xkxk+1g2(x)=0g1(x)=0g3(x)=00()fx1( )fxx 4 沿非线性约束面的搜索沿非线性约束面的搜索 2.产生可行方向的条件产生可行方向的条件 可行方向是指沿该方向作微小移动后，所得到的可行方向是指沿该方向作微小移动后，所得到的新点是可行点，且目标函数值有所下降。新点是可行点，且目标函数值有所下降。 可行方向应满足两个条件可行方向应满足两个条件: (1)可行可行; (2)下降下降。 1）可行条件）可行条件 方向的可行条件是指沿该方向作微小移动后，所得到方向的可行条件是指沿该方向作微小移动后，所得到的新点为可行点。的新点为可行点。 dkx

31、k()kg xdkxk1()kg x122()kg xg1(x)=0g2(x)=0()0kTkg xd()0(1,2, )kTkjjJgxd2）下降条件）下降条件 方向的下降条件是指沿该方向作微小移动后，所得方向的下降条件是指沿该方向作微小移动后，所得新点的目标函数值是下降的。新点的目标函数值是下降的。 ()0kTkfxddkxkg1(x)=0g2(x)=00()fx满足可行和下降条件，即式满足可行和下降条件，即式:()0(1,2, )kTkjjJgxd()0kTkfxddkxk1()kg x122()kgxg1(x)=0g2(x)=0可行下降方向区0()fx 位于约束位于约束曲面在点曲面在点

32、xk的切线和目的切线和目标函数等值标函数等值线在点线在点xk的的切线所围成切线所围成的扇形区内，的扇形区内，该扇形区称该扇形区称为可行下降为可行下降方向区方向区。 同时成立的方向称可行方向。同时成立的方向称可行方向。3.可行方向的产生方法可行方向的产生方法 满足可行、下降条件的方向位于可行下降扇满足可行、下降条件的方向位于可行下降扇形区内，在扇形区内寻找一个最有利的方向作为形区内，在扇形区内寻找一个最有利的方向作为本次迭代的搜索方向。本次迭代的搜索方向。 （1 1）优选方向法）优选方向法 ()0(1,2, )kTkjjJgxd()0kTkfxd由条件：由条件：求一个以搜索方向求一个以搜索方向d

33、为设计变量的约束优化问题为设计变量的约束优化问题 min ()kTkfxd()0(1,2, )kTkjjJgxd()0kTkfxds.t.1kd各函数均为设计变量各函数均为设计变量dk的线性函的线性函数，因此该式为一个（线性）数，因此该式为一个（线性）规划问题。规划问题。 当当xk点目标函数的负梯度方向不满足可行条件时点目标函数的负梯度方向不满足可行条件时，可将，可将 方向投影到约束面（或约束面的交集方向投影到约束面（或约束面的交集）上，得到投影向量）上，得到投影向量 dk。 ()kfxxkdkg g1 1( (x)=0)=0g g2 2( (x)=0)=0g g3 3( (x)=0)=0g

34、g4 4( (x)=0)=0()kf x()/()kkkff dPxPxP P投影算子，投影算子，为为nX Xn阶矩阵阶矩阵 1TTPIG G GGG 起作用约起作用约束函数的梯度矩束函数的梯度矩阵，阵，nX XJ阶矩阵；阶矩阵； 12(),(),()kkkJggg Gxxx（2）梯度投影法）梯度投影法 4.4.步长的确定步长的确定1(0,1,2,)kkkkkxxd 确定的确定的步长步长应使新的迭代点为可行点，且目标函应使新的迭代点为可行点，且目标函数具有最大的下降量数具有最大的下降量约束一维搜索。约束一维搜索。1 1）取最优步长）取最优步长 从从xk点出发，沿点出发，沿dk方向进行一维最优方

35、向进行一维最优化搜索，取得最优步长，计算新点化搜索，取得最优步长，计算新点x的值的值 。0 x1x2xkdkxk+1g2(x)=0g1(x)=0a*dk(2)(2)取到约束边界的最大步长取到约束边界的最大步长 从从xk点出发，沿点出发，沿dk方向进行一维最优化搜索，方向进行一维最优化搜索，得到的新点得到的新点x为不可行点为不可行点。0 x1x2xkdkxk+1g2(x)=0g1(x)=0a*dkaMdkx 改变步长，改变步长，使新点使新点x返回到返回到约束面上来。约束面上来。使新点使新点x恰好位恰好位于约束面上的于约束面上的步长称为最大步长称为最大步长步长 ,记作记作 。M 的确定 1) 试验

36、步长t)(kX)1( kX将 在 处作泰勒展开, 仅取到线性项:)(XF)(kX)()()()()()1()()()1(kkTkkkXXXFXFXF (1) 定义目标函数相对下降量:)()()()()1()(kkkfXFXFXF (2)迭代公式 )()()1(ktkkSXX(3)(4)将(2)、(3)代入(1)后整理得:)()()()()(kTkkftSXFXF 迭代点在边界附近偏域内一侧时使 用, 采用最有利的适用可行方向.)(kS 2) 按此法, 直至使迭代点进入约束容差带或至域外为止.* 1) 为保证 是 的一个邻近点, 的值不能取得太大. 通常)1( kX)(kXf1 . 005. 0

37、fM2） 调整调整 ( (将已出界的迭代点调回到将已出界的迭代点调回到边界上边界上) )(1) 约束边界容差带约束边界容差带 在实际计算中在实际计算中, ,应给约束边界一个允应给约束边界一个允许的误差限许的误差限:)(0Xgupu,.,2 , 1式中式中, 通常取通常取0.01-0.001;只要迭代点进入只要迭代点进入容差带容差带, 即认为达到了边界即认为达到了边界.(2) 调整步长因子调整步长因子c因因 与与 很接近很接近, 可认为可认为 在这两点间按线性变化在这两点间按线性变化:)1( kX)(kX)(XgjtkjkjkjjXgXgXgXg)()()()()()1()(1)为使新迭代点落在

38、容差带中部为使新迭代点落在容差带中部, 取取2)()()()()()()1()()2(ctkjkjkjkjjXgXgXgXgXg(2)于是有于是有tkjkjkjcXgXgXg)()()(2)()1()()()()2(kckkSXX(3)* 还需检验该点是否在容差带内还需检验该点是否在容差带内.若不满足若不满足,则则) )若若 , ,则则) 若若 , ,则则0g0g;)2()1(kkXXct;)2()(kkXXctt 重复以上步骤重复以上步骤, ,直至满足时止直至满足时止. .0ct)(Xgj)()(kjXg)()1( kjXgt收敛条件收敛条件2()kTkf xd2 2）设计点）设计点xk满足

39、库恩满足库恩- -塔克条件塔克条件1()()00(1,2, )jkkjjjjfgjJxxl1）设计点）设计点xk及约束允差及约束允差 满足满足例题例题5-1：用可行方向法求约束优化问题：用可行方向法求约束优化问题2212121211223142512min( )10460. .( )0( )0( )60( )80( )110fxxx xxxstgxgxg xxgxxg xxx xxx解解: (1)取初始点取初始点 ，则取作用约束集，则取作用约束集: Jk=100,1Tx1201221011()242xxfxxx011()0gx(2)寻找最优方向，即解一个以可行方向为设计变量寻找最优方向，即解一

40、个以可行方向为设计变量 的规划问题：的规划问题：12Td dd0120110122212min ( )()112. . ()0()11201TTTfddstgdfdddd xxdxdxd1d1d2*用图解法：用图解法：最优方向：最优方向：0.984,0.179Td(3)沿沿d0方向进行一维搜索方向进行一维搜索1000000.98410.179 xxd1()( )f xx1在约束边界在约束边界g3(x)=0上上: g3(x1)=0(4) 第二次迭代，用梯度投影法确定可行方向第二次迭代，用梯度投影法确定可行方向,迭代点迭代点x的目标函数负梯度的目标函数负梯度1()0.092 5.818Tfx不满足

41、方向的可行条件，将不满足方向的可行条件，将 投影到约束边投影到约束边界界g3(x)=0上。上。1()fx投影算子：投影算子：1111113333()()() ()TTTTggggPIG G GGIxxxx06.098由上式可求得：由上式可求得：1111113333()()() ()TTTTggggPIG G GGIxxxx11011001010010001 本次迭代方向本次迭代方向1110()1()P fP f xdxD为沿约束边界为沿约束边界g3(x)=0的方向，求最佳步长的方向，求最佳步长21111602.0911 xxd12.909求得：求得：265 xg5(x)=068x1x2g4(x

42、)=0g3(x)=0g2(x)=0g1(x)=0 x0d0（4）收敛判断：）收敛判断：由于由于122122103()240 xxfxxxJk=3， 5223511();()01gg xx代入代入KT条件：条件：*1*()()0 (1,2, )()0(1,2,)0(1,2,)mjjjiijjjgfinxxgjmjm xxx123110001 123,0*6,()115f xx 惩罚函数法是一种很广泛、很有效的间接解法。它的基本原理是将约束优化问题中的不等式和不等式约束函数经加权后，和原目标函数结合为新的目标函数惩罚函数。 将约束优化问题转换为无约束优化问题。求解无约束优化问题的极小值，从而得到原

43、约束优化问题的最优解。 121211, ,mljkjkx r rf xrG gxrH hx加权转化项 将有约束的优化问题转化为无约束优化问题来求解。将有约束的优化问题转化为无约束优化问题来求解。前提：一是不能破坏约束问题的约束条件，二是使它归结前提：一是不能破坏约束问题的约束条件，二是使它归结到原约束问题的同一最优解上去。到原约束问题的同一最优解上去。 min( ),. .( )01,2,( )01,2,njkfRst gjmhklxxxx 构成一个新的目标函数，称为惩罚函数构成一个新的目标函数，称为惩罚函数 ( )( )( )( )121211( ,)( )( )( )mlkkkkjkijr

44、rfrG grH hxxxx从而有从而有( )11lim( )0mkikirG gx( )21lim( )0lkjkjrH hx( )( )( )12lim( ,)()0kkkkrrfxx惩罚项必须具有以下极限性质：惩罚项必须具有以下极限性质： 求解该新目标函数的无约束极小值，以期得到原问题求解该新目标函数的无约束极小值，以期得到原问题的约束最优解。按一定的法则改变罚因子的约束最优解。按一定的法则改变罚因子r1 和和r2的值，的值，求得一序列的无约束最优解，不断地逼近原约束优化问求得一序列的无约束最优解，不断地逼近原约束优化问题的最优解。题的最优解。 根据约束形式和定义的泛函及罚因子的递推方法

45、根据约束形式和定义的泛函及罚因子的递推方法等不同，罚函数法可分为内点法、外点法和混合罚等不同，罚函数法可分为内点法、外点法和混合罚函数法三种。这种方法是函数法三种。这种方法是1968年由美国学者年由美国学者AVFiacco和和GPMcormick提出的，把不等式约束引提出的，把不等式约束引入数学模型中，为求多维有约束非线性规划问题开入数学模型中，为求多维有约束非线性规划问题开创了一个新局面。创了一个新局面。1.内点法内点法 这种方法将新目标函数定义于可行域内，序列这种方法将新目标函数定义于可行域内，序列迭代点在可行域内逐步逼近约束边界上的最优点。内迭代点在可行域内逐步逼近约束边界上的最优点。内

46、点法只能用来求解具有不等式约束的优化问题。点法只能用来求解具有不等式约束的优化问题。min( )s.t.( )0(1,2,)jfgjmxx对于只具有不等式约束的优化问题：对于只具有不等式约束的优化问题： 转化后的惩罚函数形式为：转化后的惩罚函数形式为：( )11( , )( )( )mkiirfrgxxx( )1( , )( )ln( )mkiirfrgxxx或：或：rk是惩罚因子，它是一个由大到小且趋近于是惩罚因子，它是一个由大到小且趋近于0的正数列，的正数列，即即: 01210kkrrrrr 由于内点法的迭代过程在可行域内进行，由于内点法的迭代过程在可行域内进行，“障碍项障碍项”的作用是阻

47、止迭代点越出可行域。由的作用是阻止迭代点越出可行域。由“障碍项障碍项”的的函数形式可知，当迭代点靠近某一约束边界时，其值函数形式可知，当迭代点靠近某一约束边界时，其值趋近于趋近于0，而，而“障碍项障碍项”的值陡然增加，并趋近于无的值陡然增加，并趋近于无穷大，好像在可行域的边界上筑起了一道穷大，好像在可行域的边界上筑起了一道“高墙高墙”，使迭代点始终不能越出可行域。显然，只有当惩罚因使迭代点始终不能越出可行域。显然，只有当惩罚因子子 时，才能求得在约束边界上的最优解。时，才能求得在约束边界上的最优解。 0kr 是：由于内点法只能在可行域是：由于内点法只能在可行域内迭代，而最优解很可能在可行域内靠

48、近边界处或内迭代，而最优解很可能在可行域内靠近边界处或就在边界上，此时尽管泛函的值很大，但罚因子是就在边界上，此时尽管泛函的值很大，但罚因子是不断递减的正值，经多次迭代，接近最优解时，惩不断递减的正值，经多次迭代，接近最优解时，惩罚项已是很小的正值。罚项已是很小的正值。 例例5-2 用内点法求用内点法求2212min( )fxxx1s.t.( )10gx x的约束最优解。的约束最优解。解解: 用内点法求解该问题时，首先构造内点惩罚函用内点法求解该问题时，首先构造内点惩罚函数数:22121( , )ln(1)krxxrxx用解析法求函数的极小值，运用极值条件：用解析法求函数的极小值，运用极值条件

49、： 1112220120krxxxxx 联立求解得：联立求解得：12112()2()0kkkrx rx r1112( )2rx r时不满足约束条件时不满足约束条件 1( )10g xx 应舍去应舍去 。无约束极值点为无约束极值点为*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 r1） 初始点初始点x0的选取的选取 使用内点法时，初始点应选择一个离约束边界较

50、使用内点法时，初始点应选择一个离约束边界较远的可行点。如太靠近某一约束边界，构造的惩罚远的可行点。如太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难无约束优化问题发生困难. .2） 惩罚因子初值惩罚因子初值r0的选取的选取 惩罚因子的初值应适当，否则会影响迭代计算的惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一般而言，太大，将增加迭代次数；太正常进行。一般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。无一般性的有效方法

51、。对于不同的问题，都值点。无一般性的有效方法。对于不同的问题，都要经过多次试算，才能决定一个适当要经过多次试算，才能决定一个适当 r0 3) 惩罚因子的缩减系数惩罚因子的缩减系数c的选取的选取 在构造序列惩罚函数时，惩罚因子在构造序列惩罚函数时，惩罚因子r是一个逐次递是一个逐次递减到减到0的数列，相邻两次迭代的惩罚因子的关系为的数列，相邻两次迭代的惩罚因子的关系为 :1(1,2,.)rkrcrk 式中的式中的c称为惩罚因子的缩减系数，称为惩罚因子的缩减系数，c为小于为小于1的正数。的正数。一般的看法是，一般的看法是，c值的大小在迭代过程中不起决定性作值的大小在迭代过程中不起决定性作用，通常的取

52、值范围在用，通常的取值范围在0.10.7之间。之间。 4) 收敛条件收敛条件*111*11(),(),(),kkkkkkrrrrrrxxx*12()()kkrrxx1）选择可行域内初始点）选择可行域内初始点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），否

53、则转步骤），否则转步骤5）；）；7）输出最优解（）输出最优解（X*，F*），停止计算），停止计算。2. 外点法外点法 外点法是从可行域的外部构造一个点序列去逼近外点法是从可行域的外部构造一个点序列去逼近原约束问题的最优解。外点法可以用来求解含不等式和原约束问题的最优解。外点法可以用来求解含不等式和等式约束的优化问题。等式约束的优化问题。 外点惩罚函数的形式为：外点惩罚函数的形式为： 2211( , )( )max0,( )( )mlijijrfrgrhxxxxr是惩罚因子是惩罚因子 ,012rrr 外点法的迭代过程在可行域之外进行，惩罚项的作用外点法的迭代过程在可行域之外进行，惩罚项的作用是迫

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

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

56、01-0.80975-50.00000-24.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求解得外点法惩罚因子按下式递增1kkrcr递增系数，通常取

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

58、择得当）初始罚因子要选择得当 （6）罚因子为递减，递减率）罚因子为递减，递减率c有有0c1 3. 混合法混合法 混合法是用内点法处理不等式约束，用外点法处混合法是用内点法处理不等式约束，用外点法处理等式约束。可以用来求解含不等式和等式约束的优化理等式约束。可以用来求解含不等式和等式约束的优化问题。问题。 混合惩罚函数的形式为：混合惩罚函数的形式为： r是惩罚因子是惩罚因子 , 混合法具有内点法的特点，迭代过程在可行域之内混合法具有内点法的特点，迭代过程在可行域之内进行，参数的选择同内点法。进行，参数的选择同内点法。 ( )( )2( )1111( ,)( )( )( )mlkkjkijirfr

59、hgrxxxx01210kkrrrrr 这种同时处理等式和不等式约束的惩罚函数法称为混合惩罚函数法。混合惩罚函数法与前述内点法和外点法一样，也属于序列无约束极小化(SUMT)方法中的种方法。 惩罚函数法原理简单，算法易行，且惩罚函数法原理简单，算法易行，且分内点法、外点法和混合法三种，各有特点，分内点法、外点法和混合法三种，各有特点，适用范围广。需要和有效的无约束优化方法适用范围广。需要和有效的无约束优化方法结合使用。因此该方法也是应用较多的有约结合使用。因此该方法也是应用较多的有约束优化方法。束优化方法。5-6 5-6 拉格朗日乘子法拉格朗日乘子法一一. .等式约束问题的拉格朗日乘子法等式约

60、束问题的拉格朗日乘子法qvvRDXXhXFn,.,2 , 1, 0)(),(mins.t.qXhXFXL1)()(),(1.1.建立拉氏函数建立拉氏函数2.2.在最优点处有如下在最优点处有如下n+q n+q 个方程成立个方程成立qvvniiLxL,.,2, 1,.,2, 1, 0, 0其解为其解为),(XqvvpuuRDXXhXgXFn,.,2,1,.,2,1,0)(,0)(),(mins.t.二二. .含不等式约束问题的拉格朗日乘子法含不等式约束问题的拉格朗日乘子法1.1.建立拉氏函数建立拉氏函数 再用前述方法建立拉氏函数再用前述方法建立拉氏函数 对不等式约束引入松弛变量对不等式约束引入松弛