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

发布时间：2018-08-23 21:42

【摘要】：本文提出两种求解高维实对称正定矩阵极大特征值问题的数值算法:基于Armijo型线性搜索的保守BFGS算法和有限记忆BFGS算法.分析算法的收敛性,并用数值试验验证算法的有效性.第一章,简单介绍无约束优化问题最优解,下降方向和各种线性搜索;回顾求解无约束优化问题的牛顿法和拟牛顿法;列出求解矩阵特征值问题的相关知识以及求解高维矩阵极大特征值问题的优化模型和算法;最后,简单陈述本文的主要贡献,并列出本文所用到的一些符号.第二章,基于求解无约束优化问题,提出求解大型实对称正定矩阵极大特征值问题的保守BFGS算法.所提算法有效地避免求解大型Hessian矩阵逆的问题.同时,在一些恰当的条件下,建立该算法的全局收敛性.最后,将所提算法和EIGS(Matlab内部计算矩阵极大特征值的命令)进行对比测试.实验结果表明该算法稳定,快速,高效.第三章,提出求解非凸优化问题的有限记忆BFGS算法,然后利用所提算法计算实对称正定矩阵的极大特征值.所提算法基于修正的拟牛顿方程并使用Armijo型线性搜索.不假设目标函数是凸的情况下,所提算法收敛到所求问题的一个稳定点.进一步,通过数值试验求解佛罗里达大学(UF)稀疏矩阵集维数达54,929维对称正定矩阵的极大特征值,并和EIGS进行比较.尽管该算法在理论上收敛到所求问题的一个稳定点而不是全局极小值点,但数值试验表明所提算法能够计算出极大特征值.第四章,总结全文并给出一些值得进一步研究的问题.
[Abstract]:This paper presents two numerical algorithms for solving the maximum eigenvalue problem of high dimensional real symmetric positive definite matrices: conservative BFGS algorithm based on Armijo type linear search and finite memory BFGS algorithm. The convergence of the algorithm is analyzed and the validity of the algorithm is verified by numerical experiments. In the first chapter, the optimal solution, descent direction and various linear searches of unconstrained optimization problems are introduced briefly, and the Newton method and quasi-Newton method for solving unconstrained optimization problems are reviewed. The relevant knowledge of solving matrix eigenvalue problem and the optimization model and algorithm for solving high dimensional matrix maximum eigenvalue problem are listed. Finally, the main contributions of this paper are briefly stated, and some symbols used in this paper are listed. In chapter 2, based on the unconstrained optimization problem, a conservative BFGS algorithm is proposed to solve the maximal eigenvalue problem of large real symmetric positive definite matrix. The proposed algorithm effectively avoids the problem of solving large Hessian matrix inverse. At the same time, the global convergence of the algorithm is established under some suitable conditions. Finally, the proposed algorithm is compared with the command to calculate the maximum eigenvalue of the matrix in EIGS (Matlab. Experimental results show that the algorithm is stable, fast and efficient. In chapter 3, a finite memory BFGS algorithm for solving nonconvex optimization problems is proposed, and then the maximum eigenvalues of real symmetric positive definite matrices are calculated by the proposed algorithm. The proposed algorithm is based on the modified quasi-Newton equation and uses Armijo type linear search. Without assuming that the objective function is convex, the proposed algorithm converges to a stable point of the problem. Furthermore, the maximum eigenvalues of (UF) sparse matrices with a set dimension of 54929 dimensional symmetric positive definite matrices are solved by numerical experiments and compared with EIGS. Although the algorithm theoretically converges to a stable point rather than a global minimum point of the problem, numerical experiments show that the proposed algorithm can calculate the maximum eigenvalue. The fourth chapter summarizes the full text and gives some problems worthy of further study.
【学位授予单位】：河南大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O241.6

【相似文献】