On the relative efficiencies of gradient methods
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.
-  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 0075676
-  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 Company, 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/1964), 163–168. MR 0152116, https://doi.org/10.1093/comjnl/6.2.163
-  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
- H. A. Spang, III, ``A review of minimization techniques for nonlinear functions,'' SIAM Rev., v. 4, 1962, pp. 343-365. MR 26 #3171.
- 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)
- 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)
- E. Bodewig, Matrix Calculus, North-Holland, Amsterdam, 1956, p. 45 et seq. MR 18, 235. MR 0080363 (18:235e)
- 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)
- 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 & 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)
- 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