无约束优化方法

1、第四章第四章 无约束最优化方法无约束最优化方法第一节第一节 概述概述第二节第二节 最速下降法最速下降法第三节第三节 牛顿法牛顿法第四节第四节 共轭方向法共轭方向法第五节第五节 变尺度法变尺度法第六节第六节 坐标轮换法坐标轮换法第七节第七节 powellpowell法法作业作业第一节第一节 概概 述述一、求解问题一、求解问题 () 0f X二、方法分类二、方法分类解析法解析法数值法数值法间接法：用导数信息构造搜索方向间接法：用导数信息构造搜索方向d(k)min () nf XXR(1)( )( )kkkkXXd直接法：用函数信息构造搜索方向直接法：用函数信息构造搜索方向d(k)三、数值法的基本问

2、题三、数值法的基本问题显然，若使数值法切实可行，必需首先解决以下四个问题：显然，若使数值法切实可行，必需首先解决以下四个问题：如何确定某点处的搜索方向如何确定某点处的搜索方向？如何确定步长如何确定步长？如何确定迭代过程的终止准则如何确定迭代过程的终止准则？1.1.如何衡量数值算法的好坏如何衡量数值算法的好坏？ 下降性下降性简便性简便性收敛性收敛性(1)( )()()kkf Xf X(1)( )( )kkkkXXd( )*limkkXX四、算法的收敛性四、算法的收敛性这里这里X* *是无约束问题的局部解。是无约束问题的局部解。所谓收敛，是指序列所谓收敛，是指序列 X(k) 或它的一个子列或它的一

