[SciPy-dev] Nonlinear constrained optimizer in SciPy

[Jean-Sebastien Roy]

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

[eric jones]

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

Post by Jean-Sebastien Roy
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)
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.
The Fortran source can be extracted from the scilab distribution.
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.
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
http://www.jeannot.org/~js/code/index.en.html
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.
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.
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).
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.
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
http://www.scipy.net/mailman/listinfo/scipy-dev

[Jean-Sebastien Roy]

Gathering permission from other authors could proceed in parallel.
Jean Sebastien, do you have time to do this?

I'll ask Powell about inclusion of COBYLA (which has the great advantage
of not requiring the gradient) in SciPy.

Regards,

js

PS: many thanks to David M. Cooke for the LBFGSB interface !

[Jean-Sebastien Roy]

Post by Jean-Sebastien Roy
I'll ask Powell about inclusion of COBYLA (which has the great
advantage of not requiring the gradient) in SciPy.

(Replying to myself)

Michael J.D. Powell agreed to include COBYLA in SciPy (which is very
nice of him), so what's left is writting a Python interface to it.
I plan to do it in the next days/weeks.

Regards,

js

[David M. Cooke]

Post by Jean-Sebastien Roy
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.

I've written a python wrapper (using F2PY) that I've been using for a
few months. I just rolled it together and put it on my website at

http://arbutus.mcmaster.ca/dmc/software/

The thing to clarify with Nocedal is the 'advertising' clause in it's
conditions of use -- this wouldn't be acceptable as a subroutine you
might not realize you're using.

[eric jones]

Post by David M. Cooke

Post by Jean-Sebastien Roy
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.

I've written a python wrapper (using F2PY) that I've been using for a
few months. I just rolled it together and put it on my website at
http://arbutus.mcmaster.ca/dmc/software/
The thing to clarify with Nocedal is the 'advertising' clause in it's
conditions of use -- this wouldn't be acceptable as a subroutine you
might not realize you're using.

Could we just place this in the doc string? The doc-string could say
something like "If you use this routine in your
research or commercial application, then quote this paper." Would that
be enough?

eric

[Travis Oliphant]

Thanks to David Cooke and the very informative Jean-Sebastien Roy SciPy
now has our first multivariable constrained optimization function

Just in time for the Scipy 0.3 release.

The Zhu, Byrd, Nocedal L-BFGS-B optimizer is named

scipy.optimize.fmin_l_bfgs_b

It uses the same interface David constructed. I removed dependency on
linpack and blas and use instead the lapack returned from scipy_distutils.

The docstring contains the information for the papers people should
quote if they use the algorithm in their work.

I notice that it is slower for unconstrained problems than the other
algorithms which I suppose is not surprising. What have other people
experienced?

I just did a simple test on the rosenbrock function (notice that
optimize.rosen and optimize.rosen_der provide the function and gradient
for this famous function) both of these are vector-length agnostic so
that the initial guess defines the order of the problem. I tested order
3-5 on windows and linux without problems.

Thanks again,

-Travis Oliphant

[Travis Oliphant]

Thanks again to Jean-Sebastian for another constrained optimization code.

I've added his TNC package to SciPy.

I made a couple of changes to the interface to make it consistent with
the rest of scipy.optimize. Other than that it's pretty much his code.

This code even runs very quickly for the simple unconstrained cases I
tried.

So, it looks like now we have two decent constrained optimization codes
in SciPy.

Fantastic!! Play away.

-Travis Oliphant