Home Install Documentation Problems Tree Applications Forum

Save your money
via IT outsourcing!
Ukrainian HI-TECH Initiative

NSP

From OpenOpt

Jump to: navigation, search
Non-Smooth Problems (NSP)


\mathbf {f(x) \to min,\ max}
subjected to
\mathbf{lb} \le \mathbf{x} \le \mathbf{ub}
\mathbf{A x} \le \mathbf{b}
\mathbf{A}_\mathbf{eq} \mathbf{x} = \mathbf{b}_\mathbf{eq}
\mathbf{\forall i=0,...,I: c_i(x) \le 0}
\mathbf{\forall j=0,...,J: h_j(x) = 0}
\mathbf{ \{ {f, c_i, h_j :R^n \to R \} \subset C^0}}
(continuous functions,
sometimes with some numerical noise)
\mathbf{x \in R^n}

In NSP default stencil value (for finite-difference derivatives approximation, if derivatives are not supplied by user or FuncDesigner automatic differentiation) is 3, while in NLP it is 1 (see DerApproximator documentation). Also, word NSP instead of NLP informs other programmers (who could edit your code) that your problem is nonsmooth.

NSP solvers

Solver License Made by Info
ralg BSD Dmitrey For medium-scaled problems (nVars up to ~1000...1500); ill-conditioned, piecewise linear and polynomial, non-smooth & noisy ones are also allowed. All types of constraints (lb <= x <= ub, A*x <= b, Aeq*x = beq, c(x) <= 0, h(x) = 0). r-algorithm with adaptive space dilation had been invented by Ukrainian academician Naum Z. Shor (my teacher //Dmitrey). This solver is enhanced from time to time (almost each OpenOpt release).
interalg BSD Dmitrey Solver with guaranteed user-defined accuracy fTol: abs(f - f*) < fTol. Handling of general constraints is available since r. 0.36
gsubg BSD Dmitrey For large-scaled convex problems with guaranteed user-defined precision. Lots of work still remains to be done, especially for constrained problems.
amsg2p BSD Dmitrey Currently unconstrained only, for medium-scaled problems (nVars up to ~1000...1500)

Requires known fOpt (optimal value) and fTol (required objective function tolerance, may be very small).
Parameters: gamma (default value 1.0). For pure quadratic functions you could set it to 2.0.
Algorithm: ams means "Agmon-Motzkin step", g2p means involving space dilation of 2 latest (normilized) subgradients difference and aggregated vector. For more details see recent publications of its author Petro I. Stetsyuk (that is our dept chief).
This solver is used in SNLE nssolve for unconstrained problems.
Future plans include constrained version.

ShorEllipsoid BSD Dmitrey currently it's a tentative implementation of Naum Z. Shor method of ellipsoids; it's unconstrained, for small-scale problems with nVars = 1..10, requires r0: norm(x0-x*)<r0) No
scipy_fmin BSD an implementation of Nelder-Mead simplex algorithm; unconstrained, cannot handle user-supplied derivatives
sbplx LGPL Steven G. Johnson. A variant of Nelder-Mead algorithm. Requires nlopt installed. Can handle box bound constrains.
Retrieved from "http://www.openopt.org/NSP"
Personal tools
Latest OOSuite 0.37