Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On the sparse and symmetric least-change secant update

Author: Trond Steihaug
Journal: Math. Comp. 42 (1984), 521-533
MSC: Primary 65H05; Secondary 65F50
MathSciNet review: 736450
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: To find the sparse and symmetric n by n least-change 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 quasi-Newton methods using the approximate least-change update. We show that the quasi-Newton methods are locally and superlinearly convergent after one or more preconditioned conjugate gradient iterations.

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

  • [1] O. Axelsson, "Solution of linear systems of equations: iterative methods," Sparse Matrix Techniques (V. A. Barker, ed.), Lecture Notes in Math., vol. 572, Springer-Verlag, New York, 1976, pp. 1-51. 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. 145-163. MR 537775 (80e:65048)
  • [3] C. G. Broyden, J. E. Dennis, Jr. & J. J. Moré, "On the local and superlinear convergence of quasi-Newton methods," J. Inst. Math. Appl., v. 12, 1973, pp. 223-245. MR 0341853 (49:6599)
  • [4] R. S. Dembo, S. C. Eisenstat & T. Steihaug, "Inexact Newton methods," SIAM J. Numer. Anal., v. 19, 1982, pp. 400-408. MR 650059 (83b:65056)
  • [5] J. E. Dennis, Jr. & J. J. Moré, "A characterization of superlinear convergence and its application to quasi-Newton methods," Math. Comp., v. 28, 1974, pp. 549-560. MR 0343581 (49:8322)
  • [6] J. E. Dennis, Jr. & J. J. Moré, "Quasi-Newton methods, motivation and theory," SIAM Rev., v. 19, 1977, pp. 46-89. MR 0445812 (56:4146)
  • [7] J. E. Dennis, Jr. & R. B. Schnabel, "Least change secant updates for quasi-Newton methods," SIAM Rev., v. 21, 1979, pp. 443-459. MR 545880 (80j:65021)
  • [8] S. C. Eisenstat & T. Steihaug, Local Analysis of Inexact Quasi-Newton Methods, Department of Mathematical Sciences TR 82-7, Rice University, Houston, 1982.
  • [9] E. S. Marwil, Exploiting Sparsity in Newton-Like Methods, Ph.D. Thesis, Cornell University, Computer Science Research Report TR 78-335, 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. 1-27. MR 0386270 (52:7128)
  • [12] T. Steihaug, Quasi-Newton 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. 626-637. MR 701102 (84g:49047)
  • [14] T. Steihaug, Damped Inexact Quasi-Newton Methods, Department of Mathematical Sciences TR 81-3, 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. 954-961. 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. 1036-1045. 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

Article copyright: © Copyright 1984 American Mathematical Society

American Mathematical Society