04机械优化设计第四章(哈工大―孙靖民)

2020年2月12日9时28分14.1概述4.2最速下降法4.3牛顿型方法4.4共轭方向及共轭方向法重点4.5共轭梯度法4.6变尺度法4.7坐标轮换法4.8鲍威尔方法4.9单型替换法第四章无约束优化方法2020年2月12日9时28分2第1章所列举的机械优化设计问题大都是在一定限制条件下追求某一指标为最小，属于约束优化问题。为什么要研究无约束优化问题？1）有些实际问题，其数学模型本身就是一个无约束问题；2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础；3）约束优化问题的求解可用通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。2020年2月12日9时28分3对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。2020年2月12日9时28分41、无约束优化问题n求维设计变量使目标函数12,,TnXxxxminfXX，而对没有任何限制条件。§4-1概述这就是把求函数极值的问题变成求解方程的问题。即求X,使其满足0f00021nxfxfxf2020年2月12日9时28分5这是一个含有n个未知量，n个方程的方程组（一般是非线性的方程组），除了一些特殊情况外，求解析解比较困难，一般需要采用数值方法求解。但是，与其用数值计算方法求解非线性方程组，倒不如用数值计算方法直接求解无约束极值问题。00021nxfxfxf2020年2月12日9时28分6（1）利用极值条件来确定极值点的位置。（2）数值计算方法——搜索方法基本思想：从给定的初始点出发，沿某一搜索方向0x0d进行搜索，确定最佳步长0使函数值沿0d下降最大。依此方式不断进行，形成迭代的下降算法：1kkkkXXd(0,1,2)k2、求解方法目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。在上式中，dk是第是k+1次搜索或迭代方向，称为搜索方向（迭代方向）。2020年2月12日9时28分7数值方法*最常用的数值方法是搜索方法，其基本思想如下图所示：0X1X2X3XkX1kXkd2d1d0d1kkkkXXd2020年2月12日9时28分83、无约束优化算法的粗框图开始给定X、d的初始值满足收敛条件否？结束是形成新的d否计算使极小()fXdXXd一维搜索本章重点2020年2月12日9时28分9dk和ak的形成和确定方法不同就派生出不同的n维无约束优化问题的数值解法。根据构成搜索方向dk所使用的信息性质的不同，无约束优化方法可以分为两类。1.利用目标函数的一阶或二阶导数信息构造搜索方向的无约束优化方法；2.只用目标函数值的信息构造搜索方向的无约束优化方法2020年2月12日9时28分10最速下降法牛顿法共轭方向法共轭梯度法变尺度法坐标轮换法鲍威尔方法单型替换法无约束优化方法利用目标函数的导数信息利用目标函数值信息用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n≤20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。间接法直接法2020年2月12日9时28分111、基本思想函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，即利用负梯度作为搜索方向，故称为最速下降法或梯度法。dfX搜索方向取该点的负梯度方向即，使函数值在该点附近的范围内下降最快。§4-2最速下降法（梯度法）1(0,1,2,)kkkkskxx1()(0,1,2,)kkkkafkxxx2020年2月12日9时28分122、最速下降法的原理（1）使，按此规律不断走步，形成迭代算法：dfX1kkkkXXfX(0,1,2)k（2）其步长因子取一维搜索的最佳步长，即k根据一元函数极值的必要条件和多元复合函数求导公式，得0TkkKkfXfXfX10Tkkdd10Tkkfxfx或1minminkkkkkkkfxfxafxfxafx2020年2月12日9时28分13由上式可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。梯度法的搜索路线：最速下降法中，迭代点向函数极小点靠近的过程，走的是曲折的路线。这一次的搜索方向与前一次的搜索方向互相垂直，形成“之”字形的直齿锯齿现象，如图所示最速下降法的搜索路径2020年2月12日9时28分14在接近极小点的位置，由于锯齿现象使每次迭代行进的距离缩短，因而收敛速度减慢，这种情况似乎与“最速下降”的名称相矛盾，这主要是因为梯度是函数的局部性质（从局部上看，在一点附近函数的下降是快的），但从整体上看则走了许多弯路，函数的下降并不算快。2020年2月12日9时28分15方法特点1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点；2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。2020年2月12日9时28分16最速下降法的程序框图开始给定结束0,x()kkfdx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k2020年2月12日9时28分17例：求目标函数221225fXxx的极小点解法1：取初始点02,2TX，则初始点处的函数值及梯度分别为：01021042450100fXxfXx0100000242421002100XXfX0为一维搜索最佳步长，应满足极值必要条件10022minmin(24)25(2100)minfXfXfX0008(24)5000(2100)006260.02003072312522020年2月12日9时28分18则第一次迭代设计点位置和函数值0120241.91987721000.307178510X13.686164fX经过10次迭代后，得到最优解：0,0TX0fX该问题的目标函数的等值线为一族椭圆，迭代点走的是一段锯齿形路线，如下图。2020年2月12日9时28分19等直线为椭圆的迭代过程2020年2月12日9时28分20解法2：引入变化11225yxyx，则目标函数12,fxx变为221212,yyyy0104Y010224220YyYy0100000242410201020YYY0260.552010240102000Y10Y0,0TX0fX，经过坐标（尺度）变化后，只需要经过一次迭代，就可找到最优解：Y0(2,10)2020年2月12日9时28分21等直线为圆的迭代过程2020年2月12日9时28分22讨论1221212122201,250502xfxxxxxxx1221212122201,022yyyyyyyy可以看出二者的对角形矩阵不同，前者的等值线为一族椭圆，后者的等值线为一族同心圆，这说明对角形矩阵是表示度量的矩阵或者是表示尺度的矩阵，最速下降法的收敛速度和变量的尺度有很大关系。2020年2月12日9时28分233、最速下降法收敛速度的估计式2121kkmXXXXMMfx的海赛矩阵最大特征值上界——的海赛矩阵最小特征值下界fx——m在适当条件下，有当相邻两个迭代点之间满足上式时（右边的系数为小于等于1的正的常数），我们称相应的迭代方法是具有线性收敛速度的迭代法。因此，最速下降法是具有线性收敛速度的选代法。2020年2月12日9时28分24梯度法的特点：（1）理论明确，程序简单，对初始点要求不严格；（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降法仅仅是指某点的一个局部性质；（3）梯度法相邻两次搜索方向的正交性决定了迭代全过程的搜索路径呈锯齿形，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢；（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线（面）为同心圆（球）的目标函数，一次搜索即可达到极小点。2020年2月12日9时28分25基本思想：在领域内用一个二次函数来近似代替原目标函数，并将的极小值作为目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。kx)(x)(x)(xf)(xf1kx),2,1,0()()('''1kxfxfxxkkkk§4-3牛顿型方法原始牛顿法2020年2月12日9时28分26对于多元函数fX，设kX为fX极小点X的第一个近似点，fX泰勒展开，保留到二次项，得:设1kX为X的极小点，它作为fX极小点X的下一个近似点，根据极值必要条件：10kX即210kkkkfXfXXX112(0,1,2)kkkkXXfXfXk2kfX——海赛矩阵1、牛顿法---多元函数求极值的牛顿法迭代公式。fxx212TTkkkkkkfxfxxxxxfxxx原始牛顿方向2020年2月12日9时28分27对于二次函数，其展开到二次项的泰勒展开式就是其本身，海赛矩阵G是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。如果某一迭代方法能使二次型函数在有限次迭代内达到极小点，称此迭代方法是二次收敛的。因此牛顿方法是二次收敛的。2020年2月12日9时28分28例:221212,25fxxxx用牛顿法求的极小值解：取初始点02,2TX，则01022450100XxfXx2020050fX1201021050fX110200102402121000050XXfXfX代入牛顿法迭代公式可得:从而经过一次迭代即求得极小点和函数极小值。2020年2月12日9时28分29从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升。因此需要对牛顿法进行改进，引人数学规划法的搜寻概念，产生了阻尼牛顿法。2020年2月12日9时28分30把12kkkdfXfX看作一个搜索方向，称其为牛顿方向，则阻尼牛顿法的迭代公式为：112(0,1,2)kkkkkkkkXXdXfXfXkk——阻尼因子，即沿牛顿方向进行一维搜索的最佳步长，