Free Python optimization framework

Tuesday, October 28, 2008

Major changes for ralg

I have committed some major changes for NLP/NSP solver ralg.

A couple of ideas have been stolen from SolvOpt (made by our dept worker Alex Kuntsevich during his voyage to Austria, in collaboration with Franz Kappel), that still remains to be most famous Naum Z. Shor r-algorithm implementation with Fortran90, C and MATLAB API.

However, the implementation is more heuristic than original Naum Z. Shor r-algorithm; since convergence of latter hasn't been proved yet even for smooth convex functions, proving convergence for SolvOpt's implementation will hardly be ever possible (especially because of those heuristics like backward line search approach, see SolvOpt's paper for algorithm details).

So my dept chief is not fond of SolvOpt heuristics (he consider they reduce % of problems that can be solved, because SolvOpt can stop further from optimum, then primal Naum Z. Shor r-algorithm), still SolvOpt remains rather popular in our optimization dept.

Currently I have taken 2 ideas from SolvOpt: modifications for initial step size and step multiplier for forward line search. As for backward search, I found SolvOpt's approach very unclear and currently my own way still remains in OO ralg implementation. Handling of constraints is also performed in a different way.

Also, some code cleanup for OO kernel have been committed.

Tuesday, October 21, 2008

PSwarm 1.3 has been connected

I have connected new PSwarm version: 1.3.

As PSwarm developer Ismael Vaz promised, now Python API has much more available parameters to modify (see updated GLP page for details) and outputfcn connected (that improves text and graphics output), so now user-provided callback function(s) can be handled by the solver (also, openopt GUI p.manage() function works better, see previous post for description).

Wednesday, October 15, 2008

Introducing OpenOpt GUI

I'm glad to introduce initial version of OpenOpt GUI.

I had some months of GUI experience in PyGTK and tcl/tk so I have some experience in GUI development; on the other hand I know very well what's the deuce it is: you have to try all possible combinations of buttons (and the dummy task is NP-Hard of course) to ensure all works ok, to enable/disable buttons in correct order, to story related variables etc.

For OO I decided to use Tkinter, because it doesn't require any additional soft installation (it is included in Python distribution).

I had took a look at AMPL and GAMS GUIs before starting my own one, and of course I have no intention to duplicate Python IDEs.

Running OO GUI is performed via

r = p.manage()

instead of p.solve(), or via

from scikits.openopt import manage
r = manage(p, solver, ...)

Let me also note: manage() can handle named argument start = {False}/True/0/1, that means start w/o waiting for user-pressed "Run".

Currently there are only 3 buttons: "Run/Pause", "Exit" and "Enough".
As you probably know lots of solvers have troubles with stop criteria. Especially it's relevant to NSP solvers, where calculating derivatives only for to check stop criteria isn't a good idea. So pressing "Enough" button yields triggering of stop criterion, like this:
------------
solver: ralg problem: GUI_example goal: minimum
iter objFunVal log10(maxResidual)
...
102 5.542e+01 -6.10
istop: 88 (button Enough has been pressed)
Solver: Time Elapsed = 1.19 CPU Time Elapsed = 1.12
Plotting: Time Elapsed = 6.86 CPU Time Elapsed = 5.97
objFunValue: 55.423444 (feasible, max constraint = 7.98936e-07)

Let me also note that
  • pressing "Exit" before "Enough" and before solver finish will return None, so there will be no fields r.ff, r.xf etc.
  • for some IDEs pressing "Exit" doesn't close matplotlib window (if you are using p.plot=1). You should either wait for newer matplotlib version (they intend to fix it) or try to fix it by yourself via choosing correct Agg, see here for details
  • OO Doc webpage entry related to OO GUI will be committed later
  • you could play with the GUI example by yourself

Saturday, October 11, 2008

bugfix for ooIterPrint.py in Python 2.4

I have been informed of Python 2.4 issue
File
"/usr/lib/python2.4/site-packages/scikits/openopt/Kernel/ooIterPrint.py",
line 6
'isFeasible': lambda p: ('+' if p.rk < p.contol else
'-')
^
SyntaxError: invalid syntax

I have committed workaround for Python 2.4. Still I guess it's better to use Python 2.5, as it is mentioned in OO install webpage.

Friday, October 10, 2008

Example of 10X speedup for NLP via oofun

I have committed the example of unconstrained NLP where using oofun yields 10X speedup vs classic style (via reducing of the time required for gradient approximation for a costly function).

Of course,
  • I could construct example where the profit is 100X or even more, but it's longer to wait for output.
  • There can be similar examples constructed for constrained NLP or some other classes from non-linear group (NSP, NLSP, LSP).
  • I used scipy_ncg solver but speedup ~ 4X...10X is observed while using any other non-linear solver as well (provided the solver deals with at least 1st derivatives, so scipy_cobyla, goldenSection, scipy_fminbound, scipy_powell or GLP solvers are inappropriate).
Also, some changes to oofun-, oovar-related and some other OO Kernel files have been committed.

Tuesday, October 7, 2008

oovar and oolin

I have committed my implementation of oovar and oolin to OpenOpt svn repository.

So, 2 new entries to oofun doc webpage have been added:
  • using oovar (OpenOpt Variable)
  • using oolin (that is linear oofun)
Currently oolin(f) returns (f, x) (that is numpy.dot). In future I intend to add c: oolin(f, c) is (f, x) + c.
Also, mb ooquad(H, f, c) will be implemented in future (that is 0.5 * xTHx + fx + c).

Friday, October 3, 2008

new Python optimization soft: Pyomo

I've got to know about Pyomo (thanks to Nils Wagner) that is made by Sandia Labs (Trilinos/PyTrilinos developers). In the article they say "However, Coopr Opt is not as mature as the OpenOpt package", I guess that's the reason why my site daily visitors number has jumped from ~ 50-60 to ~ 80-90 this week.

Also, in the paper they inform of willing to collaborate with OO. I had contacted them long time ago but the provided examples of their soft usage were too difficult for me to understand and connect to OO during an adequate time. I guess it will be much easier for them to understand my code instead.

Very important bugfix for nonlinear problems

I have committed very important bugfix for nonlinear problems.
I don't know how many days the nasty bug was hiding and lurkering (I guess several months), did the one affects some solvers work or no, because it has been somehow (but maybe not everytime) overwritten by other code, and only my latest changes (committed to subversion repository some days ago) have revealed the one.