机械优化设计2-1

1、第三章第三章 无约束优化问题无约束优化问题（1 1）熟悉无约束优化问题的解法可以为研究约束优化问题打）熟悉无约束优化问题的解法可以为研究约束优化问题打下良好的基础。下良好的基础。（2 2）有约束优化问题的求解可以通过一系列无约束优化方法）有约束优化问题的求解可以通过一系列无约束优化方法来达到，也可所把有约束优化问题变为无约束优化问题。来达到，也可所把有约束优化问题变为无约束优化问题。无约束优化问题是：无约束优化问题是：求求n n维设计变量维设计变量12Tnxxxx使目标函数使目标函数 ，而对，而对 没有如何限制条件。没有如何限制条件。min)(xfx求解无约束优化问题常用的数值计算方法。求解无

2、约束优化问题常用的数值计算方法。最常用的是搜索方法，其基本思想是从给定的初始最常用的是搜索方法，其基本思想是从给定的初始点出发，沿某一搜索方向点出发，沿某一搜索方向 进行搜索，确定最佳步进行搜索，确定最佳步长长 使函数值沿方向使函数值沿方向 下降最大。下降最大。dd依此方式按下述公式不断进行，形成迭代的下降算法：依此方式按下述公式不断进行，形成迭代的下降算法：1(0,1,2)kkkkxxdk各种无约束优化方法的区别就在于确定其搜索方向各种无约束优化方法的区别就在于确定其搜索方向 的方法不同。的方法不同。d根据构成搜索方向所使用的信息性质的不同，无约束优化方根据构成搜索方向所使用的信息性质的不同

3、，无约束优化方法可以分为两类。法可以分为两类。一类是利用目标函数的一阶或二阶导数的无约束优化方法，一类是利用目标函数的一阶或二阶导数的无约束优化方法，如最速下降法，共轭梯度法、牛顿法及变尺度法等。如最速下降法，共轭梯度法、牛顿法及变尺度法等。另一类是只利用目标函数值的无约束优化方法，如坐标轮另一类是只利用目标函数值的无约束优化方法，如坐标轮换法，单形法，鲍威尔法。换法，单形法，鲍威尔法。一、一、 多元函数的方向导数与梯度多元函数的方向导数与梯度1、方向导数、方向导数一个二元函数一个二元函数 在点在点 处的偏导数，处的偏导数，其定义是：其定义是：),(21xxf),(20100 xxx01021

4、01201020011102021020022(,)(,)(,)(,)limlimxxxxf xx xf xxfxxf xxxf xxfxx函数函数 在点在点 处沿某一方向处沿某一方向 的变化率如图所示。的变化率如图所示。),(21xxf),(20100 xxxd 其定义应为：其定义应为：dxxfxxxxfdfdx),(),(20102201100lim0称它为该函数沿此方向的方向导数。称它为该函数沿此方向的方向导数。偏导数偏导数 、 可以看成是可以看成是函数函数 在在 分别分别沿沿 、 坐标方向的方向导数。坐标方向的方向导数。01xxf02xxf),(21xxf),(20100 xxx1x2

5、x所以方向导数是偏导数概念的推所以方向导数是偏导数概念的推广，偏导数是方向导数的特例。广，偏导数是方向导数的特例。方向导数与偏导数之间的数量关系方向导数与偏导数之间的数量关系:22112220110220110011201020110020102201100coscos),(),(),(),(),(),(000limlimlimxxdddxxfxfdxxxxxfxxxxfdxxxxfxxxfdxxfxxxxfdf2、二函数元的梯度、二函数元的梯度二元函数二元函数 在在 处的方向导数的表达式可写处的方向导数的表达式可写为下面的形式为下面的形式),(21xxf),(20100 xxx2121221

6、1coscos,coscos000 xxxxfxfxfxfdf令令Txxfxfxfxfxf021210,)(称称 为函数为函数 在点在点 处的梯度。处的梯度。0012(),Txfff xxx),(21xxf),(20100 xxx设设 ， 为方向单位向量，则有方向导数为方向单位向量，则有方向导数21coscosdddxfdfTx)(00即函数即函数 在在 点处沿某一方向点处沿某一方向 的方向导数的方向导数 等等于函数在该点处的梯度于函数在该点处的梯度 与与 方向的单位向量的内积。方向的单位向量的内积。),(21xxf0 xd0 xdf)(0 xfd我们可以把向量之间的内积写成向量之间的投影形式

7、，即我们可以把向量之间的内积写成向量之间的投影形式，即0000()() cos(), )Txff xdf xf xdd 当在平面内画出当在平面内画出 的等值线的等值线 （ 为为一系列常数）时，从上图可一系列常数）时，从上图可以看出：以看出：),(21xxfcxxf),(21c（1）在）在x0处等值线的切线方向处等值线的切线方向d就是函数变化率为零的方向，即有就是函数变化率为零的方向，即有0),cos()()(000dfxfdxfdfTx所以所以0),cos(df(2)在在x0处等值线的法线方向处等值线的法线方向d就是函数变化率为最大的方向，即有就是函数变化率为最大的方向，即有0000()()

8、cos(, )()Txff xdf xf df xd 所以所以cos(, )1f d函数变化率最大的方向是梯度方向。函数变化率最大的方向是梯度方向。例例:求函数求函数 在在 处变化率最处变化率最大的方向和数值。大的方向和数值。22121212( ,)42f x xxxxx0(0,0)x 解：求解：求 在在 点处的梯度方向和数值，计算如下：点处的梯度方向和数值，计算如下：),(21xxf0 x242242)(21210 xxxfxfxf52)2()4()()()(2222210 xfxfxf0024()1215,21()2 5555Tf xpf x 在在x1x2平面上画出函数等值线和点平面上画出

9、函数等值线和点 处的梯度方向处的梯度方向p，如图所示。如图所示。0(0,0)x 从图中可以看出，在从图中可以看出，在x0点处函数变化率最大的方向点处函数变化率最大的方向p即为等值即为等值线的法线方向，也就是同心圆的半径方向。线的法线方向，也就是同心圆的半径方向。3、多元函数的梯度、多元函数的梯度将二元函数推广到多元函数，则对于函数将二元函数推广到多元函数，则对于函数 在在 处的梯度处的梯度 ，可定义为，可定义为),(21nxxxf),(020100nxxxx)(0 xfTxnxnxfxfxfxfxfxfxf0021210)( 对于对于 在在 处沿处沿 的方向导数可表示为的方向导数可表示为),(

10、21nxxxf0 xd),cos()()(cos00100dfxfdxfxfdfTniixix其中其中ndcoscoscos21为为 方向上的单位向量。方向上的单位向量。d212100)(xniixfxf为梯度为梯度 的模。的模。)(0 xf)()(00 xfxfp为梯度方向的单位向量为梯度方向的单位向量。它与函数等值面它与函数等值面 相垂直，也就是和等值面上相垂直，也就是和等值面上过过 的一切曲线相垂直，如图的一切曲线相垂直，如图cxf)(0 x二、二、 多元函数的泰勒展开多元函数的泰勒展开多元函数的泰勒展开在优化方法中十分重要，许多方法及多元函数的泰勒展开在优化方法中十分重要，许多方法及其

11、收敛性证明都是从它出发的。其收敛性证明都是从它出发的。1、一元函数、一元函数一元函数一元函数 在点在点 处的泰勒展开式为处的泰勒展开式为( )f x0 xx 20 00)(21)()()(xxfxxfxfxf2、二元函数、二元函数二元函数二元函数 在点在点 处的泰勒展开式为：处的泰勒展开式为：),(21xxf),(2010 xxx 222222121221212221120102100000221),(),(xxfxxxxfxxfxxfxxfxxfxxfxxxxx即：即：xxGxxxfxfxfTT)(21)()()(00002221120222212()xffxx xG xffx xx 022

12、21120222212()xffxx xG xffx xx 称称为海赛为海赛（Hessian）矩阵矩阵,( )0Txxx GxG对于任意向量若，则称 正定；反之负定。G正定则取得极小值。正定则取得极小值。G负定则取得极大值。负定则取得极大值。将多元函数的泰勒级数展开式推广到多元函数时，则将多元函数的泰勒级数展开式推广到多元函数时，则在在 点处的点处的泰勒展开式的矩阵形式为泰勒展开式的矩阵形式为),(21nxxxf0 xxxGxxxfxfxfTT)(21)()()(000为函数为函数 在在 点处的梯度点处的梯度0()f x)(xf0 x22221222222122122122120)(nnnnn

13、xfxxfxxfxxfxfxxfxxfxxfxfxG为函数为函数 在在 点处的点处的海赛矩阵。海赛矩阵。)(xf0 x若将函数的泰勒级数展开式只取到线性项，若将函数的泰勒级数展开式只取到线性项，即取即取)()()()(000 xxxfxfxzT则则 是过点是过点 和函数和函数 所代表的超曲面相切的切平面。所代表的超曲面相切的切平面。)(xz0 x)(xf,( )0Txxx GxG对于任意向量若，则称 正定；反之负定。G正定则取得极小值。正定则取得极小值。G负定则取得极大值。负定则取得极大值。基本思路基本思路-原理图原理图说明验证说明验证计算方法计算方法程序框图程序框图计算实例计算实例教学思路：

14、教学思路：提出基本思路提出基本思路几何原理说明几何原理说明数学说明与验证数学说明与验证计算方法计算方法步骤步骤程序框图流程程序框图流程计算实例体会计算实例体会第一节第一节 最速下降法最速下降法自然的想法：从某点出发，其搜索方向自然的想法：从某点出发，其搜索方向d取该点的取该点的负梯度方负梯度方向向（最速下降方向），使函数值在（最速下降方向），使函数值在该点该点附近附近的范围内下降最快的范围内下降最快。按此规律，形成以下迭代的算法：按此规律，形成以下迭代的算法：1(0,1,2)()kkkkkkxxdkdf x 1()(0,1,2)kkkkxxf xk由于最速下降法是由于最速下降法是以负梯度方向作

15、为搜索方向。以负梯度方向作为搜索方向。所以最速下降所以最速下降法又称为法又称为梯度法梯度法。为了使目标函数值沿搜索方能获得最大的下降值，其步长为了使目标函数值沿搜索方能获得最大的下降值，其步长因子应取一维搜索的最佳步长。因子应取一维搜索的最佳步长。即有即有1()()min()min()kkkkkkkkkkfxfxafxfxfx 根据一元函数极值的必要条件和多元复合函数求导公式，得根据一元函数极值的必要条件和多元复合函数求导公式，得()()()0Tkkkkkfxfxfx 即即1()()0Tkkf xf x或写成或写成1()0Tkkdd最速下降法是一个求解极值问题的古老算法，它直观、简单。最速下降

16、法是一个求解极值问题的古老算法，它直观、简单。由于它采用了函数的负梯度方向作为下一步的搜索方向，所以收由于它采用了函数的负梯度方向作为下一步的搜索方向，所以收敛速度较慢。敛速度较慢。应用最速下降法使目标函数应用最速下降法使目标函数在开头几步下降很快，所以它可在开头几步下降很快，所以它可与其它无约束优化方法配合使用与其它无约束优化方法配合使用。特别是一些更有效的方法都是。特别是一些更有效的方法都是在对它改进后，或在它的启发下在对它改进后，或在它的启发下获得的，因此最速下降法仍是许获得的，因此最速下降法仍是许多有约束和无约束优化方法的基多有约束和无约束优化方法的基础。础。第三节第三节 牛顿型方法牛

17、顿型方法牛顿型方法和最速下降法一样，也是求解极值问题古老的算法之一。牛顿型方法和最速下降法一样，也是求解极值问题古老的算法之一。对于一元函数对于一元函数 , 一维搜索的牛顿方法。一维搜索的牛顿方法。( )f x1()(0,1,2)()kkkkfxxxkfx对于多元函数对于多元函数 ，设，设 为为 极小值极小值 的一个近似点，在的一个近似点，在 处将处将 进行展开，保留到二次项，得进行展开，保留到二次项，得)(xfkx)(xf*xkx)(xf2( )( )1()() ()()()()2TTkkkkkkf xxf xf xxxxxf xxx 式中式中 在在 处的海赛矩阵。处的海赛矩阵。2()kf

18、x)(xfkx设设 为为 的极小点，它作为的极小点，它作为 极小点极小点 的下一个近的下一个近似点，根据极值必要条件似点，根据极值必要条件1kx)(x)(xf*x1()0kx即即21()()()0kkkkf xf xxx得得121()()(0,1,2)kkkkxxf xf xk 这就是多元函数求极值的这就是多元函数求极值的牛顿法迭代公式。牛顿法迭代公式。若某一迭代方法能使二次型函数在有限次迭代内达到极小点，若某一迭代方法能使二次型函数在有限次迭代内达到极小点，则称此法迭代方法是二次收敛的，因此牛顿方法是二次收敛的。则称此法迭代方法是二次收敛的，因此牛顿方法是二次收敛的。对上述牛顿法进行改进对上

19、述牛顿法进行改进:如果我们把如果我们把12()()kkkdf xf x 看作是一个搜索方向，称其为看作是一个搜索方向，称其为阻尼牛顿方法。阻尼牛顿方法。阻尼牛顿法采用如下的迭代公式阻尼牛顿法采用如下的迭代公式121()() (0,1,2)kkkkkkkkxxdxf xf xk式中，式中， 沿牛顿方向进行一维搜索的最佳步长，可称为沿牛顿方向进行一维搜索的最佳步长，可称为阻尼因子阻尼因子。k可通过如下极小化过程求得可通过如下极小化过程求得k1()()min()kkkkkkkkf xf xdf xd第四节第四节 共轭方向共轭方向及共轭方向法及共轭方向法一、共轭方向的概念一、共轭方向的概念对于二次函数

20、：对于二次函数：1( )2TTf xx Gxb xc1000 xxd为最佳步长，所以为最佳步长，所以01100( )0Txff xdd 二次函数选择搜索方向二次函数选择搜索方向 直指极小点直指极小点 而取得最优。而取得最优。1d*x*111xxd方向上的最佳步长。方向上的最佳步长。11d：1( )2TTf xx Gxb xc1000 xxd11()f xGxb当当 时，时， 。 是函数是函数 的极小值点，应满足极的极小值点，应满足极值必要条件，故有值必要条件，故有*1xx10*x)(xf0)(*bGxxf即即*111111()()( )0f xG xdbf xGd得得01()0TdGd 所以所

21、以d1和和d0关于矩阵关于矩阵G共轭共轭。或。或称称d1和和d0对对G是共轭方向。是共轭方向。二、共轭方向的性质二、共轭方向的性质()0,( ,1,2, )()TijdGdi jn ij若若 ,则则 ,说明说明 与与 正交（正交（垂直垂直）。）。GI()0,()Tijddijidjd性质性质1 若非零向量系若非零向量系 是对是对G共轭的，则这共轭的，则这n个向个向量是量是线性无关线性无关的。的。011,nd dd性质性质2 在在n维空间中互相共轭的非零向量的个数不超过维空间中互相共轭的非零向量的个数不超过n。性质性质3 从任意初始点从任意初始点 出发，顺次沿出发，顺次沿 n个个的的G共轭方向共

22、轭方向 进行进行一维搜索一维搜索，最多经过，最多经过n次迭代就可以找到二次次迭代就可以找到二次函数函数 极小值极小值 。此性质表明这种迭代方法。此性质表明这种迭代方法具有二次收敛具有二次收敛性。性。0 x011,nd dd)(xf*x三、共轭方向法三、共轭方向法 共轭方向法是建立在共共轭方向法是建立在共轭方向性质轭方向性质3的基础上的，的基础上的，它提供了求二次函数极小点它提供了求二次函数极小点的原则方法。的原则方法。一般来说，可以选取一般来说，可以选取线性无关的向量系线性无关的向量系 , ,如坐标轴的单位向量。令：如坐标轴的单位向量。令：,(0,1,2,1)kvkn00dv11100dvd根

23、据共轭条件，得根据共轭条件，得0101100()()()0TTdGddG vd011000()()TTdGvdGd 0111000()()TTdGvdvddGd从而求出共轭方向，一般地设：从而求出共轭方向，一般地设：111,0kkkkrrrdvd依次根据共轭条件，求出共轭方向依次根据共轭条件，求出共轭方向111,0()()()0kTTjkjkkrrrdGddG vd11,()()TjkkjTjjdGvdGd 1110()()TkjkkkjTjjjdGvdvddGd例例求求210121012G的一组共轭向量的一组共轭向量012,dd d解解 选三个坐标轴上的单位向量选三个坐标轴上的单位向量 作为

24、一组线性无关作为一组线性无关向量系向量系012,e e e100010001210eee取取00100de 设设11100ded011000210010012110120()12101()210012100120TTdGedGd 22211200dedd设设1221112100110121020121()21()32102110121120120TTdGedGd 022000210010012100121()02101()10012110120TTdGedGd 211302220133101d 得得计算表明计算表明0()()( ,0,1,2)0()TijijdGdi jij说明说明 对对 共轭

25、。共轭。012,d d dG1101211012000d 第四节第四节 共轭梯度法共轭梯度法共轭梯度法是共轭方向法中的一种，因为在该方法中每一共轭梯度法是共轭方向法中的一种，因为在该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。称作共轭梯度法。考虑二次函数考虑二次函数 ；从；从 点出发，沿点出发，沿 的某一共轭方向的某一共轭方向 作一维搜索，到达作一维搜索，到达 点，即点，即cxbGxxxfTT21)(kxGkd1kx1kkkkxxa d或或1kkkkxxa d而在而在 、 点处的梯度点处的梯度 、 分别为

26、分别为kx1kxkg1kg11(),()kkkkgf xgf x 所以有所以有11()kkkkkkggG xxa Gd若若 和和 对对 是共轭的，则有是共轭的，则有 jdkdG0)(kTjGdd对两端前乘对两端前乘 ，即得，即得Tjd )(1() ()0jTkkdgg这就是共轭方向与梯度之间的关系。这就是共轭方向与梯度之间的关系。表明沿方向表明沿方向 进行一维搜索，其终点与始点的梯度之差进行一维搜索，其终点与始点的梯度之差 与与 的共轭方向的共轭方向 正交。正交。kd1kkggkdjd共轭梯度法就是利用这个性质做到不必计算矩阵共轭梯度法就是利用这个性质做到不必计算矩阵G G就能就能求得共轭方向

27、的。此性质的几何说明如图所示。求得共轭方向的。此性质的几何说明如图所示。共轭梯度法的计算过程如下：共轭梯度法的计算过程如下：1)1)设初始点设初始点 ，第一个搜索方向取点，第一个搜索方向取点 的负梯度的负梯度 ，即即 。0 x0 x0g00dg 沿沿 一维搜索，得一维搜索，得 ，并算出，并算出 点处的梯点处的梯度度 。 是以是以 为切线和某等值曲线的切点。为切线和某等值曲线的切点。0d1000 xxa d1x1g1x0d根据梯度和该点等值面的切面相垂直的性质，因此根据梯度和该点等值面的切面相垂直的性质，因此 和和 正交，有正交，有 ，从而，从而 和和 正交，即正交，即 ， 和和 组成平面正交系

