北邮最优化 使用导数的最优化方法ppt课件

1、帅天平帅天平北京邮电大学数学系北京邮电大学数学系:tpshuaigmail,Tel:62281308, Rm:主楼主楼81410， 使用导数的最优化方法使用导数的最优化方法最优化理论与算法第十章 使用导数的最优化方法最速下降法牛顿法共轭梯度法拟牛顿法信赖域法10.1最速下降法10.110.1最速下降法最速下降法 考虑无约束问题 min f(x), xRn (10.1.1)其中 f(x)具有一阶连续偏导数。在处理这类问题时，一般策略是，希望从某一点出发，选择一个目标函数值下降最快的方向，沿此方向搜索以期尽快达到极小点，基于这一思想，Cauchy于1847年提出了最速下降法。这是无约束最优化中最简

2、单的方法。10.1最速下降法1函数f(x)在点x处沿方向d的变化率可用方向导数表示，当函数可微时有，方向导数( , )( ) (1.2)TDf x df xd求函数f(x)在点x处下降最快的方向,归结为求min ( ). 1 (1.3)Tf xdstd( )( )( ) ( )( ) (1.4)TTf xdf xdf xf xdf x ,Schwartz由不等式10.1最速下降法2由上式知.当( ) (1.5)( )f xdf x 时等号成立.故在点x处沿(1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向.注意注意:在不同的尺度下最速下降方向是不同的在不同的尺度下最速下降方向是不同的

3、.10.1最速下降法3最速下降算法最速下降算法最速下降算法的迭代公式为(1)( )( )( )( )( )( )( ) (1.6),().kkkkkkkkkxxddxxdf x 其中是从出发的搜索方向,此处取在点的最速下降方向即 ( )( )( )( )( )( )0 ()() (1.7)minkkkkkkkkxdf xdf xd是从出发沿方向进行一维搜索的步长,即满足10.1最速下降法4算法描述算法描述( )( )( )( )( )( )( )( )( )( )0(1)( )( )1,0,12,()3,()()4,:1,2min knkkkkkkkkkkkkkkkStepxEkStepdf

4、xStepdxdf xdf xdStepxxdkkStep给定初始点允许误差置计算搜索方向若停止 否则 从出发 沿进行一维搜索 求使得 令置转例1.1 用最速下降法求解下列问题2212(1)min ( )21(1,1) ,10Tf xxxx初点第一次迭代目标函数f(x)在点x处的梯度124( )2xf xx令搜索方向(1)(1)4()21642 51/10df xd (1)(1),xd1从出发 沿方向进行一维搜索 求步长即(1)(1)0(1)(1)22min ( )()14141212( )2(14 )(12 )f xdxd 令1( )16(14 )4(12 )0 5/18 (2)(1)(1)

5、11/94/9xxd在直线上的极小点第二次迭代(2)(2)(2)4/9()8/9451/109df xd (2)( )f xx在点处的最速下降方向为(2)(2),:xd从出发 沿方向进行一维搜索(2)(2)0(2)(2)22min ( )()1/94/9( 14 )/94/98/9(48 )/9216( )( 14 )(12 )8181f xdxd 令21664()( 14)(12)08181 5 /12(3)(2)(2)212127xxd 得到第三次迭代(3)(3)(3)24()127451/1027df xd (3)( )f xx在点处的最速下降方向为(3)(3),:xd从出发 沿方向进行

6、一维搜索(3)(3)0(3)(3)2222min ( )()1214242111227272784( )(14 )(12 )2727f xdxd 令2()0 5 /18此时(4)(3)(3)21/91224/9427243xxd(4)81()524310f x已经满足精度要求,得近似解124243x问题的最优解为x*=(0.0)算法的收敛性算法的收敛性( )( )1.1 ( )( )0 ,.kkTheoremf xxf xxxx设是连续可微的实函数,解集合=最速下降法产生的序列含于某个紧集,则序列的每个聚点证明证明:最速下降算法最速下降算法A可表示为合成映射可表示为合成映射A=MD其中D(x)

7、=(x,-f(x),是En En En的映射.每给定一点x,经算法D作用,得到点x和在x处的负梯度(从x出发的方向d).算法M是En En En 映射.每给定一点x及方向d=-f(x),经M作用,即一维搜索,得到一个新点,在这一点,与前面的迭代点相比,具有较小的目标函数值,根据Th1.1,当 f(x) 0时,M是闭映射.由于f(x)是连续可微实函数, 故D连续,据Th8.1.1推论2,A在x(f(x) 0)处是闭的. 其次,当x时, d=-f(x) 0,那么f(x) T d0,因而对于yA(x),有f(y)0,满足1,且对每一个成立定:(1理)2) .kxxx则牛顿法产生的序列收敛于10.2.

8、2 局部收敛性10.2 牛顿法证明:根据(10.2.2)，牛顿算法映射定义为21( )( )( )A xxf xf x (a) ,( )-xxx x 定义解集合令函数=下证(x) 是关于解集合和算法A的下降函数.2121212A( )0,( )( )()( ) ( )( )( ) ( )( )( )() (b)f xyxxf xf xxxxf xf xxf f xxf xf x xx 根据算法 的定义及的假设 有,( ).xXxxyA x令且又令10.2 牛顿法于是可得2121 2( )( )( )( )() (c)yxf xxf xf x xxk kxxxx ( )( )( ),.Akkcy

9、XxXXXxx由可知故迭代产生的序列根据定义知 是紧集,故迭代产生的序列含于紧集.此外,算法映射 在紧集 上是闭的.综上,迭代产生的序列必收敛于从而(x) 是关于解集合和算法A的下降函数10.2 牛顿法2202()(),*( *)0,Hesse( *)*,Hesse( )( )Lipschitz,L0,( )( ),k10 2 2*. nnkfCRxf xf xxxG xf xx yRG xG yL xyxx局部收敛定理 设函数它在的梯度矩阵正定.若初始点充分靠近并且矩阵满足条件 即存在使得有 则对,迭代格式(. . )有意义,且迭代点序列以二阶的收敛速度收敛到定定理理10.2 牛顿法当牛顿法

10、收敛时,有下列关系2(1)( ) kkxxc xxc,2是某个常数 因此算法至少是 阶收敛的.特别的,对于二次凸函数,用牛顿法求解,经一次迭代即达到极小点.设有二次凸函数其中A是对称正定矩阵1( )2TTf xx Axb xc10.2 牛顿法先用极值条件求解.令( )0f xAxb得最优解1xA b 下用牛顿法解,任取一初始点x(1)(2)(1)1(1)(1)1(1)1()()xxAf xxAAxbA b (2),.xx显然即一次迭代即达极小点定义:若一个算法用于求解严格二次凸函数极小值问题时从任意初始点出发,算法在有限次迭代后可到达函数的极小值点,称此算法具有二次终止性.于是牛顿法具有二次终

11、止性10.2 牛顿法注意,当初始点远离极小点时,牛顿法可能不收敛阻尼牛顿法阻尼牛顿法基本思想:增加了沿牛顿方向的一维搜索.迭代公式为(1)( )( ) kkkkxxd=( )2( )1( )()(),kkkdf xf x k其中为牛顿方向,是由一维搜索所得的步长 即满足( )( )( )( )() kkkkkf xdf xd)=min10.2 牛顿法算法(阻尼牛顿法)(0)( )2( )1( )( )( )2( )1( )( )( )( )( )( )( )1,0,1;2,(),()3,(),;, ()()4,: min() () kkkkkkkkkkkkkkStepxkStepf xf xS

