On the sparse and symmetric leastchange secant update
Author:
Trond Steihaug
Journal:
Math. Comp. 42 (1984), 521533
MSC:
Primary 65H05; Secondary 65F50
MathSciNet review:
736450
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: To find the sparse and symmetric n by n leastchange secant update we have to solve a consistent linear system of n equations in n unknowns, where the coefficient matrix is symmetric and positive semidefinite. We give bounds on the eigenvalues of the coefficient matrix and show that the preconditioned conjugate gradient method is a very efficient method for solving the linear equation. By solving the linear system only approximately, we generate a family of sparse and symmetric updates with a residual in the secant equation. We address the question of how accurate a solution is needed not to impede the convergence of quasiNewton methods using the approximate leastchange update. We show that the quasiNewton methods are locally and superlinearly convergent after one or more preconditioned conjugate gradient iterations.
 [1]
Owe
Axelsson, Solution of linear systems of equations: iterative
methods, Sparse matrix techniques (Adv. Course, Technical Univ.
Denmark, Copenhagen, 1976) Springer, Berlin, 1977, pp. 1–51.
Lecture Notes in Math., Vol. 572. MR 0448834
(56 #7139)
 [2]
Ȧke
Björck and Tommy
Elfving, Accelerated projection methods for computing pseudoinverse
solutions of systems of linear equations, BIT 19
(1979), no. 2, 145–163. MR 537775
(80e:65048), http://dx.doi.org/10.1007/BF01930845
 [3]
C.
G. Broyden, J.
E. Dennis Jr., and Jorge
J. Moré, On the local and superlinear convergence of
quasiNewton methods, J. Inst. Math. Appl. 12 (1973),
223–245. MR 0341853
(49 #6599)
 [4]
Ron
S. Dembo, Stanley
C. Eisenstat, and Trond
Steihaug, Inexact Newton methods, SIAM J. Numer. Anal.
19 (1982), no. 2, 400–408. MR 650059
(83b:65056), http://dx.doi.org/10.1137/0719025
 [5]
J.
E. Dennis Jr. and Jorge
J. Moré, A characterization of superlinear
convergence and its application to quasiNewton methods, Math. Comp. 28 (1974), 549–560. MR 0343581
(49 #8322), http://dx.doi.org/10.1090/S00255718197403435811
 [6]
J.
E. Dennis Jr. and Jorge
J. Moré, QuasiNewton methods, motivation and theory,
SIAM Rev. 19 (1977), no. 1, 46–89. MR 0445812
(56 #4146)
 [7]
J.
E. Dennis Jr. and R.
B. Schnabel, Least change secant updates for quasiNewton
methods, SIAM Rev. 21 (1979), no. 4,
443–459. MR
545880 (80j:65021), http://dx.doi.org/10.1137/1021091
 [8]
S. C. Eisenstat & T. Steihaug, Local Analysis of Inexact QuasiNewton Methods, Department of Mathematical Sciences TR 827, Rice University, Houston, 1982.
 [9]
E. S. Marwil, Exploiting Sparsity in NewtonLike Methods, Ph.D. Thesis, Cornell University, Computer Science Research Report TR 78335, 1978.
 [10]
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New YorkLondon, 1970. MR 0273810
(42 #8686)
 [11]
M.
J. D. Powell, Convergence properties of a class of minimization
algorithms, Nonlinear programming, 2 (Proc. Sympos. Special Interest
Group on Math. Programming, Univ. Wisconsin, Madison, Wis., 1974)
Academic Press, New York, 1974, pp. 1–27. MR 0386270
(52 #7128)
 [12]
T. Steihaug, QuasiNewton Methods for Large Scale Nonlinear Problems, Ph.D. Thesis, Yale University, SOM Technical Report #49, 1980.
 [13]
Trond
Steihaug, The conjugate gradient method and trust regions in large
scale optimization, SIAM J. Numer. Anal. 20 (1983),
no. 3, 626–637. MR 701102
(84g:49047), http://dx.doi.org/10.1137/0720042
 [14]
T. Steihaug, Damped Inexact QuasiNewton Methods, Department of Mathematical Sciences TR 813, Rice University, Houston, 1981.
 [15]
Ph.
L. Toint, On sparse and symmetric matrix
updating subject to a linear equation, Math.
Comp. 31 (1977), no. no 140, 954–961. MR 0455338
(56 #13577), http://dx.doi.org/10.1090/S00255718197704553384
 [16]
Ph.
Toint, On the superlinear convergence of an algorithm for solving a
sparse minimization problem, SIAM J. Numer. Anal. 16
(1979), no. 6, 1036–1045. MR 551324
(81f:65046), http://dx.doi.org/10.1137/0716076
 [1]
 O. Axelsson, "Solution of linear systems of equations: iterative methods," Sparse Matrix Techniques (V. A. Barker, ed.), Lecture Notes in Math., vol. 572, SpringerVerlag, New York, 1976, pp. 151. MR 0448834 (56:7139)
 [2]
 A. Björk & T. Elfving, "Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations," BIT, v. 19, 1979, pp. 145163. MR 537775 (80e:65048)
 [3]
 C. G. Broyden, J. E. Dennis, Jr. & J. J. Moré, "On the local and superlinear convergence of quasiNewton methods," J. Inst. Math. Appl., v. 12, 1973, pp. 223245. MR 0341853 (49:6599)
 [4]
 R. S. Dembo, S. C. Eisenstat & T. Steihaug, "Inexact Newton methods," SIAM J. Numer. Anal., v. 19, 1982, pp. 400408. MR 650059 (83b:65056)
 [5]
 J. E. Dennis, Jr. & J. J. Moré, "A characterization of superlinear convergence and its application to quasiNewton methods," Math. Comp., v. 28, 1974, pp. 549560. MR 0343581 (49:8322)
 [6]
 J. E. Dennis, Jr. & J. J. Moré, "QuasiNewton methods, motivation and theory," SIAM Rev., v. 19, 1977, pp. 4689. MR 0445812 (56:4146)
 [7]
 J. E. Dennis, Jr. & R. B. Schnabel, "Least change secant updates for quasiNewton methods," SIAM Rev., v. 21, 1979, pp. 443459. MR 545880 (80j:65021)
 [8]
 S. C. Eisenstat & T. Steihaug, Local Analysis of Inexact QuasiNewton Methods, Department of Mathematical Sciences TR 827, Rice University, Houston, 1982.
 [9]
 E. S. Marwil, Exploiting Sparsity in NewtonLike Methods, Ph.D. Thesis, Cornell University, Computer Science Research Report TR 78335, 1978.
 [10]
 J. M. Ortega & W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. MR 0273810 (42:8686)
 [11]
 M. J. D. Powell, "Convergence properties of a class of minimization algorithms," Nonlinear Programming, Vol. 2 (O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, eds.), Academic Press, New York, 1975, pp. 127. MR 0386270 (52:7128)
 [12]
 T. Steihaug, QuasiNewton Methods for Large Scale Nonlinear Problems, Ph.D. Thesis, Yale University, SOM Technical Report #49, 1980.
 [13]
 T. Steihaug, "The conjugate gradient method and trust regions in large scale optimization," SIAM J. Numer. Anal., v. 20, 1983, pp. 626637. MR 701102 (84g:49047)
 [14]
 T. Steihaug, Damped Inexact QuasiNewton Methods, Department of Mathematical Sciences TR 813, Rice University, Houston, 1981.
 [15]
 P. L. Toint, "On sparse and symmetric matrix updating subject to a linear equation," Math. Comp., v. 31, 1977, pp. 954961. MR 0455338 (56:13577)
 [16]
 P. L. Toint, "On the superlinear convergence of an algorithm for solving a sparse minimization problem," SIAM J. Numer. Anal., v. 16, 1979, pp. 10361045. MR 551324 (81f:65046)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65H05,
65F50
Retrieve articles in all journals
with MSC:
65H05,
65F50
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198407364502
PII:
S 00255718(1984)07364502
Article copyright:
© Copyright 1984
American Mathematical Society
