On the sparse and symmetric least-change secant update

Steihaug, Trond

doi:10.1090/S0025-5718-1984-0736450-2

On the sparse and symmetric least-change secant update
HTML articles powered by AMS MathViewer

by Trond Steihaug PDF

Math. Comp. 42 (1984), 521-533 Request permission

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

Owe Axelsson, Solution of linear systems of equations: iterative methods, Sparse matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976) Lecture Notes in Math., Vol. 572, Springer, Berlin, 1977, pp. 1–51. MR 0448834
Ȧ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, DOI 10.1007/BF01930845
C. G. Broyden, J. E. Dennis Jr., and Jorge J. Moré, On the local and superlinear convergence of quasi-Newton methods, J. Inst. Math. Appl. 12 (1973), 223–245. MR 341853
Ron S. Dembo, Stanley C. Eisenstat, and Trond Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (1982), no. 2, 400–408. MR 650059, DOI 10.1137/0719025
J. E. Dennis Jr. and Jorge J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp. 28 (1974), 549–560. MR 343581, DOI 10.1090/S0025-5718-1974-0343581-1
J. E. Dennis Jr. and Jorge J. Moré, Quasi-Newton methods, motivation and theory, SIAM Rev. 19 (1977), no. 1, 46–89. MR 445812, DOI 10.1137/1019005
J. E. Dennis Jr. and R. B. Schnabel, Least change secant updates for quasi-Newton methods, SIAM Rev. 21 (1979), no. 4, 443–459. MR 545880, DOI 10.1137/1021091

Local Analysis of Inexact Quasi-Newton Methods

Exploiting Sparsity in Newton-Like Methods

J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
M. J. D. Powell, Convergence properties of a class of minimization algorithms, Nonlinear programming, 2 (Proc. Special Interest Group on Math. Programming Sympos., Univ. Wisconsin, Madison, Wis., 1974) Academic Press, New York, 1974, pp. 1–27. MR 0386270

Quasi-Newton Methods for Large Scale Nonlinear Problems

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, DOI 10.1137/0720042

Damped Inexact Quasi-Newton Methods

Ph. L. Toint, On sparse and symmetric matrix updating subject to a linear equation, Math. Comp. 31 (1977), no. 140, 954–961. MR 455338, DOI 10.1090/S0025-5718-1977-0455338-4
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, DOI 10.1137/0716076