12、tepf xxdf xf xStepxdf xdf xd 给定初始点允许误差置计算若停止 得解否则 令 从出发 沿方向作一维搜索 (1)( )( ) 5,:1,2kkkkxxdStepkk令置转10.2 牛顿法10.2.3 修正牛顿法例 用阻尼牛顿法求解下列问题421122min( )(1)f xxx xx(1)(1)2(1)(0,0) .,Hessian001(),()212Txf xf x 取初点在该点 函数的梯度和阵为牛顿方向(1)2(1)1(1)1()()01021220df xf x 10.2 牛顿法(1)(1),xd从出发 沿方向进行一维搜索 令(1)(1)4)=16+1f xd

13、( )= ( 1( )=0=0显然,用阻尼牛顿法不能产生新点, 而点x(1) =(0,0) T并不是问题极小点.可见从x(1)动身,用阻尼牛顿法求不出问题的极小点, 原因在于 Hessian 矩阵 2f (x(1)非正定再令10.2 牛顿法考虑 (10.2.2),记搜索方向d(k) = x- x(k) ( )2( )1( )()() (e)kkkdf xf x 阻尼牛顿法所用搜索方向是上述方程的解2( )( )( )()() (d)kkkf xdf x 此处假设逆矩阵 存在2( )1()kf x10.2 牛顿法2( )()kHessianf x解决矩阵非正定问题的基本思想2( )2( )1(

14、)( )(),( )(): () (f)kkkkkkkf xGdGf xG df x 修正构造一个对称正定矩阵在方程中用取代矩阵( )1( )() (g)kkkdGf x 再沿此方向作一维搜索2( )k?,() (h)I,.kkkkGGf xI 如何构造比如 可令其中 是单位阵是一个适当的正数10.2 牛顿法算法 修正牛顿法(0)( )( )( )2( )( )1( )( )( )1,0,0;2,(),(),;step3 3, (),0),()()4,kkkkkkkkkkkkkkkkStepxkStepgf xf xxStepGf xBGEEGdBf xStepxd 给定初始点允许误差置计算梯

15、度=若停止 得解否则转计算Hesse矩阵置矩阵其中为修正矩阵(当正定时 它取计算修正牛顿方向 从出发 沿方向作(精确或( )( )( )( )(1)( )( ): min() () ,:1,2kkkkkkkkkf xdf xdxxdkk非精确)一维搜索 令置转10.2 牛顿法000() :RD D|( )()lim()() 0.nf xkxfRxfSxD f xf xf x设在某开集上二阶连续可微,且修正牛顿法的初始点使得的水平集是紧集.若矩阵序列定理 全局收敛定满足有界分性理解特,则10.3共轭梯度法1 1 共轭方向与扩张子空间定理共轭方向与扩张子空间定理定义定义10.3.1 10.3.1

16、设设A A是是n nn n对称矩阵对称矩阵, ,若若Rn Rn 中的两个方向中的两个方向d 1 d 1 和和d2d2满足满足 (d 1)T Ad 2 =0 (d 1)T Ad 2 =0 （10.3.110.3.1）则称这两个方向关于则称这两个方向关于A A共轭共轭, ,或称它们关于或称它们关于A A正交正交. .(1)(2)( )( )( ),.,A0, ,1,2,. . (10.3.2)ki TjdddkdAdiji jkn 若是E 中 个方向,它们两两关于共轭,即 则称这组方向是A共轭,或称它们为A的k个共轭方向10.3 共轭梯度法几何意义几何意义设有二次函数1( )()() (10.3.

17、3)2Tf xxxA xx其中A是nn对称正定矩阵, x是一个定点.1()()2TxxA xxc是以x为中心的椭球面,( )()0 f xA xxA正定,故x是f(x)的极小值点.f(x)的等值面由于10.3共轭梯度法设 x(1)是在某等值面上一点,此面在点x(1)处的法向量(1)(1)()()f xA xx又设d (1)是在该等值面在点x (1)处的一切向量.d (2) = x - x (1)(1)(1)(1)(1),().()0,Tdf xdf x显然与正交即于是(1)(2)0TdAd 即等值面上一点x(1)处的切向量与由这点指向极小点的向量关于A共轭.10.3共轭梯度法x1x2(1)d(

18、2)d(1)xx10.3共轭梯度法0000011111(),(),()02(),();,()01,3(),)0(0,1,., );1 算算法法 共共轭轭方方向向法法nTkkkkkkkknkTjxRf xdf xdkf xdxxdf xkndRdGdjkkR步 初始化 给定初始点计算给定一个搜索方向0,使得0;置步线搜索 求解一维极小化问题min若或停止 否则转步3步 计算共轭方向 计算一个非零方向使得(置12 k转步(1)(2)( ),.1.,A1,.03kdddk 设A是n阶对称正定矩阵,是 个共轭的非零向量 则这个向量组线定理.性无关.10.3共轭梯度法(1)(2)( )(1)(1)(2)

19、( )(1)(2)(1)(1)(1)1( )2A,.,A,.,.,(,1).0 3 2 TTknkkkf xx Axb xcndddxRdddxxxxf xxk(扩张子空间定理)设有函数 其中 是 阶对称正定矩阵是 共轭的非零向量.以任意的为初始点,依次沿进行一维搜索 得到点列则是函数在线性流形 上的唯一极小点特别地 当定定理理. . . .(1)( )1(1)(2)( ),( ).,(,),.,. knkiiiiknxf xEx xdddd时是函数在上的唯一极小点其中是生成的子空间10.3共轭梯度法(1)(1)(1)(1)( ),( ),().kkkf xxf xxxf x证明:由于严格凸

20、要证明是函数在线性流形 上的唯一极小点只要证在点,与子空间正交.用归纳法证之,为方便,用g j表示函数f(x)在x(j)处的梯度,即( )() (10.3.6) jjgf x1,kkgk 证明对 归纳211,.kg 当由一维搜索的定义知121mn,.mmmmkgg 假设时下证10.3共轭梯度法利用上式可以将 gm+2 和d (i) 的内积写成( )( )( )(1)211 (10.3.8)ii Ti TmmmmdgdgdAd当i=m+1时,由一维搜索定义,知(1)20 (10.3.9)mTmdg当1im+1时,由归纳假设知( )10 (10.3.10)i Tmdg(1)(2)(1),.,A,m

21、ddd由于关于 共轭 则( )(1)=0 (10.3.11)i TmdAd由二次函数梯度的表达式和点x(k+1)的定义,有(2)(1)(1)21(1)11() ( 10.3.7) mmmmmmmmgAxA xdbgAd10.3共轭梯度法即由10.3.8-11,知( )20 i Tmdg21.mmg (1)(1),( ).( ),.kkxf xxf x根据上述证明是在上的极小点由于严格凸故必为此流形上的唯一极小点(1)(2)( )1(1),.,0,.nnnnnkn dddEgxE当,是的一组基 此时必有从而是函数在上的唯一极小点( )1:10.3.2 TjkThgdjk在的条件下, =0, 推论

22、10.3共轭梯度法上述定理表明,对于二次凸函数,若沿一组共轭方向(非零向量)搜索,经有限步迭代必到达极小点.2 线性共轭梯度法与二次终止性线性共轭梯度法与二次终止性Hesteness和Stiefel于1952年为解线性方程组而提出基本思想:把共轭性与最速下降法相结合,利用已知点处的梯度构造一组共轭方向,并沿着这组方向进行搜索,求出目标函数的极小点10.3共轭梯度法先讨论对于二次凸函数的共轭梯度法,考虑问题1min( ) (10.3.12)2,TTnf xx Axb xcxEAc对称正定 是常数.求解方法(1)1(1)(1)1(1)(2)(2)2(1)(2)(2)20 () (10.3.13),

23、.,0 xgdf xgdxxggddd首先, 任意给定一初始点,计算出目标函数在该点的梯度,若,则停止计算,否则,令沿搜索 得点计算在处的梯度 若则利用-和构造搜索方向,再沿搜索.10.3共轭梯度法( )( )( )(1)(1)( )( )( )( )( )( ) (103.14)()=min ()kkkkkkkkkkkkkxdxdxxdf xdf xd一般地,若已知点和搜索方向, 则从出发,沿进行搜索,得其中步长满足 ( )( )(1)T( )(1)T( )( )()( )()0 (10.3.15) ()0 kkkkkkf xdf xdAxb d记 令 即k下求 的表达式10.3共轭梯度法(

24、 )( )T( )( )T( )T( )( )T( )( ()0 ()0 (10.3.16) (10.3.17) kkkkkkkkkkkkkA xdb dgAddg ddAd(1)1( )(1)1(1)( )(1)( )1k( )0,A + (10.3.18) kkkkkkkkkkf xxggdddddgd计算在处的梯度,若,则停止计算,否则,利用-和构造下一搜索方向并使和关于 共轭,按此设想.令10.3共轭梯度法 综上分析,在第一个搜索方向取负梯度的前提下,重复使用公式3.14,3.17-3.19就能伴随计算点的增加,构造出一组搜索方向.( )( )(1)( )( )( )1k( )1( )

25、( )(1)(1),+0 (10.3.19) k Tk Tkk Tk Tkkk Tkkk TkkkdAdAddAgdAddAgdAdxd上式两端左乘并令再从出发,沿方向搜索.10.3共轭梯度法 定理10.3.3 对于正定二次函数(10.3.12),具有精确一维搜索的Fletcher-Reeves法在mn次一维搜索后即终止,并且对所有i(1 i m),下列关系成立:( )( )( )( )1,0, 1,2,.,12,0, 1,2,.,13, (0)i TjTijTiTiiiidAdjig gjig dg gd 蕴涵证明: 显然m1,下用归纳法(对i)证之. (1)11,),2,idgi 当时由于

26、从而3 成立 对时关系1)和2)成立,从而3)也成立.10.3共轭梯度法设对某个im,这些关系均成立,我们证明对于i+1也成立.先证2),(1)( )( )iiiixxd由迭代公式两端左乘A,再加上b,得( )1 (10.3.20)iiiiggAd其中 由式(10.3.17)确定,即i( )( )( )( )( )0 (10.3.21)TiTiiiii Tii Tig dg gdAddAd10.3共轭梯度法考虑到(10.3.20)和(10.3.18),那么( )1( )( )(1)1() (10.3.22)TTiijiijTi TjjijijgggAdgg gdAdd( )(1)111)TTi

