机械优化设计2-1

第三章无约束优化问题（1）熟悉无约束优化问题的解法可以为研究约束优化问题打下良好的基础。（2）有约束优化问题的求解可以通过一系列无约束优化方法来达到，也可所把有约束优化问题变为无约束优化问题。无约束优化问题是：求n维设计变量12Tnxxxx使目标函数，而对没有如何限制条件。min)(xfx求解无约束优化问题常用的数值计算方法。最常用的是搜索方法，其基本思想是从给定的初始点出发，沿某一搜索方向进行搜索，确定最佳步长使函数值沿方向下降最大。dd依此方式按下述公式不断进行，形成迭代的下降算法：1(0,1,2)kkkkxxdk各种无约束优化方法的区别就在于确定其搜索方向的方法不同。d根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。一类是利用目标函数的一阶或二阶导数的无约束优化方法，如最速下降法，共轭梯度法、牛顿法及变尺度法等。另一类是只利用目标函数值的无约束优化方法，如坐标轮换法，单形法，鲍威尔法。一、多元函数的方向导数与梯度1、方向导数一个二元函数在点处的偏导数，其定义是：),(21xxf),(20100xxx0102101201020011102021020022(,)(,)(,)(,)limlimxxxxfxxxfxxfxxfxxxfxxfxx函数在点处沿某一方向的变化率如图所示。),(21xxf),(20100xxxd其定义应为：dxxfxxxxfdfdx),(),(20102201100lim0称它为该函数沿此方向的方向导数。偏导数、可以看成是函数在分别沿、坐标方向的方向导数。01xxf02xxf),(21xxf),(20100xxx1x2x所以方向导数是偏导数概念的推广，偏导数是方向导数的特例。方向导数与偏导数之间的数量关系:22112220110220110011201020110020102201100coscos),(),(),(),(),(),(000limlimlimxxdddxxfxfdxxxxxfxxxxfdxxxxfxxxfdxxfxxxxfdf2、二函数元的梯度二元函数在处的方向导数的表达式可写为下面的形式),(21xxf),(20100xxx21212211coscos,coscos000xxxxfxfxfxfdf令Txxfxfxfxfxf021210,)(称为函数在点处的梯度。0012(),Txfffxxx),(21xxf),(20100xxx设，为方向单位向量，则有方向导数21coscosdddxfdfTx)(00即函数在点处沿某一方向的方向导数等于函数在该点处的梯度与方向的单位向量的内积。),(21xxf0xd0xdf)(0xfd我们可以把向量之间的内积写成向量之间的投影形式，即0000()()cos((),)Txffxdfxfxdd当在平面内画出的等值线（为一系列常数）时，从上图可以看出：),(21xxfcxxf),(21c（1）在x0处等值线的切线方向d就是函数变化率为零的方向，即有0),cos()()(000dfxfdxfdfTx所以0),cos(df(2)在x0处等值线的法线方向d就是函数变化率为最大的方向，即有0000()()cos(,)()Txffxdfxfdfxd所以cos(,)1fd函数变化率最大的方向是梯度方向。例:求函数在处变化率最大的方向和数值。22121212(,)42fxxxxxx0(0,0)x解：求在点处的梯度方向和数值，计算如下：),(21xxf0x242242)(21210xxxfxfxf52)2()4()()()(2222210xfxfxf0024()1215,21()25555Tfxpfx在x1－x2平面上画出函数等值线和点处的梯度方向p，如图所示。0(0,0)x从图中可以看出，在x0点处函数变化率最大的方向p即为等值线的法线方向，也就是同心圆的半径方向。3、多元函数的梯度将二元函数推广到多元函数，则对于函数在处的梯度，可定义为),,(21nxxxf),,(020100nxxxx)(0xfTxnxnxfxfxfxfxfxfxf0021210)(对于在处沿的方向导数可表示为),,(21nxxxf0xd),cos()()(cos00100dfxfdxfxfdfTniixix其中ndcoscoscos21为方向上的单位向量。d212100)(xniixfxf为梯度的模。)(0xf)()(00xfxfp为梯度方向的单位向量。它与函数等值面相垂直，也就是和等值面上过的一切曲线相垂直，如图cxf)(0x二、多元函数的泰勒展开多元函数的泰勒展开在优化方法中十分重要，许多方法及其收敛性证明都是从它出发的。1、一元函数一元函数在点处的泰勒展开式为()fx0xx20''0'0)(21)()()(xxfxxfxfxf2、二元函数二元函数在点处的泰勒展开式为：),(21xxf),(2010xxx222222121221212221120102100000221),(),(xxfxxxxfxxfxxfxxfxxfxxfxxxxx即：xxGxxxfxfxfTT)(21)()()(00002221120222212()xffxxxGxffxxx02221120222212()xffxxxGxffxxx称为海赛（Hessian）矩阵,()0TxxxGxG对于任意向量若，则称正定；反之负定。G正定则取得极小值。G负定则取得极大值。将多元函数的泰勒级数展开式推广到多元函数时，则在点处的泰勒展开式的矩阵形式为),,(21nxxxf0xxxGxxxfxfxfTT)(21)()()(000为函数在点处的梯度0()fx)(xf0x22221222222122122122120)(nnnnnxfxxfxxfxxfxfxxfxxfxxfxfxG为函数在点处的海赛矩阵。)(xf0x若将函数的泰勒级数展开式只取到线性项，即取)()()()(000xxxfxfxzT则是过点和函数所代表的超曲面相切的切平面。)(xz0x)(xf,()0TxxxGxG对于任意向量若，则称正定；反之负定。G正定则取得极小值。G负定则取得极大值。基本思路--原理图—说明验证—计算方法—程序框图—计算实例教学思路：提出基本思路—几何原理说明—数学说明与验证—计算方法步骤—程序框图流程—计算实例体会第一节最速下降法自然的想法：从某点出发，其搜索方向d取该点的负梯度方向（最速下降方向），使函数值在该点附近的范围内下降最快。按此规律，形成以下迭代的算法：1(0,1,2)()kkkkkkxxdkdfx1()(0,1,2)kkkkxxfxk由于最速下降法是以负梯度方向作为搜索方向。所以最速下降法又称为梯度法。为了使目标函数值沿搜索方能获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有1()()min()min()kkkkkkkkkkfxfxafxfxfx根据一元函数极值的必要条件和多元复合函数求导公式，得'()()()0Tkkkkkfxfxfx即1[()]()0Tkkfxfx或写成1()0Tkkdd最速下降法是一个求解极值问题的古老算法，它直观、简单。由于它采用了函数的负梯度方向作为下一步的搜索方向，所以收敛速度较慢。应用最速下降法使目标函数在开头几步下降很快，所以它可与其它无约束优化方法配合使用。特别是一些更有效的方法都是在对它改进后，或在它的启发下获得的，因此最速下降法仍是许多有约束和无约束优化方法的基础。第三节牛顿型方法牛顿型方法和最速下降法一样，也是求解极值问题古老的算法之一。对于一元函数,一维搜索的牛顿方法。()fx'1''()(0,1,2)()kkkkfxxxkfx对于多元函数，设为极小值的一个近似点，在处将进行展开，保留到二次项，得)(xfkx)(xf*xkx)(xf2()()1()()()()()()2TTkkkkkkfxxfxfxxxxxfxxx式中－在处的海赛矩阵。2()kfx)(xfkx设为的极小点，它作为极小点的下一个近似点，根据极值必要条件1kx)(x)(xf*x1()0kx即21()()()0kkkkfxfxxx得121()()(0,1,2)kkkkxxfxfxk这就是多元函数求极值的牛顿法迭代公式。若某一迭代方法能使二次型函数在有限次迭代内达到极小点，则称此法迭代方法是二次收敛的，因此牛顿方法是二次收敛的。对上述牛顿法进行改进:如果我们把12()()kkkdfxfx看作是一个搜索方向，称其为阻尼牛顿方法。阻尼牛顿法采用如下的迭代公式121()()(0,1,2)kkkkkkkkxxdxfxfxk式中，－沿牛顿方向进行一维搜索的最佳步长，可称为阻尼因子。k可通过如下极小化过程求得k1()()min()kkkkkkkkfxfxdfxd第四节共轭方向及共轭方向法一、共轭方向的概念对于二次函数：1()2TTfxxGxbxc1000xxd为最佳步长，所以01100[()]0Txffxdd二次函数选择搜索方向直指极小点而取得最优。1d*x*111xxd方向上的最佳步长。11d：1()2TTfxxGxbxc1000xxd11()fxGxb当时，。是函数的极小值点，应满足极值必要条件，故有*1xx10*x)(xf0)(**bGxxf即*111111()()()0fxGxdbfxGd得01()0TdGd所以d1和d0关于矩阵G共轭。或称d1和d0对G是共轭方向。二、共轭方向的性质()0,(,1,2,,)()TijdGdijnij若,则,说明与正交（垂直）。GI()0,()Tijddijidjd性质1若非零向量系是对G共轭的，则这n个向量是线性无关的。011,,nddd性质2在n维空间中互相共轭的非零向量的个数不超过n。性质3从任意初始点出发，顺次沿n个的G共轭方向进行一维搜索，最多经过n次迭代就可以找到二次函数极小值。此性质表明这种迭代方法具有二次收敛性。0x011,,nddd)(xf*x三、共轭方向法共轭方向法是建立在共轭方向性质3的基础上的，它提供了求二次函数极小点的原则方法。一般来说，可以选取线性无关的向量系,如坐标轴的单位向量。令：,(0,1,2,,1)kvkn00dv11100dvd根据共轭条件，得0101100()()()0TTdGddGvd011000()()TTdGvdGd0111000()()