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

致知力行明德任责KunmingUniversityofScienceandTechnologyFacultyofMechanicalandElectricalEngineering第四章无约束优化方法总结明德任责致知力行目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。min()nfRxx按照是否使用目标函数导数可分为：（1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。（2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法、单形替换法等。无约束优化问题12[]Tnxxxx求n维设计变量使目标函数明德任责致知力行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相邻两个迭代点上的函数梯度相互垂直。特点：以锯齿状向极值点靠近，而且越接近极小点锯齿越细明德任责致知力行最速下降法搜索过程演示（以二维为例）1x2xo0x*x1x2x3x0d1d2d00()dfx()kkdfx明德任责致知力行最速下降方法特点（1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。明德任责致知力行2()()()()()1()()()2kkTkkTkkffffxxxxxxxxxxx设为的极小点1kx()x1()0kx牛顿法基本思想：在xk邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。牛顿法是求函数极值的最古老算法之一。()x()x()fx1kx()fx21()()()0kkkkffxxxx牛顿型法明德任责致知力行121[()]()(0,1,2,)kkkkffkxxxx这就是多元函数求极值的牛顿法迭代公式。对于二次函数，海赛矩阵H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。阻尼牛顿法（避免了迭代后函数值上升的现象）121[()]()(0,1,2,)kkkkkkkksffkxxxxxk阻尼因子，沿牛顿方向进行一维搜索的最佳步长从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升。明德任责致知力行牛顿法搜索过程演示（以二维为例）1x2xo0x*x0d100()dGfx1()kkdGfx明德任责致知力行阻尼牛顿方法特点（1）初始点应选在X*附近，有一定难度；（2）尽管每次迭代都不会是函数值上升，但不能保证每次下降；（3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；（4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。明德任责致知力行DFP变尺度法首先有戴维顿（Davidon）与1959年提出，又于1963年由弗莱彻（Fletcher）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。DFP法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。三、变尺度法变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降到最低限度。明德任责致知力行梯度法构造简单，只用到一阶偏导数，计算量小，初始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近X*时，即使对二次正定函数收敛也非常慢。牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。变尺度法将两种算法的优点综合起来，扬长避短梯度法和牛顿法特性回顾明德任责致知力行变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降低到最低限度。尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质。牛顿法就可看成是经过尺度变换后的梯度法。经过尺度变换，使函数偏心率减小到零，函数的等值面变为球面(或超球面)，使设计空间中任意点处函数的梯度都通过极小点，用最速下降法只需一次迭代就可达到极小点。对变换前的二次函数，在使用牛顿方法时，由于其牛顿方向直接指向极小点，因此只需一次迭代就能找到极小点。明德任责致知力行•变尺度法搜索过程演示（以二维为例）1x2xo0x*x1x0d1d0000()HHIdg111Hdg0010000000000ssHyyHHHsyyHyTTTT1kkkkkkkkkkkkkssHyyHHHsyyHyTTTT11kkkkkkyggsss明德任责致知力行四、鲍威尔方法鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。1964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。明德任责致知力行1()2TfTxxGxbxc对函数：基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。1.共轭方向的生成设xk,xk+1为从不同点出发，沿同一方向dj进行一维搜索而到的两个极小点。kx1kxkg1kgjdjdkd共轭方向的生成演示明德任责致知力行基本算法二维情况描述鲍威尔的基本算法:1）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位向量e1=[1,0]T和e2=[0,1]T作为初始搜索方向。2）从x0出发，顺次沿e1，e1作一维搜索，得点，两点连线得一新方向d10012,xx1002dxx02x10x11x12x01x1x2xo00x2e2d1d1e2e*x明德任责致知力行21120dxx沿d2作一维搜索得点x2。即是二维问题的极小点x*。方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。用d1代替e1形成两个线性无关向量d1,e2，作为下一轮迭代的搜索方向。再从出发，沿d1作一维搜索得点，作为下一轮迭代的初始点。02x10x3）从出发，顺次沿e2,d1作一维搜索，得到点，两点连线得一新方向:1112,xx10x02x10x11x12x01x1x2xo00x2e2d1d1e2e*x明德任责致知力行02x10x11x12x01x二维情况描述鲍威尔的搜索过程演示1x2xo00x2e2d1d1e2e*x明德任责致知力行02x10x11x12x01x二维改进鲍威尔方法的搜索过程演示1x2xo00x2e2d1d1e2e*x0000()Fffx0222()Fffx130()Ffx101ff212ff12max(,)m30FF和202302(2)()mFFFFF2030.5()mFF若d1换em否则，使用原来的方向组e1、e2，以F2、F3最小值点位新的起点1000202xxx映射,非搜索明德任责致知力行五、单形替换法一、基本思想单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。该方法只需要计算目标函数值，无需求其导数，因此计算比较简单，其几何概念也比较清晰，属于直接法的无约束最优化方法。这类方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况。这也是直接法的一个优点。明德任责致知力行定义：单纯形n维空间中的恰好有n+1个顶点（极点）的有界的凸多面体称之为一个单纯形。根据定义，可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这4个操作来实现。下面以二维问题为例来对4种操作进行说明（参见下图）。明德任责致知力行X2X1X3X8X4X5X6X7123()()()fxfxfx423/2xxx5441412xxxxxx64411.2~2.0xxxx74540.5xxxx84540.5xxxx目标函数：中点：反射点：扩张点：收缩点：进一步收缩：53()()fxfx65()()fxfx如果：扩张如果：取x2，x3，x6；否则取x2，x3，x5。352()()()fxfxfx如果：则取x2，x3，x5。251()()()fxfxfx如果：则收缩71()()fxfx若：取x2,x3,x7。否则x2,x3,x5。51()()fxfx如果：81()()fxfx若：取x2,x3,x8，否则弃x8。1()()fxfx若缩边。X9单形替换法过程动画演示明德任责致知力行方法搜索方向函数梯度修正因子所用目标函数信息梯度法I（单位阵）一阶导数(阻尼)牛顿法一、二阶导数共轭梯度法一阶导数变尺度法一阶导数鲍威尔方法零阶方法目标函数值单形替换法最差点和其余点重心连线零阶方法目标函数值kkdg1[]kkkdGg1[]kGkkkdQg111[][]kTkkkTkgdQIggkkkdHg1kkkHHE1kkkxxd无约束优化方法搜索方向之间的相互联系明德任责致知力行无约束优化方法——间接法总结1、梯度法方向负梯度用到一阶导数适合于精度不高或用于复杂函数寻找一个好的初始点2、牛顿法用到一阶导数和海赛矩阵，具有二次收敛性要求海赛矩阵非奇异，且维数不宜太高3、变尺度法收敛快，效果好，被认为是目前最有效的无约束优化方法。适用于维数较高，具有一阶偏导数的目标函数明德任责致知力行无约束优化方法——直接法总结1、坐标轮换法计算效率较低适合维数较低，目标函数无导数或导数较难求得2、Powell法具有二次收敛性，收敛速度较快，可靠性高，被认为是直接法中最有效的方法之一3、单纯形法思路清楚，收敛慢本章结束