机械优化设计第三章ppt课件

1、第三章 无约束问题的 最优化方法主要内容 3.1 引言 3.2 一维搜索方法 3.3 坐标轮换法和 Powell 法 3.4 梯度法和共轭梯度法 3.5 牛顿法和变尺度法 3.6 无约束优化设计方法小结3.1 3.1 引言引言求一组 n 维设计变量 X= x1, x2 ,x n T, 使目标函数达到 min. f (X) X R n即求目标函数的最优解：最优点 x* 和最优值 f (x*) 。意义：意义： 为有约束优化方法的研究提供了策略思想、概念基础和基本方法； 为有约束优化问题的直接解法提供了有效而方便的方法； 不可避免地还存在无约束优化的设计问题。3.1 3.1 引言引言 （续）（续）内

2、容：内容：一维搜索：求最优步长因子(k)确定搜索方向 S (k)多维变量优化：黄金分割插值法坐标轮换法共轭方向法梯度法共轭梯度法牛顿法DFP变尺度法3.2 3.2 一维搜索方法一维搜索方法一、一维搜索定义：一、一维搜索定义： 在第K次迭代时，从已知点 X(k)动身，沿给定方向求最优步长因子(k)，使 f (X(k) + S(k) )达到最小值的过程，称为一维搜索。方法：方法：解析法： f (x (k+1) ) = min. f (x (k) + S (k) ) = f (x (k) + (k) S ( k) ) 步骤： f (X(k) + S(k) )沿S(k) 方向x(k) 台劳展开； 取二

