A quasi-Newton method with no derivatives

Author:
John Greenstadt

Journal:
Math. Comp. **26** (1972), 145-166

MSC:
Primary 65K05

DOI:
https://doi.org/10.1090/S0025-5718-1972-0305592-X

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 , provide a (generally) convergent sequence of approximations to the Hessian of . These formulas, however, require the independent calculation of the gradient of . 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.

**[1]**William C. Davidon,*Variable metric method for minimization*, SIAM J. Optim.**1**(1991), no. 1, 1–17. MR**1094786**, https://doi.org/10.1137/0801001**[2]**R. Fletcher and M. J. D. Powell,*A rapidly convergent descent method for minimization*, Comput. J.**6**(1963/1964), 163–168. MR**0152116**, https://doi.org/10.1093/comjnl/6.2.163**[3]**C. G. Broyden,*Quasi-Newton methods and their application to function minimisation*, Math. Comp.**21**(1967), 368–381. MR**0224273**, https://doi.org/10.1090/S0025-5718-1967-0224273-2**[4]**G. W. Stewart III,*A modification of Davidon’s minimization method to accept difference approximations of derivatives*, J. Assoc. Comput. Mach.**14**(1967), 72–83. MR**0216737**, https://doi.org/10.1145/321371.321377**[5]**D. Goldfarb,*Sufficient conditions for the convergence of a variable metric algorithm*, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 273–281. MR**0287905****[6]**G. P. McCormick and J. D. Pearson,*Variable metric methods and unconstrained optimization*, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 307–325. MR**0267905****[7]**J. Greenstadt,*Variations on variable-metric methods. (With discussion)*, Math. Comp.**24**(1970), 1–22. MR**0258248**, https://doi.org/10.1090/S0025-5718-1970-0258248-4**[8]**H. H. Rosenbrock,*An automatic method for finding the greatest or least value of a function*, Comput. J.**3**(1960/1961), 175–184. MR**0136042**, https://doi.org/10.1093/comjnl/3.3.175**[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.**7**(1964), 155–162. MR**0187376**, https://doi.org/10.1093/comjnl/7.2.155**[12]**Thomas P. Vogl,*Recent advances in optimization techniques*, Proceedings of the Symposium on Recent Advances in Optimization Techniques, held at Carnegie Institute of Technology, Pittsburgh, Pennsylvania, April 2 1-23, vol. 1965, John Wiley & Sons, Inc., New York-London-Sydney, 1966. MR**0198722****[13]**Donald Goldfarb,*A family of variable-metric methods derived by variational means*, Math. Comp.**24**(1970), 23–26. MR**0258249**, https://doi.org/10.1090/S0025-5718-1970-0258249-6**[14]**J. Kowalik and M. R. Osborne,*Methods for unconstrained optimization problems*, American Elsevier Publishing Co., Inc., New York, 1968. Modern Analytic and Computational Methods in Science and Mathematics, No. 13. MR**0323104****[15]**A. R. Colville,*A Comparative Study of Non-Linear Programming Codes*, IBM Tech. Rep. #320-2949, 1968.**[16]**Anthony V. Fiacco and Garth P. McCormick,*Nonlinear programming: Sequential unconstrained minimization techniques*, John Wiley and Sons, Inc., New York-London-Sydney, 1968. MR**0243831**

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

Retrieve articles in all journals with MSC: 65K05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1972-0305592-X

Keywords:
Quasi-Newton methods,
gradient-free nonlinear optimization

Article copyright:
© Copyright 1972
American Mathematical Society