sitemeter 

    Home    About    Documentation    Install    Newsline    Links    Feedback    Appeal    Guestbook

free html hit counter
since 2007/10/24

ralg

a free OpenOpt NLP/NSP solver

Introduction:

  • ralg is free (BSD-licensed) constrained NLP/NSP solver (spreads with OpenOpt code and is one of OO main features).
  • 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.

Notes:

  • 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*nVars2 multiplication operations. Some modifications (by Dmitrey) reduce the number to (2 + 3*s)*nVars2, where s from [0, 1] is average sparsity coefficient (depends on number of zeros triggering from gradients df, d(maxResidual) and number of switches feasible <-> infeasible region during optimization trajectory).
  • Current impementation doesn't care do you return some constraints values or max(these constraints) in the point involved.
  • There are other (Fortran-written) ralg modifications that allows storing matrix of size nVars * m instead (where m << nVars) and further decrease of iter multiplications number.