On sparse and symmetric matrix updating subject to a linear equation
Author:
Ph. L. Toint
Journal:
Math. Comp. 31 (1977), 954961
MSC:
Primary 65F30
MathSciNet review:
0455338
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A procedure for symmetric matrix updating subject to a linear equation and retaining any sparsity present in the original matrix is derived. The main feature of this procedure is the reduction of the problem to the solution of an n dimensional sparse system of linear equations. The matrix of this system is shown to be symmetric and positive definite. The method depends on the Frobenius matrix norm. Comments are made on the difficulties of extending the technique so that it uses more general norms, the main points being shown by a numerical example.
 [1]
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
 [2]
W. C. DAVIDON, Variable Metric Method for Minimization, Report #ANL5990 (Rev.), A.N.L. Research and Development Report, 1959.
 [3]
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)
 [4]
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
 [5]
J.
Greenstadt, Variations on variablemetric methods.
(With discussion), Math. Comp. 24 (1970), 1–22. MR 0258248
(41 #2895), http://dx.doi.org/10.1090/S00255718197002582484
 [6]
H.
Y. Huang, Unified approach to quadratically convergent algorithms
for function minimization, J. Optimization Theory Appl.
5 (1970), 405–423. MR 0288939
(44 #6134)
 [7]
M.
J. D. Powell, A new algorithm for unconstrained optimization,
Nonlinear Programming (Proc. Sympos., Univ. of Wisconsin, Madison, Wis.,
1970) Academic Press, New York, 1970, pp. 31–65. MR 0272162
(42 #7043)
 [8]
J. K. REID, Two Fortran Subroutines for Direct Solution of Linear Equations Whose Matrix is Sparse, Symmetric and Positive Definite, Report AERER. 7119, Harwell, 1972.
 [9]
L.
K. Schubert, Modification of a quasiNewton method
for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 0258276
(41 #2923), http://dx.doi.org/10.1090/S00255718197002582769
 [1]
 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)
 [2]
 W. C. DAVIDON, Variable Metric Method for Minimization, Report #ANL5990 (Rev.), A.N.L. Research and Development Report, 1959.
 [3]
 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)
 [4]
 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)
 [5]
 J. GREENSTADT, "Variations on variablemetric methods," Math. Comp., v. 24, 1970, pp. 122. MR 41 #2895. MR 0258248 (41:2895)
 [6]
 H. Y. HUANG, "Unified approach to quadratically convergent algorithms for function minimization," J. Optimization Theory Appl., v. 5, 1970, pp. 405423. MR 44 #6134. MR 0288939 (44:6134)
 [7]
 M. J. D. POWELL, "A new algorithm for unconstrained optimization," Nonlinear Programming (J. B. ROSEN, O. L. MANGASARIAN & K. RITTER, Editors), Academic Press, New York, 1970, pp. 3165. MR 42 #7043. MR 0272162 (42:7043)
 [8]
 J. K. REID, Two Fortran Subroutines for Direct Solution of Linear Equations Whose Matrix is Sparse, Symmetric and Positive Definite, Report AERER. 7119, Harwell, 1972.
 [9]
 L. K. SCHUBERT, "Modification of a quasiNewton method for nonlinear equations with a sparse Jacobian," Math. Comp., v. 24, 1970, pp. 2730. MR 41 #2923. MR 0258276 (41:2923)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F30
Retrieve articles in all journals
with MSC:
65F30
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197704553384
PII:
S 00255718(1977)04553384
Keywords:
Matrix updating,
quasiNewton methods,
unconstrained optimization
Article copyright:
© Copyright 1977
American Mathematical Society
