Updating quasi-Newton matrices with limited storage

Author:
Jorge Nocedal

Journal:
Math. Comp. **35** (1980), 773-782

MSC:
Primary 65K05; Secondary 90C30

DOI:
https://doi.org/10.1090/S0025-5718-1980-0572855-7

MathSciNet review:
572855

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study how to use the BFGS quasi-Newton matrices to precondition minimization methods for problems where the storage is critical. We give an update formula which generates matrices using information from the last *m* iterations, where *m* is any number supplied by the user. The quasi-Newton matrix is updated at every iteration by dropping the oldest information and replacing it by the newest information. It is shown that the matrices generated have some desirable properties.

The resulting algorithms are tested numerically and compared with several well-known methods.

**[1]**C. G. Broyden,*The convergence of a class of double-rank minimization algorithms. II. The new algorithm*, J. Inst. Math. Appl.**6**(1970), 222–231. MR**0433870****[2]**A. G. Buckley,*A combined conjugate-gradient quasi-Newton minimization algorithm*, Math. Programming**15**(1978), no. 2, 200–210. MR**509962**, https://doi.org/10.1007/BF01609018**[3]**W. C. DAVIDON & L. NAZARETH,*DRVOCR-A FORTRAN Implementation of Davidon's Optimally Conditioned Method*, TM-306, Argonne National Lab., Argonne, Ill., 1977.**[4]**J. E. Dennis Jr. and Jorge J. Moré,*Quasi-Newton methods, motivation and theory*, SIAM Rev.**19**(1977), no. 1, 46–89. MR**0445812**, https://doi.org/10.1137/1019005**[5]**R. FLETCHER, "A new approach to variable metric algorithms,"*Comput. J.*, v. 13, 1970, pp. 317-322.**[6]**Hermann Matthies and Gilbert Strang,*The solution of nonlinear finite element equations*, Internat. J. Numer. Methods Engrg.**14**(1979), no. 11, 1613–1626. MR**551801**, https://doi.org/10.1002/nme.1620141104**[7]**L. NAZARETH,*A Relationship Between the BFGS and Conjugate Gradient Algorithms*, ANL-AMD Tech. Memo 282 (rev.), Argonne National Lab., Argonne, Ill., 1977.**[8]**L. NAZARETH & J. NOCEDAL,*A Study of Conjugate Gradient Methods*, Tech. Rep. SOL 78-29, Dept. of Operations Research, Stanford University, Stanford, Calif., 1979.**[9]**L. NAZARETH & J. NOCEDAL, "Convergence analysis of optimization methods that use variable storage," Manuscript, 1978.**[10]**A. PERRY,*A Modified Conjugate Gradient Algorithm*, Discussion paper No. 229, Center for Mathematical Studies in Economics and Management Science, Northwestern University, Evanston, Ill., 1976.**[11]**D. SHANNO,*Conjugate Gradient Methods With Inexact Line Searches*, MIS Tech. Report 22, University of Arizona, Tucson, Ariz., 1977.**[12]**D. SHANNO,*On Variable-Metric Methods for Sparse Hessians*, MIS Tech. Rep. 27, University of Arizona, Tucson, Ariz., 1978.**[13]**D. SHANNO & K. PHUA,*A Variable Method Subroutine for Unconstrained Nonlinear Minimization*, MIS Tech. Rep. No. 28, University of Arizona, Tucson, Ariz., 1978.**[14]**Josef Stoer,*On the convergence rate of imperfect minimization algorithms in Broyden’s 𝛽-class*, Math. Programming**9**(1975), no. 3, 313–335. MR**0413491**, https://doi.org/10.1007/BF01681353**[15]**Ph. L. Toint,*On sparse and symmetric matrix updating subject to a linear equation*, Math. Comp.**31**(1977), no. no 140, 954–961. MR**0455338**, https://doi.org/10.1090/S0025-5718-1977-0455338-4

Retrieve articles in *Mathematics of Computation*
with MSC:
65K05,
90C30

Retrieve articles in all journals with MSC: 65K05, 90C30

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1980-0572855-7

Article copyright:
© Copyright 1980
American Mathematical Society