On the relative efficiencies of gradient methods
HTML articles powered by AMS MathViewer
- by John Greenstadt PDF
- Math. Comp. 21 (1967), 360-367 Request permission
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.References
-
H. A. Spang, III, “A review of minimization techniques for nonlinear functions,” SIAM Rev., v. 4, 1962, pp. 343–365. MR 26 #3171.
- Jean Bronfenbrenner Crockett and Herman Chernoff, Gradient methods of maximization, Pacific J. Math. 5 (1955), 33–50. MR 75676
- Marvin Marcus and Henryk Minc, A survey of matrix theory and matrix inequalities, Allyn and Bacon, Inc., Boston, Mass., 1964. MR 0162808
- E. Bodewig, Matrix calculus, North-Holland Publishing Co., Amsterdam, 1956. MR 0080363
- R. Courant and D. Hilbert, Methods of mathematical physics. Vol. I, Interscience Publishers, Inc., New York, N.Y., 1953. MR 0065391 H. Eisenpress & J. Greenstadt, “The estimation of non-linear econometric systems,”Econometrica (To appear.) W. C. Davidon, Variable Metric Method for Minimization, AEC Research and Development Report ANL-5990, 1959.
- R. Fletcher and M. J. D. Powell, A rapidly convergent descent method for minimization, Comput. J. 6 (1963/64), 163–168. MR 152116, DOI 10.1093/comjnl/6.2.163
- D. K. Faddeev and V. N. Faddeeva, Computational methods of linear algebra, W. H. Freeman and Co., San Francisco-London, 1963. Translated by Robert C. Williams. MR 0158519
Additional Information
- © Copyright 1967 American Mathematical Society
- 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