Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Variations on variable-metric methods. (With discussion)


Author: J. Greenstadt
Journal: Math. Comp. 24 (1970), 1-22
MSC: Primary 65.30
DOI: https://doi.org/10.1090/S0025-5718-1970-0258248-4
MathSciNet review: 0258248
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In unconstrained minimization of a function $ f$, the method of Davidon-FletcherPowell (a "variable-metric" method) enables the inverse of the Hessian $ H$ of $ f$ to be approximated stepwise, using only values of the gradient of $ f$. It is shown here that, by solving a certain variational problem, formulas for the successive corrections to $ H$ can be derived which closely resemble Davidon's. A symmetric correction matrix is sought which minimizes a weighted Euclidean norm, and also satisfies the "DFP condition." Numerical tests are described, comparing the performance (on four "standard" test functions) of two variationally-derived formulas with Davidon's. A proof by Y. Bard, modelled on Fletcher and Powell's, showing that the new formulas give the exact $ H$ after $ N$ steps, is included in an appendix.


References [Enhancements On Off] (What's this?)

  • [1] M. J. Box, "A comparison of several current optimization methods, and the use of transformations in constrained problems," Comput. J., v. 9, 1966, pp. 67-77. MR 33 #870. MR 0192645 (33:870)
  • [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] W. C. Davidon, Variable Metric Method for Minimization, AEC Res. and Develop. Report, ANL-5990 (Rev.), 1959.
  • [4] R. Fletcher & M. J. D. Powell, "A rapidly convergent descent method for minimization," Comput. J., v. 6, 1963/64, pp. 163-168. MR 27 #2096. MR 0152116 (27:2096)
  • [5] J. Greenstadt, "On the relative efficiencies of gradient methods," Math. Comp., v. 21, 1967, pp. 360-367. MR 36 #6122. MR 0223073 (36:6122)
  • [6] J. Greenstadt, Variations on Variable-Metric Methods, IBM NY Scientific Center Report 320-2901, June, 1967.
  • [7] B. Klein, "Direct use of extremal principles in solving certain optimizing problems involving inequalities," J. Operations Res. Soc. Amer., v. 3, 1955, pp. 168-175. MR 16, 937. MR 0068758 (16:937c)
  • [8] W. C. Davidon, "Variance algorithm for minimization," Comput. J., v. 10, 1968, pp. 406-110. MR 36 #4790. MR 0221738 (36:4790)
  • [9] C. G. Broyden, "Quasi-Newton methods and their application to function minimisation," Math. Comp., v. 21, 1967, pp. 368-381. MR 36 #7317. MR 0224273 (36:7317)
  • [10] P. Wolfe, Another Variable-Metric Method, Working Paper, 1967.
  • [11] D. Goldfarb, "A family of variable-metric methods derived by variational means," Math. Comp., v. 24, 1970, pp. 23-26. MR 0258249 (41:2896)

Similar Articles

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-1970-0258248-4
Keywords: Variable-metric, Davidon method, unconstrained minimization, variational method
Article copyright: © Copyright 1970 American Mathematical Society

American Mathematical Society