[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