无约束优化计算方法

1、第四章第四章无约束问题的最优化方法无约束问题的最优化方法4.1 4.1 引言引言4.2 4.2 单变量优化计算方法单变量优化计算方法4.3 4.3 多变量优化计算方法多变量优化计算方法4.4 4.4 多变量优化计算的梯度方法多变量优化计算的梯度方法4.5 4.5 多变量多变量无约束优化设计方法小结无约束优化设计方法小结4.1 4.1 引言引言一一. . 目的：目的：求一组求一组 n n 维设计变量维设计变量 X= xX= x1 1, x, x2 2 , ,x ,x n n T T, , 使目标函数达到使目标函数达到 min. f(x) XRmin. f(x) XRn n即求目标函数的最优解：最

2、优点即求目标函数的最优解：最优点 x x* * 和最优值和最优值 f(xf(x* *) ) 。二二.意义意义：l 为有约束优化方法的研究提供了策略思想、概念基础和基本方为有约束优化方法的研究提供了策略思想、概念基础和基本方法；法；l 为有约束优化问题的间接解法提供了有效而方便的方法；为有约束优化问题的间接解法提供了有效而方便的方法；l 对于某些工程问题，进行分析后，便于提供解决的有效方法；对于某些工程问题，进行分析后，便于提供解决的有效方法；l 不可避免地还存在无约束优化的设计问题。不可避免地还存在无约束优化的设计问题。4.1 4.1 引言引言三三. . 内容：内容：一维搜索：一维搜索： 求最