28、。组成平面正交系。1g0d0)(10gdT0g1g001ggT0d1g2)2)在在 和和 所构成的平面正交系中求所构成的平面正交系中求 的共轭方向的共轭方向 ，作为下一步的搜索方向。把作为下一步的搜索方向。把 取成取成 与与 两个方向的线两个方向的线性组合，即性组合，即 1g0d0d1d1d1g0d0011dgd式中式中 待定常数，它可以根据共轭方向与梯度的关系求得。待定常数，它可以根据共轭方向与梯度的关系求得。0由由0)()(011 ggdT有有0)()(01001ggdgT将此式展开，考虑到将此式展开，考虑到00dg 100Tg g 可求得可求得202100110ggggggTT02021

29、11dgggd沿沿 方向进行一维搜索，得方向进行一维搜索，得 ，并算出该点梯，并算出该点梯度度 ，有，有 ，即，即1d2111xxa d2g0)(21gdT0)(2001gdgT因为因为 和和 共轭，根据共轭方向与梯度的关系式有共轭，根据共轭方向与梯度的关系式有0d1d0)()(120 ggdT考虑到考虑到 ，因此，因此 , ,即即 和和 正交。正交。0)(10gdT0)(20gdT2g0g根据根据 ，得，得 ，即，即 又和又和 正交。正交。0)(2001gdgT021ggT2g1g由此可知由此可知 构成一个正交系。构成一个正交系。012,gg g3)3)在在 所构成一个正交系中，求与所构成一

