最优化理论与算法(第四章)

1第四章共轭梯度法§4.1共轭方向法共轭方向法是无约束最优化问题的一类重要算法。它一方面克服了最速下降法中，迭代点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，尤其是共轭方向法具有所谓二次收敛性质，即当将其用于二次函数时，具有有限终止性质。一、共轭方向定义4.1设G是nn对称正定矩阵，1d，2d是n维非零向量，若120TdGd（4.1）则称1d，2d是G－共轭的。类似地，设1,,mdd是nR中一组非零向量。若0TijdGd()ij（4.2）则称向量组1,,mdd是G－共轭的。注：(1)当GI时，共轭性就变为正交性，故共轭是正交概念的推广。(2)若1,,mddG－共轭，则它们必线性无关。二、共轭方向法共轭方向法就是按照一组彼此共轭方向依次搜索。模式算法：1）给出初始点0x，计算00()ggx，计算0d，使000Tdg，:0k（初始共轭方向）；2）计算k和1kx，使得0()min()kkkkkfxdfxd，令1kkkkxxd；3）计算1kd，使10TkjdGd，0,1,,jk，令:1kk，转2）。三、共轭方向法的基本定理共轭方向法最重要的性质就是：当算法用于正定二次函数时，可以在有限多次迭代后终止，得到最优解（当然要执行精确一维搜索）。2定理4.2对于正定二次函数，共轭方向法至多经过n步精确搜索终止；且对每个1ix，都是()fx在线性流形00,ijjjjxxxd中的极小点。证明：首先证明对所有的1in，都有10Tijgd，0,1,,ji（即每个迭代点处的梯度与以前的搜索方向均正交）事实上，由于目标函数是二次函数，因而有11kkkkkkggGxxGd1）当ji时，1111iTTTijjjkkjkjgdgdggd110iTTjjkkjkjgddGd2）当ji时，由精确搜索性质知：10Tijgd综上所述，有10Tijgd(0,1,,)ji。再证算法的有限终止结论。若有某个10ig（1in），则结论已知。若不然，那么由上面已证则必有：0Tnjgd(0,,1)jn。而由于01,,ndd是nR的一组基，由此可得0ng。故至多经过n次精确一维搜索即可获得最优解。下面证明定理的后半部分。由于1()2TTfxxGxbxc是正定二次函数，那么可以证明000(,,)()iijjjttfxtd是线性流形上的凸函数。事实上，000000000(,,)()1()()()2iijjjiiiTTjjjjjjjjjttfxtdxtdGxtdbxtdc3200000011()[]()22iiTTTTTjjjjjjjjtdGdxGdbdtxGxbxc由0TjjdGd(0,,)ji知0(,,)itt为0,,itt的凸函数。因而100(,,)min(,,)0iiittRjttt(0,,)ji00()0iTjjjjfxtdd(0,,)ji注意到：当jjt，(0,,)ji时，00100iijjjjijjxtdxdx。而由定理前部分证明，在1ix处有11()0TTijijfxdgd(0,,)ji，故在00(,,)(,,)iitt处，0(,,)itt取得极小，即100iiijjxxd是()fx在线性流形上的极小点。§4.2共轭梯度法上节一般地讨论了共轭方向法，在那里n个共轭方向是预先给定的，而如何获得这些共轭方向并为提及。本节讨论一种重要的共轭方向法——共轭梯度法。这种方法在迭代过程中通过对负梯度方向进行适当校正获得共轭方向，故而称之为共轭梯度法。一、共轭梯度的构造（算法设计针对凸二次函数）设1()2TTfxxGxbxc其中G为nn正定矩阵，则()gxGxb。对二次函数总有11kkkkkkggGxxGd41）设0x为初始点。首先取00dg，令1000xxd（0为精确步长因子）则有：100Tgd（精确一维搜索性质）。2）令1100dgd，适当选择0，使100TdGd，得101101100001000()()TTTTTTgGdgggggdGddgggg（从而得到1d）由前一节共轭方向法的基本定理有：210Tgd，200Tgd，再由0d与1d的构造，还可得：210Tgg，200Tgg3）再令220011dgdd，适当选择0，1，使得20TidGd（0,1i），由此得：00，22122112111()()TTTTgggggdgggg4）一般地，在第k次迭代中，令10kkkiiidgd适当选取i，使0TkidGd（0,,1ik），可得到11()()TTkikiiiTTiiiiigGdgggdGddgg（0,,1ik）（4.3）同样由前一节共轭方向的基本定理有：0Tkigd（0,,1ik），（4.4）再由ig与id的关系得：0Tkigg（0,,1ik）（4.5）将（4.4）与（4.5）代入（4.3）得：当0,,2ik时，0i，而111111()()TTkkkkkkTTkkkkkgggggdgggg。共轭梯度法的迭代公式为：1kkkkxxd（kd为共轭方向，k为最佳步长因子）对二次函数5TkkkTkkgddGd；而对非二次函数，则采用精确一维搜索得到k。共轭方向的修正公式为：11kkkkdgd（4.6）其中，k由下面诸式之一计算：1）111()()TkkkkTkkkgggdgg（Crowder-Wolfe公式）（4.7）2)11TkkkTkkgggg（Fletcher-Reeves公式）（4.8）3）11()TkkkkTkkggggg（Polak-Ribiere-Polyak公式）（4.9）4）11TkkkTkkggdg（Dixon公式）（4.10）注：对二次函数而言，上述四个公式都是等价的。而且求得的搜索方向均为共轭方向；若对非二次函数，则将导出互不相同的算法，而且据此求出的搜索方向不再保证是共轭的。（事实上，此时不存在一个常值正定矩阵G，共轭的提法都已无意义）。二、共轭梯度法的性质定理4.3对于正定二次函数，采用基于精确一维搜索的共轭梯度算法，必定经过mn步迭代后终止。且对1im，下列关系式成立：1）0TijdGd（0,1,,1ji）（4.11）2）0Tijgg（0,1,,1ji）（4.12）3）TTiiiidggg（4.13）4）01000[,,,][,,,]iiggggGgGg（4.14）5）01000[,,,][,,,]iidddgGgGg（4.15）证明：先用归纳法证明（4.11）～（4.13）。对于1i，容易验证（4.11），（4.12），4.13）成立。现假设这些关系式对某个im成立，下面证明对于1i，这些关系式仍然成立。事实上，对于二6次函数，显然有11()iiiiiiiggGxxgGd（4.16）对上式左乘Tid，并注意到i是精确步长因子，得0TTiiiiiTTiiiigdggdGddGd（4.17）利用（4.16），（4.17），得111()TTTTTijijiijijiijjjggggdGgggdGdd（4.18）当ji时，（4.18）成为10TTTTiiijiiiiTiiggggggdGddGd当ji时，由归纳法假设可知111()0TTTijijiijjjggggdGdd于是（4.12）得证。再由共轭梯度法的迭代公式及（4.17），有1111jjTTTTTijijiijiiijjggdGdgGddGdgdGd（4.19）当ji时，由（4.12），（4.17）及（4.8），（4.19）成为111110TTTTTiiiiiiiiiiTTiiiiggggdGddGddGdgggg当ji时，直接由归纳法假设知（4.19）为零，于是（4.11）得证。又由于1111111TTTTiiiiiiiiidgggdggg于是（4.13）得证。下面利用归纳法证明（4.14）与（4.15）。当1i时，由00dg及1000000ggGdgGg，容易看出：0100[,][,]gggGg再由00dg及1100100dgdgg，易见：010100[,][,][,]ddgggGg。故当1i时，（4.14）与（4.15）成立。假定（4.14）与（4.15）对i成立。下证结论对1i也成立。7由于1iiiiggGd，而从归纳法假设知000,[,,,]iiigdgGgGg故有11000[,,,]iiggGgGg还可证明：100001[,,,][,,,]iiiggGgGgddd否则由101[,,,]iigddd及10Tijgd(0,,)ji（共轭方向法基本定理）则必有10ig（与算法结束前，不会出现10ig矛盾）因此1011000[,,,][,,,]iiggggGgGg再由11iiiidgd立即有：101011000[,,][,,,][,,,]iiiddggggGgGg。定理证毕。注：1）上面定理中出现的这些生成子空间通称为Krylov子空间；2）在共轭梯度法中，11kkkkdgd，若采用精确一维搜索，则k不论采用哪种公式计算，都有11111110TTTTkkkkkkkkkgdgggdgg，即1kd总是下降方向，若不采用精确一维搜索，则就不一定了；3）对Dixon公式，使用不精确搜索准则1TTkkkkgdgd，(0,1)，能保证搜索方向总是下降的。事实上，由1111TkkkkkTkkggdgddg有111111TTTkkkkkkTkkgdgdgggd，而1111TTTTTkkkkkkkkkkTkkgdgdgdgdgdgd（由0Tkkgd），由此即得110Tkkgd故1kd为下降方向；4）Fletcher－Reeves公式最为简洁，使用得最多；85）共轭梯度算法用于非二次函数时，没有有限终止性质，一般经过n次搜索后，就取一次负梯度方向，称再开始。Polak-Ribiere-Polyak具有自动再开始的特点，事实上，当算法改进不大时，会出现1kkgg，这时用Polak-Ribiere-Polyak公式计算出的0k，从而导致11kkdg。§4.3共轭梯度法的收敛性由前面的讨论已经知道，当共轭梯度算法用于正定二次函数时必定有限终止。本节研究将其用于一般非二次函数时的收敛性问题。一、共轭梯度法的总体收敛性定理4.4设水平集0()()Lxfxfx有界，f是nR上具有一阶连续偏导数的凸函数。{}kx是由Fletcher-Reeves共轭梯度算法产生的迭代点列。则1）{()}kfx为严格单调下降序列，且lim()kkfx存在。2）{}kx的任意聚点都是最优解，于是：lim()min()nkkxRfxfx。证明：在算法迭代过程中，由于每隔n次采用一次再开始措施。因而搜索方向要么是共轭梯度方向，要么是最速下降方向。但不管是哪种情形都有：20Tkkkgdg（采用严格一维搜索）因而{()}kfx单调下降，又由L有界，故{()}kfx也有下界，因此lim()kkfx存在，记为*f。又由{()}kfx单调下降