Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation

References

• Brandstädt A., Le V. B., Spinrad J. P.Graph Classes: A Survey: Monographs on Discrete Mathematics and Applications (1999) (SIAM, Philadelphia) Crossref, Google Scholar
• Büskens C., Maurer H., Gröschel M., Krumke S., Rambau J. Sensitivity analysis and real-time optimization of parametric nonlinear programming problems. Online Optimization of Large Scale Systems (2001) (Springer, Berlin) 3–16Crossref, Google Scholar
• Coleman T. F., Cai J. The cyclic coloring problem and estimation of sparse Hessian matrices. SIAM J. Algebraic Discrete Methods (1986) 7(2):221–235Crossref, Google Scholar
• Coleman T. F., Moré J. J. Estimation of sparse Hessian matrices and Graph coloring problems. Math. Programming (1984) 28:243–270Crossref, Google Scholar
• Dancre M., Tournebise P., Panciatici P., Zaoui F. Optimal power flow applied to state estimation enhancement. Proc. 14th Power Systems Comput. Conf. (2002) (Sevilla, Spain) . Paper 3, Session 37Google Scholar
• Dixon L., Griewank A., Corliss G. Use of automatic differentiation for calculating Hessians and Newton steps. Automatic Differentiation of Algorithms: Theory, Implementation, and Application (1991) (SIAM, Philadelphia) 114–125Google Scholar
• Gay D., Berz M., Bischof C., Corliss G., Griewank A. More AD of nonlinear AMPL models: Computing Hessian information and exploiting partial separability. Computational Differentiation: Techniques, Applications, and Tools (1996) (SIAM, Philadelphia) 173–184Google Scholar
• Gebremedhin A. H., Manne F., Pothen A. What color is your Jacobian? Graph coloring for computing derivatives. SIAM Rev. (2005) 47(4):629–705Crossref, Google Scholar
• Gebremedhin A. H., Tarafdar A., Nguyen D., Pothen A. ColPack: A graph coloring package for supporting sparse derivative matrix computation. ACM Trans. Math. Software (2009) . In preparationGoogle Scholar
• Gebremedhin A. H., Tarafdar A., Manne F., Pothen A. New acyclic and star coloring algorithms with application to computing Hessians. SIAM J. Sci. Comput. (2007) 29:1042–1072Crossref, Google Scholar
• Griewank A.Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation (2000) Number 19(SIAM, Philadelphia) . Frontiers in Applied MathematicsGoogle Scholar
• Griewank A., Juedes D., Utke J. ADOL-C: A package for the automatic differentiation of algorithms written in C/C++. ACM Trans. Math. Software (1996) 22:131–167Crossref, Google Scholar
• Lin Y., Skiena S. S. Algorithms for square roots of graphs. SIAM J. Discrete Math. (1995) 8:99–118Crossref, Google Scholar
• Lovász L. A characterization of perfect graphs. J. Combin. Theory (1972) 13:95–98Crossref, Google Scholar
• McCormick S. T. Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem. Math. Programming (1983) 26:153–171Crossref, Google Scholar
• Papadimitriou C. The NP-completeness of the bandwidth minimization prolem. Computing (1976) 16:263–270Crossref, Google Scholar
• Powell M. J. D., Toint P. L. On the estimation of sparse Hessian matrices. SIAM J. Numer. Anal. (1979) 16(6):1060–1074Crossref, Google Scholar
• Vanderbei R., Shanno D. An interior-point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. (1999) 13:231–252Crossref, Google Scholar
• Wächter A., Biegler L. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Programming (2006) 106(1):25–57Crossref, Google Scholar
• Walther A. Computing sparse Hessians with automatic differentiation. ACM Trans. Math. Software (2008) 34(1). Paper 3Crossref, Google Scholar