[Ipopt] Hessian Computation

[Teeter, Chuck]

Hi Andreas,

Thanks for your reply.  Actually, AIMMS normally provides first and
second derivatives to a solver, except in the special case where
external functions are utilized to build some of the constraints.  In
this special case, AIMMS provides no second derivatives for ANY
constraint functions, whether they are native AIMMS constraints or not
(ie, external constraints).  This is why I think my observed results are
rather extraordinary - no Hessian computations are performed at all, and
great results are still obtained.

I have requested the ability to provide second derivatives for external
constraint functions from Paragon Decision Technology.  If they are
willing to implement this functionality, AIMMS will then be able to pass
FULL Hessian information back to Ipopt.  I was fairly certain that the
computational results (time required for solution and robustness of
solution) would be improved further with the addition of Hessian
information, but had no real way to quantify this expectation.

The reason that more time is require per iteration when using the LBFGS
Hessian approximation is that when I specify "Exact" for Hessian
computation, no time at all is required in the AIMMS modeling
environment, since no Hessian is computed for the special case described
above.  So, even though LBFGS Hessian approximation may not take a lot
of time, it still requires more time than no computation at all.

I also wanted to share my observation that Ipopt seems to handle
discontinuous derivatives amazingly well.  I'm not sure why this is so,
but I can say that for my work at least, Ipopt is the fastest, most
reliable nonlinear solver I have ever used - commercial or otherwise.  I
am using it exclusively for refinery planning models, which up until now
have been solved exclusively with SLP (or distributed recursion).
Anyway, I hope to write a success story in the near future!



-----Original Message-----
From: ipopt-bounces at list.coin-or.org
[mailto:ipopt-bounces at list.coin-or.org] On Behalf Of Andreas Waechter
Sent: Tuesday, April 20, 2010 10:39 AM
To: Chuck Teeter
Cc: ipopt mailing list
Subject: Re: [Ipopt] Hessian Computation

Hi Chuck,

(Sorry for the late reply, as you can see, I'm working my way backwards
through the Ipopt emails...)

I'm not sure I understand, so this is what I understood:  In AIMMS, you
can compute second derivatives for "internal" function, but not for
external functions, so you simple ignore the second derivatives for
external functions.  I'm surprised this works as well as you describe,
but I guess if this is only a subset you might be getting away with it
well. 
I'm a little surprised you write that Ipopt takes more time per
iteration when you use the LBFGS Hessian approximation, since then the
matrix that is factorized is even easier than in the case where you
ignore parts of the derivatives (or at least it is roughly the same as
if the exact Hessian is only a diagonal).  However, depending on how
large you set the limited_memory_max_history option, a number of
backsolves have to be performed, so, you might get faster times per
iteraion if you decrease this option, but then the result might be that
overall you need more iterations...

>From a theoretical point of view, in order to guarantee global
convergence, you can essentially provide any (uniformly bounded) matrix
as Hessian matrix, since Ipopt will make sure it is positive definite in
the null space of the constraints (well, there are more assumptions to
prove global convergence, but simplified speaking, the is very little
required for the Hessian).  But of course the closer the matrix is to
the true Hessian, the faster convergence will usually be.

In any case, I probably didn't bring much light into this issue; but it
was interesting to hear your observation that ignoring some of the
second derivatives still works pretty well!

Regards,

Andreas

On Sun, 4 Apr 2010, Chuck Teeter wrote:

> Hi All,
>
> I have a question about the options available for Hessian computation 
> in Ipopt.  First, some background:  I use Ipopt with the AIMMS 
> modeling system for refinery planning.  My model makes use of some 
> external, nonlinear constraint functions which are implemented in C++.

> For these functions, I also use automatic differentiation to provide 
> first partial derivatives to AIMMS (and hence on to Ipopt).  It just 
> so happens that in AIMMS, if external functions are used as model 
> constraints, second derivatives are not made available to Ipopt for 
> ANY constraints, either constraints implemented natively in AIMMS, or 
> constraints that are implemented in external functions.
>
> When solving my model, I set the method for Hessian computation to
"exact".
> It solves quickly and reliably 99% of the time without ANY Hessian 
> information from AIMMS.  For comparison purposes, I have also used the

> quasi-newton Hessian approximation option.  It also solves reliably as

> well, although it takes much longer per iteration because it now has 
> to do much more work.  I found these results to be somewhat curious, 
> in that solution reliability does not appear to be adversely affected 
> by lack of Hessian information or lack of Hessian quality.  I have a 
> variety of nonlinear constraints in my model.  Although some nonlinear

> constraints involve bilinear terms, most are far more complex and are 
> definitely 2nd order differentiable.
>
> I guess my questions boil down to these:  Is this result expected?  
> Would you expect significantly improved performance/reliability if 
> exact Hessian information was made available to Ipopt?  Under what 
> conditions would you expect accurate Hessian information to be 
> critical in achieving quick and/or reliable solutions?
>
> Thanks in advance for any insights!
>
> Chuck
>

_______________________________________________
Ipopt mailing list
Ipopt at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/ipopt
------------------------------------------------------------------------
This email and its contents are private and confidential, for the sole use of the addressees. If you are not an intended recipient, copying, forwarding or other distribution of this email or its contents by any means is prohibited. If you believe that you received this email in error please notify the original sender immediately. 

Petro-Canada is a Suncor Energy business.

------------------------

Ce courriel et son contenu sont privés et confidentiels, et sont destinés à l’usage exclusif des destinataires. Si vous n'êtes pas le destinataire prévu, toute reproduction, transfert ou autre forme de diffusion de ce courriel ou de son contenu par quelque moyen que ce soit est interdit. Si vous croyez avoir reçu ce courriel par erreur, veuillez en aviser l'expéditeur original immédiatement. 

Petro-Canada est une entreprise de Suncor Énergie.