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@xxxxxxxxx
http://www.scipy.net/mailman/listinfo/scipy-dev