Home    About    Documentation    Install    Newsline    Links    Feedback    Appeal    Guestbook

since 2007/10/24

Non-linear problems (NLP)

f(x) -> min
subjected to

• Box - bound constraints
  • lb <= x <= ub (some coords of lb and ub can be +/- inf)
    
• General linear constraints
  • A*x <= b
    
  • Aeq*x = beq
    
• Non-linear constraints
  • c_i(x) <= 0, i = 0...I
    
  • h_j(x) = 0, j = 0...J
    

---

OpenOpt NLP example >>>

---

NLP solvers

• Single-variable:

solver	license	requires finite lb-ub	uses x0 value	uses gradient	info
goldenSection	BSD	Yes	No	No	Alg: golden section (pure)
scipy_fminbound	BSD	Yes	No	No	Alg: golden section + quadratic spline approximation. Seems like the scipy solver works incorrectly (sometimes solution out of lb-ub bounds is returned)

---

• Unconstrained:

solver	license	info
scipy_powell	BSD	cannot handle user-supplied gradient
scipy_bfgs	BSD
scipy_cg	BSD
scipy_ncg	BSD	can handle d2f, see the example

---

• Box-bound constraints only (lb <= x <= ub):

Solver	License	Made by
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
scipy_tnc	BSD	Stephen G. Nash

---

• All types of constraints (lb <= x <= ub, A*x <= b, Aeq*x = beq, c(x) <= 0, h(x) = 0):

Solver	License	Made by	Info	Splitting non-linear constraints can benefit
ralg	BSD	Dmitrey	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). This solver is intended to be enhanced from time to time. OO version 0.18 has bug for A, Aeq constraints handling, so update from svn or tarball is required. Detailed ralg info: >>>	Yes
scipy_cobyla	BSD	M.J.D. Powell, connected to scipy by Jean-Sebastien Roy	can't handle user-supplied gradient info	No
(coming) algencan (requires algencan v >= 2.0.3)	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	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. Currently ALGENCAN requires a good user-supplied estimation of stop criterion gradtol (try p.gradtol = 1e-1...1e-6); ignores xtol, ftol, so using maxTime, maxCPUTime, maxIter, maxFunEvals is welcome. Recommended! Read some algencan issues here and here	Yes (inequalities only)
scipy_slsqp	BSD	Dieter Kraft, connected to scipy by Rob Falck	requires scipy.__version__ = 0.7.0 or more recent	No
ipopt (currently linux-only)	CPL	Carl Laird (Carnegie Mellon University) and Andreas Wachter	requires installation of ipopt and pyipopt (latter is made by Eric You Xu), and currently pyipopt is available for linux only. Some stop criteria don't work (maxTime, maxCPUTime etc) because Python (2.5) can't catch exception though ipopt's code. OpenOpt 0.18 has bug related to ipopt handling Ax <= b and Aeq x = beq constraints, so use more recent version (from svn or tarball from installation webpage). IPOPT requires one of 3 LP solvers, and IIRC only MUMPS has OSI-approved license (IIRC GPL);see /Ipopt-3.*.*/ThirdParty/Mumps for more details and installation script; also, during installation MUMPS can be turned up to use several CPU. 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.cpntol 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). See also some pyipopt install issues.	No
lincher	BSD	Dmitrey	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.	No