[SciPy-dev] Nonlinear constrained optimizer in SciPy
Jean-Sebastien Roy
js at jeannot.org
Fri Apr 9 13:06:28 CDT 2004
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
More information about the Scipy-dev
mailing list