30、个正交系中，求与 及及 均共轭均共轭的方向的方向 。012,gg g0d1d2d设设001122gggd式中式中 、 待定系数。待定系数。10因为要求因为要求 与与 和和 均共轭，根据公式均共轭，根据公式 中共轭方向与梯度的关系，有中共轭方向与梯度的关系，有2d0d1d1() ()0j Tkkdgg0)()(0)()(12001120100112ggggggggggTT考虑到考虑到 相互正交，从而有相互正交，从而有012,gg g1110002211100TTTTg gg gg gg g设设 ，得，得112122112211ggggggTT01001110ggggTT因此因此221100211

31、10002110121()dggggggggdgd 从而得出从而得出1212222dgggd再沿再沿 方向继续进行一维搜索，如此继续下去可求得共轭方方向继续进行一维搜索，如此继续下去可求得共轭方向的向的递推公式递推公式为为2d21112(0,1,21)kkkkkgdgdkng 沿着这些共轭方向一直搜索下去，直到最后迭代点处梯度的模沿着这些共轭方向一直搜索下去，直到最后迭代点处梯度的模小于给定允许值为止。小于给定允许值为止。001000002111002111110112022220113222220212221,xgdgxxdgx g dgdgdxxdggxgdgddgdxxdg 若目标函数为

32、非二次函数，若目标函数为非二次函数，经经n次搜索还未达到最优次搜索还未达到最优点时，则以最后得到的点点时，则以最后得到的点作为初始点，重新计算共作为初始点，重新计算共轭方向，一直到满足精度轭方向，一直到满足精度要求为止。要求为止。共轭梯度法的程序框图如共轭梯度法的程序框图如图所示。图所示。用共轭梯度法求二次函数用共轭梯度法求二次函数211222121242),(xxxxxxxf的极小点及极小值。的极小点及极小值。解：解：1 1）取初始点）取初始点0(1,1)x则则2424422)(0122100 xxxxxxfg取取2400gd沿沿 方向进行一维搜索，得方向进行一维搜索，得0d00000012

33、1412411aaadaxx其中的其中的 为最佳步长，可通过为最佳步长，可通过0a101100()min(),()0af xaa求得求得 ，则，则 410a01021411 22axa 2 2）为建立第二个共轭方向）为建立第二个共轭方向 ，需计算点，需计算点 处的梯度及系处的梯度及系数数 值，得值，得1d1x02124422)(1122111xxxxxxfg4120520210gg从而求得第二个共轭方向从而求得第二个共轭方向1100214132242dgd 再沿再沿 进行一维搜索，得进行一维搜索，得1d1211111222213132222axxa daa 其中的其中的 为最佳步长，通过为最佳

34、步长，通过1a122121()min(),()0af xaa求得求得 ，则，则11a 12122413222axa 计算计算 点处的梯度点处的梯度2x21222212240()0420 xxxgf xxx 说明说明 点满足极值必要条件，再根据点满足极值必要条件，再根据 点的海赛矩阵点的海赛矩阵 2x2x4222)(2xG是正定的，可知满足极值充分必要条件。故为极小点，即是正定的，可知满足极值充分必要条件。故为极小点，即242*xx而函数极小值为而函数极小值为共轭梯度法的优点是共轭梯度法的优点是程序简单程序简单，存储量少存储量少，具有最速下降法的，具有最速下降法的优点，而在收敛速度上比最速下降法

35、快，具有优点，而在收敛速度上比最速下降法快，具有二次收敛性二次收敛性。8)(xf第五节第五节 变尺度法变尺度法一、尺度矩阵的概念一、尺度矩阵的概念变量的尺度变换是变量的尺度变换是放大或缩小各个坐标放大或缩小各个坐标，通过尺度变换可以把，通过尺度变换可以把函数的偏心程度降低到最低限度。函数的偏心程度降低到最低限度。例如：求例如：求 的极小值问题，如用最速下降法时，的极小值问题，如用最速下降法时，需要进行需要进行1010次迭代才能达到极小点次迭代才能达到极小点 。但是，若作变换。但是，若作变换22212125),(xxxxf*(0,0)x11225yxyx即把即把 的尺度放大的尺度放大5 5倍，就

36、可以将等值线为椭圆的函数倍，就可以将等值线为椭圆的函数 变换成等值线为圆的函数变换成等值线为圆的函数 ，从而消除了函，从而消除了函数的偏心，用最速下降法只需迭代一次即可求得极小点。数的偏心，用最速下降法只需迭代一次即可求得极小点。2x),(21xxf221212(,)y yyy对于一般二次函数对于一般二次函数cxbGxxxfTT21)(如果进行尺度变换如果进行尺度变换xQx则在新的坐标系中，函数则在新的坐标系中，函数 的二次项变为的二次项变为( )f x1122TTTx GxxQ GQx选择这样变换的目的，仍然是为了降低二次项的偏心程度。若选择这样变换的目的，仍然是为了降低二次项的偏心程度。若

37、矩阵矩阵 是正定的，则总存在是正定的，则总存在 使使GQTQ GQI（单位矩阵）（单位矩阵）将函数将函数偏心度变为零。偏心度变为零。用用 右乘等式两边，得右乘等式两边，得1Q1TQ GQ再用再用 左乘等式两边，得左乘等式两边，得QTQQ GI所以所以1TQQG这说明二次函数矩阵的逆阵这说明二次函数矩阵的逆阵 ，可以通过尺度变换矩阵，可以通过尺度变换矩阵 来求得。来求得。GQ牛顿迭代过程中的牛顿方向便可以写成牛顿迭代过程中的牛顿方向便可以写成)()(1kTkkxfQQxfGd牛顿迭代公式变为牛顿迭代公式变为)(1kTkkkkkkxfQQaxdaxx例如：二次函数例如：二次函数22212125),

