最优化理论-第4章-4-无约束优化-共轭梯度法-拟牛顿法.课件.ppt

1、第第4章章 无约束非线性规划无约束非线性规划哈尔滨工程大学哈尔滨工程大学 理学院理学院戴运桃戴运桃Email: 共轭方向法是介于最速下降法与牛顿法之间的一类方共轭方向法是介于最速下降法与牛顿法之间的一类方法。它仅需利用一阶导数信息，但克服了最速下降法法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存储和计算牛顿法所需要的收敛慢的缺点，又避免了存储和计算牛顿法所需要的二阶导数信息。因而简便、易实现、且十分适合大规二阶导数信息。因而简便、易实现、且十分适合大规模（稀疏）优化问题的计算，通常只经过较少的迭代模（稀疏）优化问题的计算，通常只经过较少的迭代次数就能获得满足所要求精度的

2、近似解。次数就能获得满足所要求精度的近似解。共轭方向法共轭方向法共轭梯度法共轭梯度法定义定义1 1 设A是nn对称矩阵,若Rn 中的两个方向d 1 和d2满足 (d 1)T Ad 2 =0 （1）则称这两个方向关于A共轭,或称它们关于A正交.(1)(2)( )( )( ),.,A0, ,1,2,. . (2)ki TjdddkdAdiji jkn 若是E 中 个方向,它们两两关于共轭,即 则称这组方向是A共轭共轭,或称它们为A的的k个共轭方向个共轭方向(1)(2)( ),.,A,1.kdddk 设A是n阶对称正定矩阵,是 个共轭的非零向量 则这个向理量组线性无关定0000011111(),()

3、,()02(),();,()01,3(),)0(0,1,., );1 算算法法 共共轭轭方方向向法法nTkkkkkkkknkTjxRf xdf xdkf xdxxdf xkndRdGdjkkR步 初始化 给定初始点计算给定一个搜索方向0,使得0;置步线搜索 求解一维极小化问题min若或停止 否则转步3步 计算共轭方向 计算一个非零方向使得(置12 k转步共轭梯度法共轭梯度法先讨论对于二次凸函数的共轭梯度法,考虑问题1min( ) (1)2,TTnf xx Axb xcxEAc对称正定 是常数.求解方法(1)1(1)(1)1(1)(2)(2)2(1)(2)(2)20 () (2),.,0 xgd

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

5、0 (4) (5)kkkkkkkkkkkkkA xdb dgAddg ddAd (1)1( )(1)1(1)( )(1)( )1k( )0,A + (6)kkkkkkkkkkf xxggdddddgd 计算在处的梯度,若,则停止计算,否则,利用-和构造下一搜索方向并使和关于 共轭,按此设想.令 综上分析,在第一个搜索方向取负梯度的前提下,重复使用公式3,5-7就能伴随计算点的增加,构造出一组搜索方向.( )( )(1)( )( )( )1k( )1( )( )(1)(1),+0 (7)k Tk Tkk Tk Tkkk Tkkk TkkkdAdAddAgdAddAgdAdxd 上式两端左乘并令再

6、从出发,沿方向搜索. 注意,初始搜索方向选择最速下降方向十分重要, 如果选择别的方向作为初始方向,其余方向均按FR方法构造,则极小化正定二次函数时,这样构造出来的一组方向并不能保证共轭性. 注意注意,在在FR法中法中,初始搜索方向必须取最速下降方向初始搜索方向必须取最速下降方向 定理定理 3 对于正定二次函数, 具有精确一维搜索的Fletcher-Reeves法在mn次一维搜索后即终止,并且对所有i(1 i m),下列关系成立:( )( )( )( )1,0, 1,2,.,12,0, 1,2,.,13, (0)i TjTijTiTiiiidAdjig gjig dg gd 蕴涵1min( )

7、2,TTnf xx Axb xcxEAc对称正定 是常数.证明: 显然m1,下用归纳法(对i)证之. (1)11,),2,idgi 当时由于从而3 成立 对时关系1)和2)成立,从而3)也成立.设对某个im,这些关系均成立,我们证明对于i+1也成立.先证2),(1)( )( )iiiixxd由迭代公式两端左乘A,再加上b,得( )1 (1)iiiiggAd其中i( )( )( )( )( )0 (2)TiTiiiii Tii Tig dg gdAddAd由于( )1( )( )(1)1() TTiijiijTi TjjijijgggAdgg gdAdd( )(1)111)TTi Tiiiggg

8、 gdAd(注:j=1时上式为( )(i 1)( )( )1,0,(2) 0 i Ti TiTiiiTiijidAddAdg ggg 当时由归纳假设根据故（3）( 1)( )1k + kkkdgd( )1iiiiggAd当ji时,根据归纳假设,式(3)等号右端各项均为010Tijgg故 再证1),运用(1)( )( )( )11( )( )1TiTjijiijjTi TjiijdAdgdAdgggdAd 当j=i时,把 k代入上式第一个等号的右端,立得(1)( )0iTjdAd( )1( )( )k Tkkk TkdAgdAd(1)( )1k +kkkdgd ( )1 iiiiggAd当ji时