3、优步长因子求最优步长因子(k)(k)多维（变量）优化：确定搜索方向多维（变量）优化：确定搜索方向 S (k)S (k)黄金分割黄金分割插值法插值法坐标轮换法坐标轮换法共轭方向法共轭方向法梯度法梯度法共轭梯度法共轭梯度法牛顿法牛顿法DFPDFP变尺度法变尺度法 定义定义:在第在第K K次迭代时，从已知点次迭代时，从已知点 X X(k)(k)出发，出发，沿给定方向求最优步长因子沿给定方向求最优步长因子(k)(k)，使，使 f f (X(X(k)(k) + + S S(k) (k) ) )达到最小值的过程，称达到最小值的过程，称为一维搜索。为一维搜索。方法：方法：1.解析法：解析法： f(x(k+1

4、)=min.f(x(k)+S(k)=f(x(k)+(k)S(k) 步骤步骤: : f(X f(X(k)(k) + S + S(k) (k) ) ) 沿沿S S(k)(k) 方向方向x x(k)(k) 台劳展开；台劳展开； 取二次近似：取二次近似： )()()(2)()()()()()(21)()(kkTkkTkkkkSxHSSxfxfSxf 4.2.1 4.2.1 搜索区间的确定：搜索区间的确定： 4.2 4.2 单变量优化计算方法单变量优化计算方法：0)()()(kkSxfdd对对求导，令其为零。求导，令其为零。 0)()()()()()()(kkTkkTkSxHSSxf)()()()()(

5、)()()(kkTkkTkkSxHSSxf2. 2. 数值迭代法：数值迭代法：直接法直接法应用序列消去原理：应用序列消去原理： 分数法、分数法、黄金分割法黄金分割法近似法近似法利用多项式函数逼近（曲线拟合）原理：利用多项式函数逼近（曲线拟合）原理： 二次插值法二次插值法、 三次插值法三次插值法 求得最优步长因子求得最优步长因子： 4.2.1 4.2.1 搜索区间的确定：搜索区间的确定： 4.2.1 4.2.1 搜索区间的确定：搜索区间的确定：单峰区间：单峰区间： 在区间在区间 1 1，3 3 内，函数只有一内，函数只有一个峰值，则此区间为单峰区间。单峰个峰值，则此区间为单峰区间。单峰区间内，一

6、定存在一点区间内，一定存在一点* *，当任意一，当任意一点点2 2* *时，时，f(f(2 2) )f(f(* *) )，说明：说明：l 单峰区间内，函数可单峰区间内，函数可以有不可微点，也可以以有不可微点，也可以是不连续函数；是不连续函数；f(x)0130f(x)31f()32*10当当2 2* *时，仍有时，仍有f (f (2 2 ) ) f(f(* *) ) ，则，则* *是最优点，也即为最优是最优点，也即为最优步长因子步长因子(k)(k)。2l确定的搜索区间必定确定的搜索区间必定是一个含有最优点是一个含有最优点* *的的单峰区间。单峰区间。 4.2.1 4.2.1 搜索区间的确定：搜索

7、区间的确定：给定初始点给定初始点(0)(0)、初始步长、初始步长h,h,求初始搜索区间的步骤求初始搜索区间的步骤: :(0)(0) 可任取，最好接近最小点，可取可任取，最好接近最小点，可取(0)(0)=0=0，h0,h0,(2)(2)令令(0)(0)(1)(1) ， (1)(1)+h+h(2)(2) ,得两个试点得两个试点(1)(1)(2)(2) 计算计算f(f(1)(1), f(), f(2)(2),),令令f(f(1(1）)f)f1 1, f(, f(2(2）)f)f2 2, ,(3)(3)比较比较f f1 1与与f f2,2,若若f f2 2fff3 3, ,则则以以（3 3）为起点，步

8、长加倍，直至两端大中间小，为起点，步长加倍，直至两端大中间小，（4 4）f f2 2ff1,1, 则后退则后退 运算。运算。 （如图）（如图） 4.2.1搜索区间的确定：搜索区间的确定： 4.2.1 4.2.1 搜索区间的确定：搜索区间的确定：定步长搜索法定步长搜索法: : 。it3，若不是若是，转第步；：1ifif判断)；if(tif,t1it1,ii ,0tit令。2t3，2t1，若不是若是，转第步；：1f2f判断)；2f(t2f,0t12t ,0t0t2,i令若不是，转第步；若是，转第步；：1f2f判断)；2f(t2f,0t12t2,i令)；1f(t1，f0)、初始步长t1(t1选初始点

9、 3. 3. 加速步长搜索法加速步长搜索法：.0t2i或t0t1i2t0tit 4. 4. 外推法：外推法：2111ittf 2 =f (1+t0 ) 1f1 。*,)f()若f(；*,)f()若f(则收敛，,）（中，,第m次在区间收敛条件：；,舍去，,)则*f()此例中f(,)和f(f(比较）；（）（）（，,）内取两点,（此例中在,第二次在区间；,舍去，,)则*f()若f(；,和,舍去，,)则*f()若f(；,舍去，,)则*f()若f(),)和f(f(比较）（），（，,内取两点,第一次在区间1）；（0定公比(m)1(m)3(m)1(m)3(m)3(m)1(1)1(1)31m(m)1(m)3(

10、m)3(m)1(2)32222(2)122212221(1)1(1)3(2)122(1)1(1)32(1)3(2)1(2)3(2)3212221(1)311(2)3(2)111(1)1(1)3111211(1)31211(1)112111211(1)31212(1)112111211(1)1(1)3(1)112(1)1(1)3(1)3111211(1)3(1)14.2.2 4.2.2 黄金分割法黄金分割法 (0.618(0.618法法) )1. 1. 序列消去原理：序列消去原理：f()3(1)12*1(1)03(2)1121221(2)1(3)3(3)4.2.2 4.2.2 黄金分割法黄金分割

11、法 (0.618)(0.618)在搜素区间在搜素区间a,ba,b内内, ,任取两点任取两点(1(1）与与(2(2），且，且aa(1) (1) (2) (2) bb计算计算f(f(1)(1),),与与f(f(2)(2),),并进行比较。有三种情况：并进行比较。有三种情况：（1 1） f(f(1)(1), f(), f() f(2)(2),), （图（图c c、d)d) 丢掉丢掉a,a,(1)(1) )， * *必在必在 (1)(1),b,b内内（3 3） f(f(1)(1)=f()=f(2)(2),),（图（图e e） 这时，不论丢掉这时，不论丢掉a,a,(1)(1) ) 还是还是(2)(2),

12、b, ,b, * *必在留必在留 下的部分内下的部分内对于第对于第(1)(1)、(2)(2)种情况，只要种情况，只要再取一个点再取一个点(3)(3) 就可进行比较、就可进行比较、消去。但对于第三种情况，就要消去。但对于第三种情况，就要补充两个点。因此第三种合并为补充两个点。因此第三种合并为前两种前两种: :(1)(1) f( f(1)(1)f()f(2)(2) )、 (2) f(2) f(1)(1)f()f(2)(2) )4.2.2 4.2.2 黄金分割法黄金分割法 (0.618)(0.618)2. 2. 黄金分割与黄金分割与0.6180.618：bd 古希腊建筑师认为：边长为古希腊建筑师认为

13、：边长为 b b，d d 的矩形建筑的矩形建筑物，若边长能符合以下条件，则最美观：物，若边长能符合以下条件，则最美观：618. 001,2解得，则dbddb欧几里德几何称这种边长分割为黄金分割。欧几里德几何称这种边长分割为黄金分割。 序列消去法中，为提高效率，减少计算量和存序列消去法中，为提高效率，减少计算量和存储量，储量，希望在每一次缩短搜索区间迭代过程中希望在每一次缩短搜索区间迭代过程中两计算点两计算点(1)(1)、(2)(2)，在区间中的位置相对于边，在区间中的位置相对于边界来说应是对称的，而且还要求丢去一段后保留界来说应是对称的，而且还要求丢去一段后保留点在新区间中的位置与丢去点再原区

14、间中的位置点在新区间中的位置与丢去点再原区间中的位置相当。相当。令令a,ba,b长为长为L, L, 并令并令l/L=l/L= 2 2+ +-1=0 -1=0 =0.6180339887=0.6180339887 llLLl0.618法计算程序框图3.4 3.4 二次插值法（抛物线法）二次插值法（抛物线法）1. 1. 基本原理：基本原理： 。的最优点近似的极小值，以拟合曲线即用抛物线逼近拟用一元二次多项式的一元函数，是*,)(21fpfpfcbapSxfxfpkkk步骤：步骤： 133221321213132133221322212212312322323332222212111321231,f

15、ffcfffbfcbapfcbapfcbappfff：解得，得：，代入，已知函数值，及中间任意一点，选目标函数值的点。三个已知确定二项式系数，需选3.4 3.4 二次插值法（抛物线法）二次插值法（抛物线法）2. 2. 步骤步骤 ( (续续) )： 32112122131312121,)(212*02cffcffccccbcbddpp其中得令3. 3. 结果分析：结果分析：。，重取插值点，再拟合若不满足，则缩小区间。则且。则且，若满足判断是否满足精度：代替校核以若外，结论：重新处理。在其中若。：轴的直线上，结论位于一条平行与则若4422422423414314341423212*,*,*,0,*

16、,0*,0fffffffcpp问题：若不满足精度，如何缩小区间，再拟合（分四种情况分析）问题：若不满足精度，如何缩小区间，再拟合（分四种情况分析） ？ p*=44.2.3 4.2.3 二次插值法（抛物线法）二次插值法（抛物线法）(1)确定初始插值点确定初始插值点(1)(1)=a,=a,(3)(3)=b=b， (2)(2)=0.5(=0.5(1)(1)+ + (3)(3) )计算计算f f1 1,f,f2 2,f,f3 3, ,构成构成p p1 1,p,p2 2,p,p3 3(2)(2)计算计算p p* *= =(4)(4)、f f4 4(3)(3)缩短搜索区间缩短搜索区间 取取f f2 2,f

17、,f4 4小者的点为小者的点为(2)(2) 两侧邻点为两侧邻点为(1)(1)、(3)(3) 根据原区间中根据原区间中(4)(4)，(2) (2) 的相对位置及的相对位置及f f2 2,f,f4 4的比的比较，有四种情况（如图）较，有四种情况（如图）, ,阴影线部分为丢去的，再对阴影线部分为丢去的，再对新区间三个新店代号一次作新区间三个新店代号一次作(1)(1)、(2)(2)、(3)(3)处理。计处理。计算算f f1 1,f,f2 2,f,f3 34.2.3 4.2.3 二次插值法（抛物线法）二次插值法（抛物线法）算法框图算法框图4.2.3 4.2.3 二次插值法（抛物线法）二次插值法（抛物线法

18、） 与黄金分割法相比，二次插值法充分利用函数值的信息；与黄金分割法相比，二次插值法充分利用函数值的信息；收敛快；调用函数次数少。收敛快；调用函数次数少。4.4.方法评价方法评价: :4.2 4.2 坐标轮换法和坐标轮换法和 Poweel Poweel 法法一一. . 坐标轮换法：坐标轮换法：1. 1. 基本思想：基本思想：2. 2. 搜索方向与步长：搜索方向与步长： 每次以一个变量坐标轴作为搜索方向，将每次以一个变量坐标轴作为搜索方向，将 n n维的优化问题转化为一维搜索问题。例，第维的优化问题转化为一维搜索问题。例，第 k k轮迭代的第轮迭代的第 i i 次搜索，是固定除次搜索，是固定除 x

19、 xi i外的外的 n-n-1 1 个变量，沿个变量，沿 x xi i 变量坐标轴作一维搜索，求变量坐标轴作一维搜索，求得极值点得极值点 x xi i(k)(k) n n 次搜索后获得极值点序列次搜索后获得极值点序列 x x1 1(k)(k), x, x2 2(k(k）, , x, xn n(k)(k)，若未收敛，则开始第，若未收敛，则开始第 k+1 k+1 次迭代，直至收敛到最优点次迭代，直至收敛到最优点 x x* *。 。：次搜索的收敛条件轮第第；：次搜索的迭代公式轮第第；：次搜索的步长轮第第向；个设计变量的坐标轴方为第次搜索的方向：轮第第)()()()()(1)()()()(,.,2 ,

20、 1,kikikikikikikikikiSikniSxxikSikiSik4.3.1 4.3.1 坐标轮换法坐标轮换法算法框图算法框图4.3.1 4.3.1 坐标轮换法坐标轮换法加速步长法：加速步长法：( )( )134()(),2iiikkiitf xf xi(k)(k)ii-11ii1、先规定初始步长 ，探测下降方向2、取初始步长的若干倍作为搜索步长t、以计算新点 x=x+ e、若取继续向前， 直到目标函数值增大，取前一点为本次新点5、不满足精度时取t =(0.10.5)4.3.1 4.3.1 坐标轮换法坐标轮换法例例4-1 4-1 设目标函数设目标函数求其无约束的最优点（求其无约束的最

21、优点（x x1 1* *,x,x2 2* *）。）。解：目标函数的等值线及加速步解：目标函数的等值线及加速步长的搜索路线如图所示。长的搜索路线如图所示。22141212221212922244)(xxxxxxxxxxf2 . 425. 20125. 02 . 45 . 225. 0,25. 00625. 042),(76.20)(2 . 425. 20125. 02 . 45 . 20625. 0042.25)(,2 . 4 5 . 21 10)1(101101100sxxttxfxfsxxxxfxT）取取试试验验步步长长应应正正值值。轴轴的的移移动动方方向向：沿沿。先先判判断断。试试验验步步

22、长长取取，）取取初初始始点点053. 1)(,025. 1 ,053. 1)(08. 7)(2 . 20 . 21025. 082 . 40 . 2),(2 . 7)(95. 30 . 21025. 02 . 40 . 23 68.16)(,2 . 40 . 2 )(74.16)(2 . 45 . 10125. 042 . 45 . 225. 044)(68.16)(2 . 40 . 20125. 022 . 45 . 25 . 025. 022)(4125.19)(*)1(2)1(2)1(2)1(1)1(22)1(1)1(22)1(1)1(11)1(1)1(1)1(1)1(1)1(1)1(1

23、)1(1)1(1xfxxfxfxxfxfsxxxxfxxxfxfxxfxfxxfxfT最最优优化化值值为为求求得得最最优优化化点点为为依依次次继继续续下下去去，最最后后可可试试验验步步长长应应取取负负值值。方方向向搜搜索索：）沿沿方方向向得得到到的的好好点点为为故故沿沿再再加加大大步步长长取取加加大大步步长长取取4.3.1 4.3.1 坐标轮换法坐标轮换法)(ki4.4.最优步长法：最优步长法： 最优步长法就是利用一维优化搜索方法(如0.618方法或二次插值方法)，求出每维搜索计算的 值，如图所示。在这种情况下，每一次沿坐标方向进行搜索计算，都使目标函数值降至最小，如此反复迭代计算，直至达到收

24、敛条件 为止。)( kis4.3.1 4.3.1 坐标轮换法坐标轮换法3. 3. 方法评价：方法评价：方法简单，容易实现。方法简单，容易实现。当维数增加时，效率明显下降。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点收敛慢，以振荡方式逼近最优点。 受目标函数的性态影响很大。受目标函数的性态影响很大。 如图如图 a) a) 所示，二次就收敛到极值点；所示，二次就收敛到极值点； 如图如图 b) b) 所示，多次迭代后逼近极值点；所示，多次迭代后逼近极值点； 如图如图 c) c) 所示，目标函数等值线出现山脊（或所示，目标函数等值线出现山脊（或称陡谷），若搜索到称陡谷），若搜索到 A A

25、点，再沿两个坐标轴，以点，再沿两个坐标轴，以t t0 0步长测试，目标函数值均上升，计算机判断步长测试，目标函数值均上升，计算机判断 A A 点为最优点。事实上发生错误。点为最优点。事实上发生错误。4.3.2 4.3.2 Poweel Poweel 法法（共轭方向法、方向加速法）：（共轭方向法、方向加速法）：1. 1. 基本思想：基本思想：2. 2. 共轭方向的定义：共轭方向的定义：若沿连接相邻两轮搜索末端的向量若沿连接相邻两轮搜索末端的向量 S S 方向搜索，收方向搜索，收敛速度加快。敛速度加快。(1)2x(2)2xS其中： 因为两条平行线因为两条平行线 S S1 1, S, S1 1与同心

26、椭圆族相切，两个切与同心椭圆族相切，两个切点的连线点的连线 S S 直指中心。称直指中心。称 S S1 1, S, S1 1 与与 S S 为共轭方向。为共轭方向。 目的目的：以共轭方向打破振荡，加速收敛。：以共轭方向打破振荡，加速收敛。阵A共轭。则称这组向量是关于矩j),(i0jASTiS能满足,nS,.,2S ,1若有一组非零向量S，设A为正定实对称矩阵正交。2和S1S则0,2ST1S即，0时2IST1S则，若A为单位矩阵I的方向是共轭方向。2和S1S是关于矩阵共轭，2和S1S则称向量,02AST1S满足，2和S1S若有两个n维向量，设A为实对称正定矩阵 4.3.2 4.3.2 Powee

27、l Poweel 法法（共轭方向法、方向加速法）：（共轭方向法、方向加速法）：3. 3. 共轭方向的性质：共轭方向的性质：二次收敛性。为步可收敛至极值点，称多方向进行一维搜索，至出发，依次沿从任意初始点，次函数个非零向量，则对于二矩阵共轭的是关于设矩阵共轭。中每一个向量关于，也是与向量组，向量和搜索，分别得到最优点方向进行一维出发，沿和分别从两个初始点个非零向量，对于函数矩阵共轭的是关于设。满足，个向量则可以构造出是线性无关的向量组，若是线性无关的。个非零向量矩阵共轭的这组关于）（）（）（）（）（）（nniSxAXXXBCxfnASSSAniSxxSxxniSxxxfnASSSjiSASSSS

28、nSSSSSSnAiTTniinjTinnn),.,2 , 1(21)(,.,),.,2 , 1(),.,2 , 1()(,.,)(,0,.,.,.,)0(211221)2(0)1(021)2()2(2222111211214.3.2 4.3.2 Poweel Poweel 法法4. 4. 步骤：步骤： 。的极值点xx作第三次搜索，求得f，沿此方向xx构筑共轭方向：S。x,的极值点xx分别求得f作两次一维搜索，S,两个坐标轴方向S，依次沿xx，令选初始点x第一轮迭代：131012112111211(0)10(0)4.3.2 4.3.2 Poweel Poweel 法法4. 4. 步骤：步骤：

29、迭代。若不满足，则作下一轮。xx*则,若满足。fff或,xx是否满足收敛条件：每轮迭代结束时，检验。的极值点xx作第三次搜索，求得f，沿此方向xx构筑共轭方向：S。x,的极值点xx一维搜索，分别求得f方向作两次S,，分别沿Sxx令第二轮迭代：1)(k321k0k01k01k01k023202222221112(1)3204.3.2 4.3.2 Poweel Poweel 法法6. 6. 方法评价：方法评价：l 计算步骤复杂计算步骤复杂; ;l 是二次收敛方法，收敛快。对非正定函数，也很有效是二次收敛方法，收敛快。对非正定函数，也很有效; ;l 是比较稳定的方法。是比较稳定的方法。 5. 5.

30、说明：说明：l 若是正定二次函数，若是正定二次函数，n n 轮迭代后收敛于最优点轮迭代后收敛于最优点 x x* * 。 若是非正定二次函数，则迭代次数增加。若是非正定二次函数，则迭代次数增加。l若是若是 n n 维问题，步骤相同。维问题，步骤相同。 搜索方向：第一轮迭代，沿初始方向组搜索方向：第一轮迭代，沿初始方向组 S Si i(1)(1) (i=1,2, (i=1,2,n) ,n) 的的 n n 个方向和共轭方向个方向和共轭方向 S S(1)(1)，搜索，搜索 n+1 n+1 次得极值点次得极值点 x xn+1n+1(1)(1) ；第二轮；第二轮迭代，沿方向组迭代，沿方向组 S Si i(

31、2)(2) ( i=1,2, ( i=1,2,n,n；im ) im ) 的的 n-1 n-1 个方向和共个方向和共轭方向轭方向 S S(1)(1)，构筑共轭方向，构筑共轭方向 S S(2) (2) 搜索搜索 n+1n+1次得极值点次得极值点 x xn+1n+1(2)(2) 。其。其中，为保证搜索方向的线性无关，去除了中，为保证搜索方向的线性无关，去除了 S Sm m(2) (2) 方向方向 。l 在第在第 k k 轮迭代中，为避免产生线性相关或近似线性相关，需轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向要去除前一轮中的某个方向 S Sm m(k)(k)。去除的原则请

32、自学。去除的原则请自学。4.3.2 4.3.2 Poweel Poweel 法法4.3.2 4.3.2 Poweel Poweel 法法Poweel法计算框图例例4-2 4-2 用用PowellPowell法求函数法求函数4.3.2 4.3.2 Poweel Poweel 法法的最优点的最优点x x* *=x=x1 1* *，x x2 2* * T T。计算精度要求。计算精度要求0.00010.0001解：取初始点解：取初始点 x x0 0（1 1）x x(0)(0)=0=0，00T T，第一轮，第一轮迭代的搜迭代的搜索方向取两个坐标的单索方向取两个坐标的单位向量位向量从从 出发，先从出发，先

33、从 方向进行一维最优搜索，计算出最方向进行一维最优搜索，计算出最优步长优步长 由此得最优点由此得最优点)1(0 x)1(1s。 5)1(12122212141060)(xxxxxxxf10 012)1(21)1(1eses和和0501500)1(1x方方向向上上的的极极小小点点。，并并求求替替换换成成立立，故故应应以以检检验验判判别别条条件件下下降降量量计计算算相相邻邻二二点点函函数数值值的的方方向向上上的的反反射射点点计计算算个个方方向向计计算算第第优优点点方方向向进进行行一一维维搜搜索索得得最最同同理理，沿沿)1(3)1()1(3231)1(2)1(2132113)1(33)1(22)1(

34、011)1(1)1()1(1)2(2)1(1)1()1(2)1(1)1(2)1(1)1(0)1(1)1(2)1(1)1(0023)1(302)1(3)1(2)1(2)5 .253128 .18657( ,)(5 . 0)(2()6015( ,15)(,75.14)(,60)(,25,max25.20)()(,25)()(75.14)(,35)(,60)( 9102 5 . 45005 . 45 15 . 45105 . 405sssfffffffffxffxffxffessxfxfxfxfxfxfxfxxxsxxsnxsmmmmm08695. 07362. 54725. 710)9891. 0

35、(7253. 64725. 75 . 45,107253. 64725. 7* 22753. 64725. 75 . 454945. 05 . 45*4945. 05 . 4521125 . 4,55 . 450,912. 7)()2(2)2(2)2(2)2(1)2(2)2(1)2(1)2(0)2(1)1(3)2(22)1(2)2(1)2(0)1(33125 . 4521125 . 4,55 . 450,5 . 4)(33)2(2)2(2)2(2)2(113)1(3)1(3)1(2HsssxfHsssxfTTTTsxxsxxssessxxksxx其其中中时时当当为为优优化化步步长长)2(3)2

36、(3)2(2)2(3231)1(2)2(2132113)2(1)2()2(2)2(1)2(2)2(1)2(0)2(1)2(3)2(2)2(1)2(0)2(0)2(2)2(3)2(0)2(2)2(3)2(2*)2313. 00477. 0( ,)(5 . 0)(2)1869. 94991. 8( ,9782. 01720. 0)()(9782. 02087. 81869. 9)()(4991. 8)(,0367. 8)(,2087. 8)(,1869. 9)(5297. 53421. 825978. 04348. 07253. 64725. 71275. 69073. 71275. 69073.

37、 75 . 4508695. 07362. 54725. 7sxxsfffffffffxfxfxfxfxfxfxfxfxxxxxsxmmm一维搜索一维搜索成立，故沿成立，故沿（判别条件判别条件次一维搜索。总共进行，故停止运算。，误差已小于精确解其中：60001. 068*0001. 69999. 75978. 04348. 0213. 01275. 69073. 7*213. 05978. 04348. 021125978. 0,4348. 05978. 04348. 03477. 0,3129. 0)()2(3)2(3)2(3)2(3)2(2xxHsssxfTT4.3.3单纯形法单纯形法单纯

38、形法单纯形法是一种利用单纯形法是一种利用n n维设计空间中的几何图形不断向好点移维设计空间中的几何图形不断向好点移动迭代的一种算法。动迭代的一种算法。 单纯形法是在单纯形法是在n n维设计空间内由维设计空间内由n+1n+1个顶点组成的几何形体，如在个顶点组成的几何形体，如在二维空间，单纯形为三角形，在三维空间内为四面体等。若各顶二维空间，单纯形为三角形，在三维空间内为四面体等。若各顶点间的距离相等，则称为正单纯形。点间的距离相等，则称为正单纯形。(a) 二维空间三角形的反射(b) 三维空间四面体的收缩4.3.34.3.3单纯形法单纯形法单纯形法迭代的单纯形法迭代的基本要点基本要点是是如何保证单

39、纯形不断地向优点如何保证单纯形不断地向优点移动并使单纯形缩小直到趋于一点。移动并使单纯形缩小直到趋于一点。这个过程是通过所谓反射，这个过程是通过所谓反射，收缩和扩展三种运算实现的。收缩和扩展三种运算实现的。1, 2 , 1),(max)( 1, 2 , 1),(min)( 11njxfxfxnjxfxfxjhhj设单纯形的设单纯形的n+1n+1个顶点为个顶点为x xj j(j=1(j=1，2 2，n+1)n+1)计算出它的目标函数值计算出它的目标函数值f(xf(xj j) )，并从中确定出目标函数值最小的点，并从中确定出目标函数值最小的点x xl l 和最大点和最大点x xh h , ,即即并

40、计算出除并计算出除x xh h点外的其余所有点的形心点外的其余所有点的形心x x0 0 。即。即然后可以进行单纯行的移动运算然后可以进行单纯行的移动运算：), 2 , 1(1)(10nixxnhjijjini如果如果 x xh h为单纯形顶点中目标函数值最大的顶点，如图为单纯形顶点中目标函数值最大的顶点，如图(a)(a)所示，所示，则应以形心为镜面像其对面反射可能获得目标函数值小于它的点则应以形心为镜面像其对面反射可能获得目标函数值小于它的点x xr r，即称即称反射点反射点，即，即 其中其中 为为反射系数反射系数。这样。这样x xr r 点将位于点将位于x xh h 和和x x0 0的连线上

41、，它与的连线上，它与x x0 0点的距离为点的距离为4.3.3单纯形法单纯形法如果 f(xr) 的值小于f(xh) ，则xr 为一个新的单纯形，如图中的三角形x1x2xr。如果反射点xr的目标函数值，刚好等于xh的目标函数，则这两点刚好是目标函数脊线为镜面的对称点，这时将使搜索过程陷入死循环，对此可以利用目标函数值次最大值点xg，用它进行反射得新的xr 或是用xr替换xg点形成一个新的单纯形。0)1 (xxxhr(1) 反射：000 xxxxhr4.3.3单纯形法单纯形法如果反射点xr的f(xr) f(x1) 则xr 为一个新的目标函数值最小点。此时沿x0和xr方向可以进一步移动，有可能获得更

42、小目标函数值的点。因此，扩展点扩展点x xe e为其中 为扩展系数扩展系数，它与x0点的距离为 如果f(xe) f(x1) ，则用xe代替xh，构成新单纯形，进入下次的运算过程。若f(xe) f(x1) ，则表示扩展不成功，仍用xr代替xh构成新单纯形，再进入下一次运算过程。 0)1 (xxxre（2）扩展100 xxxxre4.3.3单纯形法单纯形法如果反射点如果反射点x xr r的函数值的函数值f(xf(xr r) )虽小于虽小于f(xf(xh h) ) ，但它大于所有其余，但它大于所有其余各点的值，则可用各点的值，则可用x xr r代替代替x xh h，这时，在新单纯形中的，这时，在新单

43、纯形中的x xh h为原来的为原来的x xr r，并缩小这个单纯形，其收缩点为并缩小这个单纯形，其收缩点为x xc c 其中其中为收缩系数为收缩系数(0(01)1)。它与。它与x x0 0点的距离为点的距离为 如果如果 ，则用，则用x xc c代替代替x xh h点，再进行下点，再进行下一次运算过程，反之，这个收缩过程失败，此时可将所有单纯形的一次运算过程，反之，这个收缩过程失败，此时可将所有单纯形的顶点向最好点顶点向最好点x x1 1收缩收缩1/21/2，则用，则用 代替所有的顶点，然后再进行运算过程。代替所有的顶点，然后再进行运算过程。0)1(xxxhc（3）收缩00 xxxxhc)(),

44、(min)(rhcxfxfxf) 1, 2 , 1;, 2 , 1( 2/ )(njnixxxlijiji4.3.3单纯形法单纯形法如图所示，在迭代计算中，由于单纯形不断向最好点移动和缩小，因此当单纯形的n+1顶点的目标函数值的均方差很小，即 就认为算法收敛，终止计算，并令x*x1。2/1111)()(20njnxfxfjQ3 3、迭代格式：、迭代格式：X X(k+1)(k+1)=X=X(k)(k)- -(k)(k) f(X f(X(k)(k) )X X(k+1)(k+1)=X=X(k)(k)- -(k)(k)量。量。是负梯度方向的单位向是负梯度方向的单位向,)()()()()(kkkxfxf

45、S4.4 4.4 多变量优化设计的梯度方法多变量优化设计的梯度方法4.4.14.4.1梯度法（最速下降法）梯度法（最速下降法）：1. 1. 基本思想：基本思想：2. 2. 搜索方向：搜索方向： 目标函数负梯度向量方向代表最速目标函数负梯度向量方向代表最速下降方向，因此选择负梯度向量方向作下降方向，因此选择负梯度向量方向作为搜索方向，期望很快找到最优点。为搜索方向，期望很快找到最优点。)()()()(kkxfxf4.4.1 4.4.1 梯度法梯度法4. 4. 梯度法的计算框图：梯度法的计算框图：4.4.1 4.4.1 梯度法梯度法5. 5. 方法评价：方法评价：l 迭代过程简单，对初始点的选迭代

46、过程简单，对初始点的选择，要求不高。择，要求不高。l 梯度方向目标函数值下降迅速梯度方向目标函数值下降迅速只是个局部性质，从整体来看，只是个局部性质，从整体来看，不一定是收敛最快的方向。不一定是收敛最快的方向。l 以二维二次函数为例，相邻两以二维二次函数为例，相邻两次的搜索方向是正交的，所以搜次的搜索方向是正交的，所以搜索路径是曲折的锯齿形的；对于索路径是曲折的锯齿形的；对于高维的非线性函数，接近极值点高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形搜索处，容易陷入稳定的锯齿形搜索路径。路径。4.4.2 4.4.2 共轭梯度法共轭梯度法1. 1. 基本思想基本思想：2. 2. 共轭方向：共

47、轭方向：对梯度法作一个修正，将搜索方向对梯度法作一个修正，将搜索方向由负梯度方向旋转一个角度，使相邻由负梯度方向旋转一个角度，使相邻的两次搜索方向由正交变为共轭，成的两次搜索方向由正交变为共轭，成为二次收敛。为二次收敛。为共轭系数。(k)：其中,(k)S(k)1)(kf(x1)(kS1次搜索的方向为第k),(k)f(x(k)S第k次搜索的方向为3. 3. 共轭系数：共轭系数：2)(2)1()()()(kkkxfxf推导过程请参考书本。(k) S(k)4.4.2 4.4.2 共轭梯度法共轭梯度法步骤：步骤：转第步。,1kk令,S)f(xS：，构造新的共轭方向计算则进行下一步；，n若k转第步；，x

48、x则令，n若k，检查搜索次数步；若不满足，则进行第；xx*，若满足，则迭代结束,)f(x是否判断；Sxx方向作一维搜索，求得沿S)；f(xS计算，0k令；和计算精度选取初始点x(k)(k)1)(k(k)(k)1)(k(0)1)(k1)(k(k)(k)(k)1)(k(k)(k)(k)(0)Kn给定给定X0,n,K=1,X(K)=X0S(K)=-f(X(K)从从X(K)始始，沿沿S(K)进行一维搜索得进行一维搜索得X(K+1)K=K+1是是是是否否否否计算计算(1)(1)(),()KKfXfX(1)()Kf X结结 束束(1)(1)()KKXXff X) 1(0KXX(1)2( )(1)(1)(

49、)()()()()KKKKKKKf Xf XSf XS重置负梯度方向重置负梯度方向5.5.迭代框图迭代框图6. 6. 方法评价：方法评价：l迭代程序简单，容易实现编程，存储量较小。迭代程序简单，容易实现编程，存储量较小。l 需用到一阶导数需用到一阶导数l 开始采用梯度方向，目标函数值下降快，后又为旋转梯度方开始采用梯度方向，目标函数值下降快，后又为旋转梯度方 向，具有二次收敛性，收敛快。向，具有二次收敛性，收敛快。例例4-34-3设目标函数为设目标函数为 ，起始，起始点为点为x x(0)(0)00，00T T，试用共轭梯度法求其极小点。，试用共轭梯度法求其极小点。2122212141060)(

50、xxxxxxxf(1)(1)12,( )Txxf x将代入得4.4.2 4.4.2 共轭梯度法共轭梯度法解解：第一次迭代的方向为：第一次迭代的方向为：所以所以第二次迭代方向第二次迭代方向为为053.3631.7410 7631.0,0)()(7611660)(41041041042102)()0()0()1(0)*d)(d)0(2)0()0()1(2)1(1)0()0()0()0()1()0,0(1221)0()0()0()0(xfxfxxxxxxxxxfsf得得3054.0526.5210.242102)()()(2222222)0(2)1()410()526.5(210.2()()()0(

51、)1(1)1(2)1(2)1(1)1()0()0()1()1(xfxfxxxxxfxfxfs4.4.2 4.4.2 共轭梯度法共轭梯度法故经两次搜索即达极小点故经两次搜索即达极小点x x* *=8,6=8,6T T 。99999. 599999. 77479. 68434. 04367. 0052. 3631. 74367. 0 7479. 68434. 04103054. 0526. 5210. 2)1()1()1()2(7479. 68434. 021127479. 6,8434. 07479. 68434. 0521. 5,210. 2)(*(1)1()1()()()()(sxxsTTk

52、TkkrkHsssxf所所以以用用一一维维搜搜索索解解析析法法求求所所以以4.4.3 4.4.3 牛顿法和修正牛顿法牛顿法和修正牛顿法 1. 1. 基本思想：基本思想： 将将 f(x) f(x) 在在 x x(k)(k) 点作台劳展开，取二次函数式点作台劳展开，取二次函数式(x) (x) 作为近作为近似函数似函数, ,以以(x) (x) 的极小值点作为的极小值点作为 f(x) f(x) 的近似极小值点。的近似极小值点。( )( )( )( )( )( )( )( )( )( )( )( )1( )minmin( )( )1()()() ()()()2( )()()(),( )0,()(),*k

53、kkTkkTkkkkkkkkf xxxf xf xxxxxH xxxxf xH xxxxxxH xf xxx (k)(k+1)(k)(令得。由于在x 点附近，函数 (x)和f(x)是近似的，所以 x=x -H(xk) -1(k)f(x )说明：说明：lf(x) f(x) 若是正定二次函数，一般迭代一次即可；若是严重非若是正定二次函数，一般迭代一次即可；若是严重非线性函数，则可能不收敛，或收敛到鞍点。线性函数，则可能不收敛，或收敛到鞍点。)为牛顿步长。(K)f(x1)(k)H(x矩阵。为Hesse矩阵的逆1 )(k)H(x 4.4.3 4.4.3 牛顿法和修正牛顿法牛顿法和修正牛顿法212221

54、2141060)(xxxxxxxf21122112)(2112)(41024210)(31211211)0()0()0(1)0(2)0(2)0(1)0(xHxHxxxxxf例4-4 设目标函数为，试用牛顿法求其极小点。初始点取x(0)=0,0T解：先计算所以得由此可见（与例4-3比较），对于任何正定二次函数，只需迭代一次，即求出其极小点。可以证明，当目标函数满足一定条件，且初始点选得较好时，牛顿法的收敛速度是非常快的。68410211200)()(31)0(1)0()0()1(xfxHxx4.4.3 4.4.3 牛顿法和修正牛顿法牛顿法和修正牛顿法2. 2. 修正牛顿法：修正牛顿法：为最优步长

55、因子。(k)其中, )(k)f(x1)(k)H(x(k)(k)x1)(kx则称为牛顿方向，)(k)f(x1)(k)H(x(k)S令 算法框图：算法框图：4.4.3 4.4.3 牛顿法和修正牛顿法牛顿法和修正牛顿法l 使用牛顿法时，若目标函数是严重非线性函数，则是否收敛将使用牛顿法时，若目标函数是严重非线性函数，则是否收敛将与初始点有很大关系；而使用修正牛顿法，能保证每次迭代目标与初始点有很大关系；而使用修正牛顿法，能保证每次迭代目标函数值下降，从而放宽了对初始点的要求。函数值下降，从而放宽了对初始点的要求。l 若初始点选得合适，牛顿法的收敛速度相当快。若初始点选得合适，牛顿法的收敛速度相当快。

56、l 牛顿法求逆矩阵的工作量大，计算量与存储量均随牛顿法求逆矩阵的工作量大，计算量与存储量均随 n n2 2上升。上升。4. 4. 方法评价：方法评价：梯度法和牛顿法的比较：梯度法和牛顿法的比较：1 1、迭代格式、迭代格式)()()()(1)()()()1()()()()1(kkkkkkkkkxfxHxxxfxx2 2、梯度法只需计算一阶偏导数，计算工作量小，远离最优点时函、梯度法只需计算一阶偏导数，计算工作量小，远离最优点时函 数下降快，接近最优点时收敛速度慢。数下降快，接近最优点时收敛速度慢。3 3、牛顿法不仅需要计算一阶偏导数，还需计算二阶偏导数矩阵及其、牛顿法不仅需要计算一阶偏导数，还需计算二阶偏导数矩阵及其 逆矩阵，计算工作量大。但牛顿法具有二阶收敛性，接近最优点逆矩阵，计算工作量大。但牛顿法具有二阶收敛性，接近最优点 时收敛速度很快。时收敛速度很快。梯度法和牛顿法的比较梯度法和牛顿法的比较4.4.4 4.4.4 变尺度法变尺度法1. 1. 变尺度的定义：变尺度的定义：每确定一次搜索方向，调整一次模（尺度）的大小，称为变尺度。每确定