机械优化设计无约束优化

1、1第章 无约束优化方法nRXXf ),( minn无约束优化算法：无约束优化算法：直接法：直接法：间接法：间接法：即不用导数信息的算法，它只需进行函数值即不用导数信息的算法，它只需进行函数值的计算与比较，来确定迭代方向和步长。如：的计算与比较，来确定迭代方向和步长。如：坐标轮换法、共轭方向法和鲍威尔法。坐标轮换法、共轭方向法和鲍威尔法。即使用导数信息的算法，它需要利用函数的即使用导数信息的算法，它需要利用函数的一阶或二阶偏导数矩阵，来确定迭代方向和一阶或二阶偏导数矩阵，来确定迭代方向和步长。如：梯度法、牛顿法和变尺度法。步长。如：梯度法、牛顿法和变尺度法。4.1 概述概述n无约束优化问题的数学

2、模型：无约束优化问题的数学模型：24.2 坐标轮换法（变量轮换法） 基本原理将一个多维无约束优化问题转化为一系列一维优化问题来求解。即：一次沿着坐标轴的方向进行一维搜索，求得极小点。图4.1 坐标轮换法的基本原理3图4.1 坐标轮换法的基本原理;0 , 0 , 1 ,) 1(111111XexxnnT得到好点得到好点进行一维搜索，进行一维搜索，的方向的方向第一个变量第一个变量即由初始点沿着即由初始点沿着第一个变量第一个变量化化个变量固定不动，只变个变量固定不动，只变将将维无约束优化问题，先维无约束优化问题，先对于对于;,0 , 1 , 0) 1(12122XexnT得到好点得到好点索，搜索方向

3、为：索，搜索方向为：进行一维搜进行一维搜对第二个变量对第二个变量个变量不变，个变量不变，再保持再保持4算算。搜搜索索后后，完完成成一一轮轮计计次次进进行行一一维维一一维维搜搜索索的的起起始始点点，依依搜搜索索的的好好点点作作为为本本次次且且将将前前一一次次一一维维方方向向（即即坐坐标标方方向向），如如此此沿沿11211,neeen特点：特点：坐标轮换法坐标轮换法简单易行简单易行，但由于它只能轮流，但由于它只能轮流沿沿n个坐标方向前进，因而个坐标方向前进，因而效率低下效率低下，特别是，特别是维数较高或目标函数性态不好的情况下，收敛维数较高或目标函数性态不好的情况下，收敛速度很慢。速度很慢。近近最

4、最优优点点为为止止。直直至至满满足足收收敛敛准准则则、逼逼循循环环，如如此此反反复复，进进行行下下一一轮轮的的为为起起始始点点的的末末点点若若未未收收敛敛，则则以以前前一一轮轮,1nX5图4.2 模式搜索法4.3 模式搜索法由图4.1可见，在沿着坐标进行了一轮搜索后，如果沿着所定义的方向进行一次寻优，将大大提高坐标轮换法寻优的速度，其基本原理如图4.2所示。kknjXXS1 n基本原理基本原理基基本本寻寻优优步步骤骤：knkXX ,1; 1,) 110khX和和迭迭代代轮轮数数计计算算精精度度步步长长选选定定初初始始点点6图4.2 模式搜索法;)20knkXX搜搜索索，求求出出开开始始，进进行

5、行坐坐标标轮轮换换从从n特点：特点：模式搜索法是对坐标轮换法的一种改进模式搜索法是对坐标轮换法的一种改进，它改变了完全沿着，它改变了完全沿着坐标方向寻优的模式，可以较好的提高计算精度，并利用已有的坐标方向寻优的模式，可以较好的提高计算精度，并利用已有的计算信息，但该方法需要储存函数在计算信息，但该方法需要储存函数在k轮迭代开始的坐标值。轮迭代开始的坐标值。转转入入步步骤骤令令寻寻优优起起点点得得新新的的方方向向进进行行一一维维寻寻优优，沿沿计计算算方方向向否否则则，则则收收敛敛，输输出出若若满满足足判判断断)2, 1,;,)3100*0kkXSXXSXXXXkkkknkknkkn74.4 Po

