Positive Semidefinite Polynomial with Bounded Degree in each Variable

Question

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?

Answer 1

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.