Factorized variable metric methods for unconstrained optimization
Author:
Donald Goldfarb
Journal:
Math. Comp. 30 (1976), 796811
MSC:
Primary 65K05; Secondary 90C30
MathSciNet review:
0423804
Fulltext PDF Free Access
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 ranktwo correction which maintains symmetry and positive definiteness. These ideas are applied to variable metric (quasiNewton) methods to produce numerically stable algorithms.
 [1]
Yonathan
Bard, On a numerical instability of
Davidonlike methods, Math. Comp. 22 (1968), 665–666. MR 0232533
(38 #858), http://dx.doi.org/10.1090/S00255718196802325335
 [2]
John
M. Bennett, Triangular factors of modified matrices, Numer.
Math. 7 (1965), 217–221. 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, IBMUK 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
(33 #6825), http://dx.doi.org/10.1090/S00255718196501986706
 [5]
C.
G. Broyden, QuasiNewton methods and their
application to function minimisation, Math.
Comp. 21 (1967),
368–381. MR 0224273
(36 #7317), http://dx.doi.org/10.1090/S00255718196702242732
 [6]
C.
G. Broyden, The convergence of a class of doublerank minimization
algorithms. II. The new algorithm, J. Inst. Math. Appl.
6 (1970), 222–231. MR 0433870
(55 #6841)
 [7]
W. C. DAVIDON, Variable Metric Method for Minimization, A.E.C. Res. and Devel. Rep. ANL5990 (Rev.), 1959.
 [8]
William
C. Davidon, Variance algorithm for minimization, Comput. J.
10 (1967/1968), 406–410. MR 0221738
(36 #4790)
 [9]
L.
C. W. Dixon, QuasiNewton algorithms generate identical
points, Math. Programming 2 (1972), 383–387. MR 0303716
(46 #2852)
 [10]
R. FLETCHER, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317322.
 [11]
R. FLETCHER, Fortran Subroutines for Minimization by QuasiNewton Methods, Report R7125, 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
(27 #2096)
 [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
(48 #7575)
 [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
(49 #8299), http://dx.doi.org/10.1090/S00255718197403435586
 [16]
P.
E. Gill and W.
Murray, QuasiNewton methods for unconstrained optimization,
J. Inst. Math. Appl. 9 (1972), 91–108. MR 0300410
(45 #9456)
 [17]
P. E. GILL, W. MURRAY & R. A. PITFIELD, The Implementation of Two Revised QuasiNewton Algorithms for Unconstrained Optimization, NPL Report NAC 11, 1972.
 [18]
Donald
Goldfarb, A family of variablemetric methods
derived by variational means, Math. Comp.
24 (1970), 23–26.
MR
0258249 (41 #2896), http://dx.doi.org/10.1090/S00255718197002582496
 [19]
D. GOLDFARB, Variable Metric and Conjugate Direction Methods in Unconstrained Optimization: Recent Developments, ACM Proceedings1972.
 [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 nonlinear
functions subject to linear constraints, Math. Programming
10 (1976), no. 1, 1–31. MR 0406523
(53 #10310)
 [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
(42 #2806)
 [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
(44 #1442)
 [24]
M.
J. D. Powell, On the convergence of the variable metric
algorithm, J. Inst. Math. Appl. 7 (1971),
21–36. MR
0279977 (43 #5698)
 [25]
D.
F. Shanno, Conditioning of quasiNewton methods
for function minimization, Math. Comp. 24 (1970), 647–656.
MR
0274029 (42 #8905), http://dx.doi.org/10.1090/S0025571819700274029X
 [26]
P. WOLFE, Another Variable Metric Method, IBM working paper.
 [1]
 Y. BARD, "On a numerical instability of Davidonlike methods," Math. Comp, v. 22, 1968, pp. 665666. MR 38 #858. MR 0232533 (38:858)
 [2]
 JOHN M. BENNETT, "Triangular factors of modified matrices," Numer. Math., v. 7, 1965, pp. 217221. 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, IBMUK Scientific Center, Peterlee, 1972.
 [4]
 C. G. BROYDEN, "A class of methods for solving nonlinear simultaneous equations," Math. Comp., v. 19, 1965, pp. 577593. MR 33 #6825. MR 0198670 (33:6825)
 [5]
 C. G. BROYDEN, "QuasiNewton methods and their application to function minimisation," Math. Comp., v. 21, 1967, pp. 368381. MR 36 #7317. MR 0224273 (36:7317)
 [6]
 C. G. BROYDEN, "The convergence of a class of doublerank minimization algorithms 2, The new algorithm," J. Inst. Math. Appl., v. 6, 1970, pp. 222231. MR 0433870 (55:6841)
 [7]
 W. C. DAVIDON, Variable Metric Method for Minimization, A.E.C. Res. and Devel. Rep. ANL5990 (Rev.), 1959.
 [8]
 W. C. DAVIDON, "Variance algorithm for minimization," Comput. J., v. 10, 1967/68, pp. 406410. MR 36 #4790. MR 0221738 (36:4790)
 [9]
 L. C. W. DIXON, "QuasiNewton algorithms generate identical points," Math. Programming, v. 2, 1972, pp. 383387. MR 46 #2852. MR 0303716 (46:2852)
 [10]
 R. FLETCHER, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317322.
 [11]
 R. FLETCHER, Fortran Subroutines for Minimization by QuasiNewton Methods, Report R7125, 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. 163168. 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. CSRR2062, 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. 505535. MR 49 #8299. MR 0343558 (49:8299)
 [16]
 P. E. GILL & W. MURRAY, "QuasiNewton methods for unconstrained optimization," J. Inst. Math. Appl., v. 9, 1972, pp. 91108. MR 45 #9456. MR 0300410 (45:9456)
 [17]
 P. E. GILL, W. MURRAY & R. A. PITFIELD, The Implementation of Two Revised QuasiNewton Algorithms for Unconstrained Optimization, NPL Report NAC 11, 1972.
 [18]
 D. GOLDFARB, "A family of variablemetric methods derived by variational means," Math. Comp., v. 24, 1970, pp. 2326. MR 41 #2896. MR 0258249 (41:2896)
 [19]
 D. GOLDFARB, Variable Metric and Conjugate Direction Methods in Unconstrained Optimization: Recent Developments, ACM Proceedings1972.
 [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. 131. 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. 307325. 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. 215246. 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. 2136. MR 43 #5698. MR 0279977 (43:5698)
 [25]
 D. SHANNO, "Conditioning of quasiNewton methods for function minimization," Math. Comp., v. 24, 1970, pp. 647656. 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:
http://dx.doi.org/10.1090/S00255718197604238042
PII:
S 00255718(1976)04238042
Article copyright:
© Copyright 1976
American Mathematical Society
