ralg

ralg

Introduction:

ralg is a free constrained NLP/NSP solver written in Python and NumPy by Dmitrey.
It spreads with OpenOpt framework and is one of OO main features.
ralg (and OpenOpt) BSD License allows to use it in both free and non-free code.
The solver can handle user-provided 1st derivatives df, dc, dh (subgradient is OK as well).
Current implementation is intended for medium-scaled problems (nVars up to 1000..1500, nConstraints - any).
The solver handles Ill-conditioned, piecewise linear and polynomial, non-smooth & noisy problems rather good.
Currently most famous r-algorithm implementation is SolvOpt; it has Fortran90, C and MATLAB API, see also SolvOpt paper.

Algorithm:

It is based on r-algorithm with adaptive space dilation, invented by Ukrainian academician Naum Z. Shor (//that was my teacher// - D.). Most of optimization software written by our department of optimization (cybernetics institute, Ukrainian NAS) is based on r-algorithm (mostly Fortran code).
Current Python implementation is a mix of classic r-algorithm and filter methods. I didn't intended to implement filter methods to ralg, but that is what it became after a series of changes made for my dissertation.
Currently both ralg and SolvOpt are direct solvers, while some other implementations use dual subproblem.

Notes:

known issue: current implementation has experimental handling of linear equality constraints that is not perfect yet.
r-algorithm is heuristic one. Convergence for the one hasn't been proved even for smooth convex unconstrained functions.
Current implementation stores in computer memory matrix of size nVars * nVars, and each iteration consumes $5 \times nVars^2$ multiplication operations.
There are other (Fortran-written) ralg modifications that allows storing a matrix of size $nVars \times m$ instead (where m << nVars) and further decrease of iter multiplications number.

See also: