重新开始的MPRP共轭梯度法及其n一步二次收敛

摘要

PRP算法是最著名的非线性共轭梯度法之一。在精确线性搜索下,该算法具有全局收敛性和线性收敛速度.如果在算法中采用重新开始的策略,则采用精确线性搜索的PRP算法具有n-步超线性或二次收敛性。最近,一种修正的PRP(MPRP)算法被提出,该算法具有充分下降性。在一定的条件下,采用某种非精确线性搜索的MPRP算法具有全局收敛性。
　　 本文研究了采用非精确线性搜索的MPRP算法的收敛速度。首先证明采用Armijo型线性搜索和Wolfe-Powell型线性搜索的MPRP算法具有线性收敛速度。进一步,我们给出一种精确线性搜索步长估计,利用此估计作为非精确线性搜索的初始步长,以提高算法的效率.为了提高算法的收敛速度,我们在MPRP算法中提出一种重新开始准则。在此基础上提出一种采用重新开始策略的MPRP算法(称为RMPRP算法)。在一定的条件下,我们证明,采用重新开始策略的MPRP算法在Armijo型和Wolfe-Powell型非精确线性搜索下具有n-步超线性或二次收敛速度。最后通过大量的数值试验检验本文提出的RMPRP算法的数值效果。首先,我们选取规模较小的问题,检验RMPRP算法的n-步二次收敛性。然后,我们运用RMPRP算法求解大量的大规模的问题,并对RMPRP算法与不采用重新开始策略的MPRP进行比较。我们从算法的CPU时间,函数的计算次数和梯度的计算次数三个方面对RMPRP算法与和不采用重新开始策略的MPRP算法进行比较。结果表明本文提出的RMPRP算法具有明显的优势。

目录

文摘

英文文摘

第1章 绪论

1.1 求解无约束最优化问题的下降算法

1.2 共轭梯度法及其收敛性

1.3 重新开始的共轭梯度法

1.4 本文的主要工作

第2章 重新开始的MPRP算法及其收敛性分析

2.1 MPRP算法的线性收敛性

2.2 重新开始的MPRP算法及其全局收敛性

2.3 重新开始的MPRP算法的n-步二次收敛性

第3章 数值试验

3.1 小规模问题的数值试验

3.2 大规模问题的数值试验

结论

参考文献

附录A

附录B

致谢