Limited-memory BFGS systems with diagonal updates

DOI10.1016/J.LAA.2012.02.005zbMATH Open1246.65088arXiv1112.6060OpenAlexW2962844830MaRDI QIDQ417600FDOQ417600

Roummel F. Marcia, Jennifer B. Erway

Publication date: 14 May 2012

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: In this paper, we investigate a formula to solve systems of the form (B + {sigma}I)x = y, where B is a limited-memory BFGS quasi-Newton matrix and {sigma} is a positive constant. These types of systems arise naturally in large-scale optimization such as trust-region methods as well as doubly-augmented Lagrangian methods. We show that provided a simple condition holds on B_0 and sigma, the system (B + sigma I)x = y can be solved via a recursion formula that requies only vector inner products. This formula has complexity M^2n, where M is the number of L-BFGS updates and n >> M is the dimension of x.

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

Recommendations

• On solving large-scale limited-memory quasi-Newton equations
• Shifted L-BFGS systems
• Diagonal BFGS updates and applications to the limited memory BFGS method
• Dynamic scaling on the limited memory BFGS method
• Generalizations of the limited-memory BFGS method based on the quasi-product form of update

zbMATH Keywords

numerical experimentstrust-region methodslarge-scale optimizationquasi-Newton methodsinversesBroyden-Fletcher-Goldfarb-Shanno (BFGS)diagonal updatesdoubly-augmented Lagrangian methodlimited-memory methodsSherman-Morrison-Woodbury

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Nonlinear programming (90C30) Interior-point methods (90C51) Methods of quasi-Newton type (90C53)

Cites Work

• Computing a Trust Region Step
• Title not available (Why is that?)
• Methods for Modifying Matrix Factorizations
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the limited memory BFGS method for large scale optimization
• Updating Quasi-Newton Matrices with Limited Storage
• Title not available (Why is that?)
• On the Inverse of the Sum of Matrices
• Representations of quasi-Newton matrices and their use in limited memory methods
• Quasi-Newton Methods, Motivation and Theory
• Trust Region Methods
• A numerical study of limited memory BFGS methods
• A quasi-Newton trust-region method
• Reduced Storage, Quasi-Newton Trust Region Approaches to Function Optimization
• Title not available (Why is that?)
• A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization
• Interior Methods for Nonlinear Optimization
• Iterative Methods for Finding a Trust-region Step
• A Subspace Minimization Method for the Trust-Region Step
• Computing Optimal Locally Constrained Steps
• Newton’s Method with a Model Trust Region Modification
• The interior-point revolution in optimization: History, recent developments, and lasting consequences
• Title not available (Why is that?)
• Two new unconstrained optimization algorithms which use function and gradient values
• Iterative Solution of Augmented Systems Arising in Interior Methods
• New least-square algorithms
• A subspace implementation of quasi-Newton trust region methods for unconstrained optimization
• Title not available (Why is that?)

Cited In (6)

• On efficiently combining limited-memory and trust-region techniques
• Nonlinear conjugate gradient method for spectral tomosynthesis
• Algorithm 943
• On solving large-scale limited-memory quasi-Newton equations
• A limited memory BFGS method for a nonlinear inverse problem in digital breast tomosynthesis
• Shifted L-BFGS systems

Uses Software

• L-BFGS
• GQTPAR
• MSS
• NSOIA

This page was built for publication: Limited-memory BFGS systems with diagonal updates

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