A limited memory BFGS algorithm for nonconvex min

Authors: Zhanwen Shi Guanyu Yang Yunhai Xiao

Publish Date: 2015/12/26

Volume: 83, Issue: 2, Pages: 243-264

PDF Link

Abstract

This study aims to present a limited memory BFGS algorithm to solve nonconvex 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 54929 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 accuracyWe are grateful to the associate editor and two anonymous referees for their valuable comments and suggestions which have helped us improve the presentation of this paper greatly The work was supported by the Major State Basic Research Development Program of China 973 Program Grant No 2015CB856003 the National Natural Science Foundation of China Grant No 11471101 and the Program for Science and Technology Innovation Talents in Universities of Henan Province Grant No 13HASTIT050

Keywords: