polynomial
index
/homes/combi/seidler/Programmierung/polynomial_comparison/python/polynomial.py

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

 
Modules
       
aux
cvxpy
json_tricks
matlab
numpy
random
re
sqlite3
sympy
warnings

 
Classes
       
builtins.object
Polynomial

 
class Polynomial(builtins.object)
    Class for multivariate polynomials in sparse notation, focus on optimisation.
 
  Methods defined here:
__add__(self, other)
Return the sum of this polynomial with another one.
__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
        lazy [default True] - flag whether to create the optimisation problem instances at the start;
                True means that the problem instances are created only when needed, this is advised for larger degree
        hull_size [default None] - int, up to which index we have to take the first few coefficients to get the convex hull
                if None is given, the programme computes the hull itself
        matlab_instance [default newly created] - bridge to matlab, to avoid starting multiple instances
__neg__(self)
Return the negation of this polynomial.
__str__(self)
Return the polynomial as string.
__sub__(self, other)
Return the difference between this polynomial and another one.
as_dict(self)
Return polynomial as dictionary of type { exponent: coefficient }.
copy(self)
Return a copy of itself.
evaluate(self, x)
Evaluate the polynomial at point x.
get_decomposition(self)
Return a decomposition into non-negative polynomials, according to currently stored solution.
get_solutions(self)
Return a list of (solver, time, optimum) for all solutions found.
gloptipoly_opt(self)
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
improve_sonc(self)
Reduce numerical errors in the solution for the SONC-problem.
 
Usually the solvers return a solution which violates the constraints.
But due to the nature of the SONC-problem it is very easy to obtain a feasible solution.
 
Note: This only update the variables (and thus the violation of the constraints).
        It does NOT update the optimum self.prob_sonc.value.
 
Call:
        p.improve_sonc()
opt(self, method='even', T=None, language='python', solver=None)
Optimise the polynomial given by (A,b) via SONC 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 non-negative circuit polynomials.
 
Call:
        data = p.opt([method, T, solver, check])
Input:
        method [optional, default 'even']: solving method, currently allows the following
                - even: get a cover, where each simplex contains zero,
                        split the interior points evenly and opt each simplex separately
                - outer: get a cover with simplices, trying to use each summand
                        solve one big problem, with variable splitting of the coefficients
                - cascade: get a cover with simplices, trying to use each summand
                        Then optimise each simplex, starting with those far away from zero and update the remainig coefficients.
        solver [optional, default 'sedumi'/'ECOS']: solver, to solve the problem, currenty possible: 
                Matlab: 'sedumi', 'sdpt3'
                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: 3D-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_solutions(self, form='grid', only_valid=False)
Print a table of all stored solutions.
 
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
run_all(self, keep_alive=False)
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 SCS (if matrix-size <= 120) 
 
- sonc-cvx in Matlab, using sedumi
- sonc-cvx in Matlab, using sdpt3
- sonc-cvx in Python using ECOS
- sonc-cvx in Python using SCS (if A has <= 400 entries)
 
CVXOPT in Python is not used, since it fails in nearly every case.
If the Matkab engine was not found, only Python is run.
set_cover(self, T)
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_matlab_simplex(self, solver='sedumi')
Optimise the polynomial given by (A,b) via SONC 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 non-negative circuit polynomials.
 
Note: This function only works if the convex hull of A's columns form a simplex.
 
Call:
        data = p.sonc_opt_matlab_simplex([solver])
Input:
        solver [optional, default 'sedumi']: solver, to solve the problem, currenty possible: 'sedumi', 'sdpt3'
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_opt_python(self, solver='ECOS', **solverargs)
Optimise the polynomial given by (A,b) via SONC 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 non-negative circuit polynomials.
 
Note: This function is for the general case.
        If the Newton polytope is a simplex, call p.sonc_opt_python_simplex().
 
Call:
        data = p.sonc_opt_python([solver], **solverargs)
Input:
        solver [optional, default 'ECOS']: solver, to solve the problem, currenty possible: 'CVXOPT', 'SCS', 'ECOS'
        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_opt_python_simplex(self, solver='ECOS', **solverargs)
Optimise the polynomial given by (A,b) via SONC 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 non-negative circuit polynomials.
 
Note: This function only works if the convex hull of the Newton polytope forms a simplex.
 
Call:
        data = p.sonc_opt_python_simplex([solver], **solverargs)
Input:
        solver [optional, default 'ECOS']: solver, to solve the problem, currenty possible: 'CVXOPT', 'SCS', 'ECOS'
        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
sos_opt_matlab(self, solver='sedumi')
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 'sedumi']: solver, to solve the problem, currenty possible: 'sedumi', 'sdpt3'
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='SCS', **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.
 
Call:
        data = p.sos_opt_python(A,b,[solver],**solverargs)
Input:
        solver [optional, default 'CVXOPT']: solver, to solve the problem, currenty possible: 'CVXOPT', '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, 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
symbolic(self)
Return the polynomial as symbolic expression in sympy.
tex(self)
Return the polynomial as string for LaTeX.
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

Data descriptors defined here:
__dict__
dictionary for instance variables (if defined)
__weakref__
list of weak references to the object (if defined)

 
Data
        matlab_found = True
x = x