Polynomial Optimization via SONC

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.

Version

• Current Version: 0.1.1.0(a)
• Latest Update: 2018-04-09.

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.

Developers

Henning Seidler and Timo de Wolff.

Download

• You can download the code as zip-archive. Gitlab support will follow soon.
• Our database of examples can be downloaded as 7z-archive. To use it, read the file into a data base.

Setup

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.

• Install Python3 with IPython3 and pip3.
• Optional: Install Matlab, including the packages CVX, SDPT3, SeDuMi, SOStools, Yalmip and Gloptipoly.
• Download our code from this website.
• 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/SCS in Python
  • SONC, using cvx and SeDuMi/SDPT3 in Matlab
  • SOS, using cvxpy and SCS in Python
  • SOS, using cvx and SeDuMi/SDPT3 in Matlab
  • SOS, using SOStools/Yalmip/Gloptipoly in Matlab
  all methods are accessed via a Python interface.
• obtain the decomposition into non-negative polynomials (see Known Issues).

Detailed Documentation of the Functions

The following documentation files were generated by pydoc.

• polynomial.html
• generate_poly.html
• polytope.html
• aux.html
• runner.html

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))
	
	#create new random instance: shape, variables, degree, terms
	p3 = Polynomial('standard_simplex',30, 60, 100, seed = 0)
	p4 = Polynomial('simplex',10, 24, 56, seed = 1)
	#general shape has additional input: minimum number of interior points
	p5 = Polynomial('general',4,8,8,3,seed = 0)
	
	#run chosen method
	p3.sonc_opt_python_simplex()
	p4.sonc_opt_matlab_simplex()
	
	#run all methods and display time and optimum
	#should take about 1 minute on modern machine 
	p5.run_all()
	p5.print_solutions()
	
	

Known Issues

• Decomposition into squares will fail, if Gloptipoly/SOStools do not return a full-sized matrix, i.e. if some monomials do not appear in the solution.
• Reallocation of coefficients via

  p.sonc_realloc()

  often fails, since ECOS tends to fail after some iterations.

Upcoming Features

• Constrained Optimization.
• Improve the covering of the Newton polytope with simplices.
• Improve distribution of the negative coefficients.

License

The Software is published under GNU public license.

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.

Support

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

Last Update: July 24, 2018