Optimization Online


On Efficiently Combining Limited Memory and Trust-Region Techniques

Oleg Burdakov (oleg.burdakov***at***liu.se)
Lujin Gong (lujin.gong***at***samsung.com)
Ya-xiang Yuan (yyx***at***lsec.cc.ac.cn)
Spartak Zikrin (spartak.zikrin***at***liu.se)

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

Keywords: Unconstrained Optimization; Large-scale Problems; Limited Memory Methods; Trust Region Methods; Shape-Changing Norm; Eigenvalue Decomposition

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Citation: Technical Report LiTH-MAT-R--2013/13--SE, Department of Mathematics, Linkoping University, Sweden, November/2013

Download: [PDF]

Entry Submitted: 11/25/2013
Entry Accepted: 11/25/2013
Entry Last Modified: 04/10/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society