Variations on variable-metric methods. (With discussion)

Greenstadt, J.

doi:10.1090/S0025-5718-1970-0258248-4

Variations on variable-metric methods. (With discussion)
HTML articles powered by AMS MathViewer

by J. Greenstadt PDF

Math. Comp. 24 (1970), 1-22 Request permission

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

M. J. Box, A comparison of several current optimization methods, and the use of transformations in constrained problems, Comput. J. 9 (1966), 67–77. MR 192645, DOI 10.1093/comjnl/9.1.67
Jean Bronfenbrenner Crockett and Herman Chernoff, Gradient methods of maximization, Pacific J. Math. 5 (1955), 33–50. MR 75676, DOI 10.2140/pjm.1955.5.33

Variable Metric Method for Minimization

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
John Greenstadt, On the relative efficiencies of gradient methods, Math. Comp. 21 (1967), 360–367. MR 223073, DOI 10.1090/S0025-5718-1967-0223073-7

Variations on Variable-Metric Methods

Bertram Klein, Direct use of extremal principles in solving certain optimizing problems involving inequalities, J. Operations Res. Soc. Amer. 3 (1955), 168–175. MR 68758, DOI 10.1287/opre.3.2.168
William C. Davidon, Variance algorithm for minimization, Comput. J. 10 (1967/68), 406–410. MR 221738, DOI 10.1093/comjnl/10.4.406
C. G. Broyden, Quasi-Newton methods and their application to function minimisation, Math. Comp. 21 (1967), 368–381. MR 224273, DOI 10.1090/S0025-5718-1967-0224273-2

Another Variable-Metric Method

Donald Goldfarb, A family of variable-metric methods derived by variational means, Math. Comp. 24 (1970), 23–26. MR 258249, DOI 10.1090/S0025-5718-1970-0258249-6