6、well共轭方向法共轭方向法及其构成坐标轮换法的收敛速度很慢，原因在于其搜索方向总是平行于坐标轴，不适应函数的变化情况。有有何何关关系系？与与具具有有什什么么性性质质？问问题题：快快收收敛敛速速度度。加加进进行行一一维维搜搜索索，可可大大大大，并并沿沿此此方方向向线线）新新的的搜搜索索方方向向（图图中中虚虚连连接接起起来来，形形成成一一个个末末点点与与若若把把这这一一轮轮的的起起点点122202222220)2)1eSSXXSXX 8图4.3 共轭方向的形成。同同心心椭椭圆圆族族，如如图图所所示示附附近近的的等等值值线线是是近近似似的的，则则极极值值点点的的极极值值点点为为设设函函数数,),(

7、*2*1*21xxXxxf。连连接接二二切切点点构构成成向向量量的的相相切切点点。与与函函数数等等值值线线（椭椭圆圆）分分别别是是两两条条平平行行线线和和显显然然，。和和一一维维搜搜索索，求求得得极极小小点点进进行行沿沿这这两两个个平平行行方方向向分分别别向向设设给给定定两两个个平平行行方方12221211,XXSXXXXS即即共共轭轭方方向向。具具有有这这种种性性质质的的方方向向，满满足足下下式式：与与则则方方向向为为正正定定对对称称矩矩阵阵矩矩阵阵的的若若函函数数可可以以证证明明0),(:212121HSSSSHHessianxxf9图4.3 共轭方向的形成共共轭轭。关关于于与与是是共共轭

8、轭的的，或或简简称称关关于于实实对对称称正正定定矩矩阵阵与与则则称称向向量量满满足足的的两两个个非非零零向向量量，如如果果欧欧式式空空间间维维为为与与阶阶实实对对称称正正定定矩矩阵阵，而而为为设设共共轭轭方方向向：ASSASSASSRnSSnnAn21212121010021 ASS证证明明：)()()()()()(21)()()()(*2*2*XXXfXfXfXfXXXfXXXXXfXfXfX ：阶阶导导数数由由上上式式可可求求得得函函数数的的一一开开式式为为：附附近近的的二二次次泰泰勒勒近近似似展展设设二二维维函函数数在在极极值值点点)()()()()()(*2*2*2*1*2*1XXXf

9、XfXfXXXfXfXf故故有有：0)()()(0)()()(*2*2*121*1*2*111211211）（）（的的梯梯度度方方向向，即即有有：、应应垂垂直直于于故故方方向向，、点点分分别别为为为为等等值值线线的的切切线线，其其切切由由于于二二平平行行方方向向XXXfXfSXfSXXXfXfSXfSXXSXXS110)()()(12*21121XXXfSXfXfS上上两两式式相相减减得得：故故由由上上式式可可得得：而而0)()(),(2*2112*21122SXfSXXXfSXXS可可得得下下式式：令令),(*2XfH021HSS共共轭轭的的向向量量。构构成成一一组组关关于于维维空空间间中中

10、可可以以逐逐步步维维函函数数，即即在在上上述述算算法法可可推推广广到到Hnn12n共轭方向法的基本原理共轭方向法的基本原理图4.4 共轭方向法的迭代过程u先采用坐标轮换法进先采用坐标轮换法进行第一轮迭代；行第一轮迭代；u然后以第一轮迭代的然后以第一轮迭代的最末一个极小点和初最末一个极小点和初始点相连，构成一个始点相连，构成一个新方向；新方向；u并以此新方向为最末并以此新方向为最末一个方向，而去掉第一个方向，而去掉第一个方向，得到第二一个方向，得到第二轮迭代的轮迭代的n个方向。个方向。 如此进行下去，直至如此进行下去，直至求得问题的最小点。求得问题的最小点。13u共轭方向法的迭代过程（以图示二维

11、问题为例）：共轭方向法的迭代过程（以图示二维问题为例）：; 1 , 00 , 1 , 1) 1 (210，向向初始搜寻方向为坐标方初始搜寻方向为坐标方取初始点取初始点令循环次数令循环次数kkkSSXk;)2(21210kkkkkXXSSX和和得得到到相相应应的的极极小小点点别别方方向向进进行行一一维维搜搜索索，分分和和出出发发，依依次次沿沿从从14;,)3(*33023次次循循环环的的极极小小点点第第进进行行一一维维搜搜索索，得得到到沿沿构构造造新新方方向向kkkkkXkSXXS);2(, 1,)4(3122111*310转转令令，构构造造新新的的搜搜索索方方向向去去掉掉原原来来的的第第一一方

12、方向向取取下下次次循循环环的的初初始始点点kkSSSSSXXkkkkkkk迭迭代代计计算算结结束束。，直直至至满满足足收收敛敛条条件件，至至继继续续循循环环)4()2(15nPowell共轭方向法的基本原理共轭方向法的基本原理共轭方向法的基本要求：共轭方向法的基本要求：各方向组的向量应该是各方向组的向量应该是线性线性无关无关的。的。), 2 , 1(niSki 然而很不理想的是，上述方法每次迭代时所然而很不理想的是，上述方法每次迭代时所产生的新方向产生的新方向可能出现线性相关，可能出现线性相关，使搜索运算使搜索运算将将在维数下降了的空间在维数下降了的空间进行，从而导致计算不能收进行，从而导致计

13、算不能收敛到真正的极小点而失败。敛到真正的极小点而失败。16针对上述问题，针对上述问题，Powell提出了对共轭方向法的提出了对共轭方向法的如下改进方法：如下改进方法：在每一轮迭代完成并产生共轭方向后，在每一轮迭代完成并产生共轭方向后，先对共轭方向先对共轭方向的好坏进行判别，检验它是否与其他方向线性相关。的好坏进行判别，检验它是否与其他方向线性相关。 u若共轭方向不好，则不用它作为下一轮的迭代方向，若共轭方向不好，则不用它作为下一轮的迭代方向，而仍采用原来的一组迭代方向。而仍采用原来的一组迭代方向。u若共轭方向好，则可用它替换前一轮迭代中使若共轭方向好，则可用它替换前一轮迭代中使函数函数值下降

14、最多值下降最多的一个方向，而不一定替代第一个迭代的一个方向，而不一定替代第一个迭代方向。方向。17在在Powell共轭方向法中，判别是否用新的方向替换原方共轭方向法中，判别是否用新的方向替换原方向组中某一方向的向组中某一方向的判别原则判别原则按下式是否同时满足来处理：按下式是否同时满足来处理：图4.5);(0101kkXffXkf的的函函数数值值次次循循环环中中起起始始点点表表示示在在第第上上两两式式中中，23122123113)(5 . 0)(2(fffffffffkmkm (4-1);(22knknXffXkf函函数数值值的的一一维维搜搜索索后后的的终终点点依依次次方方向向组组中中各各迭迭

15、代代方方向向次次循循环环中中沿沿基基本本表表示示在在第第18图4.5；的映射点，的映射点，对对为为为映射点的函数值，为映射点的函数值，kknknknkknkknknXXXXXXXXfXfff010101332),2()( 量量最最大大者者，表表示示循循环环中中函函数数值值下下降降km kmkmkmkikikmSXfXfniXfXf其相应的方向为即)()(, 2 , 1),()(max1119）；一一维维搜搜索索求求得得的的极极小小点点循循环环中中沿沿新新方方向向次次为为第第初初始始点点为为次次循循环环的的并并取取第第次次循循环环的的基基本本方方向向组组构构成成第第以以即即的的最最后后，并并去去

16、掉掉方方向向次次循循环环的的基基本本方方向向组组补补入入将将选选用用新新方方向向次次循循环环中中，式式，则则在在第第若若同同时时满满足足判判别别准准则则knknknkkiknknkmkmkkkmknknSkXXXkniSkSSSSSSSkSSk1*1*11011112111(1), 2 , 1(1,1,1)14(。时时，取取当当时时，取取即即当当两两点点中中函函数数值值较较小小者者，和和则则应应选选取取初初始始点点，而而个个搜搜索索方方向向仍仍用用原原来来的的次次循循环环第第否否则则knkknkknknkkiXXffXXffXXXniSnk110321032110;), 2 , 1(1,20;

17、) 1 (210、和和允允许许误误差差给给定定初初始始点点XnPowell共轭方向法的迭代步骤共轭方向法的迭代步骤;)( 1,), 2 , 1()2(00XXkkeSnienkikii，为为迭迭代代轮轮次次置置搜搜索索方方向向为为个个坐坐标标轴轴的的单单位位向向量量取取kmkmkmkikikmkikikXXSniXfXfXnniSX110, 2 , 1),()(max, 2 , 1)3(向：最大差值及其相应的方的差值，并找出其中的函数值计算各相邻极小点目标个极小点依次得）作一维搜索，（出发，分别沿从21;,11,;1,) 14()5(1111111112121111*110*1*11knknk

18、nknkmkmkmkmkkkkknkmknkknknknknSSSSSSSSSSSSkkSSXXkXXSX搜搜索索方方向向为为：轮轮的的，即即第第轮轮迭迭代代的的最最末末一一个个方方向向作作为为方方向向而而将将然然后后去去掉掉方方向向迭迭代代的的初初始始点点，即即令令轮轮为为并并以以的的极极小小点点一一维维搜搜索索，求求出出该该方方向向进进行行出出发发，沿沿方方向向，则则由由若若同同时时满满足足式式);(),(),(,2)4(1320101knknkkknknXffXffXffXXX并并求求得得计计算算反反射射点点22返返回回下下一一轮轮迭迭代代。否否则则，置置：为为最最优优点点，输输出出结结

19、果果为为则则可可终终止止迭迭代代，得得或或条条件件，若若满满足足检检验验是是否否满满足足迭迭代代终终止止, 1,);()(,)()()()6(10010*10*102100101010kkXXXfXfXXXXfXfXfXXkkkkkkkkk；时时，取取当当时时，取取当当始始点点选选取取：轮轮迭迭代代的的方方向向，迭迭代代初初仍仍采采用用第第轮轮迭迭代代时时，则则进进入入第第若若不不满满足足判判别别式式knkknkXXffXXffkk110321032;1) 14(23nPowell共轭方向法的算法框图共轭方向法的算法框图2100, X输入输入ikieSk , 11 i)(min,1kikiki

20、kiSXf 使使一维搜索求一维搜索求kikikikiSXX 11 ii?ni NYAB24kknknXXS01 kknknXXX012 kmkmS并并确确定定相相应应的的方方向向计计算算, knkknknkknSXXS111 一维搜索求一维搜索求沿沿*110knkXX knknkikikikiSSnimSSmiSS11111)1()( knkXX 10knkXX110 ), 2 , 1(1niSSkiki ?)14( 满足判别式满足判别式NY?32ff YNBC2511000 kkXXk)()(10*10* kkXfXfXX输出：输出：结束?)()()(?2100101010 kkkkkXfX

21、fXfXX或或YNAC图4.6264.5 最速下降法基本原理在迭代过程的某一点Xk处，目标函数的负梯度方向f(Xk)是函数的最速下降方向。最速下降法即利用这一性质，将n维无约束极小化问题转化为一系列沿目标函数负梯度方向进行一维寻优的一种方法，即在每一迭代点Xk ，选取搜索方向Sk 为负梯度方向：或或)()()(kkkkkXfXfSXfS 。设设计计点点，找找到到新新的的步步长长因因子子进进行行一一维维搜搜索索，以以确确定定再再沿沿kkkkkkSXXS 127最速下降法的迭代公式：最速下降法的迭代公式：)()()(11kkkkkkkkkXfXfXXXfXX 或或标标函函数数的的极极小小点点。可可

22、使使迭迭代代点点逐逐渐渐逼逼近近目目取取上上次次迭迭代代的的终终点点，即即每每次次迭迭代代的的初初始始点点进进行行若若干干次次一一维维搜搜索索，按按照照上上述述迭迭代代公公式式n迭代步骤：迭代步骤：; 0,) 1 (210kMX令令循循环环次次数数精精度度最最多多迭迭代代次次数数给给定定初初始始点点；或或计计算算搜搜寻寻方方向向)()()()2(kkkkkXfXfSXfS28);4()()(,)()3(1*1*1转转停停止止计计算算；否否则则，若若是是，输输出出判判断断是是否否满满足足kkkXfXfXXXf);5();8(,)4(否否则则，转转若若是是，转转判判断断是是否否满满足足Mk ；件件

23、为为终终止止一一维维搜搜索索的的判判别别条条确确定定步步长长因因子子方方向向作作一一维维搜搜索索，求求解解沿沿211)()(,),()(min)5(kkkkkkkkXfXfSXfXfS);7();8()6(11否则，转否则，转，若是，转，若是，转判断是否满足判断是否满足kkkXXX);2(, 1)7(转转 kk。输出结果：输出结果：)()(,)8(1*1*kkXfXfXX29图4.7 等值线是椭圆(a)和圆(b)的情况下最速下降法的迭代过程为为极极小小点点。为为初初始始点点，其其中中，点点的的过过程程。化化二二维维问问题题时时逼逼近近极极小小描描述述了了用用最最速速下下降降法法优优图图*07

24、. 4XXu对于等值线为圆的优化问题，最速下降法一次迭代就可达到对于等值线为圆的优化问题，最速下降法一次迭代就可达到极小点；极小点；u当等值线不是圆时，负梯度方向不再指向圆心（实线），迭当等值线不是圆时，负梯度方向不再指向圆心（实线），迭代次数增加，偏心越严重，迭代次数越多，形成代次数增加，偏心越严重，迭代次数越多，形成“锯齿现象锯齿现象”。而且，在搜索开始时步长越大，愈接近极小点步长愈小，最后而且，在搜索开始时步长越大，愈接近极小点步长愈小，最后收敛的速度及其缓慢。收敛的速度及其缓慢。30 最速下降法的特点： 迭代过程简单，对初始点X0的要求不高，虽要计算导数，但只要求一阶偏导，存储单元较少

25、。 收敛慢。对于复杂的优化问题，最速下降法不具备实用价值，但由于在迭代开始时函数值下降较快，常用于其他方法中作初始迭代法。的的极极小小点点。函函数数：用用最最速速下下降降法法求求目目标标例例222125)(24xxXF314.6 牛顿法u求出这个二次近似函数的极小点；求出这个二次近似函数的极小点；)()()()(21)()()()()(2kkkkkkkkXfXHHessianXXXHXXXXXfXfXXf矩阵:, 0)(得令Xn基本思想：基本思想：牛顿法是最速下降法的进一步发展，其基本思想：牛顿法是最速下降法的进一步发展，其基本思想：u在求目标函数在求目标函数f(X)的极小值时，先将的极小值时

26、，先将f(X)在点在点Xk附近作附近作泰勒展开，取其二次函数式：泰勒展开，取其二次函数式：)()(1*kkkXfXHXX32u若若f(X)是二次函数，则是二次函数，则X*即即f(X)的极小点；否则只是一个近的极小点；否则只是一个近似点。似点。 若该极小值满足精度要求，以该极小点作为原目标函数若该极小值满足精度要求，以该极小点作为原目标函数的近似极小点；否则，以此近似极小点作为下一次迭代的初的近似极小点；否则，以此近似极小点作为下一次迭代的初始点，继续以上过程，迭代下去，直至所求出的近似极小点始点，继续以上过程，迭代下去，直至所求出的近似极小点满足精度要求为止。满足精度要求为止。)()(11kk

27、kkXfXHXX 牛顿法的迭代公式：牛顿法的迭代公式：导导致致计计算算失失败败。迭迭代代点点的的发发散散而而的的情情况况下下甚甚至至可可能能造造成成值值的的稳稳定定下下降降，在在严严重重法法不不能能保保证证函函数数）的的情情况况。这这表表明明牛牛顿顿上上升升（即即出出现现函函数数值值次次型型目目标标函函数数，有有时时会会的的迭迭代代，这这对对于于非非二二，或或者者说说是是一一种种定定步步长长，没没有有步步长长因因子子在在上上述述迭迭代代公公式式中中分分析析：)()(11kkkkXfXf 33的的极极小小点点。：用用牛牛顿顿法法求求目目标标函函数数例例222125)(34xxXF34n阻尼牛顿法

28、（或修正牛顿法）阻尼牛顿法（或修正牛顿法）阻尼牛顿法是为了克服牛顿法的上述弊病，对其加以改阻尼牛顿法是为了克服牛顿法的上述弊病，对其加以改进而提出的。进而提出的。)()(11kkkkkXfXHXX 为牛顿方向。为牛顿方向。步长因子；步长因子；为阻尼因子，或称最优为阻尼因子，或称最优式中，式中，)()(1kkkkXfXHS n牛顿法的特点牛顿法的特点牛顿法不仅利用了函数的一阶导数信息，还利用了函数牛顿法不仅利用了函数的一阶导数信息，还利用了函数的二阶导数信息，其收敛速度较最速下降法快得多。的二阶导数信息，其收敛速度较最速下降法快得多。但牛顿法要计算但牛顿法要计算Hessian矩阵及其逆矩阵，计算

29、量存储量矩阵及其逆矩阵，计算量存储量均很大，且都以维数均很大，且都以维数n2比例增加，维数高时这个问题更加比例增加，维数高时这个问题更加突出。此外，若突出。此外，若Hessian矩阵是奇异矩阵时，其逆矩阵不矩阵是奇异矩阵时，其逆矩阵不存在，此方法便不能应用。存在，此方法便不能应用。对初始点的选取要求较高，否则不能收敛。对初始点的选取要求较高，否则不能收敛。阻尼牛顿法迭代公式：阻尼牛顿法迭代公式：354.7 变尺度法(DFP法及BFGS法)变尺度法是在克服了最速下降法的收敛慢和牛顿法计算量大的缺点而发展起来的，是求解无约束优化问题最有效的算法，在工程优化设计中得到了广泛的应用。n变尺度法的迭代公

30、式：变尺度法的迭代公式：算量大为减少。矩阵的计算和求逆，计。这种方法，省去了逼近过程中不断改进，最后在迭代。近似地代替阵而是用一个对称正定矩算形式，然而并不直接计利用牛顿法的迭代HessianXHAXHAXHkkkkk111)()(,)(修修正正。过过程程中中逐逐次次形形成成并并不不断断为为变变尺尺度度矩矩阵阵，在在迭迭代代，为为变变尺尺度度法法的的搜搜索索方方向向式式中中，kkkkAXfAS)( )(1kkkkkXfAXX (4-2)n基本思想：基本思想：36)(1kkkkXfXX (4-3)变变为为：，则则式式单单位位矩矩阵阵取取若若在在初初始始点点)24()(,00 IAX变变为为：时时

31、，则则式式即即当当)24()(,1* kkkXHAXX)()(11kkkkkXfXHXX (4-4)上式即最速下降法的迭代公式。上式即阻尼牛顿法的迭代公式。p最速下降法和阻尼牛顿法可看作变尺度法的一种特殊形式。两种方法。和，其中最重要的是采用不同的修正矩阵种算法的主要区别在于常丰富，算法很多。各变尺度法的内容非递推公式：，变尺度矩阵可有如下逆矩阵，最后逼近在迭代过程中逐次修正为使变尺度矩阵BFGSDFPAAAAXHHessianAkkkkkk11)(4-5)37 DFP变尺度法 DFP算法的迭代修正矩阵：kkkkkkkkkkkkgAgAggAgXXXA(4-6)二阶导数矩阵的信息。逐渐形成信息

32、收集积累起来，以的函数信息和一阶导数过程中所有说明，变尺度法将迭代这个修正矩阵公式信息之差。一阶导数即两迭代点的目标函数即两迭代点信息之差；式中，),()(,11kkkkkkXfXfgXXX38uDFP变尺度法迭代步骤变尺度法迭代步骤;,) 1 (0nRXn，维数迭代精度给定初始点);(, 0)2(000XfgIAk计算单位矩阵置;)3(kkkgAS计算搜索方向kkkkkSXX1)4(，得迭代新点：进行一维搜索求否则进行下一步；输出最优解若满足，则停止迭代，条件检验是否满足迭代终止);()(,?)()5(1*1*1kkkXfXfXXXf39);7(,)2(,)6(10则转若；转则置检查迭代次数

33、，若nkXXnkk。转。然后，置计算按式计算：)3(, 1,)64(,),(,)7(11111kkAAAAgggXfgXXXkkkkkkkkkkkk。，梯梯度度精精度度初初始始点点的的极极小小点点和和极极小小值值，取取束束优优化化问问题题：变变尺尺度度法法求求解解下下列列无无约约：试试例例01. 09 , 8)6()5(4)(4402221TXxxXfDFP40uDFP变尺度法的算法框图：变尺度法的算法框图：nX,0 给定给定)(, 0000XfgIAk kkkkkkkkkSXXSXfgAS 1)(min,求得求得?)(1 kXf?nk kkkkkkAAAAgX 1,计算：计算：1 kk10

34、kXX)(1*1* kkXffXX输出：输出：结束YNYN图4.841 DFP方法的特点： 变尺度法在最初的几步迭代，与最速下降法类似，函数值下降较快；而在最后的几步迭代，与牛顿法相近，可较快地收敛到极小点。 因此，变尺度法能够克服最速下降法收敛慢的缺点，但却保留了最速下降法在最初几步函数值下降快的优点；同时避免了计算Hessian矩阵及其逆矩阵，从而克服了牛顿法计算量大的缺点，但却有较快的收敛速度。所以，在目标函数的梯度容易计算的情况下，变尺度法是一种很有效的方法。 但在计算变尺度矩阵的公式中，其分母含有近似矩阵Ak,计算中容易引起数值不稳定，甚至可能得到奇异矩阵Ak。为提高实际运算稳定性，

35、通常将进行n次（n为目标函数的维数）迭代作为一个循环，将变尺度矩阵重置为n维单位矩阵I，并以一个循环的终点作为起点，进行下一轮的迭代。42 BFGS变尺度法为了进一步改善DFP变尺度法在实际计算中存在的算法稳定性，Broydon等人提出了改进的算法BFGS变尺度法。 BFGS法与DFP法的不同之处在于修正矩阵Ak的计算公式不同。kkkkkkkkkkkkkkkkkkgXXgAAgXgXXXgXgAgABFGS 的修正矩阵：的修正矩阵：1(4-7)完全相同。完全相同。与式与式、变量变量上式中所用的基本上式中所用的基本)64( kkkAgXuBFGS变尺度法的特点变尺度法的特点 BFGS法的修正矩阵

36、法的修正矩阵Ak的计算公式分母中不再有的计算公式分母中不再有近似矩阵近似矩阵Ak 。 BFGS法的优点在于计算中它的数值稳定法的优点在于计算中它的数值稳定性强，该方法是变尺度法中最受欢迎的一种算法。性强，该方法是变尺度法中最受欢迎的一种算法。434.8 共轭梯度法共轭梯度法是由弗来特(Fletcher)和里伍斯(Reeves)提出的。共轭梯度法是共轭方向法的一种，因为在该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，故称共轭梯度法。cxbGxxxfk 考察二次函数考察二次函数21)(kkkkkkkkkkkkkkkkkkkkkkkkkGdxxGggbGxgbGxgggxxdxxdx

37、xxdGx )(111111111故有：故有：分别为：分别为：、点处的梯度点处的梯度、而在而在或或点，即点，即作一维搜索，到达作一维搜索，到达的某一共轭方向的某一共轭方向点出发，沿点出发，沿从从(4-8)n共轭方向与梯度之间的关系共轭方向与梯度之间的关系44图4.9 共轭梯度法的几何说明0)()(,)()84(0)(1 kkjjkjkjggddGddGdd：关系关系共轭方向与梯度之间的共轭方向与梯度之间的便可得到便可得到对两端前乘对两端前乘利用式利用式是共轭的，则有是共轭的，则有对对和和若若(4-9)正交。正交。的共轭方向的共轭方向与与的梯度之差的梯度之差与始点与始点进行一维搜索，其终点进行一

38、维搜索，其终点上式表明：沿方向上式表明：沿方向jkkkkkkddggxxd)(11 共轭梯度法便共轭梯度法便是利用这个性质是利用这个性质做到做到不必计算矩不必计算矩阵阵G就能求得共就能求得共轭方向轭方向。该性质。该性质的几何说明如图的几何说明如图4-8所示。所示。45n共轭梯度法的计算过程：共轭梯度法的计算过程：组成平面正交系。组成平面正交系。和和正交，即正交，即和和从而从而有有正交，正交，和和因此因此直的性质直的性质该点等值面的切面相垂该点等值面的切面相垂切点。根据梯度和切点。根据梯度和为切线和某等值曲线的为切线和某等值曲线的是以是以。点处的梯度点处的梯度计算出计算出。进行一维搜索，得进行一

39、维搜索，得沿沿即即点的负梯度点的负梯度第一个搜索方向取第一个搜索方向取设初始点设初始点100101100101110001000000, 0, 0)(,)1gdgggggddgdxgxdxxdgdgxx 46020211120210011001010100101100011011110, 0, 00)(0)()(,)2dgggdggggggggdgggdgggddgddgddgd 可求得可求得将此式展开，考虑到将此式展开，考虑到）有（有（由由系求得。系求得。据共轭方向与梯度的关据共轭方向与梯度的关为待定常数，它可以根为待定常数，它可以根式中式中即即两个方向的线性组合，两个方向的线性组合，与与为

40、为取取。作为下一步的搜索方向作为下一步的搜索方向求求所构成的平面正交系中所构成的平面正交系中、在在 47构构成成一一个个正正交交系系。、正正交交。由由此此可可知知，又又和和即即得得又又根根据据式式正正交交。和和，即即），因因此此（）考考虑虑到到（）（梯梯度度的的关关系系，有有共共轭轭，根根据据共共轭轭方方向向与与和和因因）（即即有有并并算算出出该该点点梯梯度度方方向向进进行行一一维维搜搜索索，得得沿沿210122102201012010200121211121, 0)94(000)(0, 0)(,ggggggggggdgdggdddgdggdgdxxd (4-9)为为待待定定系系数数。、式式中

41、中，设设。均均共共轭轭的的方方向向及及求求与与所所构构成成一一个个正正交交系系中中，、在在01001122210210)3 gggddddggg 48得设相互正交，从而有、考虑到）（）（关系，有与梯度的均共轭，根据共轭方向和与因为要求2122112211111112200011121012001120100112102,000)(0)(gggggggggggggggggggggggggggddd49) 1, 2 , 1 , 0(22111nkdgggdkkkkk从从而而得得出出因因此此12122221120011200111200112201001110)(dgggddgdggggggggdg

42、ggg 共共轭轭方方向向的的递递推推公公式式为为，如如此此继继续续下下去去可可求求得得方方向向继继续续进进行行一一维维搜搜索索再再沿沿2d(4-10)50止。一直到满足精度要求为新计算共轭方向，到的点作为初始点，重最优点时，则以最后得次搜索还未达到经标函数为非二次函数，给定允许值为止。若目代点处梯度的模小于搜索下去，直到最后迭沿着这些共轭方向一直n从共轭梯度法的计算过程可以看出，第一个搜索方向取从共轭梯度法的计算过程可以看出，第一个搜索方向取作负梯度方向，这是最速下降法。其余各步的搜索方向是将作负梯度方向，这是最速下降法。其余各步的搜索方向是将负梯度偏转一个角度，即对负梯度进行修正。因此，负梯

43、度偏转一个角度，即对负梯度进行修正。因此，共轭梯共轭梯度法实质上是对最速下降法进行的一种改进度法实质上是对最速下降法进行的一种改进，故它又称，故它又称旋转旋转梯度法梯度法。n共轭梯度法的特点：共轭梯度法的特点：程序简单，存储量少，具有最速下降法的优点。而程序简单，存储量少，具有最速下降法的优点。而在收敛速度上比最速下降法快，具有二次收敛性。在收敛速度上比最速下降法快，具有二次收敛性。51图4.10 共轭梯度法的程序框图开始 ,0 x给定给定00, 0gdk )(min:1kkkkkkkdxfdxx 1kg1* kxx?nk 10 kxxkkkkkkkdgdgg 12211 kk结束YNNY52

44、4.9 单纯形法单纯形法在实际工程的最优化问题中，目标函数的导数往往很难在实际工程的最优化问题中，目标函数的导数往往很难求出或者根本无法求出。单纯形法只需要计算目标函数值，求出或者根本无法求出。单纯形法只需要计算目标函数值，无需求其导数，因此计算比较简单，其几何概念也比较清无需求其导数，因此计算比较简单，其几何概念也比较清晰，属于直接法一类的无约束最优化方法。这类方法适用晰，属于直接法一类的无约束最优化方法。这类方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况。于不知道目标函数的数学表达式而仅知其具体算法的情况。这也是直接法的一个优点。这也是直接法的一个优点。n单纯形单纯形n维欧氏空

45、间维欧氏空间En中的中的单纯形，是指在单纯形，是指在n维空间中维空间中由由n+1个线性独立的点构成的简单图形或凸多面体个线性独立的点构成的简单图形或凸多面体。如：在一维空间中为由两点构成的如：在一维空间中为由两点构成的线段线段； 在二维空间中为由不在同一直线上的三个点构成的在二维空间中为由不在同一直线上的三个点构成的三角形三角形； 在三维空间中为由不在同一平面上的四个点构成的在三维空间中为由不在同一平面上的四个点构成的四面体四面体。53n基本思想基本思想u根据问题的维数根据问题的维数n,选取由选取由n+1个顶点构成的单纯形；个顶点构成的单纯形；u求出这些顶点处的目标函数值并加以比较，确定它们求

46、出这些顶点处的目标函数值并加以比较，确定它们当中有最大值的点及函数值的下降方向，再设法找到当中有最大值的点及函数值的下降方向，再设法找到一个新的比较好的点替换那个有最大值的点，从而构一个新的比较好的点替换那个有最大值的点，从而构成新的单纯形。成新的单纯形。随着这种取代过程的不断进行，新的单纯形将向着随着这种取代过程的不断进行，新的单纯形将向着极小点收缩。这样经过若干次迭代，即可得到满足收极小点收缩。这样经过若干次迭代，即可得到满足收敛准则的近似解。敛准则的近似解。n大致求优步骤：大致求优步骤：。反反射射、扩扩张张和和压压缩缩步步骤骤，即即中中，包包括括三三种种类类型型的的的的点点替替换换最最差

47、差点点的的过过程程在在选选择择新新的的比比较较好好54eXrXlXgXcXsX sXhX1x2x图4.11 单纯形法示意图（三三角角形形）。它它们们为为顶顶点点构构造造单单纯纯形形三三个个点点，并并以以（不不在在同同一一直直线线上上）的的为为线线性性独独立立上上在在平平面面glhXXXxx,21点点的的距距离离。点点至至的的距距离离等等于于至至点点的的取取法法是是使使反反射射点点。通通常常，反反射射这这个个步步骤骤成成为为的的反反射射点点，点点称称为为最最差差点点hccrrhrXXXXXXX优优过过程程。为为例例来来说说明明单单纯纯形形的的求求下下面面以以二二维维问问题题),()(21xxfX

48、f. 1)(,)()()()(),(),(为为反反射射系系数数，一一般般取取式式中中，连连线线的的延延长长线线上上取取一一点点和和并并在在两两点点）的的形形心心点点（在在此此为为以以外外的的所所有有顶顶点点为为此此要要找找出出除除点点并并形形成成新新的的单单纯纯形形。故故应应该该丢丢掉掉点点最最好好。点点最最差差，则则说说明明：若若并并作作比比较较。数数值值计计算算这这三三个个顶顶点点处处的的函函hccrrchclghhlhlghglhXXXXXXXXXXXXXXXfXfXfXfXfXf55;,)()()114(;, )()(;, )()(0 . 2, 0 . 22 . 1)(,)()(),(

49、)() 1rlghrgrrlghreleelghelecrceerhlrlrrXXXXXXfXfXXXXXXXfXfXXXXXXfXfXXXXXXXXfXfXfXfX单纯形而形成新的替换最差点则用反射点此时如果不成立，则不能扩张，若式，构成新的单纯形代替仍以说明扩张不利，舍弃如果，构成新的单纯形最差点代替说明扩张有利，就用如果。一般取为扩张系数，式中，并使处取一点向前进行扩张，在更远继续沿果，正确，可进一步扩大效则表明所取的探索方向时即当小于最好点的函数值若反射点的函数值，有以下几种情况：对新单纯形构造的影响关于反射点(4-11)(4-12)(4-13)56.,)()(5 . 0)(,)()(

50、)(),(),()()2slghhscrcsrhrgghrXXXXXfXfXXXXXXfXfXfXfXfXf，形形成成新新的的单单纯纯形形点点则则利利用用压压缩缩点点代代替替最最差差此此时时，若若。为为压压缩缩系系数数，常常取取式式中中，并并且且得得到到的的压压缩缩点点应应为为，压压缩缩，即即进进行行走走得得太太远远，应应缩缩回回一一些些则则表表示示时时即即当当值值但但大大于于次次差差点点的的函函数数小小于于最最差差点点的的函函数数值值若若反反射射点点的的函函数数值值(4-14)(4-15)(4-16)。，就就得得到到式式换换以以中中的的如如果果将将式式这这时时所所得得的的压压缩缩点点应应为为