9、,由前面已经证明的结论和归纳假设,式中第2个等号右端显然为0,因此(1)( )0iTjdAd最后证3),易知(1)( )11111TiTiTiiiiiigdggdgg 综上,对i+1,上述三种关系成立(1)(2)(),Re.,.,A2mFletcherevesdddTh由上可知共轭梯度法所产生的搜索方向是 共轭的,根据,经有限步迭代必达极小点.定理定理4 对于正定二次函数,FR法中因子i具有下述表达式212, (1,0) iiiigigg2111( )( )12( )() ()3,.Tiiiii Ti Tiiii Tiiggggdggdgdgg 根据定理因此212, iiigg证明:( )(1

10、)( )11( )( )( )(1)( )()/()/i TTiiiiiii Tii TiiidAggA xxdAddA xx(1)(1)(1)(1)(1)( )( )( )( )( )(1)( )( )1,(),0.2,(),()min() jjjjjjjjjjjxyxdf ykjf yf ydf ydyyd 给定初始点,允许误差0.置若则停止计算 否则作一维搜索求满足 令 FR共轭梯度法(对二次凸函数)共轭梯度法步骤共轭梯度法步骤3,如果j n,转步4,否则,转5(1)(1)( )2(1)2( )4,()()():1,2.jjjjjjjdf ydf yf yjj令 =-其中 置转步(1)(

11、1)(1)(1)(1)(1)5,()1, :1,2.jnkxyyxdf yjkk 令 =,置转步2212min ( )2f xxx例 用FR法求解下列问题(1)(5,5)Tx初点令第一次迭代，目标函数f(x)在点x处的梯度122( )4xf xx(1)11020dg (1)(1),:xd1从出发 沿方向进行一维搜索 求步长(1)11(1)(1)10( 10, 20)205201018( 10, 20)0420TTg ddAd (2)(1)(1)151020/955205/918xxd 第2次迭代目标函数在点x 处的梯度(2)240/920/9g(2)(1)214100181dgd (2)(2)

