polynomial_opt
index
/home/hennich/Uni/SONC_polynomial_optimization/python/polynomial_opt.py

Class for multivariate polynomials in sparse notation, focus on optimisation.

 
Modules
       
aux
cvxpy
json_tricks
matlab
mosek
numpy
os
polynomial_base
polytope
psutil
scipy
sympy
warnings
z3

 
Classes
       
polynomial_base.Polynomial(builtins.object)
Polynomial

 
class Polynomial(polynomial_base.Polynomial)
    Class for multivariate polynomials in sparse notation, focus on optimisation.
 
 
Method resolution order:
Polynomial
polynomial_base.Polynomial
builtins.object

Methods defined here:
__init__(self, *args, **kwargs)
Create a new multivariate polynomial object for optimisation.
 
Call:
        p = Polynomial(A, b)
        p = Polynomial(s)
        p = Polynomial(shape, variables, degree, terms[, inner])
        p = Polynomial(nr)
Input:
        There are different possible inputs:
        ---
        A - (n x t)-matrix or list of lists, representiong the exponents
        b - array-like of length t
        ---
        s - string, which represents the polynomial, variables as 'x0' or 'x(0)'
        ---
        shape - string, describes Newton polytope, can be 'simplex'/'standard_simplex'/'general'
        variables - int, maximal number of variables
        degree - int, maximal degree
        terms - int, number of terms
        inner [optional, default 0] - minimal number of interior points
        ---
        nr - number, which tells the rowid of the database
        ---
 
Additional keywords
        seed [default None] - seed for the random number generator
        dirty [default True] - flag, whether the input is in an unclean state
                USE ONLY IF YOU KNOW WHAT YOU ARE DOING.
        matlab_instance [default newly created] - bridge to matlab, to avoid starting multiple instances
        orthant [default (0,...,0)] - restriction to some orthants, one entry for each variable
                0 - unknown sign
                1/-1 - positive/negative half space
clear(self)
Delete all problem associated with the polynomial, to save memory.
detect_infinity(self)
Quick check, whether we can verify that the polynomial is unbounded.
 
This method iterates over all faces with degenerate points and checks whether the polynomial restricted to that face is negative.
 
Call:
        res = p.detect_infinity()
Output:
        res: 'None' if no negative face was found.
                Otherwise it is a pair consisting of:
                x_min - argument, where neagtive value is obtained
                indices - list of indices, which vertices form that negative face
gap(self)
Return the gap between lower bound and found minimum.
get_decomposition(self, symbolic=False)
Return a decomposition into non-negative polynomials, according to currently stored solution.
 
Note: If in SONC, there are points, which are not covered with the constant term, 
        the solution in exact arithmetic may still be slightly negative.
 
Call:
        decomposition = p.get_decomposition([symbolic])
Input:
        symbolic [optional, default False]: boolean, whether to create a solution in exact arithmetic.
                Currently only implemented for SONC.
Output:
        decomposition: list of polynomials
get_solution(self, index)
Return the solution given by the index.
get_solutions(self)
Return a list of (solver, time, optimum) for all solutions found.
gloptipoly_opt(self, solver='MOSEK')
Optimise the polynomial given by (A,b) via SOS using globtipoly in Matlab.
 
Let p be the polynomial given by (A,b). We want to find min{ p(x) : x in R^n} by asking, what is the minimal gamma such that p + gamma is a sum of squares.
This is the case iff there is some psd-matrix C such that p = Z^T * C * Z, where Z is the vector of all monomials.
 
Call:
        data = p.gloptipoly_opt()
Output:
        data: dictionary containing information about the solution
                - opt: optimal value
                - C: psd-matrix such that p = Z^T * C * Z, where Z is the vector of all monomials
                - time: time to compute the solution
                - status: 1 = Solved, 0 = otherwise
is_sum_of_monomial_squares(self, eps=0)
Check whether the polynomial is a sum of monomial squares.
 
Call:
        res = p.is_sum_of_monomial_squares([eps = 0])
Input:
        eps [optional, default 0]: accuracy, up to which value a coefficient is treated as zero.
Output:
        res: bool, whether the polynomial is a sum of monomial squares (up to given accuracy)
