An explicit quasiNewton update for sparse optimization calculations
Author:
Angelo Lucia
Journal:
Math. Comp. 40 (1983), 317322
MSC:
Primary 65K05
MathSciNet review:
679448
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A new quasiNewton updating formula for sparse optimization calculations is presented. It makes combined use of a simple strategy for fixing symmetry and a Schubert correction to the upper triangle of a permuted Hessian approximation. Interesting properties of this new update are that it is closed form and that it does not satisfy the secant condition at every iteration of the calculations. Some numerical results are given that show that this update compares favorably with the sparse PSB update and appears to have a superlinear rate of convergence.
 [1]
J.
E. Dennis Jr. and Jorge
J. Moré, A characterization of superlinear
convergence and its application to quasiNewton methods, Math. Comp. 28 (1974), 549–560. MR 0343581
(49 #8322), http://dx.doi.org/10.1090/S00255718197403435811
 [2]
J.
E. Dennis Jr. and R.
B. Schnabel, Least change secant updates for quasiNewton
methods, SIAM Rev. 21 (1979), no. 4,
443–459. MR
545880 (80j:65021), http://dx.doi.org/10.1137/1021091
 [3]
S. C. Eisenstat, M. C. Gursky, M. H. Schultz & A. H. Sherman, Yale Sparse Matrix PackageThe Symmetric Codes, Report No. 112, Dept. of Computer Science, Yale University, New Haven, Conn., 1977.
 [4]
M. D. Hebden, An Algorithm for Minimization Using Exact Second Derivatives, Report No. T.P. 515, A.E.R.E. Harwell, 1973.
 [5]
E. S. Marwil, Exploiting Sparsity in NewtonLike Methods, Ph.D. Thesis, Cornell University, Ithaca, N.Y., 1978.
 [6]
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
 [7]
D.
F. Shanno, On variablemetric methods for sparse
Hessians, Math. Comp. 34
(1980), no. 150, 499–514. MR 559198
(81j:65077), http://dx.doi.org/10.1090/S00255718198005591982
 [8]
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
 [9]
Ph.
L. Toint, Some numerical results using a sparse
matrix updating formula in unconstrained optimization, Math. Comp. 32 (1978), no. 143, 839–851. MR 0483452
(58 #3453), http://dx.doi.org/10.1090/S00255718197804834527
 [1]
 J. E. Dennis & J. J. Moré, "A characterization of superlinear convergence and its application to quasiNewton methods," Math. Comp., v. 28, 1974, pp. 549560. MR 0343581 (49:8322)
 [2]
 J. E. Dennis & R. B. Schnabel, "Least change secant updates for quasiNewton methods," SIAM Rev., v. 21, 1979, pp. 443459. MR 545880 (80j:65021)
 [3]
 S. C. Eisenstat, M. C. Gursky, M. H. Schultz & A. H. Sherman, Yale Sparse Matrix PackageThe Symmetric Codes, Report No. 112, Dept. of Computer Science, Yale University, New Haven, Conn., 1977.
 [4]
 M. D. Hebden, An Algorithm for Minimization Using Exact Second Derivatives, Report No. T.P. 515, A.E.R.E. Harwell, 1973.
 [5]
 E. S. Marwil, Exploiting Sparsity in NewtonLike Methods, Ph.D. Thesis, Cornell University, Ithaca, N.Y., 1978.
 [6]
 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)
 [7]
 D. F. Shanno, "On variable metric methods for sparse Hessians," Math. Comp., v. 34, 1980, pp. 499514. MR 559198 (81j:65077)
 [8]
 Ph. L. Toint, "On sparse and symmetric matrix updating subject to a linear equation," Math. Comp., v. 31, 1977, pp. 954961. MR 0455338 (56:13577)
 [9]
 Ph. L. Toint, "Some numerical results using a sparse matrix updating formula in unconstrained optimization," Math. Comp., v. 32, 1978, pp. 839851. MR 0483452 (58:3453)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65K05
Retrieve articles in all journals
with MSC:
65K05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198306794484
PII:
S 00255718(1983)06794484
Article copyright:
© Copyright 1983
American Mathematical Society
