# Positive Semidefinite Polynomial with Bounded Degree in each Variable

Given a polynomial $p \in \mathbb{R}[x_1, \ldots, x_n]$, suppose that for each monomial in $p$, $c_\alpha x_1^{\alpha_1} \ldots x_n^{\alpha_n}$ we have $\alpha_i = 0, 1, 2$. I have been calling these polynomials multiquadratic (is there another established name for them?).

I am interested in developing an algorithm to decide if given a multiquadratic polynomial $p$ it is positive semidefinite, that is if for all inputs in $\mathbf{x} \in \mathbb{R}^n$ we have $p(\mathbf{x}) \geq 0$. In general I have been told this is a difficult problem unless one can reduce to sum of squares which is not always possible.

In the case of multiquadratic polynomials are all positive semidefinite polynomials sum of squares?

Edit: I believe the polynomial $p(x,y,z) = x^2y^2 + x^2 z^2 + y^2 z^2 - 4xyz + 1$ is PSD, multiquadratic, but not SOS

Is there still a decent algorithm for determining if a given multiquadratic polynomial is PSD? Is this a NP-hard problem?

• Yalmip in MATLAB? users.isy.liu.se/johanl/yalmip/… Besides, your polynomial should be SOS, according to Hilbert, since it has 3 variables and degree 4. en.wikipedia.org/wiki/Hilbert%27s_seventeenth_problem – Per Alexandersson Aug 25 '16 at 0:33
• I believe that result refers to homogeneous polynomials in 3 variables of degree 4. If you were to homogenize this polynomial it would be 4 variables of degree 4. Since not all PSD multiquadratic polynomials are SOS, I don't believe the MATLAB documentation you provided will be helpful. – Nick R Aug 25 '16 at 5:11
• You can use Yalmip to look for a SOS decomposition, after homogenization, in your specific case, that was my point. I have used it successfully on larger cases before. – Per Alexandersson Aug 25 '16 at 10:44

The conjectured polynomial $p(x,y,z)$ indeed works. It is PSD by comparing the arithmetic and geometric means of $x^2y^2,\ y^2z^2,\ z^2x^2$ and 1.
To show that it is not SOS, assume that $$p(x,y,z)=\sum_i f_i(x,y,z)^2.$$ Clearly, $\deg f_i\leq 2$, otherwise $\deg p$ would be greater than 4.
Notice that $$p(x,0,0)=1=\sum_i f_i(x,0,0)^2;$$ this means that all $f_i(x,0,0)$ are constants, i.e., no $f_i$ contains a non-constant monomial depending on $x$ only. The same holds for other variables.
Therefore, each monomial in $f_i$ is either constant or quadratic. But then the term $-4xyz$ cannot appear in $p$ --- a contradiction.