3、个子列( (不妨仍记为不妨仍记为 X(k) )满满足足( )*limkkXX 若对于某些算法来说若对于某些算法来说, ,只有当初始点只有当初始点X(0)充分靠近极小点充分靠近极小点X* *时，才能保证序列时，才能保证序列 X(k) 收敛到收敛到X* *，则称这类算法为局部收敛。，则称这类算法为局部收敛。 反之，若对任意的初始点反之，若对任意的初始点X(0)，产生的序列产生的序列 X(k) 收敛到收敛到X* *，则称这类算法为全局收敛则称这类算法为全局收敛. .如果算法产生的序列如果算法产生的序列 X(k) 虽然收敛到虽然收敛到X*，但收敛的太但收敛的太“慢慢”，以致于在计算机允许的时间内仍得不

4、到满意的结果，那么，以致于在计算机允许的时间内仍得不到满意的结果，那么，这类算法也称不上好算法这类算法也称不上好算法. .五、算法的收敛速率五、算法的收敛速率设序列设序列 X(k) 收敛到收敛到x x* *, ,若极限若极限存在，当存在，当0101p1时，时，p p阶收敛必为超线性收敛，阶收敛必为超线性收敛，但反之不一定成立。在最优化算法中，通常考虑线性收敛、但反之不一定成立。在最优化算法中，通常考虑线性收敛、超线性收敛和二阶收敛。超线性收敛和二阶收敛。上面谈到的收敛性和收敛速率能够较为准确地刻划出算法的上面谈到的收敛性和收敛速率能够较为准确地刻划出算法的优劣程度，但使用起来比较困难。特别是证

5、明一个算法是否优劣程度，但使用起来比较困难。特别是证明一个算法是否收敛或具有什么样的收敛速率，需要很强的理论知识。在这收敛或具有什么样的收敛速率，需要很强的理论知识。在这里给出一较为简单地判断算法优劣的评价标准里给出一较为简单地判断算法优劣的评价标准算法的二算法的二次终止性。次终止性。定义：若某个算法对于任意的正定二次函数，从任意的初始定义：若某个算法对于任意的正定二次函数，从任意的初始点出发，都能经有限步迭代达到其极小点，则称该算法具有点出发，都能经有限步迭代达到其极小点，则称该算法具有二次终止性。二次终止性。六、算法的二次终止性六、算法的二次终止性从某一点从某一点X(k)出发，以该点的最速

6、下降方向：即负梯度方向出发，以该点的最速下降方向：即负梯度方向 f( (X(k) )，进行一维搜索，得最优步长，进行一维搜索，得最优步长 k，从而获得新的迭，从而获得新的迭代点代点X(k+1)，如此重复迭代，如此重复迭代，即得到无约束问题的最优解即得到无约束问题的最优解. .第二节第二节 最速下降法最速下降法一、方法说明一、方法说明(1)( )( )kkkkXXd( )( ) () kkdf X ( )( ) ( )()()minkkf Xf Xf X 二、几何说明二、几何说明相邻两次搜索方向正交，相邻两次搜索方向正交，(1)( )(1)( ) () 0kkkkddf Xd由由( )( ) (

7、)()0kdf Xf Xd 得得(1) (1) 取初始点取初始点X(0)，精度指标，精度指标 ，置置k= =0. .三、算法步骤三、算法步骤(2) (2) 若若 则停止计算，将则停止计算，将X(k)作作为无约束问题的最优解输出；为无约束问题的最优解输出； 否则置否则置(3)(3)求解一维问题求解一维问题( )()kf X( )( )()kkdf X (4)(4)置置k=k+1，转转(2).(2).(1)( )( )kkkkXXd( )( ) ( )()minkkf Xd 得得3. 3. 若一维搜索是精确的，则最速下降法产生的相邻两次的搜若一维搜索是精确的，则最速下降法产生的相邻两次的搜索方向是

8、相互正交的。索方向是相互正交的。四、算法特点四、算法特点由此表明，最速下降法相邻的两次迭代的前进方向是相互垂由此表明，最速下降法相邻的两次迭代的前进方向是相互垂直的，因而整个行进路径呈锯齿形，因此从全局来看直的，因而整个行进路径呈锯齿形，因此从全局来看, ,收敛较收敛较慢。从前面的分析可以得到这样一个结论：最速下降法不最慢。从前面的分析可以得到这样一个结论：最速下降法不最速。换句话说，最速下降方向未必是最好的搜索方向。应该速。换句话说，最速下降方向未必是最好的搜索方向。应该考虑其它的下降方向作为搜索方向。考虑其它的下降方向作为搜索方向。1. 1. 要求目标函数连续可导；要求目标函数连续可导；2

9、. 2. 当初始点远离最优点时，或目标函数形态。接近于圆（或当初始点远离最优点时，或目标函数形态。接近于圆（或球）时，步长较大，收敛较快；球）时，步长较大，收敛较快；1 1NewtonNewton法的基本思想法的基本思想若若x x* *是无约束问题的局部解，则是无约束问题的局部解，则x x* *满足满足第三节第三节 牛顿法牛顿法因此因此, ,可以通过求解该方程组来得到无约束最优化问题解。注可以通过求解该方程组来得到无约束最优化问题解。注意到该方程组是非线性的，处理起来比较困难，因此考虑原意到该方程组是非线性的，处理起来比较困难，因此考虑原目标函数在点目标函数在点X(k)处处的一个二次逼近：的一

10、个二次逼近：* () 0f X( )( )( )2( )( )( )()()()() (-)1-()(-)2kkTkkTkkf XpXf Xf XXX XXH XXX 该二次函数的极小点可由下式求得：该二次函数的极小点可由下式求得：( )( )( )2()()()(-)0kkkpXf XH XXX 1*( )( )( )()()kkkpXXH Xf X 即：即：将二次函数的这个极小点作为原目标函数极小点的近似，将二次函数的这个极小点作为原目标函数极小点的近似，即：即：1(1)( )( )( )()()kkkkXXH Xf X 由此可见，牛顿法的搜索方向为：由此可见，牛顿法的搜索方向为：1( )

11、( )( )()()kkkdH Xf X 步长为：步长为：1k (1) (1) 取初始点取初始点X(0)，精度指标，精度指标 ，置置k= =0. .(2) (2) 若若 则停止计算，将则停止计算，将X(k)作作为无约束问题的最优解输出；为无约束问题的最优解输出； 否则置否则置(3)(3)求新的迭代点求新的迭代点( )()kf X1( )( )( )()()kkkdH Xf X (4)(4)置置k=k+1，转转(2).(2).(1)( )( )kkkXXd2 2 算法步骤：算法步骤：3 3 例题例题NewtonNewton法的优点法的优点: :(1)Newton(1)Newton法产生的点列法产

12、生的点列 X(k)若收敛，则收敛速度快，具有若收敛，则收敛速度快，具有二阶收敛速率二阶收敛速率( (证明略证明略) )。(2)Newton(2)Newton法具有二次终止性。法具有二次终止性。4 4 算法特点：算法特点：NewtonNewton法的缺点法的缺点: :(1)(1)可能会出现在某步迭代时目标函数值上升，即存在可能会出现在某步迭代时目标函数值上升，即存在k，使得，使得f(X(k+1)f(X(k)。如在上例中。如在上例中, ,取取x x(1)(1)=(1=(1，1)1)T T，f(x(x(1)(1)=4)=4，由，由NewtonNewton法得到的法得到的x x(2)(2)=(-0.7

13、5,-1.25)=(-0.75,-1.25)T T，此时，此时，f(x(x(2)(2)=4.5156)=4.5156函数值上升。函数值上升。(2)(2)当初始点当初始点x x(1)(1)距距x x* *较远时，产生的点列较远时，产生的点列 X(k)可能不收敛；或可能不收敛；或者收敛到鞍点；或者者收敛到鞍点；或者H(xH(x(k)(k) )奇异无法计算。奇异无法计算。 (3)(3)需要计算需要计算HesseHesse矩阵矩阵, ,计算量大。计算量大。修正修正NewtonNewton法是针对缺点法是针对缺点(1)(1)提出改进方案的。为了避免函提出改进方案的。为了避免函数值上升，在算法中增加一维搜

14、索策略，即将数值上升，在算法中增加一维搜索策略，即将d d(k)(k)作为搜索方作为搜索方向向( (此时称此时称d d(k)(k)为为NewtonNewton方向方向) )，而不是作为增量，由此得到如，而不是作为增量，由此得到如下算法下算法. .5.5.修正修正NewtonNewton法法1(1)( )( )( )()()kkkkkXXH Xf X( )( )( )()min kkf Xd 1( )( )( )()()kkkdH Xf X 修正修正NewtonNewton法保持了法保持了NewtonNewton法的优点法的优点, ,，如算法的二次，如算法的二次终止性等，克服了目标函数值上升的缺

15、点，由于增加了一终止性等，克服了目标函数值上升的缺点，由于增加了一维搜索，对缺点维搜索，对缺点(2)(2)有所改善，但不能完全克服。有所改善，但不能完全克服。对于缺点对于缺点(3)(3)没有任何改进，因为修正没有任何改进，因为修正NewtonNewton法仍需要计法仍需要计算算HesseHesse矩阵。矩阵。 另一种修正方案是将另一种修正方案是将NewtonNewton方向与最速下降方向相结合。方向与最速下降方向相结合。设设d(k)N是是NewtonNewton方向，即方向，即d(k)N满足满足这里假设这里假设H H(X(k)非奇异。设非奇异。设 k是是dN(k)与与- - f(X(k)之间的

16、夹角。之间的夹角。当然希望当然希望 k不要大于不要大于/2,/2,即存在正数即存在正数01,01,使得使得coscosk . .( )1( )( )()()kkkNdH Xf X GoldsteinGoldstein和和PricePrice在在19671967年提出的修正方案是令年提出的修正方案是令这样得到的这样得到的d(k)d(k)总是下降方向，并满足总是下降方向，并满足coscosk( )1( )( )( )()()()kkkkH Xf Xdf Xcoscosk其他其他第四节第四节 共轭方向法共轭方向法一、共轭方向的概念一、共轭方向的概念对于一个二维二次函数对于一个二维二次函数1()2TT

17、f XX AXB XC其等值线为同心椭圆族其等值线为同心椭圆族(0)X(0)d(1)X(1)()f X(1)d(0)0d(2)*XX(1)(0)(0)0XXd(2)(1)(1)1XXd(2)*XX两次一维搜索即可达到最优点，两次一维搜索即可达到最优点，两次搜索方向满足什么条件？两次搜索方向满足什么条件？由无约束最优点的必要条件得：由无约束最优点的必要条件得：*()0f XAXB即即(2)(1)(1)1()0AXBA XdB(1)(1)1()0f XAd(0)(1)()()0Tdf X上式两边同左乘以上式两边同左乘以d(0)，得：，得：(0)(1)(0)(1)1()()()0TTdf XdAd又

18、由于又由于故得故得(0)(1)()0TdAd称方向称方向d(0)与方向与方向d(1)关于矩阵关于矩阵A共轭共轭二、共轭方向的定义二、共轭方向的定义设矩阵设矩阵A为为n n的的对称正定矩阵，对称正定矩阵， 若若n维空间中有维空间中有m个非零向个非零向量量d(0)， d(1)， d(m-1)，满足，满足( )( )()0 ( ,0,1,.,1)()iTjdAdi jmij则称则称向量向量d(0)， d(1)， d(m-1)关于关于矩阵矩阵A相互共轭；当相互共轭；当矩阵矩阵A为单位矩阵时，为单位矩阵时，则称则称向量向量d(0)， d(1)， d(m-1)相互正交。相互正交。三、共轭方向的性质三、共轭

19、方向的性质1. 1. 若若m个非零向量个非零向量d(0)， d(1)， d(m-1)关于关于矩阵矩阵A相互共轭，相互共轭，则这则这m个非零向量线性无关。个非零向量线性无关。( )(0)(1)(1)011()(.)0 0 0,1,.,1iTmmidAdddim2. 2. 从任意初始点出发从任意初始点出发X(0) ，顺次沿，顺次沿n个个关于关于矩阵矩阵A共轭共轭方向方向d(0)， d(1)， d(n-1)进行一维搜索进行一维搜索，最多经过，最多经过n次迭代，就次迭代，就可求得可求得n维二次函数的理论极小点维二次函数的理论极小点X*，即以，即以共轭共轭方向方向d(0)， d(1)， d(n-1)作为

20、搜索方向的方法具有二次收敛性。作为搜索方向的方法具有二次收敛性。即即证明：证明：X(0)为任意初始点。为任意初始点。 若若d(0)， d(1)， d(n-1)为为n个个关于关于矩阵矩阵A的共轭的共轭方向，方向，则它们可作为则它们可作为n维空间的一组基向量，则有维空间的一组基向量，则有1()2TTf XX AXB XC设设n维二次函数维二次函数的理论极小点为的理论极小点为X*(0)(0)(1)(1)011.nnXXddd两边左乘两边左乘d(0)TA，得：，得：(0)*(0)(0)(0)(0)0()()()TTTdAXdAXdAd又由于：又由于：*() ()0f XAXBf XAXB和(0)*(0

21、)(0)(0)(0)0() () ()TTTdAXBdAXBdAd(0)(0)0(0)(0)()()()TTdf XdAd故得：故得：( )( )( )( )()()()kTkkkTkdf XdAd记：记：*( )( )(1)1.kknknXXdd则同理可得则同理可得下面证明，由下面证明，由X(k)出发，沿出发，沿共轭共轭方向方向d(k)进行一维搜索，得点进行一维搜索，得点X(k1)，即，即(1)( )( )kkkkXXd其步长如下确定：其步长如下确定：(1)( )()0kTkf Xd( )(1)()0k TkdAXB( )( )( )()0k TkkkdAXAdB( )( )( )( )()

22、k Tkkk Tkdf XdAd 由此可见：由此可见：kk故证故证其步长为：其步长为：四、共轭方向的构造四、共轭方向的构造对于对于n个线性无关向量个线性无关向量e(0)， e(1)， e(n-1)，对其进行关于，对其进行关于矩矩阵阵A的共轭的共轭化处理，得化处理，得n个个共轭共轭方向方向d(0)， d(1)， d(n-1)。然。然后顺次沿这后顺次沿这n个个共轭共轭方向方向进行一维搜索，这就是进行一维搜索，这就是共轭共轭方向法方向法的基本思想。的基本思想。1()2TTf XX AXB XC由由初始点初始点X(0)出发，出发，对于对于n维二次函数维二次函数首先取首先取(0)(0)de令令(1)(1

23、)(0)10dee由由d(0)， d(1)关于关于矩阵矩阵A的共轭，得：的共轭，得：(0)(1)10(0)(0)TTdAedAe 令令(1)( )( )1,0kkkjkjjdee由由d(k+1) 与与d(0)， d(1)， d(k)关于关于矩阵矩阵A的共轭，得：的共轭，得：( )(1)1,( )( )j Tkkjj TjdAedAe 开始开始置置e(j)=0,0,.,1,0.,0，j=0,1,n-1Min Min ( ( )=f()=f(X(k),l+ d(k) X(k+1),l = X(k),l+ k k d(k) kn?置置X(l +1) =X(n) l, l=l+1结束结束yesyesn

24、onoyesyesnono五、共轭方向五、共轭方向法算法框图法算法框图置置X(0),l= X(l),A=H( X(l)置置d(0)=e(0) , k=0k= k +1(1)( )( )1,0kkkjkjjdee( )(1)1,( )( )j Tkkjj TjdAedAe 输出输出: : X*=X(n),l和和f *= f (X(n),l)输入输入: : n, , X(0)( ),(0),n llXX?六、共轭梯度法六、共轭梯度法共轭梯度法共轭梯度法( (Conjugate Graient Method) )是最著名的共轭方向方是最著名的共轭方向方法，它首先由法，它首先由HestenesHest

25、enes和和StiefelStiefel在在19521952年提出来作为解线年提出来作为解线性方程组的方法。性方程组的方法。19641964年年FletcherFletcher和和ReevesReeves应用于求解无约应用于求解无约束问题。在该方法中每个共轭方向的构造都依赖于迭代点处束问题。在该方法中每个共轭方向的构造都依赖于迭代点处的负梯度，而不必确定矩阵的负梯度，而不必确定矩阵A A。对于一个二维二次函数对于一个二维二次函数1()2TTf XX AXB XC( +1)( )( )kkkkXXd(1)(1)1()kkkgf XAXB由由初始点初始点X(k)出发，沿出发，沿共轭共轭方向方向d(

26、k)，进行一维搜索，得点进行一维搜索，得点 X(k1)，即，即( +1)( )( )kkkkXXd或或在在点点X(k)、点、点X(k1)处的梯度记为：处的梯度记为：( )( )()kkkgf XAXB(1)( )( )1()kkkkkkggA XXAd( )kX(1)kX( )kd( ) jd( )()kkgf X (1)1()kkgf X 1kkkggg设设方向方向d(j)与与方向方向d(k)关于矩阵关于矩阵A共轭，共轭，则有则有( )( )( )1()0j Tj TkkkkdggdAd此式表明，沿此式表明，沿方方向向d(k)进行一维搜进行一维搜索索, ,其终点其终点X(k1)和始点和始点X

27、(k)的梯的梯度之差，与度之差，与d(k)的的共轭方向正交。共轭方向正交。共轭梯度法就是共轭梯度法就是利用这个性质做利用这个性质做到不必计算矩阵到不必计算矩阵A就能求得共轭就能求得共轭方向的。方向的。共轭梯度法的计算过程共轭梯度法的计算过程1. 由由X(0)出发，沿出发，沿方向方向d(0)g0 f(X(0)进行一维搜索，进行一维搜索，得点得点X(1)，即，即(1)(0)(0)0XXd2. 令令g1 f(X(1)，则，则g1与与d(0)( g0)正交，在该正交系中求与正交，在该正交系中求与方向方向d(0)共轭的方向共轭的方向d(1)，令，令(1)(0)10dgd 由共轭方向由共轭方向d(1)与梯

28、度关系：与梯度关系：(1)10()0Tdgg(0)1010() ()0Tgdgg(0)(0)110110000TTTTg gdgg gdg21(0)1110102(0)000,0,TTTTgg gg gdgdgg得：得：即：即：由由X(1)出发，沿出发，沿方向方向d(1) 进行一维搜索，得点进行一维搜索，得点X(2)，即，即(2)(1)(1)1XXd令令g2 f(X(2)，则，则g2与与d(1)正交，即正交，即(0)(0)1021202()0TTTgdgg gdg 由共轭方向由共轭方向d(0)与梯度关系：与梯度关系：(0)21()0Tdgg(0)(0)1012020()0TTdgggdggg1

29、2120Tg ggg3. 在在g0、g1 、 g2所构成的正交系中，求与方向所构成的正交系中，求与方向d(0)及及d(1)均共轭均共轭的方向的方向d(2)，设，设(2)21100dggg 因为要求因为要求d(2) 与与d(0) 和和d(1)均共轭，由共轭方向与梯度关系得：均共轭，由共轭方向与梯度关系得：2110010() ()0Tggggg2110021() ()0Tggggg考虑到考虑到g0、g1 、 g2相互正交，故有相互正交，故有11121001201100000TTTTTTgggggggggggg11222111002210010TTTTTTg ggggggggggg1110000TT

30、g ggg221110TTggg g故得故得22111TTggg g 22000TTgggg (2)2110022222102210 dgggggggggg 2221(0)212210 ()ggggdgg 22(1)(1)22121 ggdgdg 共轭梯度法共轭方向生成通式共轭梯度法共轭方向生成通式21(1)( )12(0,1,1)kkkkkgdgdkng 共轭梯度法的特点：共轭梯度法的特点：1. 共轭梯度法可看作是对最速下降法的修正，故收敛速度较最共轭梯度法可看作是对最速下降法的修正，故收敛速度较最速下降法快；速下降法快；2. 共轭梯度法具有二次收敛性；共轭梯度法具有二次收敛性；3. 共轭梯

31、度法程序简单，存储量小，对初始点要求不严。共轭梯度法程序简单，存储量小，对初始点要求不严。4. 共轭梯度法梯度模较小时容易上溢出。共轭梯度法梯度模较小时容易上溢出。第五节第五节 变尺度法变尺度法变尺度法变尺度法( (Variable Metric Method) )也称为拟也称为拟NewtonNewton法法( (Quasi-Newton Method) )，是求解无约束最优化问题最有效的算法之，是求解无约束最优化问题最有效的算法之一，它不需要求二阶一，它不需要求二阶Hesse矩阵，而只利用一阶导数来构造二矩阵，而只利用一阶导数来构造二阶信息的近似矩阵，从而该算法有较好的收敛性质。阶信息的近似

32、矩阵，从而该算法有较好的收敛性质。一、尺度矩阵的概念一、尺度矩阵的概念变量的尺度变换就是对其坐标进行放大或缩小处理，达到降低变量的尺度变换就是对其坐标进行放大或缩小处理，达到降低函数偏心率的目的。函数偏心率的目的。对于二次函数对于二次函数1()2TTf XX HXB XC进行尺度变换进行尺度变换XQX则函数的二次项变为则函数的二次项变为1122TTTX HXX Q HQX若矩阵若矩阵H H是正定的，则一定存在是正定的，则一定存在尺度矩阵尺度矩阵Q Q，使，使TQ HQI由此可见，二次函数的由此可见，二次函数的Hesse矩阵矩阵HH的逆阵的逆阵HH-1-1 ，可以通过尺，可以通过尺度矩阵度矩阵Q

33、Q求得。求得。11TTTTQ HQIQ HQQQ HIHQQNewtonNewton法迭代公式因此而变为：法迭代公式因此而变为：1(1)( )( )( )()()kkkkkXXH Xf X梯度法迭代公式为：梯度法迭代公式为：(1)( )( )()kkkkXXIf X记记TAQQ称为尺度矩阵称为尺度矩阵则则NewtonNewton法和梯度法的迭代公式可统一写为：法和梯度法的迭代公式可统一写为：(1)( )( )()kkkkXXA f X为了避免在牛顿法中直接计算目标函数为了避免在牛顿法中直接计算目标函数f(X)的的Hesse矩阵的逆阵矩阵的逆阵 H(X(k) -1-1 ，故构造一个尺度矩阵序列，

34、故构造一个尺度矩阵序列 Ak 来逼近来逼近 H(X(k) -1-1 , ,则则称称Ak为变为变尺度矩阵。从而可得尺度矩阵。从而可得变变尺度法的迭代公式为：尺度法的迭代公式为：二、变尺度矩阵的构造原则：二、变尺度矩阵的构造原则：1. 1. 为了保证迭代公式具有下降性质，要求为了保证迭代公式具有下降性质，要求 Ak 中的每个矩阵中的每个矩阵都是对称正定的。都是对称正定的。(1)( )( )()kkkkkXXAf X( )( )()()0kTkkf XAf X2. 2. 为了计算简便，要求为了计算简便，要求Ak具有如下的递推关系：具有如下的递推关系：1kkkAAA3. 3. 为了获得牛顿法的收敛速度

35、，要求为了获得牛顿法的收敛速度，要求Ak H(X(k) -1-1 。 Ak不可能在数值上近似不可能在数值上近似于于 H(X(k) 11，因为我们的目标是不，因为我们的目标是不计算计算HesseHesse矩阵矩阵 H(X(k) 11。那么，。那么， Ak只能在性质上近似只能在性质上近似 H(X(k) 11。因此，先研究一下。因此，先研究一下HesseHesse矩阵的逆阵矩阵的逆阵 H(X(k) 11的性质。的性质。考虑考虑 f(X)在在X(k)处的处的TaylorTaylor展开式展开式( )( )( )( )( )( )()()() ()1 () ()() 2kkTkkTkkf Xf Xf X

36、XXXXH XXX 令令X=X(k+1)，得，得求梯度求梯度得得( )( )( )()()()() kkkf Xf XH XXX (1)( )( )(1)( )()()()() kkkkkf Xf XH XXX记记(1)( )1(1)( )()() kkkkkkkkgggf Xf XXXX 则得拟牛顿条件：则得拟牛顿条件：( )1()g kkkXH X令令Ak+1满足拟牛顿条件，得：满足拟牛顿条件，得：(A ) g kkkkXA即即AggkkkkkXA 满足上述拟牛顿条件的满足上述拟牛顿条件的 Ak 有无穷多个，因此变尺度法是一有无穷多个，因此变尺度法是一族方法。族方法。三、三、DFPDFP变

37、尺度矩阵变尺度矩阵DFPDFP公式是由公式是由DavidenDaviden在在19591959年提出来的，后由年提出来的，后由FletcherFletcher和和PowellPowell在在19631963年于以简化，故此而得名的。年于以简化，故此而得名的。Ag (g )TTkkkkkkkkkXXAA设设代入拟牛顿条件代入拟牛顿条件得：得：AggkkkkkXA Aggg (g )g gTTkkkkkkkkkkkkkkkXXAAXA 11 gggkkTTkkkkkXA比较系数得：比较系数得：DFP变尺度矩阵迭代变尺度矩阵迭代公式为：公式为：1gg ggg (0,1,2,) TTkkkkkkkkT

38、TkkkkkXXAAAAXAk四、四、BFGSBFGS变尺度矩阵变尺度矩阵由于由于DFPDFP变尺度法的数值稳定性差，变尺度法的数值稳定性差，19701970年由年由BrogdenBrogden、FletcherFletcher、GoldfarbGoldfarb、ShannoShanno提出数值稳定性好的提出数值稳定性好的BFGSBFGS变变尺度法，其尺度矩阵迭代公式如下：尺度法，其尺度矩阵迭代公式如下：1gg1gggg gg (0,1,2,) kTTkkkkkkkTTkkkkTTkkkkkTTkkkkAXXAAXXAXX AXXk五、变尺度矩阵的统一表达式五、变尺度矩阵的统一表达式19701

39、970年年HuangHuang对变尺度矩阵迭代公式进行了统一处理，得出对变尺度矩阵迭代公式进行了统一处理，得出如下公式：如下公式：Ag ()TTkkkkkkkX uAv 其中其中1112gkkkkkkuXA2122gkkkkkkvXA当取当取112211 gggkkTTkkkkkXA 12210kk为为DFPDFP公公式式当取当取1221kk220k为为BFGSBFGS公式公式当取当取当取当取12220kk1121111 gkkkTkkX 为为McCormickMcCormick公式公式11210kk1222121 gkkkTkkkg A 为为PearsonPearson公式公式(1)(1)取

40、初始点取初始点X(0)，置初始矩阵，置初始矩阵A A0 0=I=I，置精度要求，置精度要求, ,置置k=0.=0.六、变尺度法的算法步骤六、变尺度法的算法步骤(2)(2)计算计算gk= f(X(k)，如果如果 f(X(k)，则停止计算，将，则停止计算，将X(k)作为无约束问题的解输出；否则计算搜索方向作为无约束问题的解输出；否则计算搜索方向(3)(3)沿沿d(k)方向进行一维搜索方向进行一维搜索, ,即求解一维问题即求解一维问题( )( )()kkkdAf X (4)(4)计算计算 gk+1= f(X(k+1), gk= gk+1- gk， Xk= X(k+1)- X(k) 修正矩阵修正矩阵

41、Ak和尺度矩阵和尺度矩阵 Ak+1 =Ak + Ak( )( )min ( )()kkkf XAf X 得：得：(1)( )( )()kkkkkXXAf X(5)(5)置置k=k+1，若，若k0 0，则由，则由DFPDFP公式公式( (或或 BFGSBFGS公式公式) )构造的构造的A Ak+1是正定对称的。是正定对称的。若一维搜索是精确的，假设已进行了若一维搜索是精确的，假设已进行了m次迭代，则次迭代，则: :定理：若用定理：若用DFPDFP算法算法( (或或BFGSBFGS算法算法) )求解正定二次函数求解正定二次函数1()2TTf XX HXB XC(1)(1)搜索方向搜索方向d(0),

42、d(1),d(m-1)是是m个非零的个非零的HH共轭方向共轭方向; ;(2)(2)对于对于j=0，2，m-1，有有 A Am Xj= = gj 且当且当m=n-1-1时，有时，有A An=H=H-1-1证明：证明：仅对仅对DFPDFP公式进行证明即可公式进行证明即可. .由于由于 XkT gk 0 0，蕴含着，蕴含着 gk 0 0，再由，再由A Ak的正定性，得到的正定性，得到 gkT A Ak gk 0 0 ，因此，因此DFPDFP公式有意义。公式有意义。对任意的对任意的xRxRn n，考察，考察122ggggg()( gg )(g )() gggTTTTTTkkkkkkkkTTkkkkkT

43、TTTkkkkkkkTTkkkkkXXX XX AA XX AXX A XXAX A XAX AXXAX由广义由广义Cauchy-SchwarzCauchy-Schwarz不等式不等式证得证得A Ak1是正定的，其是正定的，其对称性是显然的对称性是显然的. .2()( gg )(g )TTTkkkkkkX A XAX A证明：证明：由算法知，搜索方向由算法知，搜索方向d(0),d(1),d(m-1)是零的。现证明其共是零的。现证明其共轭性。用数学归纳法证明：轭性。用数学归纳法证明： 01 01iTjmjjX H XjimAXgjm 八、变尺度法的算例八、变尺度法的算例用用DFPDFP变尺度法求

44、解下述无约束优化问题变尺度法求解下述无约束优化问题第六节第六节 坐标轮换法坐标轮换法 (CyclicCoordinateMethod) 一、方法简介一、方法简介 ( )( )min ()kkf Xd( )0,.,0,1,0,.,0kTkde取搜索方向为坐标轴方向，即取搜索方向为坐标轴方向，即 沿该方向求最优点，即沿该方向求最优点，即(1)( )( )=kkkXXd每次迭代只改变设计变量每次迭代只改变设计变量X的一个分量的值，而其他分的一个分量的值，而其他分量的值保持不变，故该方法又称为降维法。量的值保持不变，故该方法又称为降维法。二、几何说明二、几何说明 现以二维函数极小化问题为例，说明坐标轮

45、换法的寻优过程。现以二维函数极小化问题为例，说明坐标轮换法的寻优过程。 1x2x(0)1X1e1e2e2e(1)1X(2)1X由由 (0)1X沿沿 1e求求 (1)1X即即 (1)(0)1111 1XXe(2)(0)11XX即即 (2)(1)1112 2XXe由由 沿沿 求求 (1)1X2e(2)1X完成第一轮搜索完成第一轮搜索 ，若，若 则停止搜索；负责进行则停止搜索；负责进行下一轮搜索。下一轮搜索。 三、算法框图三、算法框图 开始开始X1(0)= X(0),l=1输入输入X(0), ,n k=1 min ( ) =f(Xl(k-1)+ ek) Xl(k)= Xl(k-1)+ kl ek k

46、=n ? no k= k+1 yes ?( )(0)nllXX yes开始开始 Xl+1(0)= Xl(n) l=l+1 no输出输出X(*)= Xl(n)四、方法特点四、方法特点 1 1、简单、方便；、简单、方便； 2 2、对函数无连续性要求；、对函数无连续性要求； 3 3、收敛速度慢；、收敛速度慢； 4 4、可能产生伪最优。、可能产生伪最优。 第七节第七节 powellpowell法法一、共轭方向的直接生成一、共轭方向的直接生成 对于一个二次函数对于一个二次函数1()2TTf XX AXB XC( )kX(1)kd( ,0)kX( )kd(1)kX( +1,0)kX( )kd( )()kf

47、 X(1)()kf X设点设点X(k)和和点点X(k1)是从不同出发点，沿同一方向是从不同出发点，沿同一方向d (k)进行一维搜索而得的两个极小点，进行一维搜索而得的两个极小点，则方向则方向d(k)与与点点X(k)和和点点X(k1)处的梯度处的梯度有如下关系：有如下关系：( )( )()0k Tkdf X( )(1)()0k Tkdf X上面两式相减得：上面两式相减得：( )(1)( )()0k TkkdA XX记记(1)(1)( )kkkdXX则则( )(1)0k TkdAd即即d(k)与与d(k1)关于矩阵关于矩阵A共轭共轭二、基本算法二、基本算法 以二维问题为例，介绍以二维问题为例，介绍

48、Powell基本算法基本算法1 1）任取初始点）任取初始点X1(0)(0)，沿各个坐标轴方向，沿各个坐标轴方向( (基本方向基本方向) )进行一维搜索，进行一维搜索，即即 (1)(0)1111 1XXe(2)(1)1112 2XXe2 2）产生新生方向，并由）产生新生方向，并由X1(2)(2)出发，出发，沿新生方向进行一维搜索，沿新生方向进行一维搜索，即即 (3)(2)1111XXd(2)(0)111dXX3 3）用新生方向）用新生方向d1挤掉原挤掉原基本方向基本方向组中的第一个方向组中的第一个方向e1,形成新的形成新的基本基本方向组方向组e2, d1。1x2x(0)1X1e2e(1)1X(2

49、)1X1d(2)1X2e1d2d*X4 4）令）令(0)(3)21XX进行下一轮搜索。进行下一轮搜索。对于二元二次目标函数则可得其理论最优解。对于二元二次目标函数则可得其理论最优解。三、基本算法框图三、基本算法框图开始开始X1(0)= X(0),l=1输入输入X(0), ,n i=1 min ( ) =f(Xl(i-1)+ di) Xl(i)= Xl(i-1)+ il di i=n ? no i= i+1 yes ?( )(0)nllXX yes输出输出X(*)= Xl(n)开始开始基本方向取为基本方向取为di, i=2,n1 Xl+1(0)= Xl(n1) ,l=l+1 no将将n个坐标方向

50、作为初始基本方向个坐标方向作为初始基本方向di, i=1,n dn+1= Xl(n)- Xl(0) min ( ) =f(Xl(i-1)+ dn+1) Xl(n+1)= Xl(n)+ ln+1 dn+1 l=n ? yes noX1(0)= Xl(n+1), l=1四、基本算法的缺陷四、基本算法的缺陷 POWELL基本算法在迭代中逐次生成共轭方向，而共轭方向是较好基本算法在迭代中逐次生成共轭方向，而共轭方向是较好的搜索方向，所以鲍威尔法又称作方向加速法。的搜索方向，所以鲍威尔法又称作方向加速法。 上述基本算法仅具有理论意义，不要说对于一般函数，就是对于二次上述基本算法仅具有理论意义，不要说对于一般函数，就是对于二次函数，这个算法也可能失效，因为在迭代中的函数，这个算法也可能失效，因为在迭代中的n个搜索方向有时会变成线个搜索方向有时会变成线性相关而不能形成共轭方向。这时张不成性相关而不能形成共轭方向。这时张不成n维空间，可能求不到极小点，维空间，可能求不到极小点，所以上述基本算法有待改进。所以上述基本算法有待改进。 在鲍威尔基本算法中，每一轮迭代都用连结始点和终点在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的管它的“好坏好坏”，这是产生向量组线性相关的原因所在。因，