local_min(self, method='sonc', **kwargs)
Compute a local minimum, according to the given method.
 
Call:
        fmin, xmin = p.local_min([method,**kwargs])
Input:
        method: which method to use
                - random: gradient method with random starting points
                        see p._local_min_random()
                - sonc: single call of gradient method, starting form barycentre of SONC-minima
                        see p._local_min_sonc()
                - differential_evolution: scipy
                        see p._local_min_differential_evolution()
        **kwargs: dictionary of keyword-arguments, handled to the minimisation method
Output:
        fmin: minimal value found
        xmin: argument, where fmin is attained
opt(self, T=None, language='python', solver=None)
Optimise the polynomial given by (A,b) via SONC using cvx in Matlab.
 
WARNING: function is outdated
 
Let p be the polynomial given by (A,b). We want to find min{ p(x) : x in R^n} by asking, what is the minimal gamma such that p + gamma is a sum of non-negative circuit polynomials.
 
Call:
        data = p.opt([T, solver, check])
Input:
        solver [optional, default aux.SDP_SOLVER/aux.GP_SOLVER]: solver, to solve the problem, currenty possible: 
                Matlab: 'sedumi', 'sdpt3', 'Mosek'
                Python: 'ECOS', 'scs', 'cvxopt'
        T [optional, default None]: a covering of the interior points by simplices
                if none is given, a cover is computed
Output:
        data: dictionary containing information about the solution
                - opt: optimal value
                - C: matrix, coefficients for the decomposition
                - time: time to compute the solution
                - verify: 1 = Solved, -1 = error, 0 = otherwise/unchecked
                - status: status message of the solver
print_all(self, **kwargs)
print_solutions(self, form='grid', only_valid=False, params=False)
Print a table of all stored solutions.
 
You can obtain the solution with a given index by p.get_solution(<index>).
 
Call:
        p.print_solutions([only_valid, form])
Input:
        only_valid [boolean, default False]: flag, whether to print only verified solutions
                i.e. those with <solution>['verify'] == 1
        form [string, default 'grid'] - tableformat for tabulate
        params [boolean, default False]: flag, whether to print the parameters
relax(self)
Return a lower estimate for the polynomial.
 
All potentially newgative terms are made negative at once.
This function should be used, when checking the decomposition, obtained by get_decomposition(), since that functions works on the relaxation.
run_all(self, keep_alive=False, call_sos=True, clear=True)
Run all optimisation methods which are currently implemented.
 
The results are stored in self.old_solutions.
SOS is called only if <= 400 monomials
 
Current list of methods:
- sostools
- gloptipoly
- sos-cvx in Matlab, using sedumi 
- sos-cvx in Matlab, using sdpt3
- sos-cvx in Python using cvxopt (if matrix-size <= 120) 
 
- sonc-cvx in Matlab, using sedumi
- sonc-cvx in Matlab, using sdpt3
- sonc-cvx in Python using ECOS
 
If the Matlab engine was not found, only Python is run.
run_sonc(self, solver='ECOS')
Run SONC with two different cover strategies.
 
* cover, that maximises use of constant term
* cover, that uses all monomial squares
 
If both strategies yields the same cover, we run SONC only once.
run_sos(self)
Run all available SOS-methods to compute a lower bound.
 
If Matlab is available (if matrix-size <= 400):
        * Sostools: with and without 'sparse' flag
        * Gloptipoly
        * Yalmip: using 'solvesos' and 'sparsepop'
        * own implementation (only if <= 8000 constraints): using 'Mosek', 'sedumi' and 'sdpt3'
Python (if matrix-size <= 120):
        * cvxopt
        * MOSEK
sage_opt_python(self, solver='ECOS', **solverargs)
Optimise the polynomial given by (A,b) via SAGE using cvxpy.
 
Let p be the polynomial given by (A,b), where A is an (n x t)-matrix and b in R^t.
We want to find min{ p(x) : x in R^n} by asking, what is the minimal gamma such that p + gamma is a sum of arithmetic-geometric-mean exponentials (SAGE).
 
Call:
        data = p.sage_opt_python([solver], **solverargs)