27、 Tiiiggg gdAd(注:j=1时上式为( )(i 1)( )( )1,0,(10.3.21) 0 i Ti TiTiiiTiijidAddAdg ggg当时由归纳假设根据10.3共轭梯度法当ji时,根据归纳假设,式(10.3.22)等号右端各项均为010Tijgg故 再证1),运用(10.3.18)和(10.3.20),那么(1)( )( )( )11( )( )1TiTjijiijjTi TjiijdAdgdAdgggdAd 当j=i时,把(10.3.19)代入上式第一个等号的右端,立得(1)( )0iTjdAd10.3共轭梯度法当ji时,由前面已经证明的结论和归纳假设,式中第2个等

28、号右端显然为0,因而(1)( )0iTjdAd最后证3),易知(1)( )11111TiTiTiiiiiigdggdgg 综上,对i+1,上述三种关系成立(1)(2)(),Re.,.,A10.3.2mFletcherevesdddTh由上可知共轭梯度法所产生的搜索方向是 共轭的,根据,经有限步迭代必达极小点.10.3共轭梯度法注意,初始搜索方向选择最速下降方向十分重要, 如果选择别的方向作为初始方向,其余方向均按FR方法构造,则极小化正定二次函数时,这样构造出来的一组方向并不能保证共轭性.例例 考虑下列问题考虑下列问题2221231min 2xxx取初始点和初始搜索方向分别为(1)(1)111

