15
$\begingroup$

Is any algorithm known for determining whether or not a multivariate polynomial with integer coefficients can be written as a sum of squares of such polynomials?

By way of background, if we one replaces "polynomial" by "rational function" then there is such an algorithm, because a rational function is a sum of squares iff it is positive definite. But this equivalence fails for polynomials.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
12
$\begingroup$

Jose writes: "if you have a polynomial that is positive semidefinite, more likely than not it is a sum of squares"

This sort of statement is very sensitive to what probability distribution you use on the space of all polynomials. I am sure there are formulations in which it is true; here is one in which it is false.

Fix d greater than 1. Let Poly(2d,n) be the vector space of homogenous*, degree 2d polynomials in n variables. Let's choose polynomials uniformly at random from unit sphere in this space. Blekherman has computed that the probability that a polynomial is positive is ~ n^{-1/2}, while the probability that it is a sum of squares is ~ n^{-d/2}. So, for n large, almost all positive polynomials are not sums of squares.

Blekherman also has a recent preprint showing that, in the same sense, almost all positive convex polynomials are not sums of squares.

* If you don't like working with homogenous polynomials, notice that Poly(2d,n) is also the vector space of inhomogenous polynomials in n-1 variables with degree at most d. Just plug in 1 for the last variable. Under this correspondence, a polynomial is nonnegative on R^n if and only if it is nonnegative on R^{n-1} x {1}. The property of being strictly positive is not preserved by this transformation, but the polynomials which are nonnegative and not strictly positive form a set of measure 0.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I agree, to say "more unlikely" might need a bit more explanation. I will have to find my source and post it. Thanks for pointing out the papers of Blekherman. What I found a bit disturbing was that he used space of homogenous polynomials and made a conclusion over them,but the title and the work seems to confuse me. Is it known that if you use the density computed by Blekhherman for HOMOGENOUS positive polynomials one gets something of the same range for ANY positive polynomial? Also his paper on convex poly, does admit that there are no known non SOS polynomials that are convex $\endgroup$
    – Jose Capco
    Commented Nov 1, 2009 at 6:36
  • $\begingroup$ Here is a paper by Netzer and Lassere: tinyurl.com/y8unahb Could anyone teach me how to add hyperlinks when commenting? Anyway, in the paper they used l1-norm on the coefficient.. and from SOS being dense in PSD using that norm i concluded my remark. But to say "it is dense" is definitely not the same as "it is more", sorry for that. $\endgroup$
    – Jose Capco
    Commented Nov 1, 2009 at 7:21
  • 1
    $\begingroup$ Nothing to apologize for. It looks to me like the difference can be summarized in this way up in this way: If you hold n fixed and send d to infinity, then "most" positive polynomials are sums of squares. If you hold d fixed and send n to infinity then "most" are not. Of course, in both cases, you also have to specify the norm being used on the vector space of polynomials. $\endgroup$
    – David E Speyer
    Commented Nov 1, 2009 at 12:59
  • $\begingroup$ I added a footnote to address your question about homogenous versus nonhomogenous polynomials. $\endgroup$
    – David E Speyer
    Commented Nov 1, 2009 at 13:03
  • $\begingroup$ Thankks.. yes, I totally missed the 2d part.. I was thinking homogenous in general, if you have even degree of course dehomogenizing gives us a positive polynomial .. and if you have a degree 2d non-homegenous positive polynoomial.. homogenizing it also makes it positive (because of the even degree). I think the "intuition" i got why it feels more likely to have psd than sos, was from 2-variables as you have said things look different as variables increases.. for two variables it took some time after Hilbert's 17th problem that someone could give an example of a positive non-sos polynomial $\endgroup$
    – Jose Capco
    Commented Nov 1, 2009 at 15:49
8
$\begingroup$

Yes, the group of Parillo developed an algorithm and a matlab toolbox they called SOSTOOLS

There is a degree of complexity though, I am not an expert in their algorithm so I don't know how efficient their algorithm is. I remember reading that the sum of squares polynomials are dense in the space of positive semidefinite polynomials by some norm.. I think it was L1 norm. And if you know that your polynomial is positive and convex, then its "more likely" that its a sum of squares (as far as I know, no one has yet shown that there are convex (multivariate) polynomials that are positive but not sum of squares).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Added your link. $\endgroup$
    – David E Speyer
    Commented Nov 1, 2009 at 12:57
3
$\begingroup$

Determining whether or not a polynomial is a sum of squares can be done in polynomial time; the problem is equivalent to semidefinite programming. As Jose Capco mentioned above, Pablo Parrilo is an authority on this subject, and has written a number of papers explaining the relationship.

Parrilo has a particularly short, simple, and self-contained exposition of this relationship in Parrilo, Pablo A. "Sum of squares programs and polynomial inequalities." SIAG/OPT Views-and-News: A Forum for the SIAM Activity Group on Optimization. Vol. 15. No. 2. 2004.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ I guess it is not clear whether it is really doable in polynomial time. The complexity status of the semidefinite feasibility theorem is unknown. Although some people believe it could be in P it is not even known to be in NP. $\endgroup$
    – Markus Schweighofer
    Commented Aug 10, 2015 at 0:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .