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

Zhanwen Shi (), Guanyu Yang () and Yunhai Xiao ()
Additional contact information
Zhanwen Shi: Henan University
Guanyu Yang: Henan University
Yunhai Xiao: Henan University

Mathematical Methods of Operations Research, 2016, vol. 83, issue 2, No 4, 243-264

Abstract: Abstract 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.

Keywords: Unconstrained optimization; Limited memory BFGS method; Armijo line search; Global convergence; Largest eigenvalue problem; Critical point; 90C30; 65K05; 90C53 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00186-015-0527-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:83:y:2016:i:2:d:10.1007_s00186-015-0527-8

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-015-0527-8

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().