3、次近似： 对求导，令其为零：)()()(2)()()()()()(21)()(kkTkkTkkkkSxHSSxfxfSxf0)()()(kkSxfdd3.2 3.2 一维搜索方法续）一维搜索方法续）0)()()(kkSxfdd对求导，令其为零。 0)()()()()()()(kkTkkTkSxHSSxf)()()()()()()()(kkTkkTkkSxHSSxf2. 数值迭代法：直接法应用序列消去原理：分数法 黄金分割法近似法利用多项式函数逼近曲线拟合原理： 二次插值法 三次插值法 求得最优步长因子：一、一维搜索定义：一、一维搜索定义：3.2 3.2 一维搜索方法续一维搜索方法续2 2）单峰

4、区间：单峰区间： 在区间 1，3 内，函数只有一个峰值，则此区间为单峰区间。单峰区间内，一定存在一点*，当任意一点2*时，f (2)f (*)，说明：说明： 单峰区间内，函数可以单峰区间内，函数可以有不可微点，也可以是有不可微点，也可以是不连续函数；不连续函数；二二. 搜索区间的确定：搜索区间的确定：f (x)0130f (x)31f ()32*10当2*时，仍有f (2 ) f (*) ，则*是最优点，也即为最优步长因子(k)。2 确定的搜索区间必定是一个含有最优点*的单峰区间。3.2 3.2 一维搜索方法续一维搜索方法续3 3）定步长搜索法定步长搜索法: 。，若不是步；若是，转第：判断；令

5、。，若不是步；若是，转第：判断；令步；若不是，转第步；若是，转第：判断；令；，、初始步长选初始点iiiiiitfftffttiititttfftffttttifftffttitfftt31102321122201200122201211011)(, 1,)(, 2)(, 2)()(3. 加速步长搜索法：加速步长搜索法：.202010tittttiti或4. 外推法：外推法：2111ittf 2 =f (1+t0 ) 1f1二二. 搜索区间的确定：搜索区间的确定： 。若；若则收敛，）（中，次在区间第收敛条件：；舍去，则此例中和比较）；（）（）（，）内取两点（此例中在第二次在区间；舍去，则若；和舍

6、去，则若；舍去，则若和比较）（），（，内取两点第一次在区间）；（定公比)(1)(3)(1)(3)(3)(1)1 (1)1 (31)(1)(3)(3)(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 (1*, )()(*, )()(,*)()(, )()(,*)

7、()(,*)()(,*)()(,),()(,10mmmmmmmmmmmffffmffffffffffff3.2 3.2 一维搜索方法一维搜索方法 ( (续续4 4）三三. 黄金分割法黄金分割法 (0.618) ：1. 序列消去原理：序列消去原理：f ()3(1)12*1(1)03(2)1121221(2)1(3)3(3)3.2 3.2 一维搜索方法一维搜索方法 ( (续续5 5）2. 黄金分割与0.618：bd 古希腊建筑师认为：边长为 b，d 的矩形建筑物，若边长能符合以下条件，则最美观：618. 001,2解得，则dbddb欧几里德几何称这种边长分割为黄金分割。 序列消去法中，为提高效率，

8、减少计算量和存储量，希望 618. 00102111312111311131221解得，）（）（）（得式，式，即让三三. 黄金分割法黄金分割法 (0.618) ：3.2 3.2 一维搜索方法续一维搜索方法续6 6）四四. 二次插值法抛物线法）：二次插值法抛物线法）：1. 基本原理：基本原理： 。的最优点近似的极小值，以拟合曲线即用抛物线逼近拟用一元二次多项式的一元函数，是*,)(21fpfpfcbapSxfxfpkkk步骤：步骤： 133221321213132133221322212212312322323332222212111321231,fffcfffbfcbapfcbapfcbapp

9、fff：解得，得：，代入，已知函数值，及中间任意一点，选目标函数值的点。三个已知确定二项式系数，需选3.2 3.2 一维搜索方法续一维搜索方法续7 7）2. 步骤：步骤： 32112122131312131,)(212*,02cffcffccccbcbddpp其中得令3. 结果分析：结果分析：。，重取插值点，再拟合若不满足，则缩小区间。则且。则且，若满足判断是否满足精度：代替校核以若外，结论：重新处理。在其中若。：轴的直线上，结论位于一条平行与则若4422422424314314431423212*,*,*,0,*,0*,0fffffffcpp问题：若不满足精度，如何缩小区间，再拟合？问题：若

10、不满足精度，如何缩小区间，再拟合？ 4. 方法评价：方法评价： 与黄金分割法相比，二次插值法充分利用函数值的信息；收敛快；调用函数次数少。四四. 二次插值法抛物线法）：二次插值法抛物线法）：3.3 3.3 坐标轮换法和坐标轮换法和 Powell Powell 法法一一. 坐标轮换法：坐标轮换法：1. 基本思想：基本思想：2. 搜索方向与步长：搜索方向与步长： 每次以一个变量坐标轴作为搜索方向，将 n 维的优化问题转化为一维搜索问题。例，第 k 轮迭代的第 i 次搜索，是固定除 xi 外的 n-1 个变量，沿 xi 变量坐标轴作一维搜索，求得极值点 xi(k) n 次搜索后获得极值点序列 x1(

11、k), x2(k , xn(k)，若未收敛，则开始第 k+1 次迭代，直至收敛到最优点 x*。 。：次搜索的收敛条件轮第第；：次搜索的迭代公式轮第第；：次搜索的步长轮第第向；个设计变量的坐标轴方为第次搜索的方向：轮第第)()()()()(1)()()()(,.,2 , 1,kikikikikikikikikiSikniSxxikSikiSik3.3 3.3 坐标轮换法和坐标轮换法和 Poweel Poweel 法续）法续）一一. 坐标轮换法：坐标轮换法：3. 方法评价：方法评价： 方法简单，容易实现。 当维数增加时，效率明显下降。 收敛慢，以振荡方式逼近最优点。 受目标函数的性态影响很大。 如

12、图 a) 所示，二次就收敛到极值点； 如图 b) 所示，多次迭代后逼近极值点； 如图 c) 所示，目标函数等值线出现山脊或称陡谷），若搜索到 A 点，再沿两个坐标轴，以t0步长测试，目标函数值均上升，计算机判断 A 点为最优点。事实上发生错误。3.3 3.3 坐标轮换法和坐标轮换法和 Powell Powell 法续法续2 2）二二. Powell法共轭方向法、方向加速法）：法共轭方向法、方向加速法）：1. 基本思想：基本思想：2. 共轭方向的定义：共轭方向的定义： 若沿连接相邻两轮搜索末端的向量 S 方向搜索，收敛速度加快。其中：)1(2)2(2xxS 因为两条平行线 S1 , S2 与同心

13、椭圆族相切，两个切点的连线 S 直指中心。 称 S1 , S2 与 S 为共轭方向。 目的：以共轭方向打破振荡，加速收敛。共轭。阵则称这组向量是关于矩能满足若有一组非零向量，为正定实对称矩阵设正交。和则即，时则，为单位矩阵若的方向是共轭方向。和是关于矩阵共轭，和则称向量满足，和维向量若有两个，为实对称正定矩阵设AjiASSSSSASSSSISSIASSSSASSSSnAjTinTTT),(0,., 00,021212121212121213.3 3.3 坐标轮换法和坐标轮换法和 Poweel Poweel 法续法续3 3）3. 共轭方向的性质：共轭方向的性质：二次收敛性。为步可收敛至极值点，称

14、多方向进行一维搜索，至出发，依次沿从任意初始点，次函数个非零向量，则对于二矩阵共轭的是关于设矩阵共轭。中每一个向量关于，也是与向量组，向量和搜索，分别得到最优点方向进行一维出发，沿和分别从两个初始点个非零向量，对于函数矩阵共轭的是关于设。满足，个向量则可以构造出是线性无关的向量组，若是线性无关的。个非零向量矩阵共轭的这组关于）（）（）（）（）（）（nniSxAXXXBCxfnASSSAniSxxSxxniSxxxfnASSSjiSASSSSnSSSSSSnAiTTniinjTinnn),.,2 , 1(21)(,.,),.,2 , 1(),.,2 , 1()(,.,)(,0,.,.,.,)0(

15、211221)2(0)1 (021)2()2(222211121121二二. Powell法共轭方向法、方向加速法）：法共轭方向法、方向加速法）：3.3 3.3 坐标轮换法和坐标轮换法和 Poweel Poweel 法续法续4 4）4. 步骤：步骤： 迭代。若不满足，则作下一轮。则若满足。或是否满足收敛条件：每轮迭代结束时，检验。的极值点作第三次搜索，求得，沿此方向构筑共轭方向：。的极值点一维搜索，分别求得方向作两次，分别沿令第二轮迭代：。的极值点作第三次搜索，求得，沿此方向构筑共轭方向：。的极值点求得作两次一维搜索，分别标轴方向，依次沿两个坐，令选初始点第一轮迭代：)1(3210010101

16、023202222221112)1(320131012112111211)0(10)0(*,kkkkkkxxfffxxxxfxxSxxxfSSxxxxfxxSxxxfSSxxx3.3 3.3 坐标轮换法和坐标轮换法和 Poweel Poweel 法续法续5 5）6. 方法评价：方法评价： 计算步骤复杂。 是二次收敛方法，收敛快。对非正定函数，也很有效。 是比较稳定的方法。 5. 说明：说明： 若是正定二次函数，n 轮迭代后收敛于最优点 x* 。 若是非正定二次函数，则迭代次数增加。 若是 n 维问题，步骤相同。 搜索方向：第一轮迭代，沿初始方向组 Si(1) (i=1,2,n) 的 n 个方向

17、和共轭方向 S(1)，搜索 n+1 次得极值点 xn+1(1) ；第二轮迭代，沿方向组 Si(2) ( i=1,2,n；im ) 的 n-1 个方向和共轭方向 S(1)，构筑共轭方向 S(2) 搜索 n+1次得极值点 xn+1(2) 。其中，为保证搜索方向的线性无关，去除了 Sm(2) 方向 。 在第 k 轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向 Sm(k)。去除的原则请自学。二二. Powell法共轭方向法、方向加速法）：法共轭方向法、方向加速法）：3.4 3.4 梯度法和共轭梯度法梯度法和共轭梯度法一一. 梯度法最速下降法）：梯度法最速下降法）：1. 基本思想

18、：基本思想：2. 搜索方向：搜索方向： 目标函数负梯度向量方向代表最速下降方向，因此选择负梯度向量方向作为搜索方向，期望很快找到最优点。量。是负梯度方向的单位向,)()()()()(kkkxfxfS3. 步骤：步骤： （略）（略） 3.4 3.4 梯度法和共轭梯度法续）梯度法和共轭梯度法续）4. 方法评价：方法评价： 迭代过程简单，对初始点的选择，要求不高。 梯度方向目标函数值下降迅速只是个局部性质，从整体来看，不一定是收敛最快的方向。 以二维二次函数为例，相邻两次的搜索方向是正交的，所以搜索路径是曲折的锯齿形的；对于高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形搜索路径。一一. 梯度法

19、最速下降法）：梯度法最速下降法）：3.4 3.4 梯度法和共轭梯度法续梯度法和共轭梯度法续2 2）二二. 共轭梯度法旋转梯度法）：共轭梯度法旋转梯度法）：1. 基本思想：基本思想：2. 共轭方向：共轭方向： 对梯度法作一个修正，将搜索方向由负梯度方向旋转一个角度，使相邻的两次搜索方向由正交变为共轭，成为二次收敛。为共轭系数。：其中次搜索的方向为第次搜索的方向为第)()()()1()1()()(,)(1),(kkkkkkkSxfSkxfSk3. 共轭系数：共轭系数：2)(2)1()()()(kkkxfxf推导过程请自学。 3.4 3.4 梯度法和共轭梯度法续梯度法和共轭梯度法续3 3）步骤：步骤

20、： 5. 方法评价：方法评价： 迭代程序简单，容易实现，存储量较小。 开始采用梯度方向，目标函数值下降快，后又为旋转梯度方向，具有二次收敛速度，收敛快。步。转第令：，构造新的共轭方向计算则进行下一步；，若步；转第，则令，若，检查搜索次数步；若不满足，则进行第；，若满足，则迭代结束是否判断；方向作一维搜索，求得沿；计算，令；和计算精度选取初始点3, 1,)(. 62. 55*,)(. 4. 3)(0. 2. 1)()()1()()()1()0()1()1()()()()1()()()()0(kkSxfSnkxxnkxxxfSxxSxfSkxkkkkkkkkkkkkkkk二二. 共轭梯度法旋转梯度

21、法）：共轭梯度法旋转梯度法）：3.5 3.5 牛顿法和变尺度法牛顿法和变尺度法一一. 牛顿法二阶梯度法）：牛顿法二阶梯度法）： 1. 基本思想： 将 f(x) 在 x(k) 点作台劳展开，取二次函数式(x) 作为近似函数,以(x) 的极小值点作为 f(x) 的近似极小值点。得令min)(1)()(min)()()()()()()()()()(*, )()(, 0)(, )()()()(21)()()()()()(xxxfxHxxxxxxHxfxxxxHxxxxxfxfxxxfkkkkkkkkTkkTkkk说明：说明：l f(x) 若是正定二次函数，一般迭代一次即可；若是严重 非线 性函数，则可

22、能不收敛，或收敛到鞍点。为牛顿步长。矩阵的逆矩阵。为)()( )()(1)(1)(KkkxfxHHessexH3.5 3.5 牛顿法和变尺度法牛顿法和变尺度法 （续）（续）2. 修正牛顿法：修正牛顿法：为最优步长因子。其中则称为牛顿方向，令)()(1)()()()1()(1)()(, )()()()(kkkkkkkkkxfxHxxxfxHS步骤：步骤： （略）（略）4. 方法评价：方法评价：l 使用牛顿法时，若目标函数是严重 非线性函数，则是否收敛将与初始点有很大关系；而使用修正牛顿法，能保证每次迭代目标函数值下降，从而放宽了对初始点的要求。l 若初始点选得合适，牛顿法的收敛速度相当快。l 牛

23、顿法求逆矩阵的工作量大，计算量与存储量均随 n 的平方上升。一一. 牛顿法二阶梯度法）：牛顿法二阶梯度法）：3.5 3.5 牛顿法和变尺度法牛顿法和变尺度法 （续（续2 2）二二. DEF 变尺度法变尺度法:1. 变尺度的定义：变尺度的定义：每确定一次搜索方向，调整一次模尺度的大小，称为变尺度。2. 基本思想：基本思想： 发扬梯度法和牛顿法各自的优点，避免两者各自的缺点，将两者结合起来，形成变尺度法。了牛顿法的优点。矩阵的逆矩阵，而利用及这样避免计算二阶导数即为牛顿法。最终迭代时，时接近当不断修正尺度，逼近，中间的迭代即为梯度法，首次迭代时，为拟牛顿方向。的矩阵一个为变尺度矩阵，是：其中：迭代

24、公式HessexfxHSxfxHSxHHxxxHHxfSIHxfHSnnHxfHxxkKkkKkKkkkkkkkkkkkkkkk, )()(, )()(,)(*,)(, )(, )(,),()(1)()()(1)()(1)()()(1)()()()()0()()()()()()()()()1(3.5 3.5 牛顿法和变尺度法牛顿法和变尺度法 （续（续3 3）3. 变尺度矩阵的构造：变尺度矩阵的构造：原则：原则： 使目标函数值有下降性，则变尺度矩阵应为实对称矩阵请证明）；使目标函数值有下降性，则变尺度矩阵应为实对称矩阵请证明）； 使算法有二次收敛性，那么使算法有二次收敛性，那么 S(k) (k=1,2,)应关于应关于 H(k) 是共轭的；是共轭的；。即：件）变尺度条件（拟牛顿条)()()(,)()1()()1()1()()()1(kkkkkkkkxxxfxfHxgH构造变尺度矩阵的递推公式：构造变尺度矩阵的递推公式：4. 修正矩阵修正矩阵: 次迭代时的修正矩阵。为第其中：kEEHHkkkk)()()()1(,)()()()()()()()()()()()(kkTkkTkk