[Ipopt] improving IPOPT speed with Algorithmic Differentiation Theory

[Andreas Waechter]

Hi Andrey and Sebastian,

Yes, Andrey is right that we have this "new_x" flag in the interface to 
the problem formulation (the TNLP class) to allow caching.

The idea is that we don't want to make assumptions about in which order 
the evaluation functions are called.  The flag is true if the value of the 
x variables is different from the most recent call, and false if one of 
the other evaluation functions has been called before with that same value 
of x.

If I'm working with something that benefits from caching, I typically have 
somethink like the following at the beginning of every of the eval_* 
methods:

     if (new_x) {
       updateCache(x);
     }

and the updateCache(x) method computes all information that I can 
efficiently compute together and store it for later use.  In your case, 
you could just compute the value and the derivatives of the constraint 
function and store them in members of the class.  In the remainder of the 
eval_* code after the initial lines I just get the part of the information 
that is requested in that particular method from my internal cache.

One thing that will happen if you compute derivatives and function values 
together is that you will compute derivative information sometimes in 
vain.  Ipopt first requests the function values at a new trial point 
during the line search (and does not need the derivatives at this time). 
If this trial point is not accepted, Ipopt will not require the 
corresponding derivatives.  If the trial point is accepted as the new 
iterate, Ipopt will then request first (and second) derivatives for that 
same point.

One comment regarding performance comparison with SNOPT:

In general, the percieved trade-off between an SQP method (like SNOPT) and 
an interior point method (like Ipopt) is that typically the number of 
iterations (and therefore function evaluations) is less for SQP methods, 
but as the problem size grows, the time for each iteration increases (up 
to a point where SQP methods fail while interior point methods can solve 
much larger problems).

Another difference between the two codes is that SNOPT approximates the 
Hessian by a quasi-Newton method, while Ipopt can make use of second 
derivatives.  If second derivatives are used, the number of iterations is 
typically better, so in this sense Ipopt might perform better.  However, I 
assume that you actually can't compute second derivatives in your context, 
and that you are using Ipopt's quasi-Newton options.  In Ipopt, the 
quasi-Newton approach is to some degree a heuristic, and it is not as 
tested as the version with exact second derivatives.  Even though I have 
been using it successfully in many applications, there are certain issues 
with the quasi-Newton approach.  The most significant might be that Ipopt 
has trouble to find out when it is done, and it might do many iterations 
at the end even though the problem is essentially already solved.  For 
this, I implemented the "acceptable" termination criteria 
(see the "acceptable_*" options), and it might be worthwhile looking at 
this in case you see that Ipopt seems to be essentially done but does not 
terminate.

Finally, it might also be worthwhile to think about the problem scaling, 
see

https://projects.coin-or.org/Ipopt/wiki/HintsAndTricks#Scalingoftheoptimizationproblem

I hope this clarifies your questions.

Andreas

On Thu, 18 Sep 2008, Andrey Romanenko wrote:

> Hi!
>
> On Thursday 18 September 2008 11:50:15 Sebastian Walter wrote:
>> This is exactly what I thought, too.
>> But unfortunately this doesn't help, or maybe I'm missing something?
>>
>> My implementation looked like this:
>>
>> /----------------------------------------------/
>>
>> x_count = 0;
>> last_eval = 999999;
>>
>
> I would do something like this:
>
>> bool eval_grad_f(..., bool new_x){
>      if(new_x == true) {
>          calculate();
>          cache();
>      } else {
>           get_from_cache();
>      }
> }
>
> You do not need to tie the logic to the evaluation counter.
>
> I suspect there is no point to introduce this check in eval_f (although the
> new_x is in the argument list) because IPOPT should not need to call eval_f()
> with new_x == false. Andreas, could you please confirm?
>
> [...]
>
> Regards,
> Andrey Romanenko
>
>
> _______________________________________________
> Ipopt mailing list
> Ipopt at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/ipopt
>