Input:
        solver [optional, default aux.GP_SOVLER]: solver, to solve the problem, currenty possible: 'ECOS', 'cvxopt', 'scs', 'Mosek'
        solverargs: dictionary of keywords, handed to the solver
Output:
        data: dictionary containing information about the solution
                - opt: optimal value
                - C: (t x t)-matrix, coefficients for the decomposition, 
                - lambda: (t x t)-matrix, barycentri c coordinates
                - time: time to compute the solution
                - verify: 1 = Solved, -1 = error, 0 = otherwise/unchecked
                - status: status message of the solver
set_cover(self, T, split=True)
Set a new cover and store the previous one.
 
Call:
        p.set_cover(T)
Input:
        T: list of list of integers, where all entries are column indices of p.A
                For each l in T we need that p.A[:,l] describes a simplex with some interior points.
                If there already was a cover, it is appended to p.old_covers.
sonc_opt_python(self, solver='ECOS', **solverargs)
Optimise the polynomial given by (A,b) via SONC using cvxpy.
 
Let p be the polynomial given by (A,b). We want to find min{ p(x) : x in R^n} by asking, what is the minimal gamma such that p + gamma is a sum of non-negative circuit polynomials.
 
Call:
        data = p.sonc_opt_python([solver], **solverargs)
Input:
        solver [optional, default aux.GP_SOLVER]: solver, to solve the problem, currenty possible: 'ECOS', 'cvxopt', 'scs', 'Mosek'
        solverargs: dictionary of keywords, handed to the solver
Output:
        data: dictionary containing information about the solution
                - opt: optimal value
                - C: (m x (n-m))-matrix, coefficients for the decomposition
                - time: time to compute the solution
                - verify: 1 = Solved, -1 = error, 0 = otherwise/unchecked
                - status: status message of the solver
sonc_realloc(self, max_iters=10)
Print several solutions for SONC, with sucessively improved distribution of negative coefficients.
 
Call:
        p.sonc_realloc(max_iters)
Input:
        max_iters [optional, default 10]: number of iterations
sos_opt_matlab(self, solver='MOSEK')
Optimise the polynomial given by (A,b) via SOS using cvx in Matlab.
 
Let p be the polynomial given by (A,b). We want to find min{ p(x) : x in R^n} by asking, what is the minimal gamma such that p + gamma is a sum of squares.
This is the case iff there is some psd-matrix C such that p = Z^T * C * Z, where Z is the vector of all monomials.
 
Call:
        data = p.sos_opt_matlab([solver])
Input:
        solver [optional, default aux.SDP_SOLVER]: solver, to solve the problem, currenty possible: 'sedumi', 'sdpt3', 'Mosek'
Output:
        data: dictionary containing information about the solution
                - opt: optimal value
                - C: psd-matrix such that p = Z^T * C * Z, where Z is the vector of all monomials
                - time: time to compute the solution
                - verify: 1 = Solved, -1 = error, 0 = otherwise/unchecked
                - status: status message of the solver
sos_opt_python(self, solver='MOSEK', sparse=True, **solverargs)
Optimise the polynomial given by (A,b) via SOS using cvx.
 
Let p be the polynomial given by (A,b). We want to find min{ p(x) : x in R^n} by asking, what is the minimal gamma such that p + gamma is a sum of squares.
This is the case iff there is some psd-matrix C such that p = Z^T * C * Z, where Z is the vector of all monomials.
 
Note: scs randomly runs VERY long on trivial instances. Usage is possible, but discouraged.
 
Call:
        data = p.sos_opt_python(A,b,[solver],**solverargs)
Input:
        solver [optional, default 'CVXOPT']: solver, to solve the problem, currenty possible: 'CVXOPT', 'Mosek', 'SCS'
        solverargs: dictionary of keywords, handed to the solver
Output:
        data: dictionary containing information about the solution
                - opt: optimal value
                - C: psd-matrix such that p = Z^T * C * Z, where Z is the vector of all monomials
                - time: time to compute the solution
                - verify: 1 = Solved, -1 = error, 0 = otherwise/unchecked
                - status: status message of the solver
sostools_opt(self, solver='MOSEK', sparse=False)
Optimise the polynomial given by (A,b) via SOS using SOSTOOLS in Matlab.
 
