3-3 共轭梯度法

第3-3节共轭梯度法（1）共轭方向法概述（2）共轭梯度法（3）共轭梯度法的收敛性（4）重新开始的共轭梯度法（5）比勒三次重新开始共轭梯度法第3-3-1节共轭方向法概述共轭方向法是介于最速下降法与牛顿法之间的一类方法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存储和计算牛顿法所需要的二阶导数信息。因而简便、易实现、且十分适合大规模（稀疏）优化问题的计算，通常只经过较少的迭代次数就能获得满足所要求精度的近似解。共轭方向法是从研究二次函数的极小化产生的，但是它可以推广到处理非二次函数的极小化问题。最典型的共轭方向法就是本节研究的共轭梯度法。下一节介绍的拟牛顿法也是共轭方向法。第3-3-1节共轭方向法概述[例3.24]设，，其中A为正定矩阵。能否从任意初始点出发，经过至多两部迭代达到其极限点（最优解）？[定义3.25]（共轭方向）设A为n阶对称正定矩阵，是n维非零向量，如果，则称向量和是关于A共轭的。类似地，设是m个n维向量，如果，则称是关于A共轭的向量组。12:RRf21,dd021AddT1d2dmddd,,,21),,2,1,,(0mjijiAddjTimddd,,,21第3-3-1节共轭方向法概述[定理3.26]设A为n阶对称正定矩阵，则关于A共轭的非零向量是线性无关的。[定理3.27]（共轭方向法基本定理）设二次函数的极小化问题为，其中A是n阶对称正定矩阵，是任意一组关于A共轭的非零向量，若从任意初始点出发，依次沿方向进行精确线性搜索，则至多经过n次迭代就可达到问题的最优解。mddd,,,21cxbAxxxfTT21)(min110,,,nddd0x110,,,nddd*x第3-3-1节共轭方向法概述[定理3.28]设向量线性无关，则由这组向量可以构造m个关于A共轭的向量。110,,,mppp110,,,mddd第3-3-2节共轭梯度法共轭梯度法的迭代公式为：kkkkkkkkdxfddxxxfd)()(11100第3-3-2节共轭梯度法FR，1964：PRP，1969：CW，1972：Dixon，1972：)()()()(11kTkkTkkxfxfxfxf)()()]()([)(11kTkkkTkkxfxfxfxfxf)]()([)]()([)(111kkTkkkTkkxfxfdxfxfxf)()()(11kTkkTkkxfdxfxf第3-3-2节共轭梯度法[算法3.29]（求解二次函数的共轭梯度法）（1）给定任意初始点及精度；（2）计算。若，令，转步（7）；否则，，转步（3）；（3）进行精确线性搜索得到。（4）令；nRx00)(0xf)(0xf0*xx)(,0kkxfdkkkkkkdxx1第3-3-2节共轭梯度法（5）计算。若，令，转步（7）；否则，转步（6）；（6）计算（也可以采用上述公式之一），，转（3）；（7）输出，结束。)(1kxf)(1kxf1*kxx)()()()(11kTkkTkkxfxfxfxf1,)(1kkdxfdkkkk*x第3-3-2节共轭梯度法[例3.30]用共轭梯度法求解取初始点为1212221222123)(minxxxxxxf420x第3-3-2节共轭梯度法[定理3.31]设目标函数为正定二次函数则采用精确线性搜索的共轭梯度法经步终止，且对所有成立下列关系式：cxbaxxxfTT21)(nmmi01,,1,0,0ijAddjTi1,,1,0,0ijAddjTi1,,1,0,0)()(11ijxfxfjTi)()()(iTiiTixfxfxfd第3-3-3节共轭梯度法的收敛性[定理3.32]（FR方法总体收敛性定理）如果在有界水平集上，连续可微且有下界，那么采用和精确线性搜索的Flecher-Reeves共轭梯度法产生的迭代序列至少有一个聚点是的平稳点。)()(|)(00xfxfRxxLnRRfn:)()()()(11kTkkTkkxfxfxfxfkx)(xf第3-3-3节共轭梯度法的收敛性[定理3.33]如果在Fletcher-Reeves算法中，步长由不精确线性搜索的沃尔夫准则其中，确定，那么Fletcher-Reeves算法具有下降性质。kkTkkkkkkdxfdxfxf)()()(kTkkTkkkdxfddxf)()(2100)(kTkdxf第3-3-3节共轭梯度法的收敛性[定理3.34]设二阶连续可微，水平集有界，步长由不精确线性搜索的沃尔夫准则其中，确定，那么Fletcher-Reeves算法产生的迭代序列全局收敛，即有：)(xf)()(|)(00xfxfRxxLnkkTkkkkkkdxfdxfxf)()()(kTkkTkkkdxfddxf)()(2100)(inflimkkxf第3-3-3节共轭梯度法的收敛性[定理3.35]设二阶连续可微，水平集有界，且存在常数，使得对任意的，成立则采用精确线性搜索的PRP共轭梯度法产生的迭代点列收敛于的唯一极小点。)(xf)()(|)(00xfxfRxxLn0m)(0xLxnTRuuxfuum,)(22kx)(xf*x第3-3-4节重新开始的共轭梯度法重新开始的共轭梯度法的基本思路：将共轭梯度法应用于非二次函数的极小化时，每迭代n次就周期地选取负梯度方向作为搜索方向，所以这种算法称作重新开始的共轭梯度法，即令,2,1),(cxfdcncn第3-3-4节重新开始的共轭梯度法鲍威尔：对非二次函数，在计算中可能出现与几乎正交的情况，此时FR：PRP：kd)(kxf)()(,11kkkkxfxfxx1kkkkdxfd)(110k)(11kkxfd第3-3-4节重新开始的共轭梯度法重新开始的共轭梯度法允许采用近似线性搜索过程，只是在采用近似线性搜索时，要采取一定的检查措施，以保证所得到的搜索方向是下降方向。但是，如果频繁地利用负梯度方向作为搜索方向，将大大降低共轭梯度法的效率，而使算法的性态变得更象最速下降法。采取检查措施可以克服这个困难。11)()()()(kTkkkTkkTkdxfxfxfdxf第3-3-4节重新开始的共轭梯度法[算法3.36]（1）给出初始点及精度，令。（2）如果，则；否则，计算，令（3）精确线性搜索求得；（4）令；（5）若，则取，停止迭代；否则，若，则，转（2）；否则，，转（2）。0x00k0k)(kkxfd211)()()]()([kkTkkxfxfxfxf1)(kkkdxfdkkkkkdxx1)(1kxf1*kxxnk10,10kxxk1kk第3-3-4节重新开始的共轭梯度法[算法3.36]（采用精确线性搜索的n步重新开始的PRP共轭梯度法）（1）给出初始点及精度，令。（2）计算。若，输出，停止迭代；否则，转步（3）；（3）如果，则；否则，计算令；（4）精确线性搜索求得；（5）令。若，则。转（2）。0x00k)(kxf)(kxfkxx*0k)(kkxfd211)()()]()([kkTkkxfxfxfxf1)(kkkdxfdk1,1kkdxxkkkknk0,0kxxk第3-3-4节重新开始的共轭梯度法[定理3.37]设三阶连续可微，水平集有界，并且对任意的，存在常数，使得：则每r步重新开始的PRP或FR共轭梯度法产生的迭代点列n步二阶收敛，即存在常数，使得。)(xf)()(|)(00xfxfRxxLn)(0xLxMm0nTRuuMuxfuum,)(222kx0ccxxxxkrnkrk2**suplim第3-5-5节比勒（Beale）三次重新开始共轭梯度法（1）一些大规模优化问题，即使对于正定二次函数，由于舍入误差积累，迭代若干次（例如r次，或）后，二次函数就与目标函数不甚接近了，所产生的方向也可能不是共轭方向，这时就必须采用重新开始的策略。（2）由于一般无需迭代n次就能接近最优解，故不必在迭代n步后重新开始，常常频繁地重新开始。（3）负梯度方向不一定是最合适的搜索方向。特别是频繁地采用负梯度方向作为重新开始的方向会降低算法的效率。而继续沿着原来的方向搜索往往效果较好。nrnr第3-5-5节比勒（Beale）三次重新开始共轭梯度法Beale（1972）提出：当需要在点重新开始时，继续以算法产生的方向作为重新开始的第一次搜索方向，并要求构造的方向序列满足共轭性质。判别重新开始的条件：tx0)()()(21kkTkxfxfxf1)()(2kkTkxfdxf第3-5-5节比勒（Beale）三次重新开始共轭梯度法比勒（Beale）三次重新开始共轭梯度法tkkkkkddxfd111)()]()([)]()([)(1111kkTkkkTkkxfxfdxfxfxf1,)]()([)]()([)(;1,0111tkxfxfdxfxfxftkttTtttTkk第3-5-5节比勒（Beale）三次重新开始共轭梯度法[算法3.38]（1）给定初始点及精度，令，计算。若，则取，停止迭代；否则令；（2）采用精确线性搜索求步长；（3）令；（4）计算。若，则取，停止迭代；否则转（5）；0x00,0tk)(0xf)(0xf0*xx)(00xfdk1,1kkdxxkkkk)(kxf)(kxfkxx*第3-5-5节比勒（Beale）三次重新开始共轭梯度法（5）检验下列条件是否成立：若两个条件均不成立，则转（7）；否则，转（6）。（6）令。（7）令，21)(2.0)()(kkkxfxfxf1ntk1kttkkkkkddxfd111)()]()([)]()([)(1111kkTkkkTkkxfxfdxfxfxf第3-5-5节比勒（Beale）三次重新开始共轭梯度法（8）若，则转（9）；否则，转（2）。（9）检验不等式是否成立；若成立，则转（2），否则转（6）。1,)]()([)]()([)(;1,0111tkxfxfdxfxfxftkttTtttTkk1tk22)(8.0)()(2.1kkTkkxfxfdxf第3-5-5节比勒（Beale）三次重新开始共轭梯度法[算法3.38]（比勒（Beale）三次重新开始共轭梯度法）（1）给定初始点及精度，迭代次数n。（2）计算，若，则取，停止迭代；否则转（3）；（3）令；（4）采用精确线性搜索求步长；（5）令；0x0)(0xf)(0xf0*xx)(,0,0kkxfdtkk1,1kkdxxkkkk第3-5-5节比勒（Beale）三次重新开始共轭梯度法（6）计算。若，则取，停止迭代；否则转（7）；（7）检验条件是否成立。若成立，转（9），若不成立，转（8）；（8）检验条件是否成立。若成立，转（9），否则转（11）；（9）令；（10）计算令，转（13）；)(k