ralg

ralg

Introduction:

ralg is a free constrained NLP/NSP solver written 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).
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.
Splitting non-linear constraints can benefit
Current implementation stores in computer memory matrix of size nVars * nVars, and each iteration consumes $5 \times nVars^2$ multiplication operations. Some modifications (by Dmitrey) reduce the number to $(2 + 3 \times s) \times nVars^2$ , where s from [0, 1] is average sparsity coefficient (depends on number of zeros triggering from gradients df/dx, d(maxResidual)/dx and number of switches feasible <-> infeasible region during optimization trajectory).
Current implementation doesn't care do you return some non-linear constraints values or max(these constraints) in the point involved.
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: