[SciPy-user] Fwd: [sage-devel] Fwd: (Summer Of Code) are you interested in numerical optimization (+solving non-smooth non-linear systems of equations)?

Fernando Perez fperez.net@gmail....
Thu Feb 22 14:28:33 CST 2007


[ Forwarded from the SAGE dev list, since this may well be right up
someone's alley from the scipy crowd]

---------- Forwarded message ----------
From: William Stein <wstein@gmail.com>
Date: Feb 22, 2007 1:00 PM
Subject: [sage-devel] Fwd: (Summer Of Code) are you interested in
numerical optimization (+solving non-smooth non-linear systems of
equations)?
To: sage-devel@googlegroups.com, suvrit@cs.utexas.edu


Does anybody have any thoughts about this potentially excellent idea
of a package that could help SAGE?

---------- Forwarded message ----------
From: dmitrey <openopt@ukr.net>
Date: Feb 22, 2007 1:56 AM
Subject: (Summer Of Code) are you interested in numerical optimization
(+solving non-smooth non-linear systems of equations)?
 To: wstein@gmail.com

Hallo William Stein!
I found your email address in
http://wiki.python.org/moin/SummerOfCode/Mentors

As far as I understood there are very few constrained solvers for
Python. In google I failed to find anything but the CVXOPT, which consists
mostly of wrappers to commercial mosek, and some LP/MIP wrappers to GNU
C- or f-
code (and some optimization routines from scipy, of course).

So I'm last-year post-graduate (institute of cybernetics, Ukraine national
science academy, optimization department). Our department research
methods of optimization for non-smooth (& noisy) funcs since 1964 or so
(under leadership of academician Naum
Z. Shor till 2002 when he gone away), and parallel department under
leadership
of academician I. Sergienko & dr. V.Shilo researches combinatory
optimization
problems (something like matlab bintprog, MAXCUT etc, some weeks ago they
published article of their GRASP-based code that won comparison vs CPLEX
& some
other commercial solvers).

So all our software is opensourse & free, mostly fortran & C written.
3-4 months ago I began to write (in m-files) OpenOpt for MATLAB/Octave
(1st ver
0.15 had been reliesed in November 25, 2006). It's equivalent to commercial
TOMLAB or GAMS (currently puny of course, but free (GNU GPL2)) and
contains 4  global solvers, that I connected to the OpenOpt environment
from
matworks fileexchange, 2 my local nonsmooth solvers - ShorEllipsoid for
nVars =
1...10 & ralg for nVars = 1...1000, and nonSmoothSolve - MATLAB fsolve
equivalent for non-smooth & noisy funcs. There is a good comparison in
Examples/nonSmoothSolveEx.m, which shows, that fsolve fails even on
low-noise or
low-non-smooth funcs, but nonSmoothSolve - not.
ralg & ShorEllipsoid are MATLAB equivalents to fminsearch; however, they
can handle (as long as nonSmoothSolve):

lb<=x<=ub;
Ax<=b;
Aeq*x=beq;
c(x)<=0;
h(x)=0; %as far as I understood from CVXOPT documentation it can't
handle these constraints - see
http://www.ee.ucla.edu/~vandenbe/cvxopt/doc/e-nlcp.html

as long as gradients or subgradients df, dc, dh of f, c, h.

MATLAB fminsearch can't handle anything mentioned above, and in 95% it
fails
comparison to ralg (but I can't say I tried too much examples). Just
try, for
example, f(x)=sum(abs(x).^1.2.^(0:(length(x)-1)));
x0 = cos(1:60).';
or Lemarechal.m from OpenOpt/test (convex, continuous, non-smooth)
These and some more examples are in OpenOpt/Examples, see ooexample5.m,
ooexample2.m and others. This directory also contains some pictures of
convergence, automatically generated by the files.
Also OpenOpt performs auto scaling (but I not tested properly it yet);
providing
patterns of f, c, h (when no (sub)gradient is provided by user) can greatly
speedup calculations; possibility of parallel calculations while
obtaining df/dx
numerically (via MATLAB dfeval, Octave users must provide similar func in
prob.parallel.fun) and some more features.

So are you interested in Python version of the OpenOpt? If yes, I
probably would
be able to contact with other Kiev institute of System Analis, where a
group
 under leadership of academician Pshenichniy (perished some months ago) &
dr.
Nikitin develop smooth algorithms of optimization, and their IP-based
smooth
solvers (constrained, of course; including 2nd-order solvers) are
considered to be one of essential. So I probably
would be able to write for you Pyhton OpenOpt ver (GNU GPL2) with
essential equivalent of MATLAB fmincon, as long as ralg, ShorEllipsoid,
bintprog; drawing pictures of convergence, using patterns of
dependences, parallel obtaining of (sub)gradients to f(), c(), h();
network problems solvers etc.

If you have any questions, or can add any financial support, or want to
look at
my CV (I had about 1-1.5 years of Python experience & 3-4 years of
optimization in
MATLAB), or anything else - you can contact me via email or icq 275 -
976 - 670 (invisible).
The more financial support can be obtained, the more time can I spend
for the OpenOpt Python version, & the more icyb optim department workers
can be involved into the OpenOpt for Python development (any salary
amount are essential to the Ukraine workers).
If I gain enough money, I propose:
creating the same environment for Python as it is done for
MATLAB/Octave; (1-1.5 months)
writing ralg() & ShorEllipsoid() solvers (Unconstrained: ~1 week,
constrained: +2-3 weeks)
writing nonSmoothSolve() : ~ 1-2 weeks
writing MATLAB bintprog (f*x->min, A*x<=b, Aeq*x=beq) equivalent based
on rd. Shilo (& others) version of GRASP (works better than current
CPLEX!): ~2 weeks
writing MATLAB fmincon equivalent (smooth constrained optimization,
c(x)<=0, h(x)=0, linear constraints +1st & 2nd derivatives) based on
works of dr. Nikitin & academician Pshenichniy: (I can't estimate time
for now, I must contact to him before)
--------
+ following implementation of other solvers, their upgrade & maintenance.

I guess in future you could easily connect the py-code to the SAGE
project, for example like you did with MAXIMA package.

some links:
ftp where OpenOpt versions are storing:
 http://www.box.net/public/6bsuq765t4
(you would better to download OpenOpt0.36.tar.bz2 from here)

my page at matlabexchange area
 http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=13115&objectType=file


Let me attach a graphic file generated by the OpenOpt ooexample3.m

WBR, Dmitrey


 --
William Stein
Associate Professor of Mathematics
University of Washington
 --~--~---------~--~----~------------~-------~--~----~
 To post to this group, send email to sage-devel@googlegroups.com
 To unsubscribe from this group, send email to
sage-devel-unsubscribe@googlegroups.com
 For more options, visit this group at
http://groups.google.com/group/sage-devel
 URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
 -~----------~----~----~----~------~----~------~--~---


More information about the SciPy-user mailing list