38、(xxxxfGxxxxxxxxxxfT21500022125),(2121222121其中其中50002G若取若取 的变换的变换 ，则在变换后的坐标系中，则在变换后的坐标系中，矩阵矩阵 变为变为2510021QQxx GIGQQT10010050002002512125121从而求得从而求得5012125121251211000000TQQG只需通过一次迭代即可求得极小点只需通过一次迭代即可求得极小点 和极小值和极小值 。*(0,0)x0)(*xf比较牛顿迭代公式比较牛顿迭代公式)(1kTkkkxfQQaxx和梯度迭代公式和梯度迭代公式)(1kkkkxfaxx可以看出，差别在于牛顿法中多了可以

39、看出，差别在于牛顿法中多了 部分。部分。TQQ 实际上是在实际上是在 空间内测量距离大小的一种度量，称空间内测量距离大小的一种度量，称作作尺度矩阵尺度矩阵 。TQQxHTHQQ如在未进行尺度变换前，向量如在未进行尺度变换前，向量 长度的概念是长度的概念是x21)(xxxT变换后向量变换后向量 对于对于 尺度下的长度尺度下的长度xH212121)()()()(HxxxQQxQxQxxTTTTH为使这种尺度有用，必须对一切非零向量的为使这种尺度有用，必须对一切非零向量的 均有均有 即要求即要求尺度矩阵尺度矩阵 正定正定。既然牛顿迭代法公式可用长度变。既然牛顿迭代法公式可用长度变换矩阵换矩阵 表示出

40、来，即表示出来，即x0)(HxxTHTHQQ)(1kkkkxfHaxx二二 变尺度矩阵的建立变尺度矩阵的建立对于一般函数对于一般函数 ，当用牛顿法寻求极小点时，其牛顿迭代公式为，当用牛顿法寻求极小点时，其牛顿迭代公式为( )f x11(0,1,2)kkkKkxxa G gk其中其中)()(2kkkkxfGxfg为了避免在迭代公式中计算海赛矩阵的逆阵为了避免在迭代公式中计算海赛矩阵的逆阵 ，可用在迭代，可用在迭代中逐步建立的变尺度矩阵中逐步建立的变尺度矩阵1kG)(kkxHH 来替换来替换 ，即构造一个矩阵序列，即构造一个矩阵序列 来逼近海赛逆矩阵序来逼近海赛逆矩阵序列。每迭代一次，尺度就改变一

41、次，这正是列。每迭代一次，尺度就改变一次，这正是“变尺度变尺度”的含义。的含义。1kG1kG这样，上式变为这样，上式变为1(0,1,2)kkkkkxxa H gk其中其中 是从是从 出发，沿方向出发，沿方向 作一维搜索而得到作一维搜索而得到的最佳步长。如当的最佳步长。如当 （单位矩阵）时，它就变成最速下（单位矩阵）时，它就变成最速下降法。降法。以上就是变尺度法的基本思想。以上就是变尺度法的基本思想。kakxkkkdH g kHI为了使为了使变尺度矩阵变尺度矩阵 确实与确实与 近似近似，并具有很容易计，并具有很容易计 算的特点，必须对算的特点，必须对 附加某些条件。附加某些条件。KH1kGKH(

42、1)(1)为保证迭代公式具有下降性质，要求为保证迭代公式具有下降性质，要求 中的每一个矩阵中的每一个矩阵都是都是对称正定对称正定的。的。kH因为若要求搜索方向因为若要求搜索方向 为下降方向，即要求为下降方向，即要求 也就是也就是 ，这样，这样， 即即 应为对称正定。应为对称正定。kkkdH g 0kTkdg0kKTkgHg0kKTkgHgKH(2)(2)要求要求 之间的迭代具有之间的迭代具有简单的形式简单的形式。显然。显然 为最简单的形式。其中为最简单的形式。其中 为为校正矩阵校正矩阵。KHkkkEHH1kE(3)(3)要求要求 必须满足必须满足拟牛顿条件拟牛顿条件。kH所谓拟牛顿条件，可由下

43、面的推导给出。设迭代过程所谓拟牛顿条件，可由下面的推导给出。设迭代过程已进行到步已进行到步 ， ， 均已求出，现在推导均已求出，现在推导 所必须满足的条件。当所必须满足的条件。当 为具有正定矩阵为具有正定矩阵 的二次函的二次函数时，根据泰勒展开可得数时，根据泰勒展开可得1k 1kx1kg1kH( )f xG)(11kkkkxxGgg即即kkkkxxggG111)(因为具有正定海赛矩阵因为具有正定海赛矩阵 的一般函数，在极小点附近可的一般函数，在极小点附近可用二次函数很好的近似，所以我们就联想到如果迫使用二次函数很好的近似，所以我们就联想到如果迫使 满满足类似于上式的关系：足类似于上式的关系：1

44、kG1kH111()kkkkkHggxx那么那么 就可以很好地近似于就可以很好地近似于 。因此，把上面的关。因此，把上面的关系式称作系式称作拟牛顿条件拟牛顿条件（或拟牛顿方程）。为简便起见，记（或拟牛顿方程）。为简便起见，记1kH11kGkkkkkkxxsggy11则则拟牛顿条件拟牛顿条件可写成可写成kkksyH1根据上述拟牛顿条件，不通过海赛矩阵求逆就可以根据上述拟牛顿条件，不通过海赛矩阵求逆就可以构造一个构造一个矩阵矩阵 来逼近海赛矩阵的逆阵来逼近海赛矩阵的逆阵 ，这类方法统称作，这类方法统称作拟牛顿法。拟牛顿法。1kH11kG由于变尺度矩阵的建立应用了拟牛顿条件。所以变尺度法也由于变尺度

45、矩阵的建立应用了拟牛顿条件。所以变尺度法也是属于一种拟牛顿法。变尺度法对于具有正定矩阵是属于一种拟牛顿法。变尺度法对于具有正定矩阵 的二的二次函数，能产生对次函数，能产生对 共轭的搜索方向。因此变尺度法又可共轭的搜索方向。因此变尺度法又可以看成是一种共轭方向法。以看成是一种共轭方向法。GG三、变尺度法的一般步骤：三、变尺度法的一般步骤：对一般多元函数对一般多元函数 ，用变尺度法求极小点，用变尺度法求极小点 ，其一般步骤是：，其一般步骤是：( )f x*x1 1）选定初始点）选定初始点 和收敛精度和收敛精度 。0 x2 2）计算，选取初始对称正定矩阵）计算，选取初始对称正定矩阵 ( (例如例如

46、),),置置 。0H0HI0k3 3）计算搜索方向）计算搜索方向 。kkkdH g 4 4）沿）沿 方向进行一维搜索方向进行一维搜索 计算计算 ， ， kd1kkkkxxa d)(11kkxfg1kkksxx1kkkygg5 5）判断是否满足迭代终止准则，若满足则）判断是否满足迭代终止准则，若满足则 ，停机，停机， 否则转否则转6 6。*1kxx6 6）当迭代）当迭代 次后还没找到极小点时，重置次后还没找到极小点时，重置 为单位矩阵为单位矩阵 ，并以当前设计点为初始点并以当前设计点为初始点 ，返回到，返回到2 2进行下一轮迭进行下一轮迭代，否则转到代，否则转到7 7。nkHI10kxx7）计算

47、矩阵）计算矩阵 ，置，置 返回到返回到3kkkEHH11kk对于校正矩阵对于校正矩阵 ，可由具体的公式来计算，不同的公式，可由具体的公式来计算，不同的公式对应不同的变尺度法，但不论哪种变尺度法，对应不同的变尺度法，但不论哪种变尺度法， 必须满必须满足拟牛顿条件：足拟牛顿条件：kEkEkkksyH1即即kkkksyEH)(kkkkkyHsyE或或满足上式满足上式 的有无穷多个的有无穷多个，因此上述变尺度法（属于拟，因此上述变尺度法（属于拟牛顿法）构成牛顿法）构成一族算法一族算法。kE变尺度法计算程序框图如图所示。变尺度法计算程序框图如图所示。四、四、DFPDFP算法算法在变尺度法中，校正矩阵在变

48、尺度法中，校正矩阵 取不同的形式，就形成不同取不同的形式，就形成不同的变尺度法。的变尺度法。kEDFPDFP算法中的算法中的校正矩阵校正矩阵 取下列形式：取下列形式：kETkkkTkkkkvvuuE其中其中 是是 维待定向量，维待定向量， 、 是待定常数，是待定常数， 、 都是对称秩的矩阵，它们可以说是一种最简单的矩阵。都是对称秩的矩阵，它们可以说是一种最简单的矩阵。,kku vnkkTkkuuTkkvv根据校正矩阵根据校正矩阵 要满足拟牛顿条件要满足拟牛顿条件kEkkkkkyHsyEkkkkTkkkTkkkyHsyvvuu)(则有则有kkkkTkkkkTkkkyHsyvvyuu即即满足上面方

49、程的待定向量满足上面方程的待定向量 有多种取法，我们取有多种取法，我们取,kku vkkkTkkkkkTkkkyHyvvsyuu注意到注意到 和和 都是数量，不妨取都是数量，不妨取TkkyuTkkyvkkkkkusvH y这样就可以定出这样就可以定出kkTkkkTkkyHyys11从而可得从而可得DFPDFP算法的校正公式：算法的校正公式：kkTkkTkkkkTkTkkkkyHyHyyHysssHH1(0,1,2)k DFPDFP算法的计算步骤和变尺度法的一般步骤相同，只是具算法的计算步骤和变尺度法的一般步骤相同，只是具体计算校正矩阵时应按上面公式进行。体计算校正矩阵时应按上面公式进行。用用D

50、FPDFP算法求算法求211222121242),(xxxxxxxf的极值解。的极值解。解：解：1）取初始点）取初始点 ，为了按，为了按DFP法构造第一次搜索法构造第一次搜索方向方向 ，需计算初始点处的梯度，需计算初始点处的梯度0(1,1)x0d2424422)(0122100 xxxxxxfg取初始变尺度矩阵为单位矩阵取初始变尺度矩阵为单位矩阵 ，则第一次搜索方向为，则第一次搜索方向为0HI24241001000gHd沿沿 方向进行一维搜索，得方向进行一维搜索，得0d010000014141212axxa daa 其中其中 为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足0a100200

51、0()()(40203)minminaaf xf xa daa00.25a 5 . 021x得得2)2)再按再按DFPDFP法构造法构造 点处的搜索方向点处的搜索方向 ，需计算，需计算1x1d2124422112211xxxxxg5 . 01115 . 02432421010010 xxsggy代入校正公式代入校正公式0 0000010000001310.534100.54330110.534441010.591211010.50.25121652521192550194150100TTTTs sH y y HHHs yy H y 则第二次搜索方向为则第二次搜索方向为5658100415019

