Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A quasi-Newton method with no derivatives

Author: John Greenstadt
Journal: Math. Comp. 26 (1972), 145-166
MSC: Primary 65K05
MathSciNet review: 0305592
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The Davidon formula and others of the ``quasi-Newton'' class, which are used in the unconstrained minimization of a function $ f$, provide a (generally) convergent sequence of approximations to the Hessian of $ f$. These formulas, however, require the independent calculation of the gradient of $ f$. In this paper, a set of new formulas is derived--using a previously described variational approach--which successively approximates the gradient as well as the Hessian, and uses only function values. These formulas are incorporated into an algorithm which, although still crude, works quite well for various standard test functions. Extensive numerical results are presented.

References [Enhancements On Off] (What's this?)

  • [1] W. C. Davidon, Variable Metric Method for Minimization, Argonne National Lab., ANL-5990 Rev., 1959. MR 1094786 (91k:90160)
  • [2] R. Fletcher & M. J. D. Powell, ``A rapidly convergent descent method for minimization,'' Comput. J., v. 6, 1963/64, pp. 163-168. MR 27 #2096. MR 0152116 (27:2096)
  • [3] C. G. Broyden, ``Quasi-Newton methods and their application to function minimization,'' Math. Comp., v. 21, 1967, pp. 368-381. MR 36 #7317. MR 0224273 (36:7317)
  • [4] G. W. Stewart III, ``A modification of Davidon's minimization method to accept difference approximations of derivatives,'' J. Assoc. Comput. Mach., v. 14, 1967, pp. 72-83. MR 35 #7566. MR 0216737 (35:7566)
  • [5] D. Goldfarb, ``Sufficient conditions for the convergence of a variable-metric algorithm,'' in Optimization, R. Fletcher (Editor), Academic Press, New York, 1969. MR 0287905 (44:5107)
  • [6] G. P. McCormick & J. D. Pearson, ``Variable metric methods and unconstrained optimization,'' in Optimization, R. Fletcher (Editor), Academic Press, New York, 1969. MR 0267905 (42:2806)
  • [7] J. Greenstadt, ``Variations on variable-metric methods,'' Math. Comp., v. 24, 1970, pp. 1-22. MR 41 #2895. MR 0258248 (41:2895)
  • [8] H. H. Rosenbrock, ``An automatic method for finding the greatest or least value of a function,'' Comput. J., v. 3, 1960/61, pp. 175-184. MR 24 #B2081. MR 0136042 (24:B2081)
  • [9] E. M. L. Beale, On an Iterative Method for Finding a Local Minimum of a Function of More than One Variable, Stat. Tech. Res. Grp., Technical Report #25, Princeton University, Princeton, N. J., 1958.
  • [10] M. J. D. Powell, ``An iterative method for finding stationary values of a function of several variables,'' Comput. J., v. 5, 1962, pp. 147-151.
  • [11] M. J. D. Powell, ``An efficient method for finding the minimum of a function of several variables without calculating derivatives,'' Comput. J., v. 7, 1964, pp. 155-162. MR 32 #4828. MR 0187376 (32:4828)
  • [12] A. Leon, ``A comparison among eight known optimizing procedures,'' in Recent Advances in Optimization Techniques, A. Lavi and T. P. Vogl (Editors), Wiley, New York, 1960. MR 0198722 (33:6876)
  • [13] D. Goldfarb, ``A family of variable-metric methods derived by variational means,'' Math. Comp., v. 24, 1970, pp. 23-26. MR 41 #2896. MR 0258249 (41:2896)
  • [14] J. Kowalik & M. R. Osborne, Methods for Unconstrained Optimization Problems, American Elsevier, New York, 1968. MR 0323104 (48:1462)
  • [15] A. R. Colville, A Comparative Study of Non-Linear Programming Codes, IBM Tech. Rep. #320-2949, 1968.
  • [16] A. V. Fiacco n G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York, 1968, p. 175 et seq. MR 39 #5152. MR 0243831 (39:5152)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65K05

Retrieve articles in all journals with MSC: 65K05

Additional Information

Keywords: Quasi-Newton methods, gradient-free nonlinear optimization
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society