NLP

From OpenOpt

Jump to: navigation, search
Non-Linear Problems (NLP)
\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^1}}
(smooth differentiable functions)
\mathbf{x \in R^n}

Read also: SciPy optimization solvers

NLP solvers connected to OpenOpt:

Contents


Single-variable

(finite box-bound constraints are required, x0 and derivatives are unused)

Solver License Info
goldenSection BSD Algorithm: golden section (pure)
scipy_fminbound BSD golden section + quadratic spline approximation. Seems like the scipy solver works incorrectly (sometimes x_opt is out of lb-ub bounds)


Unconstrained

Solver License Source code language Info
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 (normalized) 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.
scipy_powell BSD Python cannot handle user-supplied gradient
scipy_fmin BSD Python an implementation of Nelder-Mead simplex algorithm; cannot handle user-supplied gradient
scipy_bfgs BSD Python quasi-Newton method of Broyden, Fletcher, Goldfarb, and Shanno (BFGS) See Wright, and Nocedal 'Numerical Optimization', 1999, pg. 198.
scipy_cg BSD Python nonlinear conjugate gradient algorithm of Polak and Ribiere See Wright, and Nocedal 'Numerical Optimization', 1999, pg. 120-122
scipy_ncg BSD Python See Wright, and Nocedal 'Numerical Optimization', 1999, pg. 140. Can handle user-provided d2f / dx2, see the example.
Of course, you could use the constrained solvers for UC problems, see the sections below


Box-bound constrained

(can handle only simplest constraints lb <= x <= ub)

Solver License Made by Source code language
scipy_lbfgsb BSD Ciyou Zhu, Richard Byrd, and Jorge Nocedal <nocedal(at)ece.nwu.edu>,
connected to scipy by David M. Cooke <cookedm(at)physics.mcmaster.ca> and Travis Oliphant		 Fortran
scipy_tnc BSD Stephen G. Nash C
bobyqa BSD M.J.D. Powell. Doesn't use derivatives. Best solver for at most box-bounded problems, where objective function gradient cannot be provided. Medium-scaled solver (number of variables up to ~700), requires nlopt installed. C (converted from Fortran)
ptn LGPL ptn means "Preconditioned truncated Newton". Made by Prof. Ladislav Luksan, requires nlopt installed, uses its LD_TNEWTON_PRECOND_RESTART routine. C (converted from Fortran)
slmvm1, slmvm2 LGPL slmvm means "Shifted limited-memory variable-metric", 1 and 2 means rank-1 and rank-2. Made by Prof. Ladislav Luksan, requires nlopt installed. C (converted from Fortran)
Of course, you could use the constrained solvers for UC problems, see the sections below; especially powerful for box-bounded problems is ALGENCAN


General constrained

(lb <= x <= ub, A*x <= b, Aeq*x = beq, c(x) <= 0, h(x) = 0)

Solver License Made by Source code language Info
ralg BSD Dmitrey Python for medium-scaled problems (nVars = 1...1000); ill-conditioned, piecewise linear and polynomial, non-smooth & noisy ones are also allowed. r-algorithm with adaptive space dilation had been invented by Ukrainian academician Naum Z. Shor (my teacher //Dmitrey).
interalg BSD Dmitrey Python Solver with user-defined solution accuracy abs(f - f*) < fTol. Handling of general constraints is available since r. 0.36
scipy_cobyla BSD M.J.D. Powell, connected to scipy by Jean-Sebastien Roy Fortran Doesn't use derivatives. Recommended: read the issue about iterfcn connection.
algencan GPL (project webpage informs that you can contact authors for obtaining another license) J. M. Martinez, Ernesto G. Birgin, connected to Python by Jan Marcel Paiva Gentil Fortran The solver is developed at the Department of Applied Mathematics of the State University of Campinas and at the Department of Computer Science of the University of São Paulo (largest higher education and research institution in Brazil), under the coordination of Professor J. M. Martínez. Based on Augmented Lagrangian multipliers. Use the URL for download and install instructions. Copy pywrapper.so to a folder from PYTHONPATH (for example /usr/lib/python2.5/site-packages/) or ensure it is already present in a PYTHONPATH folder via "try: import pywrapper; except: print 'not found' ". Currently ALGENCAN requires a good user-supplied estimation of stop criterion gtol (try p.gtol = 1e-1...1e-6); ignores xtol, ftol, so using maxTime, maxCPUTime, maxIter, maxFunEvals is welcome. Recommended! Read some algencan issues here and here
scipy_slsqp BSD Dieter Kraft, connected to scipy by Rob Falck Fortran requires scipy.__version__ = 0.7.0 or more recent
mma LGPL Steven G. Johnson C mma = "method of moving asymptotes". Requires nlopt version 2.2 or more recent.
auglag LGPL Steven G. Johnson C auglag = "augmented lagrangian". Requires nlopt version 2.2 or more recent.
sqlcp (since OO ver 0.32) MIT Enzo Michelangeli and IT Vision Ltd Python Cannot handle nonlinear constraints c, h yet.
ipopt CPL Carl Laird (Carnegie Mellon University) and Andreas Wachter C++ The most known solver from coin-or project requires installation of ipopt and pyipopt (latter is made by Eric You Xu), and currently pyipopt declares "Platform: Linux, Mac, Untested for windows". Some stop criteria don't work (maxTime, maxCPUTime etc) because Python (2.5) can't catch exception though ipopt's code. IPOPT requires one of 3 linear system solvers; see /Ipopt-3.*.*/ThirdParty/Mumps for more details and installation script. OpenOpt use tol=1e-6 by default instead of 1e-8 value that is used by default in ipopt; set p.ftol = <your value> to modify tol, p.contol to modify constr_viol_tol (OpenOpt pass 1e-6 by default), p.maxIter to modify max_iter; other parameters from ipopt.opt file specification can be set via r=p.solve('ipopt', options = 'param1=value1, param2=value2; param3 value3 [etc...]') (comma- or semicolon-separated, space or "=" for name-value separation; however, mb this approach will be changed in future).
gsubg BSD Dmitrey Python For large-scaled convex problems (maybe nonsmooth) with guaranteed user-defined precision.
lincher BSD Dmitrey Python for constraints more than lb-ub the solver requires QP solver, and the only one connected for now is CVXOPT one (GPL). This solver is very primitive for now, we intend to enhance the one from time to time.

See also

  • GLP (global problems)
  • NSP (non-smooth problems)
  • MOP (multi-objective problems)
  • DFP (data fit problems)
  • SNLE (systems of nonlinear equations)
  • QP (quadratic problems)
Retrieved from "http://openopt.org/NLP"
Personal tools
    Latest OOSuite 0.37
    Next release:

    2012-03-15


    Development