非精确搜索下重新开始MFR共轭梯度法的收敛速度

摘要

非线性共轭梯度法是求解最优化问题的一类有效算法,该算法的一个显著优点是其存储量小,且具有较好的收敛性,因此广泛应用于求解大规模的最优化问题.FR算法是最著名的非线性共轭梯度法之一.众所周知,采用精确线性搜索的FR共轭梯度法是全局线性收敛的,如果使用某种重新开始策略,则其收敛速度将为n步二次收敛.近来,ZHANG,ZHOU和LI结合谱梯度的思想提出了的一种修正FR算法(MFR算法),并证明了其在Armijo型线性搜索下的全局收敛性.本文研究Armijo型非精确线性搜索下MFR算法的收敛速度.
　　 第2章,我们证明了MFR算法在Armijo型线性搜索下的线性收敛性.第3章,我们证明了LI和TIAN提出的一种精确线性搜索步长估计满足Armijo型非精确线性搜索,并将其作为线搜索的初始步长来提高算法的效率.我们将重新开始策略引入到MFR算法中提出一种重新开始MFR算法(RMFR算法),我们证明在一定的条件下,这种RMFR算法具有全局收敛性,并证明采用Armijo型非精确线性搜索时,此算法具有n步二次收敛性.
　　 最后我们通过大量的数值试验检验本文提出的RMFR算法的数值效果.我们通过求解大量的大规模问题,从算法的CPU时间、函数计算次数和梯度计算次数三个方面对RMFR算法与和不采用重新开始策略的MFR算法、MPRP算法以及CG-DESCENT算法等进行比较.结果表明本文提出的RMFR算法具有明显的优势.

目录

文摘

英文文摘

论文说明:图表目录

第1章 绪论

1.1 非线性共轭梯度法及其收敛性

1.2 FR算法的研究进展

1.3 重新开始方法的研究进展

1.4 本文的主要工作及各章节安排

第2章 MFR算法及其收敛性

2.1 MFR算法及其全局收敛性

2.2 MFR算法线性收敛性

第3章 重新开始MFR算法及其收敛性

3.1 RMFR算法

3.2 RMFR算法全局收敛性

3.3 RMFR的N步二次收敛性

第4章 数值实验

结论

参考文献

致谢