POEM – Effective Methods in Polynomial Optimization

Here we present our Python based 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.

Version

• Current Version: 0.3.0.1
• Latest Update: 2021-08-25.

Please note that this software is research software. 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 highly welcome; please contact me via email: Henning,

Team

• Henning Seidler (Developer)

Former Contributors:

• Timo de Wolff (former advisor, until version 0.2.1.0).
• Helena Müller

Download

• The code gets released at gitlab.
• You can download the code as zip-archive.
• Our database of examples can be downloaded as zip-archive (bzip2). To use it, read the file into a data base.

Setup

The software was developed for a Linux system. Different versions of the software were tested on Ubuntu versions 14.04.5, 16.04.3, 17.10 and 18.04.

• Install Python3 with IPython3 and pip3.
• Optionally install:
  • Matlab, including the packages CVX, SDPT3, SeDuMi, SOStools, Yalmip and Gloptipoly.
  • Mosek
• Download our code from this website.
• Go to the folder python and execute setup.py to make sure, all packages are installed and to create documentation in html.

Features

• Read polynomials from string, as matrix/vector-pair or generate new random instances.
• Compute lower bounds for unconstraint polynomial minimization problems via various methods:
  • SONC, using cvxpy and ECOS/Mosek in Python
  • SAGE, using cvxpy and ECOS/Mosek in Python
  • SOS, using cvxpy and CVXOPT/Mosek/SCS in Python
  • SOS, using cvx and SeDuMi/SDPT3 in Matlab
  • SOS, using SOStools/Yalmip/Gloptipoly in Matlab
  • Branch-and-bound, over the signs of the variables, combining the above methods
  All methods are accessed via a Python interface.
• Obtain the decomposition into non-negative polynomials (for SOS see Known Issues).
• For exact given coefficients, the decomposition can have exact coefficients as well.
• Compute (local) minima, to have an optimality gap.

Planned Features

• Docker image to test the software
• Improve the covering of the Newton polytope with simplices.
• Improve distribution of the negative coefficients.
• Constrained Optimization.

Known Issues

• Matlab is currently not available. Thus it was not tested in a while, and may become deprecated.
• Mac does not seem to have the package cpuinfo, so you cannot use runner.py.
• Decomposition for SOS will fail, if psd-matrix does not have full size, i.e. if some monomials do not appear in the solution.
• Symbolic decomposition of SAGE fails in many instances.
• Reallocation of coefficients via p.sonc_realloc() often fails, since ECOS tends to fail after some iterations.

Licence

The Software is published under GNU public license.

Citing POEM

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

	@Misc{poem:software,
	  Title        = {{POEM}: Effective Methods in Polynomial Optimization, version 0.3.0.1},
	  Author       = {Seidler, Henning},
	  HowPublished = {\url{http://www.user.tu-berlin.de/henning.seidler/POEM/}},
	  Month        = {aug},
	  Year         = {2021}
	}
				

The last version that was published in collaboration with Timo de Wolff was the following.

	@Misc{poem:software,
	  Title        = {{POEM}: Effective Methods in Polynomial Optimization, version 0.2.1.0},
	  Author       = {Seidler, Henning and de Wolff, Timo},
	  HowPublished = {\url{http://www.user.tu-berlin.de/henning.seidler/POEM/}},
	  Month        = {jul},
	  Year         = {2019}
	}
				

Literature

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
   Supplementary Material
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
6. H. Seidler: "Improved Lower Bounds for Global Polynomial Optimisation",
   see ArXiv 2105.14124

Support

From July 2017 until September 2019 this work was supported by the Deutsche Forschungsgemeinschaft via the DFG grant WO 2206/1-1 (PI: Timo de Wolff).

Last Update: May 5, 2022