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?

  • $\begingroup$ 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 $\endgroup$ – Per Alexandersson Aug 25 '16 at 0:33
  • $\begingroup$ 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. $\endgroup$ – Nick R Aug 25 '16 at 5:11
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ May I ask the downvoter to express their concerns? $\endgroup$ – Ilya Bogdanov Aug 29 '16 at 7:30

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.