现代设计理论与方法(优化设计第四章)

致知力行明德任责KunmingUniversityofScienceandTechnologyFacultyofMechanicalandElectricalEngineering现代设计理论与方法（优化设计）第四章无约束优化问题机电学院刘孝保明德任责致知力行第一节最速下降法（梯度法）1第二节牛顿型法（牛顿法）2第四节坐标轮换法4第三节变尺度法3第四章无约束优化方法目录第五节鲍威尔方法5第六节单形替换法（选讲）6明德任责致知力行概述第1章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。为什么要研究无约束优化问题?（1）有些实际问题，其数学模型本身就是一个无约束优化问题。（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。明德任责致知力行（4）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。明德任责致知力行目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。min()nfRxx（1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。（2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。无约束优化问题是：12[]Tnxxxx求n维设计变量()minfx使目标函数明德任责致知力行1(0,1,2,)kkkkskxx搜索方向的构成问题乃是无约束优化方法的关键。用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n≤20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。本节结束明德任责致知力行1(0,1,2,)kkkkskxx1()(0,1,2,)kkkkafkxxx基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。()fx搜索方向s取该点的负梯度方向(最速下降方向)，使函数值在该点附近的范围内下降最快。第一节最速下降法明德任责致知力行为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有()kfxk1()[()]min[()]min()kkkkkkaaffaffafxxxxx根据一元函数极值的必要条件和多元复合函数求导公式，得'()[()]()0Tkkkkfffxxx1[()]()0kTkffxx1()0kTkss明德任责致知力行在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。图4-2最速下降法的搜索路径明德任责致知力行明德任责致知力行•最速下降法搜索过程演示（以二维为例）1x2xo0x*x1x2x3x0d1d2d00()dfx()kkdfx明德任责致知力行方法特点（1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。明德任责致知力行开始给定结束0,x()kkfdx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k明德任责致知力行00102()10424()50100xfxfxxx沿负梯度方向进行一维搜索，有01000024()2100fxxx0为一维搜索最佳步长，应满足极值必要条件122()min(24)25(2100)min()fx例4－1求目标函数的极小点。解取初始点则初始点处函数值及梯度分别为0[2,2]Tx2212()25fxxx明德任责致知力行00'()8(24)5000(2100)0算出一维搜索最佳步长06260.0200307231252第一次迭代设计点位置和函数值0120241.91987721000.307178510x1()3.686164fx继续作下去，经10次迭代后，得到最优解00Tx()0fx明德任责致知力行这个问题的目标函数的等值线为一簇椭圆,迭代点从走的是一段锯齿形路线，见图4-3。0x图4-3明德任责致知力行编程讲解：利用matlab进行编程实现图4-3明德任责致知力行例2：将上例中目标函数引入变换2212()25fxxx221212(,)yyyy其等值线由椭圆变成一簇同心圆。仍从即出发进行最速下降法寻优。此时：0[2,2]Tx0[2,10]Ty00102()10424()220yyyyy沿负梯度方向进行一维搜索：则函数f(X)变为：y1=x1,y2=5x2明德任责致知力行1000000()242410201020yyyβ为一维搜索最佳步长，可由极值条件：10022()min[()]min()()(24)(1020)yyy0()0由0260.552从而算得一步计算后设计点的位置及其目标函数：明德任责致知力行010124010200()0yy经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：11225yxyx等值线由椭圆变成圆。明德任责致知力行最速下降法的特点（1）理论明确，程序简单，对初始点要求不严格。（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。本节结束明德任责致知力行一维情况下的牛顿迭代公式第二节牛顿型方法1kkkkff推广到n维就形成了牛顿型方法明德任责致知力行•牛顿法搜索过程演示（以二维为例）1x2xo0x*x0d100()dGfx1()kkdGfx明德任责致知力行2()()()()()1()()()2kkTkkTkkffffxxxxxxxxxxx设为的极小点1kx()x1()0kx牛顿法基本思想：在xk邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。牛顿法是求函数极值的最古老算法之一。()x()x()fx1kx()fx21()()()0kkkkffxxxx明德任责致知力行121[()]()(0,1,2,)kkkkffkxxxx这就是多元函数求极值的牛顿法迭代公式。对于二次函数，海赛矩阵H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。例4－2求目标函数的极小点。解取初始点2212()25fxxx0[2,2]Tx102010102402()()121000050ffxxxx明德任责致知力行00x()0fx从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升。阻尼牛顿法121[()]()(0,1,2,)kkkkkkkksffkxxxxxk阻尼因子，沿牛顿方向进行一维搜索的最佳步长，由下式求得：1()()min()kkkkkkkffsfsxxx经过一次迭代即求得极小点函数极小值明德任责致知力行这样，原来的牛顿法就相当于阻尼牛顿法的步长因子αk取成固定值1的情况。由于阻尼牛顿法每次迭代都在牛顿方向上进行一维搜索，这就避免了迭代后函数值上升的现象，从而保持了牛顿法二次收敛的特性，而对初始点的选取并没有苛刻的要求。明德任责致知力行开始给定结束0,x21[()]()kkkffdxx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k阻尼牛顿法程序框图明德任责致知力行阻尼牛顿方法特点（1）初始点应选在X*附近，有一定难度；（2）尽管每次迭代都不会是函数值上升，但不能保证每次下降；（3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；（4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。明德任责致知力行1(0,1,2,)kkkkskxx1()(0,1,2,)kkkkafkxxx121[()]()(0,1,2,)kkkkffkxxxx121[()]()(0,1,2,)kkkkkffkxxxx一般迭代式：梯度法：牛顿法：阻尼牛顿法：梯度法与牛顿法比较：本节结束明德任责致知力行DFP变尺度法首先有戴维顿（Davidon）与1959年提出，又于1963年由弗莱彻（Fletcher）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。DFP法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。第三节变尺度法明德任责致知力行变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。值时,需要进行10次迭代才能达到极小点[0,0]Tx如作变换y1=x1,y2=5x2把的尺度放大5倍，则目标函数等值线由一簇椭圆变成一簇同心圆。x2例如在用最速下降法求极小221212(,)25f明德任责致知力行221212(,)yyyy消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。梯度法构造简单，只用到一阶偏导数，计算量小，初始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近X*时，即使对二次正定函数收敛也非常慢。牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。能不能将两种算法的优点综合起来，扬长避短？明德任责致知力行一、尺度矩阵的概念变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降低到最低限度。尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质。明德任责致知力行明德任责致知力行明德任责致知力行明德任责致知力行明德任责致知力行明德任责致知力行牛顿法就可看成是经过尺度变换后的梯度法。经过尺度变换，使函数偏心率减小到零，函数的等值面变为球面(或超球面)，使设计空间中任意点