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

Author:
Ph. L. Toint

Journal:
Math. Comp. **37** (1981), 425-433

MSC:
Primary 65F30; Secondary 15A24, 65K10

DOI:
https://doi.org/10.1090/S0025-5718-1981-0628706-6

MathSciNet review:
628706

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**[1]**C. G. Broyden,*A class of methods for solving nonlinear simultaneous equations*, Math. Comp.**19**(1965), 577–593. MR**0198670**, https://doi.org/10.1090/S0025-5718-1965-0198670-6**[2]**W. C. Davidon,*Variable Metric Method for Minimization*, Report #ANL-5990, (Rev.) A.N.L. Research and Development Report, 1959.**[3]**J. E. Dennis Jr. and Jorge J. Moré,*Quasi-Newton methods, motivation and theory*, SIAM Rev.**19**(1977), no. 1, 46–89. MR**0445812**, https://doi.org/10.1137/1019005**[4]**J. E. Dennis & R. B. Schnabel,*Least Change Secant Updates for Quasi-Newton Methods*, Report #TR78-344, Dept. of Computer Science, Cornell Univ., 1978.**[5]**J. E. Dennis & H. F. Walker,*Convergence Theorems for Least Change Secant Update Methods*, Report #TR476-(141-171-163)-2, Dept. of Mathematical Science, Rice University, Houston, 1979.**[6]**Donald Goldfarb,*A family of variable-metric methods derived by variational means*, Math. Comp.**24**(1970), 23–26. MR**0258249**, https://doi.org/10.1090/S0025-5718-1970-0258249-6**[7]**J. Greenstadt,*Variations on variable-metric methods. (With discussion)*, Math. Comp.**24**(1970), 1–22. MR**0258248**, https://doi.org/10.1090/S0025-5718-1970-0258248-4**[8]**H. Y. Huang,*Unified approach to quadratically convergent algorithms for function minimization*, J. Optimization Theory Appl.**5**(1970), 405–423. MR**0288939**, https://doi.org/10.1007/BF00927440**[9]**E. S. Marwil,*Exploiting Sparsity in Newton-Like Methods*, Ph. D. Thesis, Cornell Univ., 1978.**[10]**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810****[11]**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****[12]**M. J. D. Powell,*Quasi-Newton Formulae for Sparse Second Derivative Matrices*, Report #DAMTP 1979/NA7, Dept. of Applied Mathematics and Theoretical Physics, Cambridge University (G.B.), 1979.**[13]**L. K. Schubert,*Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian*, Math. Comp.**24**(1970), 27–30. MR**0258276**, https://doi.org/10.1090/S0025-5718-1970-0258276-9**[14]**D. F. Shanno,*On Variable-Metric Methods for Sparse Hessians, The New Method*, Report #MIS TR 27, Dept. of Management Information Systems, University of Arizona, Tuscon, 1978.**[15]**D. F. Shanno and Kang Hoh Phua,*Matrix conditioning and nonlinear optimization*, Math. Programming**14**(1978), no. 2, 149–160. MR**0474819**, https://doi.org/10.1007/BF01588962**[16]**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**, https://doi.org/10.1090/S0025-5718-1977-0455338-4**[17]**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**, https://doi.org/10.1137/0716076**[18]**Ph. Toint,*A note about sparsity exploiting quasi-Newton updates*, Math. Programming**21**(1981), no. 2, 172–181. MR**623836**, https://doi.org/10.1007/BF01584238

Retrieve articles in *Mathematics of Computation*
with MSC:
65F30,
15A24,
65K10

Retrieve articles in all journals with MSC: 65F30, 15A24, 65K10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1981-0628706-6

Keywords:
Nonlinear optimization,
sparsity,
matrix updating

Article copyright:
© Copyright 1981
American Mathematical Society