Conditioning of quasi-Newton methods for function minimization

Author:
D. F. Shanno

Journal:
Math. Comp. **24** (1970), 647-656

MSC:
Primary 90.58

MathSciNet review:
0274029

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Quasi-Newton methods accelerate the steepest-descent 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****[2]**W. C. Davidon,*Variable Metric Method for Minimization*, Argonne National Laboratory Report ANL-5990, November 1959.**[3]**C. G. Broyden,*A class of methods for solving nonlinear simultaneous equations*, Math. Comp.**19**(1965), 577–593. MR**0198670**, 10.1090/S0025-5718-1965-0198670-6**[4]**J. G. P. Barnes,*An algorithm for solving non-linear equations based on the secant method*, Comput. J.**8**(1965), 66–72. MR**0181101****[5]**E. M. Rosen, "A review of quasi-Newton methods in nonlinear equation solving and unconstrained optimization," Nat. Conference of the ACM,*Proceedings of the Twenty-First Conference*, Thompson Book Co., Washington, D.C., 1966, pp. 37-41.**[6]**Frank J. Zeleznik,*Quasi-Newton methods for nonlinear equations*, J. Assoc. Comput. Mach.**15**(1968), 265–271. MR**0237094****[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****[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, RAC-TP-302, February 1968.**[10]**C. G. Broyden,*Quasi-Newton methods and their application to function minimisation*, Math. Comp.**21**(1967), 368–381. MR**0224273**, 10.1090/S0025-5718-1967-0224273-2**[11]**Donald Goldfarb,*A family of variable-metric methods derived by variational means*, Math. Comp.**24**(1970), 23–26. MR**0258249**, 10.1090/S0025-5718-1970-0258249-6**[12]**D. F. Shanno and P. C. Kettler,*Optimal conditioning of quasi-Newton methods*, Math. Comp.**24**(1970), 657–664. MR**0274030**, 10.1090/S0025-5718-1970-0274030-6

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/S0025-5718-1970-0274029-X

Keywords:
Function minimization,
quasi-Newton methods,
variable metric methods,
gradient search,
steepest-descent methods,
stability of search methods,
conditioning of search methods,
Hessian matrix,
inverse approximations

Article copyright:
© Copyright 1970
American Mathematical Society