Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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.


References [Enhancements On Off] (What's this?)

  • [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 $ LD{L^T}$ 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.

Similar Articles

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

American Mathematical Society