最优化方法

最优化方法1梯度法2牛顿法及其改进3变尺度法4共轭方向法5鲍威尔方法第1讲所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。为什么要研究无约束优化问题???(1)、有些实际问题，其数学模型本身就是一个无约束优化问题(2)、通过熟悉它的解法可以为研究约束优化问题打下良好的基础(3)、约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础无约束优化问题是：求n维设计变量使目标函数：12[]Tnxxxx()minfxmin()nfRxx各种无约束优化解法的区别：搜索方向的不同◆分类：（1）直接解法---不使用导数信息，如坐标轮换法、Powell法、随机搜索法、单纯形法等（2）间接解法(解析法)---要使用导数，二阶有梯度法、共轭梯度法、，二阶以上用牛顿法1(0,1,2,)kkkkkxxd搜索方向的构成问题是无约束优化方法的关键无约束优化方法算法的基本过程是:从选定的某初始点x(k)出发，沿着以一定规律产生的搜索方向S(k),取适当的步长a(k),逐次搜寻函数值下降的新迭代点x(k+1),使之逐步通近最优点x*可以把初始点x(k)、搜索方向S(k)、迭代步长a(k)称为优化方法算法的三要素。其中以搜索方向S(k)更为突出和重要，它从根本上决定若一个算法的成败、收敛速率的快慢等。一个算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向S(k)是研究优化方法的最根本的任务之一4.1梯度法函数的负梯度方向是函数值下降最快的方向搜索方向d取该点的负梯度方向(最速下降方向)，使函数值在该点附近的范围内下降最快()fx1(0,1,2,)kkkkkxxd1()(0,1,2,)kkkkafkxxx为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有()kfxk1()[()]min[()]min()kkkkkkaaffaffafxxxxx根据一元函数极值的必要条件和多元复合函数求导公式，得'()[()]()0Tkkkkfffxxx1[()]()0kTkffxx1()0kTkdd在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细.开始给定结束0,x()kkfdx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k例4－1求目标函数的极小点。解取初始点则初始点处函数值及梯度分别为0[2,2]Tx00102()10424()50100xfxfxxx沿负梯度方向进行一维搜索，有01000024()2100fxxx0为一维搜索最佳步长，应满足极值必要条件122()min(24)25(2100)min()fx2212()25fxxx00'()8(24)5000(2100)0算出一维搜索最佳步长06260.0200307231252第一次迭代设计点位置和函数值0120241.91987721000.307178510x1()3.686164fx继续作下去，经10次迭代后，得到最优解00Tx()0fx这一问题的目标函数f(x)的等值线为一簇椭圆。将上例中目标函数引入变换y1=x1,y2=5x2则函数f(x)变为：2212()25fxxx221212(,)yyyy其等值线由椭圆变成一簇同心圆。0[2,2]Tx仍从即出发进行最速下降法寻优。此时：0[2,10]Ty00102()10424()220yyyyy沿负梯度方向进行一维搜索：1000000()242410201020yyyβ为一维搜索最佳步长，可由极值条件：10022()min[()]min()()(24)(1020)yyy0()0由0260.552从而算得一步计算后设计点的位置及其目标函数：010124010200()0yy经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：11225yxyx等值线由椭圆变成圆。11梯度法的特点:（1）理论明确，程序简单，对初始点要求不严格（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点4.2牛顿法及其改进1、牛顿法在xk邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。()x()x()fx1kx()fx2()()()()()1()()()2kkTkkTkkffffxxxxxxxxxxx设为的极小点1kx()x1()0kx21()()()0kkkkffxxxx121[()]()(0,1,2,)kkkkffkxxxx这就是多元函数求极值的牛顿法迭代公式。对于二次函数，海赛矩阵是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点例4－2求目标函数的极小点。解取初始点2212()25fxxx0[2,2]Tx102010102402()()121000050ffxxxx经过一次迭代即求得极小点，函数极小值。00x()0fx从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升2、阻尼牛顿法121[()]()(0,1,2,)kkkkkkkkffkxxdxxxk阻尼因子，沿牛顿方向进行一维搜索的最佳步长，由下式求得：1()()min()kkkkkkkfffxxdxd开始给定结束0,x21[()]()kkkffdxx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k阻尼牛顿法称序框图牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的主要缺点是每次迭代都要计算函数的二阶导数矩阵，并对该矩阵求逆。这样工作量很大。特别是矩阵求逆，当维数高时工作量更大。1(0,1,2,)kkkkkxxd1()(0,1,2,)kkkkafkxxx121[()]()(0,1,2,)kkkkffkxxxx121[()]()(0,1,2,)kkkkkffkxxxx一般迭代式：梯度法：牛顿法：阻尼牛顿法：梯度法与牛顿法：1()kkkkkfxxAx→变尺度法4.3变尺度法变尺度法是在牛顿法的思想上进行了重大改进的一类方法1.基本思想变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。2212()25fxxx例如在用最速下降法求的极小值时,需要进行10次迭代才能达到极小点[0,0]Tx如作变换y1=x1,y2=5x2把的尺度放大5倍，则目标函数等值线由一簇椭圆变成一簇同心圆。x2221212(,)yyyy消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。梯度法构造简单，只用到一阶偏导数，计算量小，迭代初期收敛速度快，但当迭代到最优点附近时收敛速度很慢；牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。能不能将两种算法的优点综合起来，扬长避短？1()kkkkkfxxAxAk是需要构造n×n的一个对称方阵，如Ak=I,则得到梯度法；21[()]kkfAx则得到阻尼牛顿法；如★当矩阵Ak不断地迭代而能很好地逼近21[()]kfx时，就可以不再需要计算二阶导数变尺度法的关键在于尺度矩阵Ak的产生。对于二次函数:1()2TTfxxGxbxcxQx进行尺度变换在新的坐标系中，函数f(x)的二次项变为：1122TTTxGxxQGQx目的：减少二次项的偏心如G是正定，则总存在矩阵Q，使得：TQGQI用矩阵Q-1右乘等式两边，得：用矩阵Q左乘等式两边，得：1TQGQTQQGI所以1TQQG上式说明：二次函数矩阵G的逆阵，可以通过尺度变换矩阵Q来求得。121[()]()(0,1,2,)kkkkkffkxxxx牛顿迭代公式：1()(0,1,2,)kkTkkQQfkxxx记：TAQQ牛顿方向：1()(0,1,2,)kkkfkdAx迭代公式：1()(0,1,2,)kkkkkfkxxAxA称为尺度变换矩阵2212()25fxxx在例4－2中122121222011()2505022TxfxxxxxxxGx20050G如取1021052Q11002010221050101005252TQGQI求得：1111000222111000505252TGQQ2、构造尺度矩阵Ak从初始矩阵A0=I(单位矩阵)开始，通过对公式1kkkAAA中修正矩阵的不断修正，在迭代中逐步逼近于kA1()kGx因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度。1）DFP法（Davidon-Fletcher-Powell)[][][][]TkkkkkTkkkTkkTkkxxAggAAxggAg111()()kkkkkkkkffgggxxxxx式中。2）BFGS算法(Broyden-Fletcher-Goldfrob-Shanno)DFP算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法不稳定。BFGS算法对于维数较高问题具有更好的稳定性。1[][]{[][][][][]}kkTkTkkkkkTkTkkTkkkkTkkTxxgAgAxxxgxgAgxxgA开始给定结束0,x000()fgxAI1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kkkn11111()kkkkkkkkfgxgggxxx11kkkAAA01kxx0kkkkdAg是否例4-3：用DFP算法求下列问题的极值：解：1）取初始点，为了按DFP法构造第一次搜寻方向d0，需计算初始点处的梯度221212112(,)242fxxxxxxx0[11]Tx01200212244()422xxfxxx