[Coin-ipopt] Hessian Vector product

[Andreas Waechter]

Hi Rohallah,

> I use IPOPT in a PDE constrained optimization problem (distributed parameter
> identification), i like to use second order information instead of hessian
> approximation, but direct construction of Hessian is very expensive, e.g.
> for 10^5 design variable, we should solve 10^5 additional PDE ! but
> computation of Hessian vector product is cheap, needs only solution of two
> additional PDE.

In general, you could of course use Ipopt's limited-memory Hessian 
approximation, but this might not give you performance that is robust 
enough.

You can of course compute the Hessian matrix itself by computing 
Hessian-vector products with all coordinate vectors e_i for all n columns 
of the Hessian matrix.  If you know the sparsity pattern of the Hessian 
and this one happens to be quite sparse, you might be able to get away 
with much less Hessian-vector products - a starting point for searching 
references might be papers by Trond Steihaug and Shahadat Hossain.

> I would like to know that how is difficulty of implementation of this issue
> in IPOPT and what portion of code should be modified?

This is not only an implementational issue, since the algorithm assumes 
that the step is computed from a linear system involving a matrix

/  H   A^T  \
|           |
\  A    0   /

(H: Hessian of Lagrangian,  A: Jacobian of constraints)

We assume that this is done with direct linear solver, which can provide 
information about the inertia of this matrix (number of positive and 
negative eigenvalues), which is essential for Ipopt in order to handle 
non-convex problems.

I don't see how this could be changed in a simple way so that you would 
only rely on Hessian-vector products.

There are other optimization codes (e.g., Knitro and FilterSQP) which can 
work with only Hessian-vector products.

> Also, is this issue in plan of developers (i think it considerably increase
> capability and range of application of IPOPT)?

At this point there is nothing concrete.  In the long run, we hope to have 
another algorithm implemented in the Ipopt project that can work with 
iterative linear solvers (and therefore only require Matrix-vector 
products - plus the necessity of a nice preconditioner) for computing the 
search directions, but this will not happen soon.

Sorry for the probably not very satisfying news,

Andreas