Is there a high quality nonlinear programming solver for Python?

Question

I have several challenging non-convex global optimization problems to solve. Currently I use MATLAB's Optimization Toolbox (specifically, fmincon() with algorithm='sqp'), which is quite effective. However, most of my code is in Python, and I'd love to do the optimization in Python as well. Is there a NLP solver with Python bindings that can compete with fmincon()? It must

• be able to handle nonlinear equality and inequality constraints
• not require the user to provide a Jacobian.

It's okay if it doesn't guarantee a global optimum (fmincon() does not). I'm looking for something that robustly converges to a local optimum even for challenging problems, and even if it's slightly slower than fmincon().

I have tried several of the solvers available through OpenOpt and found them to be inferior to MATLAB's fmincon/sqp.

Just for emphasis I already have a tractable formulation and a good solver. My goal is merely to change languages in order to have a more streamlined workflow.

Geoff points out that some characteristics of the problem may be relevant. They are:

• 10-400 decision variables
• 4-100 polynomial equality constraints (polynomial degree ranges from 1 to about 8)
• A number of rational inequality constraints equal to about twice the number of decision variables
• The objective function is one of the decision variables

The Jacobian of the equality constraints is dense, as is the Jacobian of the inequality constraints.

Answer 1

fmincon(), as you mentioned, employs several strategies that are well-known in nonlinear optimization that attempt to find a local minimum without much regard for whether the global optimum has been found. If you're okay with this, then I think you have phrased the question correctly (nonlinear optimization).

The best package I'm aware of for general nonlinear optimization is IPOPT[1]. Apparently Matthew Xu maintains a set of Python bindings to IPOPT, so this might be somewhere to start.

UPDATE: the current maintained Python bindings for IPOPT seems to be ipyopt

[1]: Andreas Wachter is a personal friend, so I may be a bit biased.

Answer 2

I work in a lab that does global optimization of mixed-integer and non-convex problems. My experience with open source optimization solvers has been that the better ones are typically written in a compiled language, and they fare poorly compared to commercial optimization packages.

If you can formulate your problem as an explicit system of equations and need a free solver, your best bet is probably IPOPT, as Aron said. Other free solvers can be found on the COIN-OR web site. To my knowledge, the nonlinear solvers do not have Python bindings provided by the developers; any bindings you find would be third-party. In order to obtain good solutions, you would also have to wrap any nonlinear, convex solver you found in appropriate stochastic global optimization heuristics, or in a deterministic global optimization algorithm such as branch-and-bound. Alternatively, you could use Bonmin or Couenne, both of which are deterministic non-convex optimization solvers that perform serviceably well compared to the state-of-the-art solver, BARON.

If you can purchase a commercial optimization solver, you might consider looking at the GAMS modeling language, which includes several nonlinear optimization solvers. Of particular mention are the interfaces to the solvers CONOPT, SNOPT, and BARON. (CONOPT and SNOPT are convex solvers.) A kludgey solution that I've used in the past is to use the Fortran (or Matlab) language bindings to GAMS to write a GAMS file and call GAMS from Fortran (or Matlab) to calculate the solution of an optimization problem. GAMS has Python language bindings, and a very responsive support staff willing to help out if there's any trouble. (Disclaimer: I have no affiliation with GAMS, but my lab does own a GAMS license.) The commercial solvers should be no worse than fmincon; in fact, I'd be surprised if they weren't a lot better. If your problems are sufficiently small in size, then you may not even need to purchase a GAMS license and licenses to solvers, because an evaluation copy of GAMS may be downloaded from their web site. Otherwise, you would probably want to decide which solvers to purchase in conjunction with a GAMS license. It's worth noting that BARON requires a mixed-integer linear programming solver, and that licenses for the two best mixed-integer linear programming solvers CPLEX and GUROBI are free for academics, so you might be able to get away with just purchasing the GAMS interfaces rather than the interfaces and the solver licenses, which can save you quite a bit of money.

This point bears repeating: for any of the deterministic non-convex optimization solvers I've mentioned above, you need to be able to formulate the model as an explicit set of equations. Otherwise, the non-convex optimization algorithms won't work, because all of them rely on symbolic analysis to construct convex relaxations for branch-and-bound-like algorithms.

UPDATE: One thought that hadn't occurred to me at first was that you could also call the Toolkit for Advanced Optimization (TAO) and PETSc using tao4py and petsc4py, which would have the potential added benefit of easier parallelization, and leveraging familiarity with PETSc and the ACTS tools.

