Representations of quasi-Newton matrices and their use in limited memory methods
Mathematical ProgrammingPublished 1 January 1994
Richard H. Byrd, Jorge Nocedal, Robert B. Schnabel
Citations746
SJR quartileQ1
SJR score1.73
SNIP2.20
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work derives compact representations of BFGS and symmetric rank-one matrices for optimization and presents a compact representation of the matrices generated by Broyden's update for solving systems of nonlinear equations.
Abstract
We derive compact representations of BFGS and symmetric rank-one matrices for optimization. These representations allow us to efficiently implement limited memory methods for large constrained optimization problems. In particular, we discuss how to compute projections of limited memory matrices onto subspaces. We also present a compact representation of the matrices generated by Broyden's update for solving systems of nonlinear equations.
Keywords
Computer ScienceMathematics
Mathematical ProgrammingOn the limited memory BFGS method for large scale optimization
8,529 Citations1989Dong C. Liu, Jorge Nocedal
The numerical tests indicate that the L-BFGS method is faster than the method of Buckley and LeNir, and is better able to use additional storage to accelerate convergence, and the convergence properties are studied to prove global convergence on uniformly convex problems.
Society for Industrial and Applied Mathematics eBooksNumerical Methods for Unconstrained Optimization and Nonlinear Equations
7,651 Citations1996J. E. Dennis, Robert B. Schnabel
Society for Industrial and Applied Mathematics eBooksIterative Solution of Nonlinear Equations in Several Variables
6,875 Citations2000J. M. Ortega, Werner C. Rheinboldt
Convergence of Minimization Methods An Annotated List of Basic Reference Books Bibliography Author Index Subject Index.
Practical Methods of Optimization
6,403 Citations2000R. Ian Fletcher
SIAM Journal on Scientific ComputingA Limited Memory Algorithm for Bound Constrained Optimization
6,000 Citations1995Richard H. Byrd, Peihuang Lu +2 more
An algorithm for solving large nonlinear optimization problems with simple bounds is described, based on the gradient projection method and uses a limited memory BFGS matrix to approximate the Hessian of the objective function.
Mathematics of ComputationUpdating quasi-Newton matrices with limited storage
2,710 Citations1980Jorge Nocedal
An update formula which generates matrices using information from the last m iterations, where m is any number supplied by the user, and the BFGS method is considered to be the most efficient.
Mathematics of ComputationA class of methods for solving nonlinear simultaneous equations
2,656 Citations1965C. G. Broyden
Mathematical ProgrammingSome numerical experiments with variable-storage quasi-Newton algorithms
809 Citations1989Jean Charles Gilbert, Claude Lemaréchal
It is found appropriate to use a diagonal matrix, generated by an update of the identity matrix, so as to fit the Rayleigh ellipsoid of the local Hessian in the direction of the change in the gradient.
International Journal for Numerical Methods in EngineeringThe solution of nonlinear finite element equations
502 Citations1979Hermann G. Matthies, Gilbert Strang
IMA Journal of Applied MathematicsQuasi-Newton Methods for Unconstrained Optimization
357 Citations1972Philip E. Gill, Walter Murray
SIAM Journal on Scientific and Statistical ComputingImplementation of the GMRES Method Using Householder Transformations
265 Citations1988Homer F. Walker
An alternative implementation of the GMRES method is outlined here in which orthogonalization by Householder transformations replaces the Gram-Schmidt process, which requires slightly less storage but somewhat more arithmetic.
Mathematics of ComputationTesting a class of methods for solving minimization problems with simple bounds on the variables
205 Citations1988Andrew R. Conn, Nicholas I. M. Gould +1 more
SIAM Journal on OptimizationA Reduced Hessian Method for Large-Scale Constrained Optimization
160 Citations1995Lorenz T. Biegler, Jorge Nocedal +1 more
The Computer JournalAn Algorithm for Solving Non-Linear Equations Based on the Secant Method
129 Citations1965John Barnes
This paper describes a variant of the generalized secant method for solving simultaneous nonlinear equations and it is shown that for suitable problems the method is considerably superior.
SIAM Journal on OptimizationA Theoretical and Experimental Study of the Symmetric Rank-One Update
117 Citations1993Humaid Khalfan, Richard H. Byrd +1 more
A new analysis is presented that shows that the SRi method with a line search is $( n + 1)$-step q-superlinearly convergent without the assumption of linearly independent iterates.
Mathematical ProgrammingQN-like variable storage conjugate gradients
115 Citations1983A. Buckley, A. Lenir
A new combined CG-QN algorithm which can use whatever storage is available and is presented to demonstrate that the new algorithm is never worse than CONMIN and that it is almost always better if even a small amount of extra storage is provided.
Mathematical Programming
97 Citations1990David L. Smith
Quasi-Newton Methods Using Multiple Secant Equations.
63 Citations1983Robert B. Schnabel
The author shows how to successfully specify multiple secant equations for unconstrained optimization, and that algorithms using thesesecant equations and the generalized PSB, DFP or BFGS updates are locally and q-superlinearly convergent under standard assumptions.
National Bureau of Economic ResearchSolving Systems of Non-Linear Equations by Broyden's Method with Projected Updates
42 Citations1977David Gay, Robert B. Schnabel
Elsevier eBooksSOLVING SYSTEMS OF NONLINEAR EQUATIONS BY BROYDEN'S METHOD WITH PROJECTED UPDATES
35 Citations1978David M. Gay, Robert B. Schnabel
Applied Mathematics LettersAutomatic differentiation and the step computation in the limited memory BFGS method
11 Citations1993Jean Charles Gilbert, Jorge Nocedal
It is shown that the two-loop recursion for computing the search direction of a limited memory method for optimization can be derived by means of the reverse mode of automatic differentiation applied to an auxilliary function.