Introduction

As far as I understood there are very few constrained solvers for Python. There is CVXOPT, which consists mostly of wrappers to commercial mosek; some LP/MIP wrappers to GNU C- or f- code; and some optimization routines from scipy, of course.

There are lots of commercial modeling systems for numerical optimization like AMPL, GAMS, TOMLAB. I propose to create a free Python-based equivalent to them, + connecting some non-smooth & network solvers that our optimization department researches, + inviting our collaborators from other optimization departments of our & some other institutes to provide their own solvers.

This project is based on:

1. existing m-code from my OpenOpt experience (see below)
2. Fortran standalone routines from our optimization department
3. lots of scipy solvers + connecting to other, already written.

Background and motivation

Now afaik essential free optimization environment is absent, but I strongly believe it's just a matter of time, like appearing Linux vs Unix was.

I already had some experience with my OpenOpt for MATLAB/Octave, see the examples in directory OpenOpt/Examples & some pictures generated automatically.

Goal

The environment will provide scaling, unified convenient text & graphics output, checking user-supplied analytical derivatives, parallel calculations (for example for numerical gradient/subgradient obtaining), easy comparison & similar to TOMLAB unified for all solvers call:

prob = NLP(myObjFun, x0, <optional params:> TolX=1e-4, TolCon=1e-3, doPlot=true, MaxTime=1e3, MaxIter =1e4, ...)
(similar prob=LP(f, other_args), prob=QP(...), ...)
r = prob.run(solverName (or names of some solvers), <optional params>)

output structure r will include algorithm used, license of the solver used, its authors, web homepage of the solver, time, cputime elapsed, and much more. Some of the info will be printed (by default) before or after solver's work. All of the above is already done in my OpenOpt? version for MATLAB/Octave (parallel - currently only for objfun gradient obtaining, not constraints) but for many reasons (the main is pass-by-copy in MATLAB/Octave vs pass-by-reference in Python) I'm rewriting all the code to Python now & intend to continue development using Python language. GSoC support would helped me very much.

Also in future I intend to connect glpk, lpsolve, COIN-OR & other free solvers to the environment. I don't mean writing python-c connection once again, I mean simple unified call prob=LP(...), r=prob.run(solver, <optional options>) with some benchmarking elements. As lot solvers as it can be done will be Python-written, for to avoid problems with installation C- & Fortran-code & for to RAD ability.

Timeline

Two milestones are defined. The first would be contributed to scipy.optimize and the second would be to scikits.optimize. Note that scikits.optimize can require dependencies such as matplotlib or envisage, which is not allowed for scipy.optimize.

Milestone 1

• write ralg() & ShorEllipsoid?() solvers (Unconstrained: ~1 week, constrained: +2-3 weeks)
• write nonSmoothSolve() : ~ 1-2 weeks
• writing MATLAB bintprog equivalent (f*x->min, A*x<=b, Aeq*x=beq) based on rd. Shilo (& others)
• write a Python version of GRASP: ~2-3 weeks
• create an optimization environment for Python that is similar to MATLAB/Octave (1-1.5 months)
• write MATLAB fmincon equivalent (smooth constrained optimization, c(x)<=0, h(x)=0, linear constraints +1st & 2nd derivatives) based on Nikitin & Pshenichniy
• writing or connecting of some already existing NLP UC or box-bounded solvers
• write module for checking 1st derivatives provided by user (less than 1 week)

Due *9th July.*

Milestone 2

Due *August 20.*

Documentation and development methodology

bug tracking and source control

...

Doc format

Doc format: the numpy community has recently defined a standard for documenting code, using a reST derived format.

About the author

My name is Dmitrey Kroshko. I'm last-year post-graduate (Institute of Cybernetics, Ukraine National Science Academy, Optimization Department) (former NSAU calculus center). Our department researches methods of optimization for non-smooth (& noisy) functions since 1964 or so (under leadership of academician Naum Z. Shor till 2002 when he left).

License

Same as SCIPY, that is BSD-like license (without advertisement clause).