UPDATE #2: Based on the additional information you mentioned, sequential quadratic programming (SQP) methods are going to be your best bet. SQP methods are generally considered more robust than interior point methods, but have the drawback of requiring dense linear solves. Since you care more about robustness than speed, SQP is going to be your best bet. I can't find a good SQP solver out there written in Python (and apparently, neither could Sven Leyffer at Argonne in this technical report). I'm guessing that the algorithms implemented in packages like SciPy and OpenOpt have the basic skeleton of some SQP algorithms implemented, but without the specialized heuristics that more advanced codes use to overcome convergence issues. You could try NLopt, written by Steven Johnson at MIT. I don't have high hopes for it because it doesn't have any reputation that I know of, but Steven Johnson is a brilliant guy who writes good software (after all, he did co-write FFTW). It does implement a version of SQP; if it's good software, let me know.

I was hoping that TAO would have something in the way of a constrained optimization solver, but it doesn't. You could certainly use what they have to build one up; they have a lot of the components there. As you pointed out, though, it'd be much more work for you to do that, and if you're going to that sort of trouble, you might as well be a TAO developer.

With that additional information, you are more likely to get better results calling GAMS from Python (if that's an option at all), or trying to patch up the IPOPT Python interface. Since IPOPT uses an interior point method, it won't be as robust, but maybe Andreas' implementation of an interior point method is considerably better than Matlab's implementation of SQP, in which case, you may not be sacrificing robustness at all. You'd have to run some case studies to know for sure.

You're already aware of the trick to reformulate the rational inequality constraints as polynomial inequality constraints (it's in your book); the reason this would help BARON and some other nonconvex solvers is that it can use term analysis to generate additional valid inequalities that it can use as cuts to improve and speed up solver convergence.

Excluding the GAMS Python bindings and the Python interface to IPOPT, the answer is no, there aren't any high quality nonlinear programming solvers for Python yet. Maybe @Dominique will change that with NLPy.

UPDATE #3: More wild stabs at finding a Python-based solver yielded PyGMO, which is a set of Python bindings to PaGMO, a C++ based global multiobjective optimization solver. Although it was created for multiobjective optimization, it can also be used to single objective nonlinear programming, and has Python interfaces to IPOPT and SNOPT, among other solvers. It was developed within the European Space Agency, so hopefully there's a community behind it. It was also released relatively recently (November 24, 2011).

Answer 3

Update: see the new GEKKO package that we just released.

APM Python is a free optimization toolbox that has interfaces to APOPT, BPOPT, IPOPT, and other solvers. It provides first (Jacobian) and second (Hessian) information to the solvers and provides an optional web-interface to view results. The APM Python client is installed with pip:

 pip install APMonitor

It can also be installed in a Python script with:

try:
    from APMonitor.apm import *
except:
    # Automatically install APMonitor
    import pip
    pip.main(['install','APMonitor'])
    from APMonitor.apm import *

We've done a couple benchmark tests and found that the combination of APOPT (active set method) and IPOPT (interior point method) can solve a large percentage of benchmark problems. There are a number of example problems that are included with the download zip file. The one that you'll probably want to start with is the Hock Schittkowski #71 problem. It is the simplest example and demonstrates how to solve constrained optimization problems.

There is a browser interface and an API to Python / MATLAB. The API to Python is a single script (apm.py) that is available for download from the apmonitor.com homepage. Once the script is loaded into a Python code, it gives the ability to solve problems of:

• Nonlinear equations
• Mixed integer nonlinear programming
• Differential and algebraic equations
• Least squares model fitting
• Moving horizon estimation
• Nonlinear model predictive control
• etc.

For the new user, the APM Python software has a Google Groups forum where a user can post questions. There are webinars that showcase optimization problems in operations research and engineering.

Below is an example of an optimization problem (hs71.apm).

Model
  Variables
    x[1] = 1, >=1, <=5
    x[2] = 5, >=1, <=5
    x[3] = 5, >=1, <=5
    x[4] = 1, >=1, <=5
  End Variables

  Equations
    x[1] * x[2] * x[3] * x[4] > 25
    x[1]^2 + x[2]^2 + x[3]^2 + x[4]^2 = 40

    minimize  x[1] * x[4] * (x[1]+x[2]+x[3]) + x[3]
  End Equations
End Model

The optimization problem is solved with the following Python script:

from APMonitor.apm import *
server = 'http://byu.apmonitor.com'

