[SciPy-dev] Nonlinear constrained optimizer in SciPy

eric jones eric at enthought.com
Fri Apr 9 14:48:50 CDT 2004


Just to follow up...

Adding one (or multiple) libraries would really plug a big hole in 
SciPy.  Jean-Sebastien has done both a lot of homework and a lot of work 
here -- thanks a ton.

Ideally, we would define a object model that could be wrapped around any 
of these libraries so that they could be used interchangebly.  The "best 
solver for common cases" would be the "default" solver that people would 
use when they aren't sure what to do.  People with more experience could 
try the other solvers as they needed.

It looks like there is at least one solver here that fits with SciPy's 
license, so that would seem the place to start.  Gathering permission 
from other authors could proceed in parallel.  Jean Sebastien, do you 
have time to do this?  It would good to hear if others have knowledge of 
other libraries that should be considered.

As far as logistics, there is actually going to be an "official" point 
release within the next couple of weeks (really!).  After that, we can 
start putting this code in the tree.  Jean-Sebastien, would you be 
interested in working on this?  If so, we'll get you CVS access.  Also, 
I expect Travis O. will want to be in on this because optimization is 
near and dear to his heart. :-)

Thanks again for all this information and code.  I hope to see something 
of this in SciPy soon.

eric

Jean-Sebastien Roy wrote:

> Following an earlier exchange with eric jones, I would like to suggest 
> the addition of a non linear constrained optimizer to SciPy (a 
> functionnality currently lacking).
>
> In 2001, a colleague and I did a review on non-linear bound 
> constrained optimizer that only required the gradient of the function 
> to be optimized. We did our review mosty based upon softwares listed 
> in H. Mittlemann optimization guide 
> (http://plato.la.asu.edu/guide.html), the non linear programming faq 
> (http://www-unix.mcs.anl.gov/otc/Guide/faq/) and the NEOS guide 
> (http://www-fp.mcs.anl.gov/otc/Guide/), plus a few other soucres 
> (HARWELL notably).
>
> We tested about 12 different optimizers for which the source code was 
> available and the result, while foreseeable, was not very interesting 
> : performance is largely dependent on the problem, and tuning of the 
> solvers parameters can result in huge performance increases. 
> Nevertheless, in this restricted class of optimizers, a few emerged as 
> quite good on a variety of problems. Some of them would probably be 
> good candidates for inclusion in SciPy.
>
> (Note: Very few codes come with a license explicitly allowing free 
> redistribution and inclusion in commercial software)
>
> L-BFGS-B:
> The Fortran source can be downloaded here:
> http://www.ece.northwestern.edu/~nocedal/lbfgsb.html
> We wrote to Nocedal who did not to oppose inclusion in our software, 
> so maybe we could ask him for inclusion in SciPy ?
> It was the simplest to use, iterations are fast, and it was quite robust.
> Probably the first code I would try on any problem.
>
> M2QN1:
> The Fortran source can be extracted from the scilab distribution.
> See also:
> http://www-rocq.inria.fr/estime/modulopt/optimization-routines/m2qn1.html
> An LBGFS code like the previous one, reasonnably simple to use, very 
> fast, very efficient.
> The use in commercial software if forbiden by scilab's licence, but we 
> may still ask the author, Claude Lemaréchal, who is a very nice person.
>
> TNBC:
> http://iris.gmu.edu/~snash/nash/software/software.html
> A bound constrained truncated newton code.
> Stephen Nash did not oppose use in our code, and since this code 
> provided the best performance on our problem (which may not be the 
> case on other problem), I did a C version of it (with some 
> modifications) and recently added a Python interface. It's distributed 
> with a BSD license, so it could be readily integrated in SciPy (but 
> I'm obviously biased). You can download it here (look for TNC):
> http://www.jeannot.org/~js/code/index.en.html
>
> A few more general codes:
>
> DONLP2:
> http://plato.la.asu.edu/donlp2.html
> SQP code with non linear constraints (including equality constraints).
> While it was quite difficult to use in our problem, it works well, and 
> is very general.
> The licence oppose commercial use, but we could ask the author, Peter 
> Spellucci about inclusion in SciPy.
>
> TRON:
> http://www-unix.mcs.anl.gov/~more/tron/
> Trust region newton code. Fast iterations. Sparse Hessian estimation 
> using finite differences, so it may be more difficult to use (since 
> the sparsity pattern should be computed).
> Again, Jorge More must be asked about inclusion.
>
> Other interesting codes include:
>
> IPOPT:
> http://www-124.ibm.com/developerworks/opensource/coin/Ipopt/
> An interior point code, very general (non linear equality constraints, 
> bounds).
> We did not review it (its quite recent). It comes with a free license, 
> so integration in SciPy should be possible. (Some options of IPOPT 
> requires part of the HSL library, which cannot be used in commercial 
> software).
>
> DFO:
> http://www-124.ibm.com/developerworks/opensource/coin/faqs.html#DFO
> A derivative free optimisation code, which, like IPOPT, comes with a free
> license. But it requires a non-linear gradient based optimizer and 
> some developpement.
>
> COBYLA:
> http://plato.la.asu.edu/topics/problems/nlores.html
> Another alternative for derivative free optimisation, which seems free.
>
> There are probably other codes, better alternatives, which should be 
> considered for inclusion in SciPy. Any suggestions ?
>
> Regards,
>
> js
>
> _______________________________________________
> Scipy-dev mailing list
> Scipy-dev at scipy.net
> http://www.scipy.net/mailman/listinfo/scipy-dev






More information about the Scipy-dev mailing list