A sparse quasi-Newton update derived variationally with a nondiagonally weighted Frobenius norm

Toint, Ph. L.

doi:10.1090/S0025-5718-1981-0628706-6

A sparse quasi-Newton update derived variationally with a nondiagonally weighted Frobenius norm
HTML articles powered by AMS MathViewer

by Ph. L. Toint PDF

Math. Comp. 37 (1981), 425-433 Request permission

Abstract:

The problem of symmetric sparse updating is considered from a variational point of view and a new class of sparse symmetric quasi-Newton updating formulae is derived. This class results from the use of a nondiagonally weighted Frobenius norm. The computation of the update involves only one positive definite and symmetric linear system that has the same sparsity pattern as the problem itself.

References

C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math. Comp. 19 (1965), 577–593. MR 198670, DOI 10.1090/S0025-5718-1965-0198670-6

Variable Metric Method for Minimization

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

Least Change Secant Updates for Quasi-Newton Methods

Convergence Theorems for Least Change Secant Update Methods

Donald Goldfarb, A family of variable-metric methods derived by variational means, Math. Comp. 24 (1970), 23–26. MR 258249, DOI 10.1090/S0025-5718-1970-0258249-6
J. Greenstadt, Variations on variable-metric methods. (With discussion), Math. Comp. 24 (1970), 1–22. MR 258248, DOI 10.1090/S0025-5718-1970-0258248-4
H. Y. Huang, Unified approach to quadratically convergent algorithms for function minimization, J. Optim. Theory Appl. 5 (1970), 405–423. MR 288939, DOI 10.1007/BF00927440

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, 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

Quasi-Newton Formulae for Sparse Second Derivative Matrices

L. K. Schubert, Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 258276, DOI 10.1090/S0025-5718-1970-0258276-9

On Variable-Metric Methods for Sparse Hessians, The New Method

D. F. Shanno and Kang Hoh Phua, Matrix conditioning and nonlinear optimization, Math. Programming 14 (1978), no. 2, 149–160. MR 474819, DOI 10.1007/BF01588962
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
Ph. Toint, A note about sparsity exploiting quasi-Newton updates, Math. Programming 21 (1981), no. 2, 172–181. MR 623836, DOI 10.1007/BF01584238