[Coin-ipopt] Eigenvalues of the linear system
Andreas Waechter
andreasw at watson.ibm.com
Sun Jul 10 18:50:25 EDT 2005
Hi Kirk,
1. Why does Ipopt need the inertia: We want to make sure that the search
directions that are computed are making progress to a minimizer (an not a
maximizer) during the optimization. Essentially, what Ipopt is doing is
to apply Newton's method to the nonlinear equations of the optimality
conditions, but since these are only the *first order* optimality
conditions, and are also satisfied at local maxima. Therefore, we want to
deviate from the pure Newton direction if things don't seem right, and the
indication that we use is to make sure that the inertia of the linear
system is correct. The correct inertia also ensures that the search
direction is a "descent direction" for our (filter) line search procedure.
Other IP-NLP optimization code (such as Knitro and Loqo, who work with
merit functions instead of a filter) have similar requirements. You don't
need this if you know that your problem is convex (in which case the
inertia is always correct), for example for LPs.
(If you are interested, a little bit more information can be found in
Section 3.1 of our implementation paper at
http://www.research.ibm.com/people/a/andreasw/papers/ipopt.pdf)
2. As for avoiding Harwell routines: In the new version of the code we
are planning to have interfaces to other linear solvers. In particular,
we would like to have interfaces to WSMP (a new version of WSMP is planned
to have a true indefinite factorization that can provide the inertia),
PARDISO, and TAUCS - the last one would be an open source code. (Thanks
to Yifan Hu of Wolfram we already have a TAUCS interface, but the version
of TAUCS for the indefinite factorization is not yet officially released,
and first tests within Ipopt didn't work completely yet, but that will
helpfully change. If you feel like you want to see if you can accelerate
that process, you could try to contact Sivan Toledo, the developer of
Taucs, and ask him about the status.... :)
Regards,
Andreas
On Thu, 7 Jul 2005, Kirk Abbott wrote:
> Hello All,
>
> I fully support the premise that there should be
> a fully open source version of Ipopt. I too dislike
> the whole Harwell issue, not to mention the
> difficulty in grabbing all the pieces to do a build...
>
> What exactly does Ipopt do with:
> the inertia of the linear system (the number of
> positive and negative eigenvalues?
>
> This is the only IP solver that I know of which
> uses this information. How do other systems cope
> without this information? Should we try to raise/start
> a project to get this functionality built into
> a open-sourceable linear solver? Whatever happened
> to TAUCS?
>
> Cheers,
> Kirk.
>
>
> --- coin-ipopt-request at list.coin-or.org wrote:
>
> > Send Coin-ipopt mailing list submissions to
> > coin-ipopt at list.coin-or.org
> >
> > To subscribe or unsubscribe via the World Wide Web,
> > visit
> > http://list.coin-or.org/mailman/listinfo/coin-ipopt
> > or, via email, send a message with subject or body
> > 'help' to
> > coin-ipopt-request at list.coin-or.org
> >
> > You can reach the person managing the list at
> > coin-ipopt-owner at list.coin-or.org
> >
> > When replying, please edit your Subject line so it
> > is more specific
> > than "Re: Contents of Coin-ipopt digest..."
> >
> >
> > Today's Topics:
> >
> > 1. Can you make a completely open source build?
> > (kevin.c.furman at exxonmobil.com)
> > 2. Re: Can you make a completely open source
> > build?
> > (Carl Damon Laird)
> > 3. Re: Can you make a completely open source
> > build?
> > (kevin.c.furman at exxonmobil.com)
> >
> >
> >
> ----------------------------------------------------------------------
> >
> > Message: 1
> > Date: Tue, 5 Jul 2005 12:58:23 -0400
> > From: kevin.c.furman at exxonmobil.com
> > Subject: [Coin-ipopt] Can you make a completely open
> > source build?
> > To: coin-ipopt at list.coin-or.org
> > Message-ID:
> >
> <OF4DFD41B9.C9E38B9E-ON85257035.005C0D26 at exxonmobil.com>
> > Content-Type: text/plain; charset=US-ASCII
> >
> > Are there any libraries that can be substituted for
> > the Harwell routines?
> >
> > Is there a way to build IPOPT completely from open
> > source? If not,
> > shouldn't there be one?
> >
> > Regards,
> >
> > Kevin Furman
> >
> >
> >
> > ------------------------------
> >
> > Message: 2
> > Date: Tue, 5 Jul 2005 13:32:13 -0400 (EDT)
> > From: Carl Damon Laird <claird at andrew.cmu.edu>
> > Subject: Re: [Coin-ipopt] Can you make a completely
> > open source build?
> > To: kevin.c.furman at exxonmobil.com
> > Cc: coin-ipopt at list.coin-or.org
> > Message-ID:
> >
> >
> <Pine.LNX.4.60-041.0507051322200.8152 at unix42.andrew.cmu.edu>
> > Content-Type: TEXT/PLAIN; charset=US-ASCII;
> > format=flowed
> >
> > As it stands right now, there is no tested, open
> > source substitution for
> > the Harwell routines. We are looking at some open
> > linear solvers, but we
> > do not have anything ready for prime time as yet. As
> > I understand, the
> > Harwell routines are free for "research" purposes -
> > please consult the
> > Harwell website for a more precise definition.
> >
> > Of course, we agree that there *should* be a way to
> > build IPOPT completely
> > from open source, however, this is not a trivial
> > task. The IPOPT algorithm
> > requires a sparse, indefinite linear solver
> > (symmetric) that can provide
> > the inertia of the linear system (the number of
> > positive and negative
> > eigenvalues). So far, we have found VERY few open
> > source linear solvers
> > that can provide this functionality.
> >
> > If anyone on the list has knowledge of some
> > alternatives that we could
> > consider, please let us know :)
> >
> > Cheers,
> >
> > Carl.
> >
> > On Tue, 5 Jul 2005 kevin.c.furman at exxonmobil.com
> > wrote:
> >
> > > Are there any libraries that can be substituted
> > for the Harwell routines?
> > >
> > > Is there a way to build IPOPT completely from open
> > source? If not,
> > > shouldn't there be one?
> > >
> > > Regards,
> > >
> > > Kevin Furman
> > >
> > > _______________________________________________
> > > Coin-ipopt mailing list
> > > Coin-ipopt at list.coin-or.org
> > >
> > http://list.coin-or.org/mailman/listinfo/coin-ipopt
> > >
> > >
> >
> >
> > ------------------------------
> >
> > Message: 3
> > Date: Tue, 5 Jul 2005 16:26:59 -0400
> > From: kevin.c.furman at exxonmobil.com
> > Subject: Re: [Coin-ipopt] Can you make a completely
> > open source build?
> > To: Carl Damon Laird <claird at andrew.cmu.edu>
> > Cc: coin-ipopt at list.coin-or.org
> > Message-ID:
> >
> <OF1D1D180E.8B10A2EE-ON85257035.006629C3 at exxonmobil.com>
> > Content-Type: text/plain; charset=US-ASCII
> >
> > Unfortunately, the old Harwell Archive routines are
> > only free for
> > non-commercial purposes. My understanding is that
> > industry and national
> > labs probably need to purchase them to use them,
> > even if for research
> > purposes.
> >
> > I think PARDISO has a similar licensing scheme and
> > similarly good
> > performance compared to MA57. Since PARDISO is
> > offered as part of the
> > Intel MKL, it might be a good alternative choice
> > since I think it would be
> > more commonly available. MKL probably also has
> > alternatives to most of the
> > other Harwell routines used by IPOPT as well.
> >
> > I believe IBM Watson Research center actually had
> > their own solver for
> > sparse symmetric indefinite linear systems as as
> > part of the WSMP (Watson
> > Sparse Matrix Package). Perhaps IBM would consider
> > open sourcing that
> > package.
> >
> > You might find the following recent reports
> > comparing these kinds of code
> > interesting:
> >
> ftp://ftp.numerical.rl.ac.uk/pub/reports/ghsRAL200505.pdf
> >
> ftp://ftp.numerical.rl.ac.uk/pub/reports/ghsNAGIR20051.pdf
> >
> > Regards,
> >
> > Kevin
> >
> >
> >
> >
> >
> >
> > Carl Damon Laird
> >
> >
> > <claird at andrew.cmu.ed
> > To: kevin.c.furman at exxonmobil.com
> >
> > u>
> > cc: coin-ipopt at list.coin-or.org
> >
> >
> > Subject: Re: [Coin-ipopt] Can you make a completely
> > open source build?
> >
> >
> >
> > 07/05/05 01:32 PM
> >
> >
> >
> >
> >
> >
> >
> >
> >
> === message truncated ===
>
> _______________________________________________
> Coin-ipopt mailing list
> Coin-ipopt at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-ipopt
>
More information about the Coin-ipopt
mailing list