Let p be the polynomial given by (A,b). We want to find min{ p(x) : x in R^n} by asking, what is the minimal gamma such that p + gamma is a sum of squares.
This is the case iff there is some psd-matrix C such that p = Z^T * C * Z, where Z is the vector of all monomials.
 
Call:
        data = p.sostools_opt()
Output:
        data: dictionary containing information about the solution
                - opt: optimal value
                - C: psd-matrix such that p = Z^T * C * Z, where Z is the vector of all monomials
                - time: time to compute the solution
                - status: 1 = Solved, 0 = otherwise
trivial_check(self)
Check whether p is a sum of monomial squares.
trivial_solution(self)
Compute a trivial solution to the SONC-problem.
 
Let p be the polynomial given by (A,b). We want to quickly find a gamma such that p + gamma is SONC.
 
Note: This function only works if the convex hull of the Newton polytope forms a simplex.
 
Call:
        data = p.trivial_solution()
Output:
        data: dictionary containing information about the solution
                - opt: feasible value
                - C: (m x (n-m))-matrix, coefficients for the decomposition
                - time: time to compute the solution
                - verify: 1 = Solved, -1 = error, 0 = otherwise/unchecked
                - status: status message of the solver
yalmip_opt(self, method='solvesos', solver='MOSEK')
Optimise the polynomial given by (A,b) via SOS using YALMIP in Matlab.
 
Let p be the polynomial given by (A,b). We want to find min{ p(x) : x in R^n} by asking, what is the minimal gamma such that p + gamma is a sum of squares.
This is the case iff there is some psd-matrix C such that p = Z^T * C * Z, where Z is the vector of all monomials.
 
Call:
        data = p.yalmip_opt()
Input:
        method [optional, default 'solvesos']: which method in Yalmip to use
                - solvesos
                - sparsepop
Output:
        data: dictionary containing information about the solution
                - opt: optimal value
                - C: psd-matrix such that p = Z^T * C * Z, where Z is the vector of all monomials
                - time: time to compute the solution
                - status: 1 = Solved, 0 = otherwise
z3_nonnegative(self)
Check nonnegativity via Z3.
 
Call:
        nonneg = p.z3_nonnegative()
Output:
        nonneg [bool] - whether the polynomial is nonnegative

Methods inherited from polynomial_base.Polynomial:
__add__(self, other)
Return the sum of this polynomial with another one.
__call__(self, x, dtype='float')
Evaluate the polynomial at point x.
__dict__ = mappingproxy({'__module__': 'polynomial_opt', '_...on Polynomial.z3_nonnegative at 0x7f9b7c643378>})
__eq__(self, other)
Check equality of polynomials.
__neg__(self)
Return the negation of this polynomial.
__sizeof__(self)
Return bit-size of the instance.
__str__(self)
Return the polynomial as string.
__sub__(self, other)
Return the difference between this polynomial and another one.
clean(self)
Bring polynomial into clean state.
copy(self)
Return a copy of itself.
derive(self, index)
Compute the derivative with respect to the given index.
 
Call:
        res = p.derive(index)
Input:
        index [integer] - index of variable, by which we derive p, starting with zero
Output:
        res - Polynomial, derivative of p by x_index
pip(self)
Return the polynomial in PIP-format.
prime(self, variables=None)
Compute full derivative of the polynomial.
 
Call:
        pprime = p.prime([variables])
Input:
        variables [optional, default: all occurring] - number of variables, by which we derive
Output:
        pprime - Polynomial, derivative of p
scaleround(self, factor)
Scale polynomial and round coefficients to integer.
 
Call:
        p.scaleround(factor)
Input:
        factor [number] - scale all coefficients by 'factor', then round to integer
 
Note: This function changes the coefficients in place and sets the 'dirty' flag to 'True'.
tex(self)
Return the polynomial as string for LaTeX.
to_symbolic(self)
Return the polynomial as symbolic expression in sympy.

Data descriptors inherited from polynomial_base.Polynomial:
__weakref__
list of weak references to the object (if defined)

Data and other attributes inherited from polynomial_base.Polynomial:
__hash__ = None

 
Data
        matlab_found = True
mosek_found = True
sympy_flag = True
x = x
z3_found = True