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 K. W. BRODLIE, A. R. GOURLAY & J. GREENSTADT, Product Form Corrections for Variable Metric Methods of Minimization, IBM UKSC Report No. 10, IBM-UK Scientific Center, Peterlee, 1972.
- 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 W. C. DAVIDON, Variable Metric Method for Minimization, A.E.C. Res. and Devel. Rep. ANL-5990 (Rev.), 1959.
- 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 R. FLETCHER, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317-322. R. FLETCHER, Fortran Subroutines for Minimization by Quasi-Newton Methods, Report R-7125, A.E.R.E., Harwell, England, 1972.
- 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 R. FLETCHER & M. J. D. POWELL, On the Modification of $LD{L^T}$ Factorizations, Harwell Report TP. 519, 1973.
- 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 P. E. GILL, W. MURRAY & R. A. PITFIELD, The Implementation of Two Revised Quasi-Newton Algorithms for Unconstrained Optimization, NPL Report NAC 11, 1972.
- 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 D. GOLDFARB, Variable Metric and Conjugate Direction Methods in Unconstrained Optimization: Recent Developments, ACM Proceedings—1972. D. GOLDFARB, Factorized Variable Metric Methods for Unconstrined Optimization, IBM Res. Rep. RC 4415, IBM Research Center, Yorktown Heights, New York, 1973.
- 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 P. WOLFE, Another Variable Metric Method, IBM working paper.
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Math. Comp. 30 (1976), 796-811
- MSC: Primary 65K05; Secondary 90C30
- DOI: https://doi.org/10.1090/S0025-5718-1976-0423804-2
- MathSciNet review: 0423804