Shifted L-BFGS systems

DOI10.1080/10556788.2014.894045MaRDI QIDQ2926066zbMATH OpenOpenAlexFDO

Authors Jennifer B. Erway, Vibhor Jain, Roummel F. Marcia

Publication date 29 October 2014

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.5141

zbMATH Keywords

limited-memory BFGSnumerical linear algebraquasi-Newton methodsSherman-Morrison-Woodbury formula

Mathematics Subject Classification ID

Linear equations (linear algebraic aspects) (15A06) Newton-type methods (49M15) Direct numerical methods for linear systems and matrix inversion (65F05) Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Large-scale problems in mathematical programming (90C06) Methods of quasi-Newton type (90C53)

Abstract: We investigate fast direct methods for solving systems of the form (B + G)x = y, where B is a limited-memory BFGS matrix and G is a symmetric positive-definite matrix. These systems, which we refer to as shifted L-BFGS systems, arise in several settings, including trust-region methods and preconditioning techniques for interior-point methods. We show that under mild assumptions, the system (B + G)x = y can be solved in an efficient and stable manner via a recursion that requies only vector inner products. We consider various shift matrices G and demonstrate the effectiveness of the recursion methods in numerical experiments.

Recommendations

• Limited-memory BFGS systems with diagonal updates
• On solving large-scale limited-memory quasi-Newton equations
• Efficient preconditioner updates for shifted linear systems
• Accelerated preconditioner updates for solving shifted linear systems
• L-Broyden methods: a generalization of the L-BFGS method to the limited-memory Broyden family

Cites work

• A Note on the Stability of Solving a Rank-p Modification of a Linear System by the Sherman–Morrison–Woodbury Formula
• A primal-dual augmented Lagrangian
• Accuracy and Stability of Numerical Algorithms
• Computing a Trust Region Step
• CUTE
• CUTEr and SifDec
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Interior Methods for Nonlinear Optimization
• Iterative methods for finding a trust-region step
• Iterative Solution of Augmented Systems Arising in Interior Methods
• Limited-memory BFGS systems with diagonal updates
• On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods
• On the limited memory BFGS method for large scale optimization
• Primal-Dual Interior Methods for Nonconvex Nonlinear Programming
• Quasi-Newton Methods, Motivation and Theory
• Reduced Storage, Quasi-Newton Trust Region Approaches to Function Optimization
• Representations of quasi-Newton matrices and their use in limited memory methods

Cited in

(4)

• On efficiently combining limited-memory and trust-region techniques
• Limited-memory BFGS systems with diagonal updates
• Algorithm 943: MSS: MATLAB software for L-BFGS trust-region subproblems for large-scale optimization
• Regularization of limited memory quasi-Newton methods for large-scale nonconvex minimization

This page was built for publication: Shifted L-BFGS systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2926066)