机械优化设计_第四章无约束优化方法

机械优化设计第四章无约束优化方法一、概述二、最速下降法（梯度法）三、牛顿型方法（牛顿法和阻尼牛顿法）四、共轭方向和共轭方向法五、共轭梯度法六、变尺度法七、坐标轮换法机械优化设计实际中的工程问题大都是在一定限制条件下追求某一指标为最小，属于约束优化问题。为什么要研究无约束优化问题？1）有些实际问题，其数学模型本身就是一个无约束问题；2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础；3）约束优化问题的求解可用通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。机械优化设计1、无约束优化问题n求维设计变量使目标函数12,,TnXxxxminfXX，而对没有任何限制条件。2、求解方法（1）利用极值条件来确定极值点的位置。（2）数值计算方法——搜索方法基本思想：从给定的初始点出发，沿某一搜索方向0x0d进行搜索，确定最佳步长0使函数值沿0d下降最大。依此方式不断进行，形成迭代的下降算法：1kkkkXXd(0,1,2)k一、概述机械优化设计3、算法框图机械优化设计4、无约束优化方法的分类根据确定其搜索方向方法不同，可分为：kd（2）利用目标函数的一阶或二阶导数的无约束优化方法（或称间接法）如：最速下降法（梯度法）、共轭梯度法、牛顿法及变尺度法；间接法除了要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵；（1）只利用目标函数值的无约束优化方法（或称直接法，即不使用导数信息），如：坐标轮换法、单形替换法及鲍威（Powell）法。直接法不必求函数导数，只计算目标函数值。适用于求解变量个数较少（小于20）的问题，一般情况下效率较低。搜索方向的构成问题是无约束优化方法的关键。机械优化设计二、最速下降法（梯度法）1、基本思想函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，即利用负梯度作为搜索方向，故称为最速下降法或梯度法。dfX1kkkkXXfX(0,1,2)k搜索方向取该点的负梯度方向即，使函数值在该点附近的范围内下降最快。机械优化设计2、最速下降法的原理（1）使，按此规律不断走步，形成迭代算法：dfX1kkkkXXfX(0,1,2)k（2）其步长因子取一维搜索的最佳步长，即k根据一元函数极值的必要条件和多元复合函数求导公式，得0TkkKkfXfXfX10Tkkdd10Tkkfxfx或1minminkkkkkkkfxfxafxfxafx机械优化设计由此可知，在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线，形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。最速下降法的搜索路径函数梯度为局部性质，因此并非“最快”。机械优化设计梯度法的迭代历程机械优化设计方法特点1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点；2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。机械优化设计最速下降法的程序框图机械优化设计例：求目标函数221225fXxx的极小点解法1：取初始点02,2TX，则初始点处的函数值及梯度分别为：01021042450100fXxfXx0100000242421002100XXfX0为一维搜索最佳步长，应满足极值必要条件10022minmin(24)25(2100)minfXfXfX0008(24)5000(2100)006260.0200307231252机械优化设计则第一次迭代设计点位置和函数值0120241.91987721000.307178510X13.686164fX经过10次迭代后，得到最优解：0,0TX0fX该问题的目标函数的等值线为一族椭圆，迭代点走的是一段锯齿形路线。机械优化设计解法2：引入变化11225yxyx，则目标函数12,fxx变为221212,yyyy0104Y010224220YyYy0100000242410201020YYY0260.552010240102000Y10Y0,0TX0fX，经过坐标（尺度）变化后，只需要经过一次迭代，就可找到最优解：机械优化设计不同等值线的迭代过程机械优化设计讨论1221212122201,250502xfxxxxxxx1221212122201,022yyyyyyyy可以看出二者的对角形矩阵不同，前者的等值线为一族椭圆，后者的等值线为一族同心圆，这说明对角形矩阵是表示度量的矩阵或者是表示尺度的矩阵，最速下降法的收敛速度和变量的尺度有很大关系。机械优化设计3、最速下降法收敛速度的估计式2121kkmXXXXMMfx的海赛矩阵最大特征值上界——的海赛矩阵最小特征值下界fx——m2122624150625kkkXXXXXX2122102kkYYYY机械优化设计梯度法的特点：（1）理论明确，程序简单，对初始点要求不严格；（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降法仅仅是指某点的一个局部性质；（3）梯度法相邻两次搜索方向的正交性决定了迭代全过程的搜索路径呈锯齿形，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢；（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线（面）为同心圆（球）的目标函数，一次搜索即可达到极小点。机械优化设计三、牛顿型方法基本思想：在领域内用一个二次函数来近似代替原目标函数，并将的极小值作为目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。kx)(x)(x)(xf)(xf1kx),2,1,0()()('''1kxfxfxxkkkk机械优化设计对于多元函数fX，设kX为fX极小点X的第一个近似点，fX泰勒展开，保留到二次项，得:设1kX为X的极小点，它作为fX极小点X的下一个近似点，根据极值必要条件：10kX即210kkkkfXfXXX112(0,1,2)kkkkXXfXfXk2kfX——海赛矩阵1、牛顿法对于二次函数，海赛矩阵是常矩阵，故从任何点出发，只需一步可找到极小点。---多元函数求极值的牛顿法迭代公式。fxx212TTkkkkkkfxfxxxxxfxxx机械优化设计例:221212,25fxxxx用牛顿法求的极小值解：取初始点02,2TX，则01022450100XxfXx2020050fX1201021050fX110200102402121000050XXfXfX代入牛顿法迭代公式可得:从而经过一次迭代即求得极小点和函数极小值。机械优化设计2、阻尼牛顿法把12kkkdfXfX看作一个搜索方向，称其为牛顿方向，则阻尼牛顿法的迭代公式为：112(0,1,2)kkkkkkkkXXdXfXfXkk——阻尼因子，即沿牛顿方向进行一维搜索的最佳步长，可通过如下极小化过程求得：1minkkkkkkfXfXdfXd（1）阻尼牛顿法的迭代公式在牛顿法中，迭代点的位置是按照极值条件确定，并未含有沿下降方向搜寻的概念，因此采用牛顿迭代公式，对于非二次函数，有时会使函数值上升。机械优化设计（2）阻尼牛顿法的计算步骤1）给定初始点，收敛精度，置0X0k2）计算122kkkfXfXfX、、12kkkdfXfX3）求1kkkkXXd4）检查收敛精度。若1kkXX，则，停机；1kXX否则置1kk返回到2），继续进行搜索。机械优化设计（3）阻尼牛顿法的程序框图机械优化设计方法特点：1）初始点应选在极小点附近，有一定难度；2）尽管每次迭代都不会是函数上升，但不能保证每次都下降；3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外对于二阶不可微函数也不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，可为其他算法提供思路和理论依据。机械优化设计梯度法与牛顿法的比较一般迭代式：梯度法：牛顿法：阻尼牛顿法：112(0,1,2)kkkkXXfXfXk1kkkkXXfX(0,1,2)k112(0,1,2)kkkkkkkkXXdXfXfXk1kkkkXXd(0,1,2)k机械优化设计四、共轭方向和共轭方向法（一）共轭方向的概念设G为nxn阶实对称正定矩阵，如果有两个n维向量和满足，则称向量与关于矩阵G共轭，或称他们是G的共轭方向。当G为单位矩阵时，010TdGd0d1d0d1d0)(10ddT共轭方向的概念是在研究二次函数12TTfXXGXbXcG当为对称正定矩阵时引出的使搜索方向直指极小点。为了克服最速下降法的锯齿现象，提高收敛速度，发展了一类共轭方向法。搜索方向是共轭方向。即将相邻两次搜索方向由正交变为共轭。机械优化设计首先考虑二维情况，如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象。为避免锯齿的发生，取下一次的迭代搜索方向直接指向极小点，如果选定这样的搜索方向，对于二元二次函数只需进行两次直线搜索就可以求到极小点。1000xxad*111xxad1100Txffxdd如果能选定这样的方向，则只需两步搜索得到极小点，即机械优化设计结论：010TdGd两个向量0d1d，对G是共轭向量。1d应满足什么条件？对于二次函数在处取得极小点的必要条件fx*x**0fxGxb*111111fxGxadbGxbaGd1110fxaGd等式两边同左乘得：0Td0d1d和称为对G的共轭方向。12TTfXXGXbXc01*1时，当xx机械优化设计（三）共轭方向法1、共轭方向法的步骤（1）选定初始点0X，下降方向0d和收敛精度，置0k（2）沿kd方向进行一维搜索，得1kkkkXXd（3）判断1kfX是否满足，若满足则打印，1kX停机，否则转4）。（4）提供新的共轭方向1kd，使10,0,1,2,,TjkdGdjk（5）置1kk，转2）。机械优