52、5019252111121gHd再沿再沿 进行一维搜索，得进行一维搜索，得1d21111118822550.5660.555xxa daaa 其中其中 为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足1a)211458()()(211minmin2aaadxfxfaa451a242x得得3)3)为了判断为了判断 点是否为极值点，需计算点是否为极值点，需计算 点处的梯度及其海点处的梯度及其海赛矩阵赛矩阵2x2x0024422212212xxxxxg2224G梯度为零向量，海赛矩阵正定。可见梯度为零向量，海赛矩阵正定。可见x x2 2点满足极值充要条件，点满足极值充要条件，因此因此x x2 2

53、为极小点。此函数的极值解为为极小点。此函数的极值解为*(4,2)()8xf x DFPDFP算法是戴维登（算法是戴维登（DavidonDavidon）于）于19591959年提出的，后来由弗来年提出的，后来由弗来彻（彻（FletcherFletcher）和鲍威尔（）和鲍威尔（PowellPowell）于）于19631963年作了改进，故用年作了改进，故用三人名字的字头命名。三人名字的字头命名。DFPDFP算法由于算法由于舍入误差舍入误差和一维搜索不精确，有可能和一维搜索不精确，有可能导致奇导致奇异异，而使数值稳定性方面不够理想。所以，而使数值稳定性方面不够理想。所以19701970，Broyd

