Computing Hessians with the Help of Automatically Detected Partially Separable Structure

David M. Gay - Bell Labs, Lucent Technologies

Many nonlinear optimization problems are partially separable: the objective is the sum of terms, each of which, perhaps after a suitable linear change of variables, depends on only a few variables. Knowing this structure permits one to compute the Hessian matrix (of second derivatives of the objective) efficiently, using backwards automatic differentiation to compute Hessian-vector products of each of the terms. With a suitable algebraic representation of the objective, we can find partially separable structure automatically, as will be illustrated with problems expressed in the AMPL modeling language. This makes it easy for people to use some sophisticated nonlinear solvers that require Hessians or partially separable structure---without having to discern these details.

Scheduled for Session 3.1 Computation And Econometrics - II