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.
- 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 W. C. Davidon, Variable Metric Method for Minimization, Report #ANL-5990, (Rev.) A.N.L. Research and Development Report, 1959.
- 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 & R. B. Schnabel, Least Change Secant Updates for Quasi-Newton Methods, Report #TR78-344, Dept. of Computer Science, Cornell Univ., 1978. 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.
- 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 E. S. Marwil, Exploiting Sparsity in Newton-Like Methods, Ph. D. Thesis, Cornell Univ., 1978.
- 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 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.
- 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 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.
- 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
- © Copyright 1981 American Mathematical Society
- 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