1
$\begingroup$

Could anyone please help me find $a\left(x,y,z\right)$, $b_{i}\left(x,y,x\right),$$c_{i}\left(x,y,z\right)$ and $d\left(x,y,z\right)$ that are sums of squares of polynomials or rational functions such that

$$ \begin{array}a a\left(x,y,z\right)+b_{1}\left(x,y,z\right)\left(x+y\right)+b_{2}\left(x,y,z\right)\left(x+z\right)+b_{3}\left(x,y,z\right)\left(y+z\right)\\ +c_{1}\left(x,y,z\right)\left(4-x^{2}\right)+c_{2}\left(x,y,z\right)\left(4-y^{2}\right)+c_{3}\left(x,y,z\right)\left(4-z^{2}\right)\\ +d\left(x,y,z\right)\left(4+xyz-x^{2}-y^{2}-z^{2}\right) \end{array} $$

equals $15(2+x+y)^{2}(2+x+z)^{2}(2+y+z)^{2}-32(3+x+y+z)^{3}$ by Mathematica programming? or could anyone use the Mathematica codes on this page : Expressing a polynomial as a sum of squares to find $a\left(x,y,z\right)$, $b_{i}\left(x,y,x\right),$$c_{i}\left(x,y,z\right)$ and $d\left(x,y,z\right)$ for this polynomial?

Here are some Mathemtica codes that I wrote and you may use for the search by Mathematica programming:

  p = 15 (2 + x + y)^2 (2 + x + z)^2 (2 + y + z)^2 - 32 (3 + x + y + z)^3
 q11 = x + y
 q12 = x + z
 q13 = y + z
 q21 = 4 - x^2
 q22 = 4 - y^2
 q23 = 4 - z^2
 q3 = -4 + x^2 + y^2 - x y z + z^2

Thanks a lot.

$\endgroup$
  • 1
    $\begingroup$ Can you post in a Mathematica snippet with the equation so we can just cut and paste? $\endgroup$ – MikeY Mar 16 at 13:08
  • $\begingroup$ @MikeY Okay, posted. Best regards. $\endgroup$ – Dan K. Mar 16 at 14:06
  • $\begingroup$ @MikeY Could you find or use the Mathematica codes on this page: mathematica.stackexchange.com/questions/133141/… to find a(x,y,z), bi(x,y,x),ci(x,y,z) and d(x,y,z) for the polynomial in the question? Thanks. $\endgroup$ – Dan K. May 18 at 11:52
3
$\begingroup$

The polynomial

$$ p(x,y,z) = 15 (x+y+2)^2 (x+z+2)^2 (y+z+2)^2-32 (x+y+z+3)^3 $$

has a Newton polytope hull which is

NP = {{4, 2, 0}, {4, 0, 2}, {4, 0, 0}, {0, 4, 2}, {0, 4, 0}, {0, 2, 4}, {0, 0, 4}, {0, 0, 0}, {2, 4, 0}, {2, 0, 4}}

has all the powers even. Follows a picture for the Newton polytope. In black, the hull.

enter image description here

The monomials that can generate this set of points (red and black) are

$$ Z = \left\{1,z,z^2,y,y z,y z^2,y^2,y^2 z,x,x z,x z^2,x y,x y z,x y^2,x^2,x^2 z,x^2 y\right\} $$

now

$$ \cases{ a = Z^T\cdot A\cdot Z\\ b_1 = Z^T\cdot B_1\cdot Z\\ \vdots\\ c_3 = Z^T\cdot C_3\cdot Z\\ d = Z^T\cdot D\cdot Z } $$

are feasible candidates with $\{A,B_1,\cdots,C_3,D\}$ positive definite matrices. The next step is to determine the conditions such that all the monomials for $p_0(x,y,z)$

