第四章共轭梯度法

第四章共轭梯度法数学系罗芳§4.1共轭方向法共轭方向法是无约束最优化问题的一类重要算法。它一方面克服了最速下降法中，迭代点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，尤其是共轭方向法具有所谓二次收敛性质，即当将其用于二次函数时，具有有限终止性质。一、共轭方向Gnn1d2dn120TdGd1d2dG1,,mddnR0TijdGd()ij1,,mddG定义4.1设是对称正定矩阵，，是，是－共轭的。类似地，设是是－共轭的。维非零向量，若（4.1）则称中一组非零向量。若（4.2）则称向量组GI1,,mddG注：(1)当时，共轭性就变为正交性，故共轭是正交概念的推广。(2)若－共轭，则它们必线性无关。二、共轭方向法共轭方向法就是按照一组彼此共轭方向依次搜索。模式算法：0x00()ggx0d000Tdg:0kk1kx0()min()kkkkkfxdfxd1kkkkxxd1kd10TkjdGd0,1,,jk:1kk1）给出初始点，计算，计算，使，2）计算和，使得，令3）计算，使，，令，转2）。（初始共轭方向）；三、共轭方向法的基本定理共轭方向法最重要的性质就是：当算法用于正定二次函数时，可以在有限多次迭代后终止，得到最优解（当然要执行精确一维搜索）。n1ix()fx00,ijjjjxxxd定理4.2对于正定二次函数，共轭方向法至多经过步精确搜索终止；且对每个，都是在线性流形中的极小点。§4.2共轭梯度法上节一般地讨论了共轭方向法，在那里n而如何获得这些共轭方向并为提及。本节讨论一种重要的共轭方向法——共轭梯度法。这种方法在迭代过程中通过对负梯度方向进行适当校正获得共轭方向，故而称之为共轭梯度法。个共轭方向是预先给定的，一、共轭梯度的构造（算法设计针对凸二次函数）设1()2TTfxxGxbxcGnn其中为正定矩阵，则()gxGxb对二次函数总有11kkkkkkggGxxGd100Tgd0x00dg1000xxd01）设为初始点。首先取，令（（精确一维搜索性质）。则有：为精确步长因子）1100dgd0100TdGd2）令，适当选择，使，得101101100001000()()TTTTTTgGdgggggdGddgggg（从而得到1d），220011dgdd0120TidGd0,1i0022122112111()()TTTTgggggdgggg3）再令，适当选择，，使得（由此得：），k10kkkiiidgdi0TkidGd0,,1ik11()()TTkikiiiTTiiiiigGdgggdGddgg0,,1ik4）一般地，在第次迭代中，令适当选取，使（），（）（4.3）可得到同样由前一节共轭方向的基本定理有：0Tkigd0,,1ik（），（4.4）igid再由与的关系得：0Tkigg0,,1ik（）(4.5)0,,2ik0i111111()()TTkkkkkkTTkkkkkgggggdgggg将（4.4）与（4.5）代入（4.3）得：当时，而共轭梯度法的迭代公式为：1kkkkxxdkdk（为共轭方向，为最佳步长因子）对二次函数TkkkTkkgddGd而对非二次函数，则采用精确一维搜索得到k。11kkkkdgdk111()()TkkkkTkkkgggdgg11TkkkTkkgggg11()TkkkkTkkggggg11TkkkTkkggdg共轭方向的修正公式为：（4.6）由下面诸式之一计算：（Crowder-Wolfe公式）（4.7）（Fletcher-Reeves公式）（4.8）（Polak-Ribiere-Polyak公式）（4.9）（Dixon公式）（4.10）其中，1）2)3）4）注：对二次函数而言，上述四个公式都是等价的。而且求得的搜索方向均为共轭方向；若对非二次函数，则将导出互不相同的算法，而且据此求出的搜索方向不再保证是共轭的。（事实上，此时不存在一个常值正定矩阵，共轭的提法都已无意义）。G二、共轭梯度法的性质01000[,,,][,,,]iiggggGgGg01000[,,,][,,,]iidddgGgGg定理4.3对于正定二次函数，采用基于精确一维搜索的共轭梯度算法，必定经过4）5）（4.15）TTiiiidgggmn1im0TijdGd0,1,,1ji步迭代后终止。且对，下列关系式成立：（）（4.11）1）0Tijgg0,1,,1ji（）（4.12）2）3）（4.13）（4.14）§4.3共轭梯度法的收敛性由前面的讨论已经知道，当共轭梯度算法用于正定二次函数时必定有限终止。本节研究将其用于一般非二次函数时的收敛性问题。一、共轭梯度法的总体收敛性0()()LxfxfxfnR{}kx{()}kfxlim()kkfx{}kxlim()min()nkkxRfxfx定理4.4设水平集有界，是偏导数的凸函数。是由Fletcher-Reeves共轭梯度算法产生的迭代点列。则为严格单调下降序列，且存在。的任意聚点都是最优解，于是：。上具有一阶连续1）2）注：由这个定理的证明过程易见：上述收敛定理对其它几种共轭梯度算法也是成立的。0()()Lxfxfx()fx定理4.5假设水平集是有界集，{}kx则采用精确一维搜索的Crowder-Wolfe再开始共轭梯度法产生的点列至少存在一个聚点是驻点。在其上Lipschitz连续，()fx0()()Lxfxfx0mxL22()TmyyfxynyR{}kx()fx定理4.6（Polak-Ribbiere-Polyak算法的总体收敛性）设二阶连续可微，水平集有界。又设存在常数，使得对收敛于的唯一极小点。，有：则采用精确一维搜索的P-R-P共轭梯度算法产生的点列。上述总体收敛性定理均建立在精确一维搜索基础之上。Al-Baali（1985）研究了采用不精确一维搜索的Fletcher-Reeves共轭梯度法。发现若采用Wolfe-Powell不精确一维搜索准则，也有总体收敛性。k0Tkkgd定理4.7若共轭梯度算法具体下降性质：由不精确一维搜索的Wolfe-Powell准则产生，那么Fletcher-Reeves()fx0()()nLxRfxfxkliminf0kkg定理4.8设二阶连续可微，水平集有界。设.（1）由Wolfe-Powell准则确定，那么Fletcher-Reeves共轭梯度算法产生的点列总体收敛，即有定理4.9设函数f(x)连续可微,▽f(x)满足Lipschitz条件yxMyfxf)()(若在共轭梯度法中步长由Wolfe-Powell准则确定,且下降方向和kkd)(xf之间的夹角满足，则对于共轭梯度法产生的点列，或者k2kkx存在某个，使得，或者或者k0)(xf)(kxf0)(xf共轭梯度法的收敛速度前面已经讲过，共轭梯度法具有二次终止性，即对于二次函数，采用精确一维搜索的共轭梯度法在n次迭代后终止。对于二次目标函数，共轭梯度法的收敛速度至少是线性的。由于采用精确线性搜索的共轭梯度法至多迭代n步可求得二次凸函数的极小点，相当于牛顿法执行一步。因此，若将n次迭代看作一次大的迭代，则共轭梯度法就应该与牛顿法有类似的收敛速度。下面的定理表明：在适当的条件下，共轭梯度法具有n步二阶收敛性。假设条件1：，即三次连续可微。假设条件2：设存在常数，使得),(3RRCfnRRfn:0,0Mm和,,,)(222LxRyyMyxfyymnT其中是有界水平集。)()(0xfxfRxLn定理4.9假定假设条件1和2满足，那么，每r步再开始的PRP和FR共轭梯度法产生的迭代点列n步二阶收敛，即存在常数c0，使得kx)2(sup**limcxxxxkrnkrk这个定理的证明用以下两个定理。定理4.10设定理4.7的条件满足，并设在每一个点定义二次函数为krxkrfˆ))(()(21)()()()(ˆ2krkrTkrkrTkrkrkrxxxfxxxxxfxfxf设表示应用到上的共轭梯度法，并且令krfˆkrfˆkrkrkrgdd0又设)(,),(,1ˆ0ˆ10nkrfnkrkrfkrkrkxxxxxxkrkr那么，如果对于,1)(,1,0kji)(2*xxOddkrikrikrikrikr成立，其中是小于等于n的整数，满足)(kj),ˆ(),ˆ(1)()(krkjkrkrkjkrfxxfxx)ˆ(krfx表示函数的极小点，则再开始PRP和FR共轭梯度法产生的点列满足（2）krfˆ引理4.3.9)3(,ˆ2kkTkkkdBdg其中102)4(.)(ˆddxfBkkkk引理4.3.10)5(.)1(1kkdmMg引理4.3.11对于PRP公式，)7(.)1()6(,ˆˆ1mMmMdBddBgkkkTkkkTkk对于FR公式，)7(.)1()6(,ˆˆ)(121mMdBddBggkkkTkkkTkkk引理4.3.12)9(,)1()8(21*kkkkdmMdxxMg引理4.3.13)11().()(ˆ)10(),()()(222kkikkkikdOxfBdOxfxf引理4.3.14对于PRP公式，有)12().()()(23112111kikikikikikikdOggOddOdd对于FR公式，有)13().()()()(243112111kikikikikikikikikdOggOggOddOdd引理4.3.15我们有)14(.)(211ikikikikkikikikikddMdOgggg引理4.3.16我们有)15().()()(23221kikikikikikikikikdOddOggOdd定理4.3.17设定理4.8的条件满足，那么,1)(,,1,0)18(),(,1)(,,1,0)17(),()16(,02*2kjixxOddkjidOdddkrikrikrikrikrkrikrikrikrikrk其中，对于所有k和.,krkrgdnr综合定理4.3.8和定理4.3.17，我们便可得到再开始共轭梯度法的n步二阶收敛定理4.3.7