On the relative efficiencies of gradient methods

Author:
John Greenstadt

Journal:
Math. Comp. **21** (1967), 360-367

MSC:
Primary 65.30

DOI:
https://doi.org/10.1090/S0025-5718-1967-0223073-7

MathSciNet review:
0223073

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A comparison is made among various gradient methods for maximizing a function, based on a characterization by Crockett and Chernoff of the class of these methods. By defining the ``efficiency'' of a gradient step in a certain way, it becomes easy to compare the efficiencies of different schemes with that of Newton's method, which can be regarded as a particular gradient scheme. For quadratic functions, it is shown that Newton's method is the most efficient (a conclusion which may be approximately true for nonquadratic functions). For functions which are not concave (downward), it is shown that the Newton direction may be just the opposite of the most desirable one. A simple way of correcting this is explained.

**[1]**H. A. Spang, III, ``A review of minimization techniques for nonlinear functions,''*SIAM Rev.*, v. 4, 1962, pp. 343-365. MR**26**#3171.**[2]**J. B. Crockett & H. Chernoff, ``Gradient methods of maximization,''*Pacific J. Math.*, v. 5, 1955, pp. 33-50. MR**17**, 790. MR**0075676 (17:790b)****[3]**M. Marcus & H. Minc,*A Survey of Matrix Theory and Matrix Inequalities*, Allyn and Bacon, Boston, Mass., 1964, p. 117. MR**29**#112. MR**0162808 (29:112)****[4]**E. Bodewig,*Matrix Calculus*, North-Holland, Amsterdam, 1956, p. 45 et seq. MR**18**, 235. MR**0080363 (18:235e)****[5]**R. Courant & D. Hilbert,*Methods of Mathematical Physics*, Vol. I, Interscience, New York, 1953, p. 343 et seq. MR**16**, 426. MR**0065391 (16:426a)****[6]**H. Eisenpress & J. Greenstadt, ``The estimation of non-linear econometric systems,''*Econometrica*(To appear.)**[7]**W. C. Davidon,*Variable Metric Method for Minimization*, AEC Research and Development Report ANL-5990, 1959.**[8]**R. Fletcher & M. J. D. Powell, ``A rapidly convergent descent method for minimization,''*Comput. J.*, v. 6, 1963/1964, pp. 163-168. MR**27**#2096. MR**0152116 (27:2096)****[9]**D. K. Faddeev & V. N. Faddeeva,*Computational Methods of Linear Algebra*, Freeman, San Francisco, Calif., 1963, p. 126. MR**28**#1742. MR**0158519 (28:1742)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65.30

Retrieve articles in all journals with MSC: 65.30

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1967-0223073-7

Article copyright:
© Copyright 1967
American Mathematical Society