54、en- Broyden- Fletcher-Goldfarb-ShannoFletcher-Goldfarb-Shanno提出更稳定的算法公式，称作提出更稳定的算法公式，称作BFGSBFGS算法，其校正公式为算法，其校正公式为kTkkTkkTkkkTkkkTkkkTkkkysHyssyHssysvHyHH11因为变尺度法的有效性促使其不断发展，所以出现过许多变尺度因为变尺度法的有效性促使其不断发展，所以出现过许多变尺度的算法，的算法，19701970年黄（年黄（HuangHuang）从共轭条件出发对变尺度法做了统）从共轭条件出发对变尺度法做了统一处理，写出了统一公式一处理，写出了统一公式kkk

55、kkkkkkkkkyHasavyHasau22211211TkkkTkkkvyHusE)()(并取并取可以看出，可以看出，（1 1）取）取 ， ， 就是就是DFPDFP法的公式。法的公式。02112kkaa11kkakka22（2 2）取）取 ， 时，就得到时，就得到BFGSBFGS法的公式。法的公式。kkaa2112022ka（3 3）对）对 的不同赋值可得不同变尺度算法。如取的不同赋值可得不同变尺度算法。如取 时时得麦考密克（得麦考密克（McCormickMcCormick）算法；如取）算法；如取 时，时， 即得皮尔即得皮尔逊（逊（PearsonPearson）算法等等）算法等等。kija

56、02211kkaa02111kkaa第四节第四节 坐标轮换法坐标轮换法 坐标轮换法时每次搜索只允许一个变量变化，其余变坐标轮换法时每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把许多变量的优化问题轮流地转化成单变量（其余变量视把许多变量的优化问题轮流地转化成单变量（其余变量视为常数）的优化问题，因此又称这种方法为变量轮换法。为常数）的优化问题，因此又称这种方法为变量轮换法。在搜索过程中可以不需要目标函数的导数，只需目标函数在搜索过程中可以不需要目标函数的导数，只需目标函数值信息。这比前面所讨论的利用目标函数

57、导数建立搜索方值信息。这比前面所讨论的利用目标函数导数建立搜索方向的方法要简单得多。向的方法要简单得多。以二元函数以二元函数 为例说明坐标轮换法的寻优过程，如图所示。为例说明坐标轮换法的寻优过程，如图所示。),(21xxf从初始点从初始点 出发，沿第一个坐标方向搜索，即出发，沿第一个坐标方向搜索，即 得得 按照一维搜索方法确定最佳步长因子按照一维搜索方法确定最佳步长因子 满足：满足：00 x101ed01010001daxx01a)(0100minadxfa然后从然后从 出发沿出发沿 方向搜索得方向搜索得 ，其中，其中步长因子步长因子 满足：满足： ， 为一轮为一轮 的终点。的终点。01x20

58、2ed02020102daxx02a)(0201minadxfa02x(0)k 检验始、终点间距离是否满足精度要求，即判断检验始、终点间距离是否满足精度要求，即判断 的条件是否满足。若满足则的条件是否满足。若满足则 ，否则令，否则令 ，重，重新依次沿坐标方向进行下一轮新依次沿坐标方向进行下一轮 的搜索。的搜索。0002xx02*xx 0210 xx (1)k 对于对于 个变量的函数，若在第个变量的函数，若在第 轮第轮第 个坐标方向个坐标方向 进行搜索，其迭代公式为进行搜索，其迭代公式为nkikid1(0,1,2;1,2,3, )kkkkiiiixxa dkin其中搜索方向取坐标方向，即其中搜索

59、方向取坐标方向，即ikied (1,2,3, )in若若 ，则，则 ，否则，否则 ，进行下，进行下一轮搜索，一直到精度满足为止。一轮搜索，一直到精度满足为止。kknxx0knxx *knkxx10按按此计算步骤设计出如图所此计算步骤设计出如图所示的程序框图。示的程序框图。这种方法的收敛效果与目标函数等值线的形状有很大关这种方法的收敛效果与目标函数等值线的形状有很大关系。如果目标函数为二元二次函数，其等值线为圆或长系。如果目标函数为二元二次函数，其等值线为圆或长短轴平行于坐标轴的椭圆时，此法很有效。一般经过两短轴平行于坐标轴的椭圆时，此法很有效。一般经过两次搜索即可达到最优点，如下图次搜索即可达

60、到最优点，如下图a所示；所示；如图如图b b所示。如果等值线为长短轴不平行于坐标轴的椭圆，所示。如果等值线为长短轴不平行于坐标轴的椭圆，则需多次迭代才能达到最优点，则需多次迭代才能达到最优点，如图如图c c所示。如果等值线出现脊线，本来沿脊背线方向一步所示。如果等值线出现脊线，本来沿脊背线方向一步可达到最优点，但因坐标轮换法总是沿坐标轴方向搜索而不能可达到最优点，但因坐标轮换法总是沿坐标轴方向搜索而不能沿脊线搜索，所以就终止到脊线上而不能找到最优点。沿脊线搜索，所以就终止到脊线上而不能找到最优点。从上述分析可以看出，采用坐标轮换法只能轮流沿着坐标从上述分析可以看出，采用坐标轮换法只能轮流沿着坐