Updating quasiNewton matrices with limited storage
Author:
Jorge Nocedal
Journal:
Math. Comp. 35 (1980), 773782
MSC:
Primary 65K05; Secondary 90C30
MathSciNet review:
572855
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We study how to use the BFGS quasiNewton 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 quasiNewton 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 wellknown methods.
 [1]
C.
G. Broyden, The convergence of a class of doublerank minimization
algorithms. II. The new algorithm, J. Inst. Math. Appl.
6 (1970), 222–231. MR 0433870
(55 #6841)
 [2]
A.
G. Buckley, A combined conjugategradient quasiNewton minimization
algorithm, Math. Programming 15 (1978), no. 2,
200–210. MR
509962 (80b:65083), http://dx.doi.org/10.1007/BF01609018
 [3]
W. C. DAVIDON & L. NAZARETH, DRVOCRA FORTRAN Implementation of Davidon's Optimally Conditioned Method, TM306, Argonne National Lab., Argonne, Ill., 1977.
 [4]
J.
E. Dennis Jr. and Jorge
J. Moré, QuasiNewton methods, motivation and theory,
SIAM Rev. 19 (1977), no. 1, 46–89. MR 0445812
(56 #4146)
 [5]
R. FLETCHER, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317322.
 [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
(81a:65102), http://dx.doi.org/10.1002/nme.1620141104
 [7]
L. NAZARETH, A Relationship Between the BFGS and Conjugate Gradient Algorithms, ANLAMD Tech. Memo 282 (rev.), Argonne National Lab., Argonne, Ill., 1977.
 [8]
L. NAZARETH & J. NOCEDAL, A Study of Conjugate Gradient Methods, Tech. Rep. SOL 7829, 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 VariableMetric 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
(54 #1605)
 [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
(56 #13577), http://dx.doi.org/10.1090/S00255718197704553384
 [1]
 C. G. BROYDEN, "The convergence of a class of doublerank minimization algorithms," J. Inst. Math. Appl., v. 6, 1970, pp. 7690. MR 0433870 (55:6841)
 [2]
 A. G. BUCKLEY, "A combined conjugate gradient quasiNewton minimization algorithm," Math. Programming, v. 15, 1978, pp. 200210. MR 509962 (80b:65083)
 [3]
 W. C. DAVIDON & L. NAZARETH, DRVOCRA FORTRAN Implementation of Davidon's Optimally Conditioned Method, TM306, Argonne National Lab., Argonne, Ill., 1977.
 [4]
 J. E. DENNIS & J. J. MORE, "QuasiNewton methods, motivation and theory," SIAM Rev., v. 19, 1977, pp. 4689. MR 0445812 (56:4146)
 [5]
 R. FLETCHER, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317322.
 [6]
 H. MATTHIES & G. STRANG, "The solution of nonlinear finite element equations," Internat J. Numer. Methods Engrg., v. 14, 1979, pp. 16131626. MR 551801 (81a:65102)
 [7]
 L. NAZARETH, A Relationship Between the BFGS and Conjugate Gradient Algorithms, ANLAMD Tech. Memo 282 (rev.), Argonne National Lab., Argonne, Ill., 1977.
 [8]
 L. NAZARETH & J. NOCEDAL, A Study of Conjugate Gradient Methods, Tech. Rep. SOL 7829, 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 VariableMetric 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]
 J. STOER, "On the convergence rate of imperfect minimization algorithms in Broyden's class," Math. Programming, v. 9, 1975, pp. 313335. MR 0413491 (54:1605)
 [15]
 P. TOINT, "On sparse and symmetric updating subject to a linear equation," Math. Comp., v. 31, 1977, pp. 954961. MR 0455338 (56:13577)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65K05,
90C30
Retrieve articles in all journals
with MSC:
65K05,
90C30
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198005728557
PII:
S 00255718(1980)05728557
Article copyright:
© Copyright 1980
American Mathematical Society
