A limited memory BFGS algorithm for non-convex minimization with applications in matrix largest eigenvalue problem

摘要

This study aims to present a limited memory BFGS algorithm to solve non-convex minimization problems, and then use it to find the largest eigenvalue of a real symmetric positive definite matrix. The proposed algorithm is based on the modified secant equation, which is used to the limited memory BFGS method without more storage or arithmetic operations. The proposed method uses an Armijo line search and converges to a critical point without convexity assumption on the objective function. More importantly, we do extensive experiments to compute the largest eigenvalue of the symmetric positive definite matrix of order up to 54,929 from the UF sparse matrix collection, and do performance comparisons with EIGS (a Matlab implementation for computing the first finite number of eigenvalues with largest magnitude). Although the proposed algorithm converges to a critical point, not a global minimum theoretically, the compared results demonstrate that it works well, and usually finds the largest eigenvalue of medium accuracy.