TL-DR: I would like to solve a linear program, but the problem itself involves multivariate polynomials. So I need tools to transform polynomials to their vectors of coefficients and back. Moreoever, in the end, after solving the corresponding linear program, I would like to reinterpret the solution as a ceritificate of positivity of the polynomial I am interested in, over the region of interest (defined using linear inequalities).
While I can probably write it from scratch, yet most of the functionality I need is probably already being used in SumOfSquares or Polynomials or in some other Julia package. Some comments would be appreciated.
Suppose you have 3 variables, x, y, z, say, and linear inequalities of the form
0 <= x <= 1
0 <= y <= 1
0 <= z <= 1
1 <= x + y + z <= 2
This gives us a number of nonnegative polynomials,
x
y
z
1-x
1-y
1-z
x+y+z-1
2-x-y-z
I would like to form the vector of all polynomials of degree up to 2 in the previous polynomials. This should for example contain 1, x, y, z, 1-x, etc., but also x^2, xy, x(1-x) and so on. Let us call this vector X, say.
I am given a polynomial p
p = x*(1-y) + y*(1-z) + z*(1-x)
I am interested in the problem of writing, if possible, p as a linear combination of the polynomials in X with nonnegative coefficients and, moreover, finding such an expression with the highest possible coefficient of 1.
Note that I specifically avoided mentioning sums of squares, because in the problem I am interested in, each variable actually represents a matrix, the product is the symmetric Kronecker product and the inequality represents the Loewner order. As a result, squares of polynomials in x, y and z are not necessarily nonnegative.
That being said, I wonder whether the above problem can be solved in Julia, for example using Jump and SumOfSquares or some other packages. I looked for a while in the documentation, but could not yet find what I want. If you know how I can solve the problem above, could you please help, or maybe give some clues? Thank you.