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]**Y. BARD, "On a numerical instability of Davidon-like methods,"*Math. Comp*, v. 22, 1968, pp. 665-666. MR**38**#858. MR**0232533 (38:858)****[2]**JOHN M. BENNETT, "Triangular factors of modified matrices,"*Numer. Math.*, v. 7, 1965, pp. 217-221. MR**31**#1766. MR**0177503 (31:1766)****[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.*, v. 19, 1965, pp. 577-593. MR**33**#6825. MR**0198670 (33:6825)****[5]**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)****[6]**C. G. BROYDEN, "The convergence of a class of double-rank minimization algorithms 2, The new algorithm,"*J. Inst. Math. Appl.*, v. 6, 1970, pp. 222-231. MR**0433870 (55:6841)****[7]**W. C. DAVIDON,*Variable Metric Method for Minimization*, A.E.C. Res. and Devel. Rep. ANL-5990 (Rev.), 1959.**[8]**W. C. DAVIDON, "Variance algorithm for minimization,"*Comput. J.*, v. 10, 1967/68, pp. 406-410. MR**36**#4790. MR**0221738 (36:4790)****[9]**L. C. W. DIXON, "Quasi-Newton algorithms generate identical points,"*Math. Programming*, v. 2, 1972, pp. 383-387. MR**46**#2852. MR**0303716 (46:2852)****[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 & 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)****[13]**R. FLETCHER & M. J. D. POWELL,*On the Modification of**Factorizations*, Harwell Report TP. 519, 1973.**[14]**W. M. GENTLEMAN,*Least Squares Computations by Givens Transformations Without Square Roots*, Res. Rep. CSRR-2062, Univ. of Waterloo, Waterloo, Ont., Canada, 1973. MR**0329233 (48:7575)****[15]**P. E. GILL, G. H. GOLUB, W. MURRAY & M. A. SAUNDERS, "Methods for modifying matrix factorizations,"*Math. Comp.*, v. 28, 1974, pp. 505-535. MR**49**#8299. MR**0343558 (49:8299)****[16]**P. E. GILL & W. MURRAY, "Quasi-Newton methods for unconstrained optimization,"*J. Inst. Math. Appl.*, v. 9, 1972, pp. 91-108. MR**45**#9456. MR**0300410 (45:9456)****[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]**D. GOLDFARB, "A family of variable-metric methods derived by variational means,"*Math. Comp.*, v. 24, 1970, pp. 23-26. MR**41**#2896. MR**0258249 (41:2896)****[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]**D. GOLDFARB, "Matrix factorizations in optimization of nonlinear functions subject to linear constraints,"*Math. Programming*, v. 10, 1976, pp. 1-31. MR**0406523 (53:10310)****[22]**G. P. McCORMICK & J. D. PEARSON, "Variable metric methods and unconstrained optimization,"*Optimization*(Sympos., Univ. Keele, 1968), (R. Fletcher, Editor), Academic Press, London, 1969, pp. 307-325. MR**42**#2806. MR**0267905 (42:2806)****[23]**B. A. MURTAGH & R. W. H. SARGENT, "A constrained minimization method with quadratic convergence,"*Optimization*(Sympos., Univ. Keele, 1968), (R. Fletcher, Editor), Academic Press, London, 1969, pp. 215-246. MR**44**#1442. MR**0284213 (44:1442)****[24]**M. J. D. POWELL, "On the convergence of the variable metric algorithm,"*J. Inst. Math. Appl.*, v. 7, 1971, pp. 21-36. MR**43**#5698. MR**0279977 (43:5698)****[25]**D. SHANNO, "Conditioning of quasi-Newton methods for function minimization,"*Math. Comp.*, v. 24, 1970, pp. 647-656. MR**42**#8905. MR**0274029 (42:8905)****[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