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

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]**Jean Bronfenbrenner Crockett and Herman Chernoff,*Gradient methods of maximization*, Pacific J. Math.**5**(1955), 33–50. MR**0075676****[3]**Marvin Marcus and Henryk Minc,*A survey of matrix theory and matrix inequalities*, Allyn and Bacon, Inc., Boston, Mass., 1964. MR**0162808****[4]**E. Bodewig,*Matrix calculus*, North-Holland Publishing Company, Amsterdam, 1956. MR**0080363****[5]**R. Courant and D. Hilbert,*Methods of mathematical physics. Vol. I*, Interscience Publishers, Inc., New York, N.Y., 1953. MR**0065391****[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 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**[9]**D. K. Faddeev and V. N. Faddeeva,*Computational methods of linear algebra*, Translated by Robert C. Williams, W. H. Freeman and Co., San Francisco-London, 1963. MR**0158519**

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