51、之之间间，与与，即即将将新新点点压压缩缩至至时时，应应当当压压缩缩得得更更多多些些即即当当大大于于最最差差点点的的函函数数值值若若反反射射点点的的函函数数值值)174()154()()()()(),()()3hrchchccshshrhrXXXXXXXXXXXXfXfXfXf(4-17)57。收收缩缩成成单单纯纯形形所所示示，由由单单纯纯形形如如图图移移近近为为原原距距离离的的一一半半，皆皆向向，不不动动，其其余余各各顶顶点点使使最最好好点点向向最最好好点点进进行行收收缩缩，即即形形向向探探索索。这这时时可可使使单单纯纯不不成成立立，则则不不能能沿沿此此方方或或式式都都大大于于方方向向上上所所

52、有有点点的的函函数数值值如如果果在在,12. 4)164(, )()()4lghlghlhglhchXXXXXXXXXXXfXfXX图4.12 单纯形法中的收缩步。直至满足精度要求为止直至满足精度要求为止各步，逐渐缩小单纯形各步，逐渐缩小单纯形单纯形后，再重复开始单纯形后，再重复开始从以上各步得到新的从以上各步得到新的58u单纯形法的计算步骤：单纯形法的计算步骤：的的步步长长。各各坐坐标标轴轴方方向向可可有有不不等等找找不不到到最最优优点点。当当然然沿沿而而可可能能局局限限在在较较低低维维的的空空间间内内否否则则，就就会会使使探探索索范范围围个个向向量量线线性性无无关关：保保证证下下述述这这样

