A sparse quasiNewton update derived variationally with a nondiagonally weighted Frobenius norm
Author:
Ph. L. Toint
Journal:
Math. Comp. 37 (1981), 425433
MSC:
Primary 65F30; Secondary 15A24, 65K10
MathSciNet review:
628706
Fulltext 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 quasiNewton 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
(33 #6825), http://dx.doi.org/10.1090/S00255718196501986706
 [2]
W. C. Davidon, Variable Metric Method for Minimization, Report #ANL5990, (Rev.) A.N.L. Research and Development Report, 1959.
 [3]
J.
E. Dennis Jr. and Jorge
J. Moré, QuasiNewton methods, motivation and theory,
SIAM Rev. 19 (1977), no. 1, 46–89. MR 0445812
(56 #4146)
 [4]
J. E. Dennis & R. B. Schnabel, Least Change Secant Updates for QuasiNewton Methods, Report #TR78344, Dept. of Computer Science, Cornell Univ., 1978.
 [5]
J. E. Dennis & H. F. Walker, Convergence Theorems for Least Change Secant Update Methods, Report #TR476(141171163)2, Dept. of Mathematical Science, Rice University, Houston, 1979.
 [6]
Donald
Goldfarb, A family of variablemetric methods
derived by variational means, Math. Comp.
24 (1970), 23–26.
MR
0258249 (41 #2896), http://dx.doi.org/10.1090/S00255718197002582496
 [7]
J.
Greenstadt, Variations on variablemetric methods.
(With discussion), Math. Comp. 24 (1970), 1–22. MR 0258248
(41 #2895), http://dx.doi.org/10.1090/S00255718197002582484
 [8]
H.
Y. Huang, Unified approach to quadratically convergent algorithms
for function minimization, J. Optimization Theory Appl.
5 (1970), 405–423. MR 0288939
(44 #6134)
 [9]
E. S. Marwil, Exploiting Sparsity in NewtonLike 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 YorkLondon, 1970. MR 0273810
(42 #8686)
 [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
(42 #7043)
 [12]
M. J. D. Powell, QuasiNewton 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 quasiNewton method
for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 0258276
(41 #2923), http://dx.doi.org/10.1090/S00255718197002582769
 [14]
D. F. Shanno, On VariableMetric 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
(57 #14450)
 [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
(56 #13577), http://dx.doi.org/10.1090/S00255718197704553384
 [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
(81f:65046), http://dx.doi.org/10.1137/0716076
 [18]
Ph.
Toint, A note about sparsity exploiting quasiNewton updates,
Math. Programming 21 (1981), no. 2, 172–181. MR 623836
(82i:90103), http://dx.doi.org/10.1007/BF01584238
 [1]
 C. G. Broyden, "A class of methods for solving nonlinear simultaneous equations," Math. Comp., v. 19, 1965, pp. 577593. MR 0198670 (33:6825)
 [2]
 W. C. Davidon, Variable Metric Method for Minimization, Report #ANL5990, (Rev.) A.N.L. Research and Development Report, 1959.
 [3]
 J. E. Dennis & J. Moré, "QuasiNewton methods, motivation and theory," SIAM Rev., v. 19, 1977, pp. 4689. MR 0445812 (56:4146)
 [4]
 J. E. Dennis & R. B. Schnabel, Least Change Secant Updates for QuasiNewton Methods, Report #TR78344, Dept. of Computer Science, Cornell Univ., 1978.
 [5]
 J. E. Dennis & H. F. Walker, Convergence Theorems for Least Change Secant Update Methods, Report #TR476(141171163)2, Dept. of Mathematical Science, Rice University, Houston, 1979.
 [6]
 D. Goldfarb, "A family of variable metric methods derived by variational means," Math. Comp., v. 24, 1970, pp. 2326. MR 0258249 (41:2896)
 [7]
 J. Greenstadt, "Variations on variable metric methods," Math. Comp., v. 24, 1970, pp. 122. MR 0258248 (41:2895)
 [8]
 H. Y. Huang, "Unified approach to quadratically convergent algorithms for function minimization," J. Optim. Theory Appl., v. 5, 1970, pp. 405423. MR 0288939 (44:6134)
 [9]
 E. S. Marwil, Exploiting Sparsity in NewtonLike Methods, Ph. D. Thesis, Cornell Univ., 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, "A new algorithm for unconstrained optimization," Nonlinear Programming (J. B. Rosen, O. L. Mangasarian and K. Ritter, Eds.), Academic Press, New York, 1970, pp. 3165. MR 0272162 (42:7043)
 [12]
 M. J. D. Powell, QuasiNewton 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 quasiNewton method for nonlinear equations with a sparse Jacobian," Math. Comp., v. 24, 1970, pp. 2730. MR 0258276 (41:2923)
 [14]
 D. F. Shanno, On VariableMetric 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 & K. H. Phua, "Matrix conditioning and nonlinear optimization," Math. Programming, v. 14, 1978, pp. 149160. MR 0474819 (57:14450)
 [16]
 Ph. L. Toint, "On sparse and symmetric updating subject to a linear equation," Math. Comp., v. 31, 1977, pp. 954961. MR 0455338 (56:13577)
 [17]
 Ph. L. Toint, "On the superlinear convergence of an algorithm for solving a sparse minimization problem," SIAM J. Numer. Anal., v. 16, 1979. MR 551324 (81f:65046)
 [18]
 Ph. L. Toint, "A note about sparsity exploiting quasiNewton updates," Math. Programming, v. 21, 1981. MR 623836 (82i:90103)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F30,
15A24,
65K10
Retrieve articles in all journals
with MSC:
65F30,
15A24,
65K10
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198106287066
PII:
S 00255718(1981)06287066
Keywords:
Nonlinear optimization,
sparsity,
matrix updating
Article copyright:
© Copyright 1981
American Mathematical Society
