On Efficiently Combining Limited Memory and Trust-Region Techniques
2013 (English)Report (Other academic)
Limited memory quasi-Newton methods and trust-region methods represent two efficient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited memory methods are usually combined with a line search. We show how to efficiently combine limited memory and trust-region techniques. One of our approaches is based on the eigenvalue decomposition of the limited memory quasi-Newton approximation of the Hessian matrix. The decomposition allows for finding a nearly-exact solution to the trust-region subproblem defined by the Euclidean norm with an insignificant computational overhead compared with the cost of computing the quasi-Newton direction in line-search limited memory methods. The other approach is based on two new eigenvalue-based norms. The advantage of the new norms is that the trust-region subproblem is separable and each of the smaller subproblems is easy to solve. We show that our eigenvalue-based limited-memory trust-region methods are globally convergent. Moreover, we propose improved versions of the existing limited-memory trust-region algorithms. The presented results of numerical experiments demonstrate the efficiency of our approach which is competitive with line-search versions of the L-BFGS method.
Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2013. , 33 p.
LiTH-MAT-R, ISSN 0348-2960 ; 2013:13
Unconstrained Optimization; Large-scale Problems; Limited Memory Methods;
IdentifiersURN: urn:nbn:se:liu:diva-102005ISRN: LiTH-MAT-R--2013/13--SEOAI: oai:DiVA.org:liu-102005DiVA: diva2:667359