# Application name
app = 'eqn'

# Clear previous application
apm(server,app,'clear all')

# Load model file
apm_load(server,app,'hs71.apm')

# Option to select solver (1=APOPT, 2=BPOPT, 3=IPOPT)
apm_option(server,app,'nlc.solver',3)

# Solve on APM server
solver_output = apm(server,app,'solve')

# Display solver output
print(solver_output)

# Retrieve results
results = apm_sol(server,app)

# Display results
print('--- Results of the Optimization Problem ---')
print(results)

# Display Results in Web Viewer 
url = apm_var(server,app)
print("Opened Web Viewer: " + url)

APM Python is a free web-service for optimization. The optimization problems are solved on remote servers and results are returned to the local Python script. An APMonitor local server is also available for download so that an Internet connection is not required (Download server). We recently added parallel processing support for both MATLAB and Python. The Python module is compatible with Python 2.7 or Python 3+.

Answer 4

We recently released (2018) the GEKKO Python package for nonlinear programming with solvers such as IPOPT, APOPT, BPOPT, MINOS, and SNOPT with active set and interior point methods. One of the issues with using these solvers is that you normally need to provide at least first derivatives and optionally second derivatives. There are several nice modeling languages that can do this for you, as mentioned with other answers. GEKKO compiles the equations to byte code so that it is like you wrote the model in Fortran or C++ in terms of speed. Automatic differentiation provides the 1st and 2nd derivatives in sparse form to the gradient based solvers. We designed GEKKO for optimal control problems but it can also solve problems similar to fmincon. Below is a quick example of a nonlinear programming problem with equality and inequality constraints. First, you'll need to add the GEKKO package with pip install:

pip install gekko

The Hock Schittkowski problem #71 is shown below as an example of an objective function, inequality constraint, equality constraint, and four variables with upper and lower bounds.

from gekko import GEKKO
m = GEKKO() # Initialize gekko
# Initialize variables
x1 = m.Var(value=1,lb=1,ub=5)
x2 = m.Var(value=5,lb=1,ub=5)
x3 = m.Var(value=5,lb=1,ub=5)
x4 = m.Var(value=1,lb=1,ub=5)
# Equations
m.Equation(x1*x2*x3*x4>=25)
m.Equation(x1**2+x2**2+x3**2+x4**2==40)
m.Obj(x1*x4*(x1+x2+x3)+x3) # Objective
m.options.IMODE = 3 # Steady state optimization
m.solve() # Solve
print('Results')
print('x1: ' + str(x1.value))
print('x2: ' + str(x2.value))
print('x3: ' + str(x3.value))
print('x4: ' + str(x4.value))    

GEKKO works on all platforms (Windows, MacOS, Linux, ARM processors) and with Python 2.7 and 3+. A fully local option is available without an Internet connection by setting the option "remote=False". The local option is currently only available for Windows and we are working on other versions such as Linux, MacOS, ARM processors to run locally without an Internet connection. The local version includes only free solvers that do not require a license. By default, the problem is sent to a public server where the solution is computed and returned to Python.

Although this question is specifically about solving nonlinear programming in Python, I'll also highlight a few other types of problems that GEKKO can solve and some resources for learning optimization. GEKKO also solves mixed-integer and differential algebraic equations and has several pre-programmed objects for advanced controls (similar to DMC, RMPCT, etc). Modes of operation include data reconciliation, real-time optimization, dynamic simulation, and nonlinear predictive control.

I teach two courses on optimization (design optimization and dynamic optimization) and have posted the course material online. The dynamic optimization course is offered each year starting in January and we use the GEKKO Python package (and MATLAB) for the course. GEKKO is an extension of the APMonitor Optimization Suite but has integrated the modeling and solution visualization directly within Python. APMonitor and GEKKO references give a sample of the types of applications that can be solved with this package. GEKKO is developed under the National Science Foundation Research Grant #1547110.

Answer 5

pyomo is a full GAMS/AMPL-like modeling environment for optimization in python. It is extremely powerful, has interfaces to all solvers that are supported by AMPL, and generates Jacobians etc. automatically. However, due to it running in a 'virtual python environment', it might not be trivial to link it to existing code.

Answer 6

Though this does not entirely answer your question, I author a Python package for nonlinear programming named NLPy. The most recent version may be retrieved from https://github.com/dpo/nlpy

