机械优化设计第三章

第三章无约束问题的最优化方法主要内容§3.1引言§3.2一维搜索方法§3.3坐标轮换法和Powell法§3.4梯度法和共轭梯度法§3.5牛顿法和变尺度法§3.6无约束优化设计方法小结§3.1引言求一组n维设计变量X=[x1,x2,…,xn]T,使目标函数达到min.f(X)X∈Rn即求目标函数的最优解：最优点x*和最优值f(x*)。意义：•为有约束优化方法的研究提供了策略思想、概念基础和基本方法；•为有约束优化问题的直接解法提供了有效而方便的方法；•不可避免地还存在无约束优化的设计问题。§3.1引言（续）内容：一维搜索：求最优步长因子α(k)确定搜索方向S(k)多维（变量）优化：黄金分割插值法坐标轮换法共轭方向法梯度法共轭梯度法牛顿法DFP变尺度法§3.2一维搜索方法一、一维搜索定义：在第K次迭代时，从已知点X(k)出发，沿给定方向求最优步长因子α(k)，使f(X(k)+αS(k))达到最小值的过程，称为一维搜索。方法：1.解析法：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)台劳展开；②取二次近似：③对α求导，令其为零：)()()(2)()()()()()(][21)]([)(kkTkkTkkkkSxHSSxfxfSxf0)()()(kkSxfdd§3.2一维搜索方法（续）0)()()(kkSxfdd③对α求导，令其为零。0)(][)]([)()()()()(kkTkkTkSxHSSxf)()()()()()()(][)]([kkTkkTkkSxHSSxf2.数值迭代法：直接法——应用序列消去原理：分数法黄金分割法近似法——利用多项式函数逼近（曲线拟合）原理：二次插值法三次插值法④求得最优步长因子：一、一维搜索定义：§3.2一维搜索方法（续2）1.单峰区间：在区间[α1，α3]内，函数只有一个峰值，则此区间为单峰区间。单峰区间内，一定存在一点α*，当任意一点α2＞α*时，f(α2)＞f(α*)，说明：•单峰区间内，函数可以有不可微点，也可以是不连续函数；二.搜索区间的确定：f(x)0α1α3α0αf(x)α3α1f(α)αα3α2α*α10当α2＜α*时，仍有f(α2)＞f(α*)，则α*是最优点，也即为最优步长因子α(k)。α2•确定的搜索区间必定是一个含有最优点α*的单峰区间。§3.2一维搜索方法（续3）2.定步长搜索法:。，若不是步；若是，转第：判断；令。，，若不是步；若是，转第：判断；令步；若不是，转第步；若是，转第：判断；令；，、初始步长选初始点iiiiiit⑥ff⑦tffttiitit⑥tt⑥ff⑤tfftttti④④⑥ff③tfftti②tfftt①311023'2112'2201'200122201211011)(,,1,)(,,,2)(,,2)()(3.加速步长搜索法：...202010tittttiti或4.外推法：2111ittf2=f(α1+t0)α1f1二.搜索区间的确定：。若；若则收敛，）（中，次在区间第收敛条件：；舍去，则此例中和比较）；（）（）（，）内取两点（此例中在第二次在区间；舍去，则若；和舍去，则若；舍去，则若和比较）（），（，内取两点第一次在区间）；〈〈（定公比)(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*,)()(*,)()(,],[,],[*)()(,)()(,],[],[,],[*)()(,,],[*)()(,],[*)()(,),()(,],[10mmmmmmmmmmmffffmffff②ffffffff①§3.2一维搜索方法(续4）三.黄金分割法(0.618)：1.序列消去原理：f(α)αα3(1)α12α*α1(1)0α3(2)α11α21α22α1(2)α1(3)α3(3)§3.2一维搜索方法(续5）2.黄金分割与0.618：bd•古希腊建筑师认为：边长为b，d的矩形建筑物，若边长能符合以下条件，则最美观：618.001,2解得，则dbddb欧几里德几何称这种边长分割为黄金分割。•序列消去法中，为提高效率，减少计算量和存储量，希望618.00102111312111311131221解得，）（）（）（得式，式，即让②①三.黄金分割法(0.618)：§3.2一维搜索方法（续6）四.二次插值法（抛物线法）：1.基本原理：。的最优点近似的极小值，以拟合曲线即用抛物线逼近拟用一元二次多项式的一元函数，是**,)(21fpfpfcbapSxfxfpkkk2.步骤：133221321213132133221322212212312322323332222212111321231,,fffcfffbfcbapfcbapfcbappfff①：解得，得：，代入，已知函数值，及中间任意一点，选目标函数值的点。三个已知确定二项式系数，需选§3.2一维搜索方法（续7）2.步骤：32112122131312131,)(212*,02cffcffccccbcbddp②p其中得令3.结果分析：。，重取插值点，再拟合若不满足，则缩小区间。则且。则且，若满足判断是否满足精度：代替校核以若外，结论：重新处理。在其中若。：轴的直线上，结论位于一条平行与则若4422422424314314431423212*,*,,**,0],[*,0*,,,0fffffffcpp问题：若不满足精度，如何缩小区间，再拟合？4.方法评价：与黄金分割法相比，二次插值法充分利用函数值的信息；收敛快；调用函数次数少。四.二次插值法（抛物线法）：§3.3坐标轮换法和Powell法一.坐标轮换法：1.基本思想：2.搜索方向与步长：每次以一个变量坐标轴作为搜索方向，将n维的优化问题转化为一维搜索问题。例，第k轮迭代的第i次搜索，是固定除xi外的n-1个变量，沿xi变量坐标轴作一维搜索，求得极值点xi(k)…n次搜索后获得极值点序列x1(k),x2(k,…,xn(k)，若未收敛，则开始第k+1次迭代，直至收敛到最优点x*。。：次搜索的收敛条件轮第第；：次搜索的迭代公式轮第第；：次搜索的步长轮第第向；个设计变量的坐标轴方为第次搜索的方向：轮第第)()()()()(1)()()()(,...,2,1,kikikikikikikikikiSikniSxxikSikiSik§3.3坐标轮换法和Poweel法（续）一.坐标轮换法：3.方法评价：•方法简单，容易实现。•当维数增加时，效率明显下降。•收敛慢，以振荡方式逼近最优点。•受目标函数的性态影响很大。如图a)所示，二次就收敛到极值点；如图b)所示，多次迭代后逼近极值点；如图c)所示，目标函数等值线出现山脊（或称陡谷），若搜索到A点，再沿两个坐标轴，以±t0步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。§3.3坐标轮换法和Powell法（续2）二.Powell法（共轭方向法、方向加速法）：1.基本思想：2.共轭方向的定义：若沿连接相邻两轮搜索末端的向量S方向搜索，收敛速度加快。。其中：)1(2)2(2xxS因为两条平行线S1,S2与同心椭圆族相切，两个切点的连线S直指中心。称S1,S2与S为共轭方向。目的：以共轭方向打破振荡，加速收敛。共轭。阵则称这组向量是关于矩能满足若有一组非零向量，为正定实对称矩阵设正交。和则即，时则，为单位矩阵若的方向是共轭方向。和是关于矩阵共轭，和则称向量满足，和维向量若有两个，为实对称正定矩阵设AjiASSSSSASSSSISSIASSSSASSSSnAjTinTTT),(0,,...,,,00,02121212121212121§3.3坐标轮换法和Poweel法（续3）3.共轭方向的性质：二次收敛性。为步可收敛至极值点，称多方向进行一维搜索，至出发，依次沿从任意初始点，次函数个非零向量，则对于二矩阵共轭的是关于设矩阵共轭。中每一个向量关于，也是与向量组，向量和搜索，分别得到最优点方向进行一维出发，沿和分别从两个初始点个非零向量，对于函数矩阵共轭的是关于设。满足，个向量则可以构造出是线性无关的向量组，若是线性无关的。个非零向量矩阵共轭的这组关于）（）（）（）（）（）（nniSxAXXXBCxfnASSSAniSxxSxxniSxxxfnASSSjiSASSSSnSSSSSSnAiTTniinjTinnn),...,2,1(21)(,...,,),...,2,1(),...,2,1()(,...,,)(,0][][,...,,,...,,,...,,)0(211221)2(0)1(021)2()2(222211121121二.Powell法（共轭方向法、方向加速法）：§3.3坐标轮换法和Poweel法（续4）4.步骤：迭代。若不满足，则作下一轮。则若满足。或是否满足收敛条件：每轮迭代结束时，检验。的极值点作第三次搜索，求得，沿此方向构筑共轭方向：。的极值点一维搜索，分别求得方向作两次，分别沿令第二轮迭代：。的极值点作第三次搜索，求得，沿此方向构筑共轭方向：。的极值点求得作两次一维搜索，分别标轴方向，依次沿两个坐，令选初始点第一轮迭代：)1(3210010101023202222221112)1(320131012112111211)0(10)0(*,,,,,,kkkkkkxxfffxxxxfxxSxxxfSSxxxxfxxSxxxfSSxxx§3.3坐标轮换法和Poweel法（续5）6.方法评价：•计算步骤复杂。•是二次收敛方法，收敛快。对非正定函数，也很有效。•是比较稳定的方法。5.说明：•若是正定二次函数，n轮迭代后收敛于最优点x*。若是非正定二次函数，则迭代次数增加。•若是n维问题，步骤相同。搜索方向：第一轮迭代，沿初始方向组Si(1)(i=1,2,…,n)的n个方向和共轭方向S(1)，搜索n+1次得极值点xn+1(1)；第二轮迭代，沿方向组Si(2)(i=1,2,…,n；i≠m)的n-1个方向和共轭方向S(1)，构筑共轭方向S(2)搜索n+1次得极值点xn+1(2)。其中，为保证搜索方向的线性无关，去除了Sm(2)方向。•在第k轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个