Factorized variable metric methods for unconstrained optimization

Author:
Donald Goldfarb

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

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

**[1]**Yonathan Bard,*On a numerical instability of Davidon-like methods*, Math. Comp.**22**(1968), 665–666. MR**0232533**, https://doi.org/10.1090/S0025-5718-1968-0232533-5**[2]**John M. Bennett,*Triangular factors of modified matrices*, Numer. Math.**7**(1965), 217–221. MR**0177503**, https://doi.org/10.1007/BF01436076**[3]**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.**[4]**C. G. Broyden,*A class of methods for solving nonlinear simultaneous equations*, Math. Comp.**19**(1965), 577–593. MR**0198670**, https://doi.org/10.1090/S0025-5718-1965-0198670-6**[5]**C. G. Broyden,*Quasi-Newton methods and their application to function minimisation*, Math. Comp.**21**(1967), 368–381. MR**0224273**, https://doi.org/10.1090/S0025-5718-1967-0224273-2**[6]**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**0433870****[7]**W. C. DAVIDON,*Variable Metric Method for Minimization*, A.E.C. Res. and Devel. Rep. ANL-5990 (Rev.), 1959.**[8]**William C. Davidon,*Variance algorithm for minimization*, Comput. J.**10**(1967/1968), 406–410. MR**0221738**, https://doi.org/10.1093/comjnl/10.4.406**[9]**L. C. W. Dixon,*Quasi-Newton algorithms generate identical points*, Math. Programming**2**(1972), 383–387. MR**0303716**, https://doi.org/10.1007/BF01584554**[10]**R. FLETCHER, "A new approach to variable metric algorithms,"*Comput. J.*, v. 13, 1970, pp. 317-322.**[11]**R. FLETCHER,*Fortran Subroutines for Minimization by Quasi-Newton Methods*, Report R-7125, A.E.R.E., Harwell, England, 1972.**[12]**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**[13]**R. FLETCHER & M. J. D. POWELL,*On the Modification of**Factorizations*, Harwell Report TP. 519, 1973.**[14]**W. Morven Gentleman,*Least squares computations by Givens transformations without square roots*, J. Inst. Math. Appl.**12**(1973), 329–336. MR**0329233****[15]**P. E. Gill, G. H. Golub, W. Murray, and M. A. Saunders,*Methods for modifying matrix factorizations*, Math. Comp.**28**(1974), 505–535. MR**0343558**, https://doi.org/10.1090/S0025-5718-1974-0343558-6**[16]**P. E. Gill and W. Murray,*Quasi-Newton methods for unconstrained optimization*, J. Inst. Math. Appl.**9**(1972), 91–108. MR**0300410****[17]**P. E. GILL, W. MURRAY & R. A. PITFIELD,*The Implementation of Two Revised Quasi-Newton Algorithms for Unconstrained Optimization*, NPL Report NAC 11, 1972.**[18]**Donald Goldfarb,*A family of variable-metric methods derived by variational means*, Math. Comp.**24**(1970), 23–26. MR**0258249**, https://doi.org/10.1090/S0025-5718-1970-0258249-6**[19]**D. GOLDFARB,*Variable Metric and Conjugate Direction Methods in Unconstrained Optimization*:*Recent Developments*, ACM Proceedings--1972.**[20]**D. GOLDFARB,*Factorized Variable Metric Methods for Unconstrined Optimization*, IBM Res. Rep. RC 4415, IBM Research Center, Yorktown Heights, New York, 1973.**[21]**Donald Goldfarb,*Matrix factorizations in optimization of non-linear functions subject to linear constraints*, Math. Programming**10**(1976), no. 1, 1–31. MR**0406523**, https://doi.org/10.1007/BF01580651**[22]**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****[23]**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****[24]**M. J. D. Powell,*On the convergence of the variable metric algorithm*, J. Inst. Math. Appl.**7**(1971), 21–36. MR**0279977****[25]**D. F. Shanno,*Conditioning of quasi-Newton methods for function minimization*, Math. Comp.**24**(1970), 647–656. MR**0274029**, https://doi.org/10.1090/S0025-5718-1970-0274029-X**[26]**P. WOLFE,*Another Variable Metric Method*, IBM working paper.

Retrieve articles in *Mathematics of Computation*
with MSC:
65K05,
90C30

Retrieve articles in all journals with MSC: 65K05, 90C30

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1976-0423804-2

Article copyright:
© Copyright 1976
American Mathematical Society