29、 ,210 xd 10.3共轭梯度法显然, 不是目标函数在 处的最速下降方向.(1)d(1)x下面,我们用FR法构造两个搜索方向.(1)(1),:xd1从出发 沿方向进行搜索,求步长,使满足(1)(1)(1)(1)101()min()23f xdf xd得(2)(1)(1)121/32/31/3 ,1/311xxdg (2)(1)21dgd 令10.3共轭梯度法根据公式(10.3.19),有(1)21(1)(1)2/3169TTdAgdAd 因而(2)2/315/911/325/99101d (2)(2),:xd2从出发 沿方向进行搜索,求步长,使满足(1)(1)(2)(2)202()min(

30、)2126f xdf xd得 10.3共轭梯度法(3)(2)(2)239/7818/789/78,9/785/265/26xxdg(3)(2)32dgd 令根据公式(10.3.19),有(2)32(2)(2)45676TTdAgdAd10.3共轭梯度法注意注意,在在FR法中法中,初始搜索方向必须取最速下降方向初始搜索方向必须取最速下降方向因而(3)18/785/91314519/785/9536766765/261175d (1)(2)(3)(2)(1)(3)(1)(2)(3),AAAAddddddddd可以验证与关于 共轭,与关于 共轭,但与不关于 共轭,于是,不关于共轭.10.3共轭梯度法