I must stress that NLPy is research-grade and the solvers included are by no means as robust as more seasoned codes like IPOPT. Moreover, they currently require that Jacobians be provided. That being said, the point of NLPy is to provide the tools needed for researchers to assemble custom solvers if they need to. At any rate, I'll be interested to hear your comments offline if you do give it a try. You may also find the related packages https://github.com/dpo/pykrylov and https://github.com/dpo/pyorder useful. Currently, the documentation of NLPy is definitely lacking. The other two should be reasonable.

Answer 7

What about scipy.fmin_slsqp ?

http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fmin_slsqp.html

Answer 8

PyGMO contains several solvers, providing the same interface to them. IPOPT and scipy slsqp are included in case you compile the code and download/install the third party code independently.

As a bonus, parallel use of the solver is made really easy (multistart) via the archipelago class!

Answer 9

There's cvxmod, a Python wrapper around Stephen Boyd's convex optimization software. It's part of the Sage package.

Answer 10

fmincon now can be used from Python via OpenOpt framework, optionally with dense/sparse automatic differentiation by FuncDesigner http://openopt.org/fmincon

Answer 11

How about calling Matlab from Python, using python-matlab-bridge or the like ?
That looks much easier than porting yards of code, not to mention test cases and doc.
And general: any Python $\to$ any Matlab, or most $\to$ most.
(A-tool-to-convert-matlab-code-to-python on SO lists source-to-source translators too: difficult.)
Comments from people who have used such bridges would be welcome.

Answer 12

Is basin hopping via scipy sufficient for your needs? If it returns a local min and not a global min, you can change the number of iterations and/or apply bounds.

Answer 13

How about CMA-ES? It has Python bindings and is well suited to nonconvex, nonlinear optimization problems and I've used it quite a bit: https://www.lri.fr/~hansen/cmaesintro.html

Installation through pip:

pip install cma

Here's some sample code from their website:

import cma
help(cma)  # "this" help message, use cma? in ipython
help(cma.fmin)
help(cma.CMAEvolutionStrategy)
help(cma.CMAOptions)
cma.CMAOptions('tol')  # display 'tolerance' termination options
cma.CMAOptions('verb') # display verbosity options
res = cma.fmin(cma.Fcts.tablet, 15 * [1], 1)
res[0]  # best evaluated solution
res[5]  # mean solution, presumably better with noise

Answer 14

KNITRO has Python and MATLAB interfaces, among others. Think of it as an FMINCON replacement, but much better performing, and more expensive. https://www.artelys.com/en/optimization-tools/knitro#doc-tab .

I'm a user of KNITRO, but not otherwise affiliated with the product.

Answer 15

Since MATLAB has a JIT compiler while CPython does not yet (at least, until pypy gets full numpy support). It seems like you want a free solver that outperforms commercially produced fmincon. Isn't it too much?

IIRC among commercial NLP solvers, only snopt has provided a Python API until now (although it's rather ugly).

Which OpenOpt solvers have you tried? How many variables and constraints do you have in your nonconvex task?

You could try IPOPT through OpenOpt / Funcdesigner API without installation on OpenOpt Sage server (pay attention to the "switch from sage to python" picture).

Algencan, also connected to OpenOpt, says it solve nonconvex probs rather good (unfortunately it's absent in OO sage server). On the other hand, there is no gradient-based solver capable of yielding a guaranteed solution for nonconvex problems. Even some convex NLPs with 2 variables can be constructed where any solver will fail due to machine roundoff errors, e.g. $10^{300}(x-0.1)^2 + 10^{-300}(y-0.2)^2$ with starting guess like $(x,y) = (1,1)$.

Answer 16

for global problems you could be interested in http://openopt.org/interalg and other openopt global solvers (http://openopt.org/GLP ) for local optimization openopt also provides variety of solvers: http://openopt.org/NLP

Answer 17

It is good to mention here that Google Ceres solver is actually a very powerful non-linear optimiser, used in many projects.

There is also a python wrapper available here: https://github.com/rll/cyres

Answer 18

Also possibly of interest (as of Sep-21) is the software package Drake and its python bindings pydrake, which give interfaces to a pretty wide range of solvers.

Answer 19

As of today (31-Jul-21), you can use the solver MAiNGO

https://git.rwth-aachen.de/avt-svt/public/maingo

It has a python interface. Install it with:

pip install maingopy

Bongartz, Dominik; Mitsos, Alexander, Deterministic global optimization of process flowsheets in a reduced space using McCormick relaxations, J. Glob. Optim. 69, No. 4, 761-796 (2017). ZBL1386.90112.