Factorized variable metric methods for unconstrained optimization

Goldfarb, Donald

doi:10.1090/S0025-5718-1976-0423804-2

Factorized variable metric methods for unconstrained optimization
HTML articles powered by AMS MathViewer

by Donald Goldfarb PDF

Math. Comp. 30 (1976), 796-811 Request permission

Abstract:

Several efficient methods are given for updating the Cholesky factors of a symmetric positive definite matrix when it is modified by a rank-two correction which maintains symmetry and positive definiteness. These ideas are applied to variable metric (quasi-Newton) methods to produce numerically stable algorithms.

References

Yonathan Bard, On a numerical instability of Davidon-like methods, Math. Comp. 22 (1968), 665–666. MR 232533, DOI 10.1090/S0025-5718-1968-0232533-5
John M. Bennett, Triangular factors of modified matrices, Numer. Math. 7 (1965), 217–221. MR 177503, DOI 10.1007/BF01436076

Product Form Corrections for Variable Metric Methods of Minimization

C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math. Comp. 19 (1965), 577–593. MR 198670, DOI 10.1090/S0025-5718-1965-0198670-6
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
C. G. Broyden, The convergence of a class of double-rank minimization algorithms. II. The new algorithm, J. Inst. Math. Appl. 6 (1970), 222–231. MR 433870

Variable Metric Method for Minimization

William C. Davidon, Variance algorithm for minimization, Comput. J. 10 (1967/68), 406–410. MR 221738, DOI 10.1093/comjnl/10.4.406
L. C. W. Dixon, Quasi-Newton algorithms generate identical points, Math. Programming 2 (1972), 383–387. MR 303716, DOI 10.1007/BF01584554

Comput. J.

Fortran Subroutines for Minimization by Quasi-Newton Methods

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

On the Modification of

Factorizations

W. Morven Gentleman, Least squares computations by Givens transformations without square roots, J. Inst. Math. Appl. 12 (1973), 329–336. MR 329233
P. E. Gill, G. H. Golub, W. Murray, and M. A. Saunders, Methods for modifying matrix factorizations, Math. Comp. 28 (1974), 505–535. MR 343558, DOI 10.1090/S0025-5718-1974-0343558-6
P. E. Gill and W. Murray, Quasi-Newton methods for unconstrained optimization, J. Inst. Math. Appl. 9 (1972), 91–108. MR 300410

The Implementation of Two Revised Quasi-Newton Algorithms for Unconstrained Optimization

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

Variable Metric and Conjugate Direction Methods in Unconstrained Optimization

Recent Developments

Factorized Variable Metric Methods for Unconstrined Optimization

Donald Goldfarb, Matrix factorizations in optimization of non-linear functions subject to linear constraints, Math. Programming 10 (1976), no. 1, 1–31. MR 406523, DOI 10.1007/BF01580651
G. P. McCormick and J. D. Pearson, Variable metric methods and unconstrained optimization, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 307–325. MR 0267905
B. A. Murtagh and R. W. H. Sargent, A constrained minimization method with quadratic convergence, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 215–245. MR 0284213
M. J. D. Powell, On the convergence of the variable metric algorithm, J. Inst. Math. Appl. 7 (1971), 21–36. MR 279977
D. F. Shanno, Conditioning of quasi-Newton methods for function minimization, Math. Comp. 24 (1970), 647–656. MR 274029, DOI 10.1090/S0025-5718-1970-0274029-X

Another Variable Metric Method