Efficient Computation of Sparse Hessians:
An Experimental Study Using ADOL-C
Abstract.
Interior-point methods require second-order
derivatives of the Lagrangian function, and exact Hessians are needed
in parametric sensitivity analysis. A Hessian can be computed
accurately using automatic differentiation (AD).
When the sparsity structure of the Hessian is known,
the computation can be made efficient using the following
three-steps procedure.
First, obtain a seed matrix S
that defines a column
partition of the Hessian H via a specialized graph coloring. Second,
compute the numerical values of the entries of the compressed
Hessian B=HS using AD. Third, recover the
numerical values of the entries of the original matrix H from the
compressed representation B. The coloring variant used in the first
step depends on whether
the recovery in the third step is direct
or substitution-based: a
direct method uses star coloring
whereas
a substitution method uses acyclic
coloring. In an earlier work we had designed and implemented
effective heuristic
algorithms for these two NP-hard coloring problems.
Recently we integrated part of the developed software with the AD tool
ADOL-C.
In this paper we provide a detailed description of the recovery
routines,
and experimentally demonstrate the efficacy of the coloring
techniques in the overall process of computing the Hessian of a given
function using ADOL-C as an example of an AD tool. The obtained
results show that sparsity exploitation via coloring renders enormous
savings in runtime and makes the computation of Hessians of very large
size feasible. The results also show that evaluating a Hessian via a
substitution method using acyclic coloring is faster than a direct
evaluation using star coloring---and the speedup is achieved without
compromising numerical accuracy.
Key words. sparse Hessian computation; acyclic coloring;
star coloring;
automatic differentiation; combinatorial scientific computing.
|
|