31、可以证明,对于正定二次函数,运用FR法时不作矩阵运算就能求出因子i定理定理10.3.4 对于正定二次函数对于正定二次函数,FR法中因子法中因子 i具有具有下述表达式下述表达式212, (1,0) (10.3.24)iiiigigg证明:( )(1)( )11( )( )( )(1)( )()/()/i TTiiiiiii Tii TiiidAggA xxdAddA xx10.3共轭梯度法2111( )( )12( )() (10.3.23)()10.3.3,. Tiiiii Ti Tiiii Tiiggggdggdgdgg根据定理因此212, (10.3.24)iiigg10.3共轭梯度法FR

32、法(对二次凸函数)(1)( )k( )( )(1)1111,1.2,().0, ,. 3,. ,1,0,1(10.3.24). kkkkkkkkkxkgf xgxxdgdkk给定初点置计算若停止计算 得点；否则进行下一步构造搜索方向令其中 当时当时按公式计算10.3共轭梯度法(1)( )( )(1)4,(10.3.17).5,:1,2kkkkkkxxdknxxkk令 其中按公式计算步长若则停止计算 得点 否则 置转2212min ( )2f xxx例3.2 用FR法求解下列问题(1)(5,5)Tx初点10.3共轭梯度法令第一次迭代，目标函数f(x)在点x处的梯度122( )4xf xx(1)1

