Software for estimating sparse Hessian matrices

ABSTRACT

The solution of a nonlinear optimization problem often requires an estimate of the Hessian matrix for a function f. In large scale problems, the Hessian matrix is usually sparse, and then estimation by differences of gradients is attractive because the number of differences can be small compared to the dimension of the problem. In this paper we describe a set of subroutines whose purpose is to estimate the Hessian matrix with the least possible number of gradient evaluations.

REFERENCES

• 1: Thomas F. Coleman , Burton S. Garbow , Jorge J. More, Software for estimating sparse Jacobian matrices, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.329-345, Sept. 1984 [doi>10.1145/1271.1610]
• 2: COLEMAN, T. F. AND MOR~, J.J. Estimation of sparse Hessian matrices and graph coloring problems. Math. Program. 28, (Apr. 1984), 243-270.
• 3: CURTIS, A. R. AND REID, J.K. The choice of step lengths when using differences to approximate Jacobian matrices. J. Inst. Math. Appl. 13, (Feb. 1974), 121-126.
• 4: EVERSTINE, G.C. A comparison of three resequencing algorithms for the reduction of matrix profile and wavefront. Int. J. Numer. Meth. Eng. 14, (June 1980), 837-853.
• 5: GILL, P. E., MURRAY, W. AND WRIGHT, M.H. Practical Optimization. Academic Press, New York, 1981.
• 6: GOLDFARB, D. AND TOINT, P.L. Optimal estimation of Jacobian and Hessian matrices that arise in finite difference calculations. Math. Comp. 43, (July 1984), 69-88.
• 7: GRIEWANK, A. AND TOINT, P. L. Partitioned variable metric updates for large structured optimization problems. Numer. Math. 39, (June 1982), 119-137.
• 8: MATULA, D.W. A rain-max theorem for graphs with application to graph coloring. SIAM Rev. 10, (Oct. 1968), 481-482.
• 9: David W. Matula , Leland L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, Journal of the ACM (JACM), v.30 n.3, p.417-427, July 1983 [doi>10.1145/2402.322385]
• 10: POWELL, M. J. D. AND TOINT, P.L. On the estimation of sparse Hessian matrices, SIAM J. Numer. Anal. 16, (Dec. 1979), 1060-1074.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
      G.1.6 Optimization
          Subjects: Nonlinear programming

General Terms:
Algorithms