53、样选选取取顶顶点点，可可。可可取取为为构构成成初初始始单单纯纯形形的的步步长长接接近近最最优优点点时时要要减减小小。为为为为步步长长，一一般般取取值值范范围围个个坐坐标标轴轴的的单单位位向向量量；为为第第式式中中，）（个个顶顶点点找找到到其其余余以以步步长长出出发发沿沿各各坐坐标标轴轴方方向向，从从最最优优点点尽尽量量靠靠近近维维空空间间中中选选取取初初始始点点在在构构造造初初始始单单纯纯形形时时，先先。个个顶顶点点应应有有维维向向量量，因因此此单单纯纯形形为为元元函函数数，即即为为设设目目标标函函数数)0(1)0(1)0(1)0(3)0(1)0(2)0(1)0()0()0(1)0(1121,

54、7 . 16 . 1, 0 .155 . 01, 3 , 21: ) 1, 3 , 2(,)(,1)(XXXXXXnhienijheXXnjXnheXXnXXXnnXnXfniijjin59都大；都大；函数值函数值小，但比其余各顶点的小，但比其余各顶点的比比为次差点，即为次差点，即轮探索时的最好点，即轮探索时的最好点，即表示第表示第差点：差点：数值最大的顶点，即最数值最大的顶点，即最轮探索时所有顶点中函轮探索时所有顶点中函表示第表示第顶点，其函数值顶点，其函数值轮探索的第轮探索的第表示第表示第另外，令另外，令)()()();(,),(),(min)();(,),(),(max)();(:)()

