POEM – Effective Methods in Polynomial Optimization

Here we present our software for polynomial optimization via sums of nonnegative circuit polynomials (SONC), a certificate for nonnegativity of polynomials independent of sums of squares, which were developed by Timo de Wolff and Sadik Iliman. SONC certificates are computed via geometric programs. The software can also call established solvers to compute SOS certificates. It is written in Python.


Please note that this software is a prototype and an alpha version. As such it is preliminary, released for test-purposes only, and subject to change without notice.

Although the code was tested with multiple instances, it may still contain errors, bugs, or an offensive coding style. There is no warranty, not even for merchantability or fitness for a particular purpose.

Feedback, suggestions, and bug reports are very welcome; please contact us via email: Timo, Henning.


Henning Seidler and Timo de Wolff.



The software was developed for a Linux system. The current initial version was tested on Ubuntu versions 14.04.5 LTS, 16.04.3 LTS, 17.10 and 18.04 LTS.


Detailed Documentation of the Functions

The following documentation files were generated by pydoc.
The first entries are the main files, that are meant to be accessed.

The following packages only contain auxiliary functions.

Example Code

	from polynomial import *
	#create instance from matrix and vector/list
	A = np.array([[1, 1, 1, 1],[0, 2, 4, 2],[0, 4, 2, 2]])
	b = [1, 1, 1, -3]
	p1 = Polynomial(A,b)
	#create instance from string, string can e.g. be taken from symbolic expression in Matlab or sympy
	p2 = Polynomial(str(8*x[0]**6 + 6*x[1]**6 + 4*x[2]**6+2*x[3]**6 -3*x[0]**3*x[1]**2 + 8*x[0]**2*x[1]*x[2]*x[3] - 9*x[1]*x[3]**4 + 2*x[0]**2*x[1]*x[3] - 3*x[1]*x[3]**2 + 1))
	#in strings you can use round brackets, squares brackets or no brackets at all
	p2 = Polynomial('8*x(0)**6 + 6*x(1)**6 + 4*x(2)**6+2*x(3)**6 -3*x(0)**3*x(1)**2 +  8*x(0)**2*x(1)*x(2)*x(3) - 9*x(1)*x(3)**4 + 2*x(0)**2*x(1)*x(3) - 3*x(1)*x(3)**2 + 1')
	#create new random instance: shape, variables, degree, terms
	p3 = Polynomial('standard_simplex',30, 60, 100, seed = 0)
	p4 = Polynomial('simplex',10, 24, 56, seed = 2)
	#general shape has additional input: minimum number of interior points
	p5 = Polynomial('general',4,8,8,3,seed = 0)
	#run chosen method
	p4.opt(language = 'matlab') #not tested in a while
	#run all methods and display time and optimum
	#should only take a few seconds on a modern machine 
	p5.local_min(method = 'all')
	print('Optimality gap is %s' % str(p5.gap()))

Known Issues

Upcoming Features


The Software is published under GNU public license.

Citing POEM

If you find POEM useful, you can cite it using the following BibTex entry.

	  Title        = {{POEM}: Effective Methods in Polynomial Optimization, version},
	  Author       = {Seidler, Henning and de Wolff, Timo},
	  HowPublished = {\url{https://www3.math.tu-berlin.de/combi/RAAGConOpt/poem.html}},
	  Month        = {feb},
	  Year         = {2019}


  1. S. Iliman, T. de Wolff: "Amoebas, Nonnegative Polynomials and Sums of Squares Supported on Circuits",
    Research in the Mathematical Sciences 3(1) (2016), 1-35; ArXiv version.
  2. S. Iliman, T. de Wolff: "Lower Bounds for Polynomials with Simplex Newton Polytopes Based on Geometric Programming",
    SIAM Journal on Optimization 26 (2) (2016), 1128-1146; see ArXiv version.
  3. M. Dressler, S. Iliman, T. de Wolff: "An Approach to Constrained Polynomial Optimization via Nonnegative Circuit Polynomials and Geometric Programming",
    see ArXiv 1602.06180.
  4. H. Seidler, T. de Wolff: "An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization",
    see ArXiv 1808.08431
  5. V. Magron, H. Seidler, T. de Wolff: "Exact Optimization via Sums of Nonnegative Circuits and Sums of AM/GM Exponentials",
    see ArXiv 1902.02123


This work was supported by the Deutsche Forschungsgemeinschaft via the DFG grant WO 2206/1-1 (PI: Timo de Wolff).

Last Update: February 14, 2019