On variable-metric methods for sparse Hessians

Shanno, D. F.

doi:10.1090/S0025-5718-1980-0559198-2

On variable-metric methods for sparse Hessians
HTML articles powered by AMS MathViewer

by D. F. Shanno PDF

Math. Comp. 34 (1980), 499-514 Request permission

Abstract:

The relationship between variable-metric methods derived by norm minimization and those derived by symmetrization of rank-one 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 variable-metric method is proposed. The sparse BFGS generated by this method is tested against the sparse PSB and variable-memory conjugate gradient methods, with computational experience uniformly favoring the sparse BFGS.

References

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
C. G. Broyden, The convergence of a class of double-rank minimization algorithms. II. The new algorithm, J. Inst. Math. Appl. 6 (1970), 222–231. MR 433870

A Combined Conjugate-Gradient Quasi-Newton Minimization Algorithm

Variable Metric Method for Minimization

Numerical Methods for Nonlinear Optimization

J. E. Dennis Jr. and R. B. Schnabel, Least change secant updates for quasi-Newton methods, SIAM Rev. 21 (1979), no. 4, 443–459. MR 545880, DOI 10.1137/1021091
Anthony V. Fiacco and Garth P. McCormick, Nonlinear programming: Sequential unconstrained minimization techniques, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0243831
R. Fletcher and M. J. D. Powell, A rapidly convergent descent method for minimization, Comput. J. 6 (1963/64), 163–168. MR 152116, DOI 10.1093/comjnl/6.2.163

Comput. J.

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
D. Goldfarb, Generating conjugate directions without line searches using factorized variable metric updating formulas, Math. Programming 13 (1977), no. 1, 94–110. MR 503799, DOI 10.1007/BF01584327
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

An Algorithm for Minimization Using Exact Second Derivatives

Exploiting Sparsity in Newton-Like Methods

Testing Unconstrained Optimization Software

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, DOI 10.1007/BF01582091
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

Analyzing and Improving Quasi-Newton Methods for Unconstrained Optimization

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, Conditioning of quasi-Newton methods for function minimization, Math. Comp. 24 (1970), 647–656. MR 274029, DOI 10.1090/S0025-5718-1970-0274029-X
David F. Shanno, Conjugate gradient methods with inexact searches, Math. Oper. Res. 3 (1978), no. 3, 244–256. MR 506662, DOI 10.1287/moor.3.3.244
D. F. Shanno and K. H. Phua, Numerical comparison of several variable-metric algorithms, J. Optim. Theory Appl. 25 (1978), no. 4, 507–518. MR 525744, DOI 10.1007/BF00933517

ACM Trans. Math. Software

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. L. Toint, Some numerical results using a sparse matrix updating formula in unconstrained optimization, Math. Comp. 32 (1978), no. 143, 839–851. MR 483452, DOI 10.1090/S0025-5718-1978-0483452-7