[Coin-ipopt] Hessian Vector product

[Andreas Waechter]

Hi Rohallah,

> Thanks for your illumination related to IPOPT algorithm.
>
> Your suggested way is more expensive, since in my case computation of
> Hessian product with every e_i needs solution of 2 PDE and so direct
> construction is cheaper (which is very expensive too).

In case you do want to try to compute the Hessian, it might still be 
better to work with Hessian-vector products if your Hessian is sparse and 
you can use graph coloring tricks a la Steihaug and others to compute the 
sparse Hessian elements with less than n mutliplications with the e_i's. 
(For example, if the Hessian is diagonal, you would only need one 
Hessian-vector product - the coloring techniques now try to do tricks 
similar to this to handle more complicated cases...)

Regards,

Andreas


>
> Best Regards,
> RT.
>
>
> On 10/29/07, Andreas Waechter <andreasw at watson.ibm.com> wrote:
>>
>> 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
>>
>