On variablemetric methods for sparse Hessians
Author:
D. F. Shanno
Journal:
Math. Comp. 34 (1980), 499514
MSC:
Primary 65K10; Secondary 15A57, 90C30
MathSciNet review:
559198
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The relationship between variablemetric methods derived by norm minimization and those derived by symmetrization of rankone updates for sparse systems is studied, and an analogue of Dennis's nonsparse symmetrization formula derived. A new method of using norm minimization to produce a sparse analogue of any nonsparse variablemetric method is proposed. The sparse BFGS generated by this method is tested against the sparse PSB and variablememory conjugate gradient methods, with computational experience uniformly favoring the sparse BFGS.
 [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]
C.
G. Broyden, The convergence of a class of doublerank minimization
algorithms. II. The new algorithm, J. Inst. Math. Appl.
6 (1970), 222–231. MR 0433870
(55 #6841)
 [3]
A. BUCKLEY, A Combined ConjugateGradient QuasiNewton Minimization Algorithm, Working Paper, Mathematics Department, Concordia University, Montreal, Quebec, Canada, 1977.
 [4]
W. C. DAVIDON, Variable Metric Method for Minimization, Report ANL5990 Rev (1959), Argonne National Laboratories, Argonne, Ill., 1959.
 [5]
J. E. DENNIS, ``On some methods based on Broyden's secant approximation to the Hessian,'' Numerical Methods for Nonlinear Optimization (F. A. Lootsma, Ed.), Academic Press, London, 1972, pp. 1934.
 [6]
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
 [7]
Anthony
V. Fiacco and Garth
P. McCormick, Nonlinear programming: Sequential unconstrained
minimization techniques, John Wiley and Sons, Inc., New
YorkLondonSydney, 1968. MR 0243831
(39 #5152)
 [8]
R.
Fletcher and M.
J. D. Powell, A rapidly convergent descent method for
minimization, Comput. J. 6 (1963/1964),
163–168. MR 0152116
(27 #2096)
 [9]
R. FLETCHER, ``A new approach to variable metric algorithms,'' Comput. J., v. 13, 1970, pp. 317322.
 [10]
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
 [11]
D.
Goldfarb, Generating conjugate directions without line searches
using factorized variable metric updating formulas, Math. Programming
13 (1977), no. 1, 94–110. MR 0503799
(58 #20447)
 [12]
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
 [13]
M. D. HEBDEN, An Algorithm for Minimization Using Exact Second Derivatives, Report T. P. 515, AERE, Harwell, 1973.
 [14]
E. S. MARWIL, Exploiting Sparsity in NewtonLike Methods, Report TR78335, Dept. of Computer Science, Cornell University, Ithaca, New York, 1978.
 [15]
J. J. MORÉ, B. S. GARBOW & K. E. HILLSTROM, Testing Unconstrained Optimization Software, Report TM324, Applied Mathematics Division, Argonne National Laboratory, Argonne, Ill., 1978.
 [16]
Jorge
J. Moré and Danny
C. Sorensen, On the use of directions of negative curvature in a
modified Newton method, Math. Programming 16 (1979),
no. 1, 1–20. MR 517757
(80b:90119), http://dx.doi.org/10.1007/BF01582091
 [17]
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)
 [18]
R. B. SCHNABEL, Analyzing and Improving QuasiNewton Methods for Unconstrained Optimization, Report TR77320, Dept. of Computer Science, Cornell University, Ithaca, New York, 1977.
 [19]
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
 [20]
D.
F. Shanno, Conditioning of quasiNewton methods
for function minimization, Math. Comp. 24 (1970), 647–656.
MR
0274029 (42 #8905), http://dx.doi.org/10.1090/S0025571819700274029X
 [21]
David
F. Shanno, Conjugate gradient methods with inexact searches,
Math. Oper. Res. 3 (1978), no. 3, 244–256. MR 506662
(80d:65082), http://dx.doi.org/10.1287/moor.3.3.244
 [22]
D.
F. Shanno and K.
H. Phua, Numerical comparison of several variablemetric
algorithms, J. Optim. Theory Appl. 25 (1978),
no. 4, 507–518. MR 0525744
(58 #26017)
 [23]
D. F. SHANNO & K. H. PHUA, ``Minimization of unconstrained multivariate functions,'' ACM Trans. Math. Software, v. 2, 1976, pp. 8794.
 [24]
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
 [25]
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]
 C. G. BROYDEN, ``A class of methods for solving nonlinear simultaneous equations,'' Math. Comp., v. 19, 1965, pp. 577593. MR 0198670 (33:6825)
 [2]
 C. G. BROYDEN, ``The convergence of a class of double rank minimization algorithms 2, the new algorithm,'' J. Inst. Math. Appl., v. 6, 1970, pp. 222231. MR 0433870 (55:6841)
 [3]
 A. BUCKLEY, A Combined ConjugateGradient QuasiNewton Minimization Algorithm, Working Paper, Mathematics Department, Concordia University, Montreal, Quebec, Canada, 1977.
 [4]
 W. C. DAVIDON, Variable Metric Method for Minimization, Report ANL5990 Rev (1959), Argonne National Laboratories, Argonne, Ill., 1959.
 [5]
 J. E. DENNIS, ``On some methods based on Broyden's secant approximation to the Hessian,'' Numerical Methods for Nonlinear Optimization (F. A. Lootsma, Ed.), Academic Press, London, 1972, pp. 1934.
 [6]
 J. E. DENNIS, JR. & R. B. SCHNABEL, Least Change Secant Updates for QuasiNewton Methods, Report CSCU13278, Dept. of Computer Science, University of Colorado, Boulder, July, 1978. MR 545880 (80j:65021)
 [7]
 A. V. FIACCO & G. P. MCCORMICK, Nonlinear Programming, Sequential Unconstrained Minimization Techniques, Wiley, New York, 1968, pp. 170172. MR 0243831 (39:5152)
 [8]
 R. FLETCHER & M. J. D. POWELL, ``A rapidly convergent descent method for minimization,'' Comput. J., v. 6, 1963, pp. 163168. MR 0152116 (27:2096)
 [9]
 R. FLETCHER, ``A new approach to variable metric algorithms,'' Comput. J., v. 13, 1970, pp. 317322.
 [10]
 D. GOLDFARB, ``A family of variablemetric methods derived by variational means,'' Math. Comp., v. 24, 1970, pp. 2326. MR 0258249 (41:2896)
 [11]
 D. GOLDFARB, ``Generating conjugate directions without line searches using factorized variablemetric updating formulas,'' Math. Programming, v. 13, 1977, pp. 94110. MR 0503799 (58:20447)
 [12]
 J. GREENSTADT, ``Variations on variablemetric methods,'' Math. Comp., v. 24, 1970, pp. 122. MR 0258248 (41:2895)
 [13]
 M. D. HEBDEN, An Algorithm for Minimization Using Exact Second Derivatives, Report T. P. 515, AERE, Harwell, 1973.
 [14]
 E. S. MARWIL, Exploiting Sparsity in NewtonLike Methods, Report TR78335, Dept. of Computer Science, Cornell University, Ithaca, New York, 1978.
 [15]
 J. J. MORÉ, B. S. GARBOW & K. E. HILLSTROM, Testing Unconstrained Optimization Software, Report TM324, Applied Mathematics Division, Argonne National Laboratory, Argonne, Ill., 1978.
 [16]
 J. J. MORÉ & D. C. SORENSEN, On the Use of Directions of Negative Curvature in a Modified Newton Method, Report TM319, Applied Mathematics Division, Argonne National Laboratory, Argonne, Ill., 1977. MR 517757 (80b:90119)
 [17]
 M. J. D. POWELL, ``A new algorithm for unconstrained optimization,'' Nonlinear Programming (J. B. Rosen, O. L. Mangasarian & K. Ritter, Eds.), Academic Press, New York, 1970. MR 0272162 (42:7043)
 [18]
 R. B. SCHNABEL, Analyzing and Improving QuasiNewton Methods for Unconstrained Optimization, Report TR77320, Dept. of Computer Science, Cornell University, Ithaca, New York, 1977.
 [19]
 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)
 [20]
 D. F. SHANNO, ``Conditioning of quasiNewton methods for function minimization,'' Math. Comp., v. 24, 1970, pp. 647656. MR 0274029 (42:8905)
 [21]
 D. F. SHANNO, ``Conjugate gradient methods with inexact searches,'' Math. Oper. Res., v. 3, 1978, pp. 244256. MR 506662 (80d:65082)
 [22]
 D. F. SHANNO & K. H. PHUA, ``Numerical comparison of several variablemetric algorithms,'' J. Optim. Theory Appl., v. 25, 1978, pp. 507518. MR 0525744 (58:26017)
 [23]
 D. F. SHANNO & K. H. PHUA, ``Minimization of unconstrained multivariate functions,'' ACM Trans. Math. Software, v. 2, 1976, pp. 8794.
 [24]
 PH. L. TOINT, ``On sparse and symmetric updating subject to a linear equation,'' Math. Comp., v. 31, 1977, pp. 954961. MR 0455338 (56:13577)
 [25]
 PH. L. TOINT, ``Some numerical results using a sparse matrix updating formula in unconstrained optimization,'' Math. Comp., v. 32, 1978, pp. 839852. MR 0483452 (58:3453)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65K10,
15A57,
90C30
Retrieve articles in all journals
with MSC:
65K10,
15A57,
90C30
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198005591982
PII:
S 00255718(1980)05591982
Article copyright:
© Copyright 1980
American Mathematical Society