33、1020dg (1)(1),:xd1从出发 沿方向进行一维搜索 求步长10.3共轭梯度法(1)11(1)(1)10( 10, 20)205201018( 10, 20)0420TTg ddAd (2)(1)(1)151020/955205/918xxd 第2次迭代目标函数在点x 处的梯度(2)240/920/9g10.3共轭梯度法(2)(1)214100181dgd (2)(2),:xd2从出发 沿方向作一维搜索 求构造搜索方向d .先计算因子(2)1222212221(40/9)( 20/9)4102081gg 令(2)222(2)(2)420 100(2, 1)9811920204100(

34、 4,1)81041TTg ddAd 10.3共轭梯度法(3)(2)(2)220/94091005/9102081xxd (2)200 xg 0显然点处目标函数的梯度,已达极小点010.3 共轭梯度法11100 k=0,1,. (10.3.3.1), kkkkkkkkkkxxddgddg其中初始方向步长参数由一维搜索得到，的计算公式通常有如下几种：一般迭代格式11()1, (Fletcher-Reeves(FR)()kkkTkk Tggggl3用于一般函数的共轭梯度法非线性共轭梯度法10.3共轭梯度法11()2, TkkkkTkkgggg g-PRP(Polak-Ribiere-Polyar1

35、11()3, () ()TkkkkTkkgggdggk-SW(Sorenson-Wolfe21121()()4, ()()kTkkkkTkkdf xgdf xd-Daniel115, ()TkkkTkggdgk -Dixon10.3共轭梯度法(1)(1)(1)(1)(1)( )( )( )( )( )(1)( )( )1,(),0.2,(),()min() jjjjjjjjjjjxyxdf ykjf yf ydf ydyyd 给定初始点,允许误差0.置若则停止计算 否则作一维搜索求满足 令 FR共轭梯度法10.3共轭梯度法3,如果j n,转步4,否则,转5(1)(1)( )2(1)2( )4,

36、()()():1,2.jjjjjjjdf ydf yf yjj令 =-其中 置转步(1)(1)(1)(1)(1)(1)5,()1, :1,2.jnkxyyxdf yjkk 令 =,置转步可以证明,对一般函数,共轭梯度法在一定条件下是收敛的,10.3共轭梯度法FR算法中使用精确线搜索，我们有如下收敛性结果k1:( )Lipschitz.FRArmijo0,0,liminf0(Armijo()()() nkkkkkkkkTkkkfRRf xkggf xdf xcf xd 假设函数有下界，梯度是连续的在共轭梯度法中，步长参数是由精确线搜索确定的，并且满足充分下降条件(即条件).若则 条件:选择步长满

37、足 定定理理4. 1 拟牛顿条件和算法步骤10.4 拟牛顿法基本思想基本思想:牛顿法成功的关键在于利用了牛顿法成功的关键在于利用了Hesse矩阵提供的曲率矩阵提供的曲率信息，而计算信息，而计算Hesse矩阵工作量大，并且有的目标函矩阵工作量大，并且有的目标函数的数的Hesse矩阵很难计算，甚至不好求出，这就导致矩阵很难计算，甚至不好求出，这就导致仅利用目标函数一阶导数的方法仅利用目标函数一阶导数的方法,拟牛顿法就是利用拟牛顿法就是利用目标函数值目标函数值f和一阶导数和一阶导数g的信息的信息,构造出目标函数的构造出目标函数的曲率近似，而不需要明显形成曲率近似，而不需要明显形成Hesse矩阵，同时

38、具有矩阵，同时具有收敛速度快的优点。收敛速度快的优点。牛顿法的迭代公式为10.4 拟牛顿法(1)( )( ) (10.4.1)kkkkxxd=( )( )kkdx 其中是在处的牛顿方向( )2( )1( )()()102kkkdf xf x= (.4. )( )k.kx是从出发沿牛顿方向搜索的最优步长2( )12( )1(),()kkkf xHf x为构造的近似矩阵先分析与一阶导数的关系.10.4拟牛顿法(1)(1)(1)(1)2(1)(1)( )()() ()(kkTkkTkkf xf xf xxxxxf xxx)+1 )2(1)(1),( )Taylorkkkxf xx设在第 次迭代后,得

39、点将在点展开(1)2(1)(1)( )( )()()(10.4.3)kkkg xf xf xf xxx +) (1)kx于是在附近( )kxx令,则( )(1)2(1)( )(1)()()()(kkkkkf xf xf xxx +)记10.4 拟牛顿法( )(1)( )( )(1)( )(10.4.4)()() (10.4.5)kkkkkkpxxqf xf x 那么( )2(1)( )() (10.4.6)kkkqf xp 2(1)Hessian(),kf x设矩阵可逆 则( )2(1)1( )() (10.4.7)kkkpf xq ( )( )(1)12(1)11,(10.4.7)Hessi

40、an.Hessian() ,kkkkkkpqxHf xH于是 计算出和可根据估计在处的矩阵的逆令取代牛顿法中的阵的逆则满足(10.4.8)称为拟牛顿条件(方程)，也称为割线方程.怎样确定满足这个条件的H k+1 ?10.4 拟牛顿法( )( )1= (10.4.8)kkkpHq算法 拟牛顿法000011(),(0,1)(),0.2(),3(),(,) |,0, nn nkkkkkkkkkkkkkxRHRgf xkgdH gR x dx xxdxxd初始化 给定初始点,正定矩阵,;计算置平稳性检验 若则停止 否则, 计算搜索方向线搜索 沿射线进行线搜索，求出步长令10.4 拟牛顿法1114=()

41、,kk kkkkgf xHH(修正拟牛顿方程),计算对校正，得使满足拟牛顿条件，令1，转24. 2 对称秩1校正2( )1111(),., ,.kkkkf xnHnHnIHH当是 阶对称正定矩阵时 满足拟牛顿条件的矩阵也应是 阶对称矩阵于是 构造如此的近似矩阵的一般策略是:取为任意一 阶对称正定矩阵(如单位阵 ) 然后通过修正给出令Hk称为校正矩阵.确定Hk的一个方法是令10.4 拟牛顿法1 (10.4.9)kkkHHH ( )( )kk TkkHZZ(10.4.10)( ).kkZn是一常数,是 维列向量( )(10.4.8),kZ的选择应使得到满足 令( )( )( )( )( )kkkk

42、 TkkkpH qZZq(10.4.11)从而( )( )( )( )( )kkkkk TkkpH qZZq(10.4.12)利用(10.4.10),(10.4.12-13),(10.4.9)可写成10.4 拟牛顿法( )(10.4.11),k Tq等号两端左乘整理得( )T( )( )( )( )2()()kkkk TkkkqpH qZq(10.4.13)( )( )( )( )1( )T( )( )()()()kkkkTkkkkkkkkpH qpH qHHqpH q(10.4.14)-秩秩1 1校正公式校正公式利用秩1校正极小化函数f(x),在第k次迭代中,令搜索方向( )( )()kkk

43、dHf x (10.4.15)10.4 拟牛顿法( )kkd然后沿方向搜索,求步长,满足( )( )( )( )0()min()kkkkkf xdf xd 确定后继点(1)( )( )kkkkxxd(10.4.16)4.3 对称秩2校正10.4 拟牛顿法定义校正矩阵( )( )( )( )T( )T( )( )T( )kk TkkkkkkkkkkppH qqHHpqqH q(10.4.17)DFP(Davidon-Fletcher-Power)公式( )( )( )( )T1( )T( )( )T( )kk TkkkkkkkkkkkppH qqHHHpqqH q(10.4.18)那么1，DFP

44、算法算法(变尺度法变尺度法)DFP算法10.4 拟牛顿法( )(1)1(1)1( )( )( )( )( )( )( )0(1)( )(1,0,2, ()13, 4,()min()knnkkkkkkkkkkkkkkkStepxEStepHIxgf xkStepdH gStepxdf xdf xdxxd 给定初始点允许误差置计算出在处的梯度置令从出发 沿进行一维搜索 求使 令),10.4拟牛顿法(1)(1)(1)(1)(1)( )(1)( )( )1115, (),66,2;,77,(),(10.4.18),:1,3kkkkkkkkkkkkStepf xxxStepStepknxxStepSte

45、pStepgf xpxxqggHkkStep 检验是否满足收敛准则 若停止 得否则 转若则令转否则 转令由公式计算置转例1用DFP方法求解下列问题10.4拟牛顿法22121min 242xxx初始点及初始矩阵分别为(1)1210,101 xH12( ,)Txx x在点的梯度124(1)2xgx第1次迭代10.4拟牛顿法(1)x在点处的梯度142g 令搜索方向(1)1142dH g (1)(1),:xd1从出发 沿方向进行一维搜索,求步长(1)(1)0min()f xd得到1518令10.4拟牛顿法(2)(1)(1)1248/95124/918xxd 284(14/9948/929g第2次迭代1

46、0.4拟牛顿法(1)(1)110/95/9pd(1)2140/910/9qgg2H计算(1)(1)(1)(1)T1121(1)T(1)(1)T(1)1TppH q qHHHpqqH q10.4拟牛顿法10/910/95/9105/940/90110/95/910/91040/91040/910/90110/9011040/940/910/90110/9令10.4拟牛顿法10421641101214118178638138305306(2)2286384/91383058/9306112 451dH g 10.4拟牛顿法(2)(2),:xd2从出发 沿方向进行一维搜索,求步长(2)(2)0min

47、()f xd得到21736令(3)(3)(2)210 xxd 于是得最优解10.4拟牛顿法(3)30()0gf x 12( ,)(1,0)x x2 DFP算法的正定性及二次终止性算法的正定性及二次终止性10.4拟牛顿法0,1,2,., ,DFP(1,2,., )0.1 4.1iiginH in若则方法构造的矩阵为对称正定.定矩阵理证明:用归纳法 DFP方法中, H1是给定的对称正定矩阵.设Hj是对称正定矩阵,下证Hj+1也是对称正定矩阵.根据定义,对称性是显然的,下证正定性(10.4.19)10.4拟牛顿法,nyE对任意的非零向量有( )( )T( )( )1( )T( )( )T( )( )

48、2( )2( )T( )( )T( )()() TjjTjj TjjTTjjjjjjjTjTjjTjjjjjjy H qqH yy ppyy Hyy H ypqqH qy H qy py H ypqqH q12,jjHH又对称正定 故存在对称正定阵使得1122jjjHH H令10.4拟牛顿法11( )22, (10.4.20)jjjpH y qH q那么( )( )T( )TTjTjTjjjTjy H yp py H qp qqH qq q于是(10.4.19)可写为( )221( )T( )T( )22( )T( )T()()()()()() TjTTTjjjTjTTTjjy pp qy H

49、yp ppqq qy pp p q qp qpqq q(10.4.21)由Schwartz不等式,有10.4拟牛顿法2T()()()0TTTp p q qp qq q(10.4.22)考虑到一维搜索及方向的定义,(10.4.21)右端第一项的分母( )( )( )( )1()()j Tjj Tj TjjjjjTjjjjpqdggdgH gg j0,0,jjgH由于正定,故( )( )0 (10.4.23)j Tjpq于是10.4拟牛顿法( )2( )T( )()0 (10.4.24)Tjjjy ppq下证(10.4.22)和(10.4.24)不同时为0.若不然,(10.4.22)为0,则p/q

50、,即p=q(0).从而( )( )( )T( )0jTijjypy pqp( )2( )T( )()0Tjjjy ppq综上,知10.4拟牛顿法10Tjy Hy1min( )2TTf xx Axb xc 定理10.4.2 设用DFP方法求解下列问题其中A为n阶对称正定矩阵.取初点x(1) En ,令H1为n阶对称正定矩阵,则成立:( )( )( )( )1( )(1)( )( )1, 0, 1 (10.4.25)2, , 1 (10.4.26),0,.i TjiikiiiiiipApijkHAppikpxxdkn 其中证明:对k归纳. k=1时有10.4拟牛顿法(1)(1)(1)(1)T(1)

51、(1)1121(1)T(1)(1)T(1)1()TppH q qHH ApHAppqqH q(10.4.27)由于( )(1)( )( )1() (10.4.28)iiiiiiApA xxggq(1)(1)Apq(1)(1)2H App代入(10.4.27)即得即(10.4.26)成立.当k=2时,10.4拟牛顿法(1)(2)(1)222(1)(1)22222() 0TTTTpAppAH gg H Apg p 由此结果,易证k=2时(10.4.26)亦成立下设k=m时(10.4.25-26)成立,下证当k=m+1时上述关系式也成立.先证k=m+1时(10.4.25)成立. (1)(1)(2)(

52、),.,.mmppppA与中每一个关于 共轭由归纳假设,只需证:由对(10.4.26)的归纳假设,当1im时有10.4拟牛顿法( )( )1iimHApp由此有( )(1)( )111( )( )11111( )11() i Tmi TmmmTiTimmmmmTimimpAppAHggHApgpgd (10.4.29)根据Th10.3.2的推论,有( )10 (1)Timgdim由(10.4.29),知10.4拟牛顿法( )(1)0i TmpAp再证当k=m+1时(10.4.26)成立对于1im+1有(1)(1)( )21(1)T(1)(1)(1)T( )11(1)T(1)1( )mmTimm

53、mmmmimmmmmppHApHpqHqqHApqHq(10.4.30)当i=m+1时,由(10.4.28)知(1)(1)mmApq将其代入(10.4.30)得10.4拟牛顿法(1)(1)2mmmHApp当im+1时,根据关于(10.4.26)的归纳假设及当k=m+1时(10.4.25)成立,考虑到(10.4.28),则有(1)( )(1)( )(1)( )10mTimi TmTimqHApqppAp从而可得( )( )( )21iiimmHApHAppQ.E.D.推论:在Th10.4.2的条件下,必有10.4拟牛顿法11nHADFP方法中构造出来的搜索方向是一组A共轭方向DFP方法具有二次终

54、止性.22( ),0, ( )( )( ),( ).nnnTknfExEmxC xx f xf xyEm yyf x yDFPxfE若 是上的二次连续可微实函数 对任意的存在常数使得当时有 则方法产生的序列或终止于或收敛于 在上的唯一极小点3 BFGS公式及 Broyden簇10.4拟牛顿法2(1)1(),(10.4.6),kkBf x若用不含二阶导数的矩阵近似海塞矩阵则由给出另一种形式的拟牛顿条件 即( )( )1= (10.4.32)kkkqBp( )( )( )( )T1( )T( )( )T( )kk TkkkkkkkkkkkqqB ppBBBqppB p(10.4.33)可得修正公式

55、-关于矩阵B的BFGS修正公式10.4拟牛顿法1,(10.4.32)kB设可逆 则由可知( )1( )1 = kkkpBq11(10.4.8), kB于是满足拟牛顿条件故可令111= (10.4.34)kkHB,HBFGS:ShermanMorrison于是 利用公式可得关于 的公式( )( )( )( )1( )T( )( )T( )( )( )T( )( )T( )T( )(1) k Tkkk TBFGSkkkkkkkkkkkkkkkqH qppHHpqpqpqHH qppq(10.4.35)上述公式由Broyden,Fletcher,Goldfarb,Shanno(1970)给出.10.

56、4拟牛顿法定义DFPBFGS111(1) (10.4.36)kkkHHH-Broyden簇( )( )DFPBFGS2,kkkpH q和公式都有由和构成的对称秩校正 故此两公式的加权组合仍具有相同的形式显示表达式10.4拟牛顿法( )( )( )( )T( )( )T1( )T( )( )T( )( )( )T1 kk TkkkkkkkkkkkkkDFPkkkppH qqHHHvvpqqH qHvv(10.4.37)( )( )1/2( )( )T( )( )T( )( )T( )kkkkkkkkkkkkpH qvqH qpqqH q其中(10.4.38)10.4拟牛顿法1min( )2TTf

57、 xx Axb xc 定理10.4.3 设其中A为n阶对称正定矩阵. 则对于Broyden方法,成立:( )( )( )( )11, 0, 12, , 1i TjiikpApijkHAppik 线搜索方法：每次迭代时产生一搜索方向，在此方向上进行精确或不精确一维搜索，得到下一迭代点。缺点：可能由于步长过大导致算法失败，特别当问题病态时。Ch10.5 信赖域方法主要数值方法1：主要数值方法2：信赖域方法： 在每次迭代时，强制性要求新迭代点与当前迭代点之间的距离不超过某一控制量。实际上是，在以当前迭代点为中心的邻域内对一近似于原问题的简单模型求极值。优点：算法稳定性好、收敛性强。主要内容：1 无约

58、束优化信赖域法： 1.1 算法描述 1.2 收敛性2 约束优化带一个等式约束）： 2.1 逐步二次规划法SQP） 2.2 Marotos 效应 2.3 信赖域方法1 无约束优化信赖域方法问题：基本思想：给定初始迭代点，确定一个以其为中心的邻域，在此域内优化目标函数的二次逼近式，得到下一迭代点。min( )nx Rf x信赖域子问题：信赖域内原问题的逼近问题：1.1 算法描述Step1 给定初始点Step2 假设 ，则停止计算，得解；否则，解子问题得最优解Step3 计算 ，令选取下一信赖域半径使其满足Step4 产生 转step21112134,0,0,01,01, : 1n nx BRk k

59、gkdkr1,0,0kkkkkxdrxxr11341,kkkkkdrdr 1,:1kBkk定理： 是信赖域子问题的解当且仅当它是子问题的K-T点，且 是半正定矩阵。kd*()BI1.2 收敛性在一定条件下，信赖域方法具有全局收敛性。设 是 上的实函数， 是给定初始点， 是有界闭集， 和 在 上连续，用信赖域方法求得序列 ，那么 .( )f xnR1x1|( )()Sx f xf x( ),( )f xf x2( )f xS kxlim()0kkf x2 等式约束非线性优化问题(2.1)：其中：21( )()()()2TTkkkf xf xf xddf x d( )()()Tkkc xc xc xdmin( ). .( )0f xstc x 2.1 逐步二次规划(SQP)SQP方法是求解非线性规划的一般方法，是线搜索方法的一种。基本方法：求解