Conditioning of quasiNewton methods for function minimization
Author:
D. F. Shanno
Journal:
Math. Comp. 24 (1970), 647656
MSC:
Primary 90.58
MathSciNet review:
0274029
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: QuasiNewton methods accelerate the steepestdescent technique for function minimization by using computational history to generate a sequence of approximations to the inverse of the Hessian matrix. This paper presents a class of approximating matrices as a function of a scalar parameter. The problem of optimal conditioning of these matrices under an appropriate norm as a function of the scalar parameter is investigated. A set of computational results verifies the superiority of the new methods arising from conditioning considerations to known methods.
 [1]
R.
Fletcher and M.
J. D. Powell, A rapidly convergent descent method for
minimization, Comput. J. 6 (1963/1964),
163–168. MR 0152116
(27 #2096)
 [2]
W. C. Davidon, Variable Metric Method for Minimization, Argonne National Laboratory Report ANL5990, November 1959.
 [3]
C.
G. Broyden, A class of methods for solving
nonlinear simultaneous equations, Math.
Comp. 19 (1965),
577–593. MR 0198670
(33 #6825), http://dx.doi.org/10.1090/S00255718196501986706
 [4]
J.
G. P. Barnes, An algorithm for solving nonlinear equations based
on the secant method, Comput. J. 8 (1965),
66–72. MR
0181101 (31 #5330)
 [5]
E. M. Rosen, "A review of quasiNewton methods in nonlinear equation solving and unconstrained optimization," Nat. Conference of the ACM, Proceedings of the TwentyFirst Conference, Thompson Book Co., Washington, D.C., 1966, pp. 3741.
 [6]
Frank
J. Zeleznik, QuasiNewton methods for nonlinear equations, J.
Assoc. Comput. Mach. 15 (1968), 265–271. MR 0237094
(38 #5387)
 [7]
M.
J. Box, A comparison of several current optimization methods, and
the use of transformations in constrained problems, Comput. J.
9 (1966), 67–77. MR 0192645
(33 #870)
 [8]
A. Leon, A Comparison Among Eight Known Optimizing Procedures, Internal Working Paper No. 20, Space Sciences Laboratory, University of California, Berkeley, August 1964.
 [9]
J. D. Pearson, On Variable Metric Methods of Minimization, Research Analysis Corp. Technical Paper, RACTP302, February 1968.
 [10]
C.
G. Broyden, QuasiNewton methods and their
application to function minimisation, Math.
Comp. 21 (1967),
368–381. MR 0224273
(36 #7317), http://dx.doi.org/10.1090/S00255718196702242732
 [11]
Donald
Goldfarb, A family of variablemetric methods
derived by variational means, Math. Comp.
24 (1970), 23–26.
MR
0258249 (41 #2896), http://dx.doi.org/10.1090/S00255718197002582496
 [12]
D.
F. Shanno and P.
C. Kettler, Optimal conditioning of quasiNewton
methods, Math. Comp. 24 (1970), 657–664. MR 0274030
(42 #8906), http://dx.doi.org/10.1090/S00255718197002740306
 [1]
 R. Fletcher & M. J. D. Powell, "A rapidly convergent descent method for minimization," Comput. J., v. 6, 1963/64, pp. 163168. MR 27 #2096. MR 0152116 (27:2096)
 [2]
 W. C. Davidon, Variable Metric Method for Minimization, Argonne National Laboratory Report ANL5990, November 1959.
 [3]
 C. G. Broyden, "A class of methods for solving nonlinear simultaneous equations," Math. Comp., v. 19, 1965, pp. 577593. MR 33 #6825. MR 0198670 (33:6825)
 [4]
 J. G. P. Barnes, "An algorithm for solving nonlinear equations based on the secant method," Comput J., v. 8, 1965, pp. 6672. MR 31 #5330. MR 0181101 (31:5330)
 [5]
 E. M. Rosen, "A review of quasiNewton methods in nonlinear equation solving and unconstrained optimization," Nat. Conference of the ACM, Proceedings of the TwentyFirst Conference, Thompson Book Co., Washington, D.C., 1966, pp. 3741.
 [6]
 F. J. Zeleznik, "QuasiNewton methods for nonlinear equations," J. Assoc. Comput. Mach., v. 15, 1968, pp. 265271. MR 38 #5387. MR 0237094 (38:5387)
 [7]
 M. J. Box, "A comparison of several current optimization methods, and the use of transformations in constrained problems," Comput. J., v. 9, 1966, pp. 6777. MR 33 #870. MR 0192645 (33:870)
 [8]
 A. Leon, A Comparison Among Eight Known Optimizing Procedures, Internal Working Paper No. 20, Space Sciences Laboratory, University of California, Berkeley, August 1964.
 [9]
 J. D. Pearson, On Variable Metric Methods of Minimization, Research Analysis Corp. Technical Paper, RACTP302, February 1968.
 [10]
 C. G. Broyden, "QuasiNewton methods and their application to function minimisation," Math. Comp., v. 21, 1967, pp. 368381. MR 36 #7317. MR 0224273 (36:7317)
 [11]
 D. Goldfarb, "A family of variablemetric methods derived by variational means," Math. Comp., v. 24, 1970, pp. 2326. MR 0258249 (41:2896)
 [12]
 D. F. Shanno & P. C. Kettler, "Optimal conditioning of quasiNewton methods," Math. Comp., v. 24, 1970, pp. 657664. MR 0274030 (42:8906)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
90.58
Retrieve articles in all journals
with MSC:
90.58
Additional Information
DOI:
http://dx.doi.org/10.1090/S0025571819700274029X
PII:
S 00255718(1970)0274029X
Keywords:
Function minimization,
quasiNewton methods,
variable metric methods,
gradient search,
steepestdescent methods,
stability of search methods,
conditioning of search methods,
Hessian matrix,
inverse approximations
Article copyright:
© Copyright 1970
American Mathematical Society
