两种求解大型对称正定矩阵极大特征值问题的修正BFGS算法

摘要

本文提出两种求解高维实对称正定矩阵极大特征值问题的数值算法:基于Armijo型线性搜索的保守BFGS算法和有限记忆BFGS算法.分析算法的收敛性,并用数值试验验证算法的有效性。
　　本研究分为四个部分：第一章,介绍无约束优化问题最优解,下降方向和各种线性搜索;回顾求解无约束优化问题的牛顿法和拟牛顿法;列出求解矩阵特征值问题的相关知识以及求解高维矩阵极大特征值问题的优化模型和算法。最后,简单陈述本文的主要贡献,并列出本文所用到的一些符号。第二章,基于求解无约束优化问题,提出求解大型实对称正定矩阵极大特征值问题的保守BFGS算法.所提算法有效地避免求解大型Hessian矩阵逆的问题.同时,在一些恰当的条件下,建立该算法的全局收敛性。最后,将所提算法和EIGS(Matlab内部计算矩阵极大特征值的命令)进行对比测试.实验结果表明该算法稳定,快速,高效。第三章,提出求解非凸优化问题的有限记忆 BFGS算法,然后利用所提算法计算实对称正定矩阵的极大特征值.所提算法基于修正的拟牛顿方程并使用 Armijo型线性搜索.不假设目标函数是凸的情况下,所提算法收敛到所求问题的一个稳定点.进一步,通过数值试验求解佛罗里达大学(UF)稀疏矩阵集维数达54,929维对称正定矩阵的极大特征值,并和 EIGS进行比较.尽管该算法在理论上收敛到所求问题的一个稳定点而不是全局极小值点,但数值试验表明所提算法能够计算出极大特征值。第四章,总结全文并给出一些值得进一步研究的问题。

目录

声明

第一章 绪论

§1.1 无约束最优化问题

§1.1.1 无约束最优化问题解的最优性条件

§1.1.2 求解无约束最优化问题的一般算法

§1.1.3 线性搜索

§1.2 牛顿法

§1.3 高维矩阵极大特征值问题的部分理论及研究进展

§1.3.1 求解高维矩阵极大特征值问题的无约束最优化模型

§1.3.2 Gao-Dai-Tong 所提的 BB 型算法

§1.4 本文主要工作

§1.5 本文所用记号

第二章 求解矩阵极大特征值问题的保守BFGS算法

§2.1 引言

§2.2 算法设计

§2.3 收敛性分析

§2.4 数值试验

第三章 求解非凸最优化模型的有限记忆BFGS算法在高维矩阵极大特征值问题的应用

§3.1 引言

§3.2 算法设计

§3.3 收敛性分析

§3.4 LBFGS Ar算法在求解高维矩阵极大特征值方面的应用

§3.5 数值试验

第四章 结论

参考文献

致谢

附录 攻读硕士学位期间完成或发表的论文及参与的项目