[Ipopt] improving IPOPT speed with Algorithmic Differentiation Theory
Andreas Waechter
andreasw at watson.ibm.com
Thu Sep 18 10:38:52 EDT 2008
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
>
More information about the Ipopt
mailing list