12、,:xd2从出发 沿方向作一维搜索 求构造搜索方向d .先计算因子(2)1222212221(40/9)( 20/9)4102081gg 令(2)222(2)(2)420 100(2, 1)9811920204100( 4,1)81041TTg ddAd (3)(2)(2)220/94091005/9102081xxd (2)200 xg 0显然点处目标函数的梯度,已达极小点011100 k=0,1,. , kkkkkkkkkkxxddgddg 其中初始方向步长参数 由一维搜索得到，的计算公式通常有如下几种：一般迭代格式11()1, (Fletcher-Reeves(FR)()kkkTkk T

13、ggggl用于一般函数的共轭梯度法非线性共轭梯度法11()2, TkkkkTkkgggg g-PRP(Polak-Ribiere-Polyar111()3, () ()TkkkkTkkgggdggk-SW(Sorenson-Wolfe21121()()4, ()()kTkkkkTkkdf xgdf xd-Daniel115, ()TkkkTkggdgk -Dixon拟牛顿法拟牛顿法牛顿法成功的关键在于利用了Hesse矩阵提供的曲率信息，而计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出，这就导致仅利用目标函数一阶导数的方法。 什么是拟牛顿法牛顿法的迭代公式为(

14、1)( )( ) kkkkxxd=( )( )kkdx 其中是在处的牛顿方向( )2( )1( )()()kkkdf xf x= ( )k.kx是从出发沿牛顿方向搜索的最优步长2( )12( )1(),()kkkf xHf x为构造的近似矩阵先分析与一阶导数的关系.(1)(1)(1)(1)2(1)(1)( )()() ()(kkTkkTkkf xf xf xxxxxf xxx)+1 )2(1)(1),( )Taylorkkkxf xx设在第 次迭代后,得点将在点展开(1)2(1)(1)( )( )()()(kkkg xf xf xf xxx +) (1)kx于是在附近( )kxx令,则( )(

15、1)2(1)( )(1)()()()(kkkkkf xf xf xxx +)记( )(1)( )( )(1)( )()() kkkkkkzxxyf xf x 则( )2(1)( )() kkkzf xy 2(1)Hesse(),kf x设矩阵可逆 则( )2(1)1( )() kkkzf xy ( )( )(1)12(1)11,Hesse.Hesse() ,kkkkkkzyxHf xH于是 计算出和可根据上式估计在处的矩阵的逆令取代牛顿法中的阵的逆则满足上式称为拟牛顿条件拟牛顿条件(方程方程)，也称为割线方程割线方程.怎样确定满足这个条件的H k+1 ?( )( )1= kkkzHy 对称秩对

16、称秩1 1校正校正2( )1111(),., ,.kkkkf xnHnHnIHH当是 阶对称正定矩阵时 满足拟牛顿条件的矩阵也应是 阶对称矩阵于是 构造如此的近似矩阵的一般策略是:取为任意一 阶对称正定矩阵(如单位阵 ) 然后通过修正给出令Hk称为校正矩阵校正矩阵.确定Hk的一个方法是令1 (1)kkkHHH( )( )kk TkkHuu(2)( ).kkun是一常数,是 维列向量( ),ku 的选择应使拟牛顿条件得到满足 令( )( )( )( )( )kkkk TkkkzH yuuy(3)从而( )( )( )( )( )kkkkk TkkuH yuuy(4)利用(2),(4-5),(1)

17、可写成( )(3),k Ty等号两端左乘整理得( )T( )( )( )( )2()()kkkk TkkkyzH yuy(5)( )( )( )( )1( )T( )( )()()()kkkkTkkkkkkkkzH yzH yHHyzH y(6)-秩秩1 1校正公式校正公式利用秩1校正极小化函数f(x),在第k次迭代中,令搜索方向( )( )()kkkdHf x (7)( )kkd然后沿方向搜索,求步长,满足( )( )( )( )0()min()kkkkkf xdf xd 确定后继点(1)( )( )kkkkxxdDFP校正是第一个拟牛顿校正，是校正是第一个拟牛顿校正，是1959年由年由Da

18、vidon提提出的，后来由出的，后来由Fletcher和和Powell(1963)解释和发展的解释和发展的.BFGS校正是目前最流行的也是最有效的拟牛顿校正，校正是目前最流行的也是最有效的拟牛顿校正，它是由它是由Broyden,Fletcher,Goldfarb和和Schanno在在1970年各年各自独立提出的拟牛顿法。自独立提出的拟牛顿法。11112kTTkkTTkkkkkkkHesseHHHauubvva bHyH yauu ybvv yz.( ),.( )( )考考虑虑目目标标函函数数的的矩矩阵阵的的逆逆近近似似序序列列设设对对称称秩秩二二校校正正为为：其其中中为为给给定定的的数数 假假

19、设设满满足足拟拟牛牛顿顿条条件件 对称秩对称秩2 2校正校正,u vu v这这里里并并不不唯唯一一确确定定，但但的的明明显显选选择择是是11TTkkkkkau ybv yuzvH y ,即即可可使使(2)(2)式式成成立立。于于是是确确定定出出1111TTTTkkkkkkkabu yz yv yy H y ,.因因此此，我我们们得得到到1TTkkkkkkkkTTkkkkkz zH y y HHHz yy H yDFP(Davidon-Fletcher-Power)公式kkGB.另另外外，考考虑虑的的近近似似序序列列设设对对称称秩秩二二校校正正为为TTkkBBauubvv1, 11,kkkka

20、bBBzy 其其中中为为给给定定的的常常数数, ,令令满满足足拟拟牛牛顿顿条条件件则则1TTkkkkkkkBzB zauu zbvv zy ,1,1TTkkkkkuy vB z au zbv z 显显然然，取取即即可可, ,从从而而111,TTTkkkkkkabu zy zz B z kB因因此此得得到到关关于于的的校校正正公公式式1TTkkkkkkkkTTkkkkky yB z z BBBy zz B z BFGS公公式式 DFP算法( )(1)1(1)1( )( )( )( )( )( )( )0(1)( )(1,0,2, ()13, 4,()min()knnkkkkkkkkkkkkkkk

21、StepxEStepHIxgf xkStepdH gStepxdf xdf xdxxd 给定初始点允许误差置计算出在处的梯度置令从出发 沿进行一维搜索 求使 令),(1)(1)(1)(1)(1)( )(1)( )( )1115, (),66,2;,77,(),(1),:1,3kkkkkkkkkkkkStepf xxxStepStepknxxStepStepStepgf xzxxyggHkkStep 检验是否满足收敛准则 若停止 得否则 转若则令转否则 转令由公式计算置转例 用DFP方法求解下列问题22121min 242xxx初始点及初始矩阵分别为(1)1210,101 xH12( ,)Txx

22、 x在点的梯度124(1)2xgx第1次迭代(1)x在点处的梯度142g 令搜索方向(1)1142dH g (1)(1),:xd1从出发 沿方向进行一维搜索,求步长(1)(1)0min()f xd得到1518令(2)(1)(1)1248/95124/918xxd 284(14/9948/929g第2次迭代(1)(1)110/95/9zd(1)2140/910/9ygg2H计算(1)(1)(1)(1)T1121(1)T(1)(1)T(1)1TzzH yyHHHzyyH y10/910/95/9105/940/90110/95/910/91040/91040/910/90110/9011040/940/910/90110/9令10421641101214118178638138305306(2)2286384/91383058/9306112 451dH g (2)(2),:xd2从出发 沿方向进行一维搜索,求步长(2)(2)0min()f xd得到21736令(3)(2)(2)210 xxd 于是得最优解(3)30()0gf x 12( ,)(1,0)x x于是得最优解(3)30()0gf x 12( ,)(1,0)x x