$$ \begin{array}a p_0(x,y,z) = a\left(x,y,z\right)+b_{1}\left(x,y,z\right)\left(x+y\right)+b_{2}\left(x,y,z\right)\left(x+z\right)+b_{3}\left(x,y,z\right)\left(y+z\right)\\ +c_{1}\left(x,y,z\right)\left(4-x^{2}\right)+c_{2}\left(x,y,z\right)\left(4-y^{2}\right)+c_{3}\left(x,y,z\right)\left(4-z^{2}\right)\\ +d\left(x,y,z\right)\left(4+xyz-x^{2}-y^{2}-z^{2}\right) \end{array} $$

are contained in the former Newton polytope. Those linear conditions $R(A,B_1,\cdots,C_3,D)$ are obtained as

$$ p(x,y,z) - p_0(x,y,z) = 0, \ \ \forall \{x,y,z\} $$

so the problem is reduced to:

Determine $\{A,B_1,\cdots,C_3,D\}$ positive definite, subjected to $R(A,B_1,\cdots,C_3,D)$

Resuming, we need some procedures to handle the symbolic, and a positiveness solver like CXV.

NOTE

The Newton polytope can be extracted with the script.

ExtractElements[f_, vars_] := Module[{rf, rf0, nrf, ef, cf},
rf = CoefficientRules[f, vars];
nrf = Length[rf];
If[nrf == 1, rf0 = rf[[1]], rf0 = rf];
ef = Map[First, rf0];
cf = Map[Last, rf0];
Return[{ef, cf}]]

vars = {x, y, z};
pol = 15 (2 + x + y)^2 (2 + x + z)^2 (2 + y + z)^2 - 32 (3 + x + y + z)^3;

{elems, rels} = ExtractElements[pol, vars]

and the convex hull can be obtained using (found in a repository)

ConvexDepenentQ[corners_, cand_] := Module[{w, ws}, w = Array[ws, Length@corners];
1 == Length@FindInstance[w.corners == cand && Total[w] == 1 && And @@ Table[w[[i]] >= 0, {i, Length@w}], w]];

ConvexReduce[data_] := Module[{corners, ncorners, test}, corners = data;
Do[ncorners = Delete[corners, Position[corners, data[[i]]]];
test = ConvexDepenentQ[ncorners, data[[i]]];
If[test, corners = ncorners];, {i, Length@data}];corners];

convexHull[data_] := Module[{corners, rd}, corners = {};
Do[corners = Join[corners, Select[data, Min[data[[;; , i]]] == #[[i]] ||  Max[data[[;; , i]]] == #[[i]] &]];, {i, Length@data[[1]]}];
corners = DeleteDuplicates@corners;
rd = Delete[data, First@Position[data, #] & /@ corners];
Do[If[ConvexDepenentQ[corners, rd[[i]]], , AppendTo[corners, rd[[i]]]], {i, Length@rd}];
ConvexReduce@DeleteDuplicates@corners];


CH = convexHull[elems]

The linear restrictions can be obtained with ExtractElements in the output rels

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. Just wondering, how do you know any polynomial for a hull with the powers even is always positive? Thanks a lot. $\endgroup$ – Dan K. Mar 21 at 9:36
  • $\begingroup$ It is a basic result from SOS theory. $\endgroup$ – Cesareo Mar 21 at 9:42
  • $\begingroup$ What you said is correct for SOS of polynomials, but I mean SOS of rational functions. Could you please explain why any polynomial for a hull with the powers even is always positive, or which reference has a clear explanation regarding that? Thanks a lot. $\endgroup$ – Dan K. Mar 21 at 10:14
  • $\begingroup$ Follow the Parrillo publications: google.com/… google.com/… $\endgroup$ – Cesareo Mar 21 at 10:43
  • $\begingroup$ Thank you for the link, but the reference at the link you gave does not say about Newton polytope. However, the theory in other references says that if f is PSD, then every vertex of new(f) has even coordinates and a positive coefficient. Why is any polynomial for a hull with the powers even always positive? Thanks a lot. $\endgroup$ – Dan K. Mar 21 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.