this page is related to a GSoC2007 proposition, so it's obsolete and should be removed or filled with other data.

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.

• 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)

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

Getting Started (2 weeks)

1. Learn svn, setuptools // done
2. Commit your code, integrated to scikits. // done

Core Contributions (5 weeks)

1. Create classes NLP (done), NSP (done), LP (done), add some working solvers (done, but for NLP/NSP I have only UC solvers for now)
2. add some new solvers ( specify which ): ShorEllipsoid? and ralg are added, some LP solvers are connected
3. Add MILP, QP classes with working solvers (lp_solve MILP solver + CVXOPT QP solver will be connected)
4. write 1st-order NLP solver with ALL type of constraints (lb, ub, AX<=b, AeqX=beq, c(x)<=0, h(x)=0, user-supplied df, dc, dh, f/c/h patterns)
5. add automatic checks of user-supplied derivatives df, dc, dh

Due *9th July.*

Milestone 2

Milestone 2 is broken into four parts:

1. Work on the following tickets to closure, with priority given to 296.

(Note that work on 296 has already started and since you are familiar with tnc this should be pretty easy for you to complete.)

http://projects.scipy.org/scipy/scipy/ticket/234 http://projects.scipy.org/scipy/scipy/ticket/285 http://projects.scipy.org/scipy/scipy/ticket/296 http://projects.scipy.org/scipy/scipy/ticket/377 http://projects.scipy.org/scipy/scipy/ticket/390 http://projects.scipy.org/scipy/scipy/ticket/399 http://projects.scipy.org/scipy/scipy/ticket/416 http://projects.scipy.org/scipy/scipy/ticket/344 http://projects.scipy.org/scipy/scipy/ticket/384 http://projects.scipy.org/scipy/scipy/ticket/389 http://projects.scipy.org/scipy/scipy/ticket/388

Note that you are expected to bring questions and difficulties concerning these tickets to the developers list asap! Not all questions are answered the first time: rephrase and try again! If you think a ticket should be closed as "won't fix", bring it before the developer community with your reasoning.

2. Make existing openopt code usable by adding docstrings, unit tests, and documented sample scripts.

Docstrings must conform to the standard. http://projects.scipy.org/scipy/numpy/wiki/CodingStyleGuidelines Tests must conform to the TestingGuidelines http://projects.scipy.org/scipy/scipy/wiki/TestingGuidelines Make sure ralg and lincher are fully functional, tested, and documented, completing as much as possible of your projected work on ralg (i.e., constraints to nonsmooth ralg solver (c<0, h=0, lb, ub, A, Aeq), as well as their derivatives).

3. Improve test coverage and docstrings of existing scipy.optimize libraries.

Change docstrings to conform to the standard. http://projects.scipy.org/scipy/numpy/wiki/CodingStyleGuidelines Tests must conform to the TestingGuidelines http://projects.scipy.org/scipy/scipy/wiki/TestingGuidelines Again, bring questions to the developers list in a timely fashion.

4. Write some step and line search objects for the generic optimizer code.

(Matthieu has checked the current code base into openopt/solvers.) Specifics on task will follow next week. This will add functionality to both openopt and to the optimizer as a standalone. Include appropriate docstrings and unit tests.

Due *August 20.*

For reasons discussed elsewhere, these milestone markers replace the previous markers for milestone 2. Advance on those markers is of course welcome, but progress will be judged by the milestones above.

Since you have passed the first milestone, you should be familiar enough with SciPy and that you can see how to integrate your more work into the SciPy project.

From your proposal: "will provide scaling, unified convinient text & graphics output, checking user-supplied analitical derivatives, parallel calculations (for example for numerical gradient/subgradient obtaining), easy comparison & unified for all solvers.)" As stated from the beginning, for this summer project, your should focus your development on the use of Scipy solvers (including the new solvers that you contribute). This now includes the generalized optimization framework contributed by Matthieu Brucher.

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).