55、()()()(1)(2)(1)()()(1)(2)(1)()()()(kjkhkgkgknkkklklknkkkhkhkjkjXfXfXfXXfXfXfXfkXXfXfXfXfkXXfjkX 6011)()()(211)()()(,2)()(2)(1, 2 , 1)(111. 4njkhkjknnjkhikjikinckhknXXnXjnixxnxXXX为为顶顶点点号号，或或为为各各坐坐标标方方向向的的序序号号；式式中中，计计算算点点），其其坐坐标标可可用用下下式式中中的的（相相当当于于图图心心外外，其其余余所所有有顶顶点点的的形形是是除除最最差差点点)(,) 1)()(2)(2)(3)(2)

56、()(2)()()(khknknknknkhknkgkhklXXXXXXXXXX的的反反射射点点：对对。求求的的形形心心各各顶顶点点以以及及除除最最差差点点以以外外其其余余，次次差差点点最最差差点点进进行行比比较较，找找出出最最好好点点计计算算各各顶顶点点的的函函数数值值并并即即可可进进行行以以下下步步骤骤：构构成成初初始始单单纯纯形形后后，61则则转转下下一一步步。即即反反射射点点比比最最好好点点差差，若若后后转转入入代代替替；否否则则用用并并转转步步骤骤代代替替则则用用后后，若若得得到到扩扩张张点点张张点点为为时时，则则进进行行扩扩张张，得得扩扩即即还还要要好好，比比最最好好点点如如果果反

57、反射射点点和和比比较较),()().5)5,),()()()()(,)2)()(3)()(3)()(4)()(4)(4)(2)(3)(2)(4)()(3)()(3)()(3klknkhknkhknklknknknknknknklknklknklknXfXfXXXXXfXfXXXXXXfXfXXXX)(),()()();5),()()3)(2)()(2)(5)()(3)()(3)()()(3)()(3)()(3knkhknknkhknkhknkgkhknkgknkgknXXXXXXXfXfXfXXXfXfXX压压缩缩点点为为：否否则则直直接接进进行行压压缩缩，得得后后进进行行压压缩缩，代代替替则

58、则用用若若，并并转转步步骤骤代代替替最最差差点点则则用用比比较较，如如果果与与次次差差点点将将反反射射点点62然然后后转转下下一一步步。收收缩缩后后的的单单纯纯形形顶顶点点为为收收缩缩，否否则则使使单单纯纯形形向向最最好好点点以以后后转转下下一一步步代代替替则则用用比比较较，若若后后与与最最差差点点求求得得压压缩缩点点1, 2 , 1)(5 . 0;),()()4)()()()()()()(5)()(5)()(5njXXXXXXXXfXfXXklkjklkjklkhknkhknkhkn为为任任意意的的小小数数。式式中中步步。后后转转第第否否则则使使及及则则停停止止迭迭代代并并输输出出进进行行收

59、收敛敛性性检检验验。若若11),( )()(11)5)()(21211)(2)(kkXfXXfXfnklklnjknkj634.10 HookeJeeves直接探索法直接探索法 HookeJeeves与与Powell又都属于模式探索方又都属于模式探索方法（法（Pattern Search Method）。）。 HookeJeeves法的程序简单，当变量数较少时比较有法的程序简单，当变量数较少时比较有效，适应性较强。但在每轮探索中包括了一次沿效，适应性较强。但在每轮探索中包括了一次沿坐标轴的移步，其收敛速度虽比坐标轮换法有所坐标轴的移步，其收敛速度虽比坐标轮换法有所改善，但仍然较慢。同样不适合高

60、维数问题。改善，但仍然较慢。同样不适合高维数问题。每一轮探索包括两种移动：每一轮探索包括两种移动：探测性移动和模探测性移动和模式性移动。式性移动。64。轮探测的基准点为轮探测的基准点为动阶段。第动阶段。第这样就完成了探测性移这样就完成了探测性移点或基点），点或基点），本轮探测性移动的基准本轮探测性移动的基准坐标轴探测的下降点（坐标轴探测的下降点（个个沿第沿第个坐标轴探测，得到的个坐标轴探测，得到的维问题的维问题的依次沿依次沿方向试探。方向试探。降点，则退回，并沿反降点，则退回，并沿反反之，若所得点为非下反之，若所得点为非下移动；移动；初始点沿下一个坐标轴初始点沿下一个坐标轴成功，并以此点为新的