[Ipopt] Questions on Exact Hessian and Limited Memory

[Andreas Waechter]

Hi Mahesh,

Interesting observations...

First let's make sure we are on the same page regarding one thing:  The 
limited-memory approximation is not a numerical Hessian in the sense that 
one might perform finite differences to estimate the second derivatives. 
This is not what is implemented in Ipopt (although a user could write code 
like this and give the outcome of that to Ipopt as the "exact" Hessian). 
When you choose hessian_approximation=limited-memory in Ipopt, it uses a 
limited-memory version of the BFGS quasi-Newton updates - here is it not 
the goal to achieve an exact approximation of the real Hessian, but only 
something that is good enough to give good steps.  But I assume that you 
meant the hessian_approximation=limited-memory runs when you talk about 
"NUMERICAL HESSIAN"?  Also, since this limited-memory option does not do 
finite differences, you would not see an increase in the number of 
gradient evaluations per Ipopt iteration.

When I use Ipopt with the limited-memory BFGS approximation (L-BFGS), I 
usually observe that the algorithm starts to take more steps compared to 
when I provide the exact second derivatives (this of course assumes that 
the second derivatives are computed correctly - I assume that you verified 
your implementation using the derivative checker...).  For one, the 
algorithm usually needs longer to get close to a local solution (and the 
larger the problem is, the more iterations might be required for that), 
but secondly Ipopt has trouble to determine when it is done, even if it is 
already close to the solution.  The reason for this is that the 
multipliers (that appear in the Hessian of the Lagrangian) are not 
converging well, and therefore the termination test takes a long time to 
be satisfied, even though the primal variables are very close to the 
solution.  I haven't really found a good solution for this yet, so what I 
do is to use the "acceptable" tolerances in Ipopt allow an "early" stop, 
and finding good values for those is probably problem dependent.

But your observation is contrary to that.  One possible explanation is 
that this issue with slowly converging multipliers is not happening when 
the constraints are linear...  In that case, Ipopt seems to have less 
problems to figure out when it should terminate than in the L-BFGS case. 
Are your constraints linear?  The different in the number of iterations is 
something like 40 vs 46 in what you wrote, so one option is not much 
faster than the other.

To summarize:  I agree that usually the limited-memory Hessian 
approximation requires more Ipopt iterations (for two reasons, and of 
those the one related to terminating too late might be handles with Ipopt 
termination options), but I also have seen cases where this was not the 
case, particularly when the problem had linear constraints, or if the 
Hessian is "simple" (does not change much, diagonal, etc.)

Hope this helps,

Andreas


On Fri, 7 Aug 2009, Mahesh N wrote:

> Hello,
>
> We, at ASCEND Team, have been adding support to use IPOPT for NLP problems
> in the past few weeks. Now that the solver is fully integrated with ASCEND,
> we tested both limited-memory and exact means of calculation of the lagrange
> of the hessians. In the process, we observed that limited-memory approach
> needed lesser number of iterations than exact hessians approach.
>
> I've posted the median of a series of runs with both limited-memory and
> exact hessians below:
>
> EXACT HESSIAN
> ------------------------
>
> Number of objective function evaluations             = 46
> Number of objective gradient evaluations             = 29
> Number of equality constraint evaluations            = 0
> Number of inequality constraint evaluations          = 46
> Number of equality constraint Jacobian evaluations   = 0
> Number of inequality constraint Jacobian evaluations = 29
> Number of Lagrangian Hessian evaluations             = 28
> Total CPU secs in IPOPT (w/o function evaluations)   =      0.040
> Total CPU secs in NLP function evaluations           =      0.008
>
> NUMERICAL HESSIAN
> --------------------------------
>
> Number of objective function evaluations             = 40
> Number of objective gradient evaluations             = 23
> Number of equality constraint evaluations            = 0
> Number of inequality constraint evaluations          = 40
> Number of equality constraint Jacobian evaluations   = 0
> Number of inequality constraint Jacobian evaluations = 23
> Number of Lagrangian Hessian evaluations             = 0
> Total CPU secs in IPOPT (w/o function evaluations)   =      0.064
> Total CPU secs in NLP function evaluations           =      0.000
>
>
> Observe that the number of objective function,gradient function,etc
> evaluations in the Exact means is higher than numerical Hessians method.
>
> It seems likely that IPOPT could be using the data from the numerical
> hessian
> evaluation to reduce the number of gradient evaluations,etc although usually
> one would expect the lower accuracy of numerical derivatives to slow down
> the convergence (i.e.) more number of iterations. Is something like that
> happening here?
>
> Thanks,
>
> Mahesh
>
> -- 
> Developer
> ASCEND Project
> http://ascendwiki.cheme.cmu.edu
>