机械优化设计--第四章(第5次课)

机械优化设计2017年6月上海海事大学SHANGHAIMARITIMEUNIVERSITY何军良19:451上海海事大学ShanghaiMaritimeUniversity19092009200419121958机械优化设计中的几个问题优化设计概述优化设计的数学基础2目录CONTENTS一维搜索方法无约束优化方法线性规划约束优化方法19:45第四章无约束优化方法概述01最速下降法牛顿型方法共轭方向与共轭方向法020304共轭梯度法05变尺度法坐标轮换法鲍威尔方法060708单形替换法0919:45344.1概述工程问题大都为有约束优化问题。为什么要研究无约束优化问题?1.有些实际问题，其数学模型本身就是一个无约束优化问题。2.通过熟悉它的解法可以为研究约束优化问题打下良好的基础。3.约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。19:4554.1概述无约束优化问题是：TnxxxX21求n维设计变量nRXXfXfminmin使目标函数00021nxfxfxf0f无约束优化问题极值存在的必要条件：19:4564.1概述目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。（1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。（2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法、单形替换法等。用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的(n≤20)问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。搜索方向的构成问题乃是无约束优化方法的关键。其搜索方向直接取定或由计算目标函数值所得的信息来确定。1(0,1,2,)kkkkdkxx19:4574.1概述771.选择初始迭代点x0。2.从迭代点xk出发进行搜索，确定使目标函数值下降的搜索方向dk。3.确定适当的步长因子αk，求xk+1=xk+αkdk，使f(xk+1)f(xk)。4.选择适当的终止准则，若xk+1满足终止准则，则终止迭代计算，并输出局部最优点x*←xk+1；否则，令k←k+1，返回步骤(2)继续进行优化搜索。无约束优化方法求解的四个步骤:19:4584.2最速下降法（1）基本思想搜索方向d取该点的负梯度方向(最速下降方向)，使函数值在该点附近的范围内下降最快。()fx1(0,1,2,)kkkkdkxx1()(0,1,2,)kkkkafkxxx终止判别条件1kkxx19:4594.2最速下降法（2）计算方法为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有1()[()]min[()]min()kkkkkkaaffaffafxxxxx()kfxk步长因子求解方法：解析法：根据极值点必要条件。黄金分割法牛顿法抛物线法19:45104.2最速下降法（2）计算方法根据一元函数极值的必要条件及复合函数求导公式得'()[()]()0Tkkkkfffxxx1[()]()0kTkffxx1()[()]min[()]min()kkkkkkaaffaffafxxxxx1()0kTkdd19:45114.2最速下降法（3）现象最速下降法的搜索路径1.在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。2.搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。3.形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。19:45124.2最速下降法4.在远离极小点位置，每次迭代可使函数值有较多的下降。5.在接近极小点位置，每次迭代行进的距离缩短，收敛速度减慢。6.最速下降性”只是迭代点邻域的局部性质。从全局看，并非最速下降方向。（3）现象19:45134.2最速下降法（4）计算步骤1)给定初始迭代点x0，精度ε，维数n；2)令k←0；3)计算xk的梯度；4)以xk点为出发点，求方向上的最优步长αk，有；5)终止判别？若满足条件，输出最优解，xk+1→x*,f*←f(x*)。否则，令k←k+1，转步骤3)。()kfx()kfx1()kkkkfxxx1kkxx19:45144.2最速下降法（4）计算步骤αα19:45154.2最速下降法（5）举例沿负梯度方向进行一维搜索，有0[2,2]Tx例：求目标函数的极小点。取初始点2221)(xxfx解：初始点处梯度：4422)(0210xxxxf)(001xfxx19:45164.2最速下降法（5）举例0为一维搜索最佳步长，应满足极值必要条件122000()min(24)(24)min()fx00()16(24)000.5100x010024242424x19:45174.2最速下降法（5）举例0)(0022)(0)(121111xxxxfxxff第一次迭代设计点位置和函数值因此，迭代终止：0)(001xxxfT19:45184.2最速下降法（5）举例19:45194.2最速下降法（5）举例例：用最速下降法求222125)(xxXf极小点，精度解：1）取初始点。TX]2,2[0104)(0Xf初始梯度1004502)(0210XxxXf2）沿负梯度方向一维搜索0000001100242100422)(XfXX3）求最优步长0001.0初始点处函数值221000000()min(())min24252100min()'()8(24)5000(2100)00.02003072fXfXfX19:45204.2最速下降法（5）举例4)计算新的迭代点位置和函数值686164.3)(103071785.0919877.110024212001XfX5）迭代终止条件判断16.0)2103071785.0()2919877.1(22201XX继续迭代。取初始点为X1，继续重复1-5步，直到满足精度要求。迭代10次的结果是：00)(00**XfX19:45214.2最速下降法（5）举例这个问题的目标函数的等值线为一簇椭圆,迭代点从X0走的是一段锯齿形路线，见图。19:45224.2最速下降法（5）举例221212(,)yyyy其等值线由椭圆变成一簇同心圆。00102()10424()220yyyyy则函数f(X)变为：y1=x1,y2=5x2将上例中目标函数引入变换222125)(xxXf仍从,即出发进行最速下降法寻优。此时：TX]2,2[0Ty10,2019:45234.2最速下降法（5）举例1000000()242410201020yyyβ0为一维搜索最佳步长，可由极值条件：10022()min[()]min()()(24)(1020)yyy0()00560.5112从而算得一步计算后设计点的位置及其目标函数：由沿负梯度方向进行一维搜索：19:45244.2最速下降法（5）举例010124010200()0yy经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：11225yxyx等值线由椭圆变成圆。19:45254.2最速下降法（5）举例例：用最速下降法求下面无约束优化问题：19:45264.2最速下降法（5）举例19:45274.2最速下降法（5）举例19:45284.2最速下降法（5）举例19:45294.2最速下降法（6）收敛性分析最速下降法的收敛速度和变量的尺度关系很大。在适当条件下，收敛速度的估计公式：式中m表示f(x)的海塞矩阵的最大特征值上界，M表示f(x)的海塞矩阵的最小特征值的下界1624**625kkxxxx对于等值线为椭圆的二次型函数222125)(xxXf其海塞矩阵为20050G特征值为2，50因此212*1*kkmxxxxM收敛性较慢19:45304.2最速下降法（7）最速下降法的典型特征由于一维搜索是求kkkkXfXfXf10dd的极小。故应满足：即0'11kTkkTkkkkkkkXfXfXfXfXfdXfXdfdXdf因此，在梯度法中，相邻两次搜索方向（即相邻两次迭代点的梯度方向）是正交的。19:45314.2最速下降法（7）最速下降法的典型特征1.理论明确，程序简单，对初始点要求不严格。2.对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。3.梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。4.梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆(球)的目标函数，一次搜索即可达到极小点。19:45324.3牛顿型方法（1）基本思想在xk邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。牛顿法是求函数极值的最古老算法之一。()x()x()fx1kx()fx19:45334.3牛顿型方法（2）迭代公式原函数:近似二次函数:求的极小点，要求其梯度等于零。()fx2()()()()()1()()()2kkTkkTkkffffxxxxxxxxxxx()x*x19:45344.3牛顿型方法（2）迭代公式（牛顿方向）1）迭代方向：*1k2）步长因子：令由此，这就是多元函数求极值的牛顿法迭代公式。对于二次函数，海赛G是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。121()()()()0kkkkkffxxxxx112()()kkkkffxxxx12()()kkkdffxx19:45354.3牛顿型方法（3）举例例：求目标函数的极小点。解：取初始点2212()25fxxx0[2,2]Tx102010102402()()121000050ffxxxx1004502)(0210xxxxf50002)(02xf00x经过一次迭代即求得极小点()0fx19:45364.3牛顿型方法（4）阻尼牛顿法对于正定二次函数，牛顿法可以直达极小点。对于非二次函数，基本牛顿法的步长因子恒为1，有时会导致迭代发散而失效，如果采用上述牛顿迭代公式，有时会使函数值上升。问题提出19:45374.3牛顿型方法（4）阻尼牛顿法比如，对于如下问题：2122121100minxxxXf①当TX5.05.005.60Xf50510Xf20020020010202Xf