2
$\begingroup$

How are polynomials called that are positive for all positive, real arguments, e.g., xy + z?

How can one determine if a polynomial has this property?

$\endgroup$
7
  • $\begingroup$ The answer to the second half of your question is probably Sturm's Theorem, see en.wikipedia.org/wiki/Sturm%27s_theorem $\endgroup$ Jun 15, 2011 at 11:19
  • $\begingroup$ @Roland, I thought Sturm's Theorem applied only to polynomials in one variable. $\endgroup$ Jun 15, 2011 at 12:38
  • 1
    $\begingroup$ Please read the introduction of arXiv:1010.3465v1 [math.AG] $\endgroup$ Jun 15, 2011 at 13:27
  • $\begingroup$ @Claudio, seems like the paper is only about the stronger property that the polynomial is positive (or non-negative) for all arguments, not only for all positive arguments. $\endgroup$
    – ccom
    Jun 15, 2011 at 13:38
  • 4
    $\begingroup$ @ccom You can probably apply that paper to P(x^2,y^2,...) $\endgroup$ Jun 15, 2011 at 14:35

4 Answers 4

5
$\begingroup$

A matrix $A$ such that $x'Ax\geq 0$ for all $x$ is called positive semidefinite. A matrix $A$ such that $x'Ax\geq 0$ for all $x\geq 0$ (componentwise) is called copositive. While positive semidefiniteness is easy to test algorithmically, the weaker condition of copositivity is co-NP-complete to test.

Up to some details about strict vs. nonstrict inequalities which I do not think will be crucial, testing copositivity is an instance of the problem you propose, so we should expect this problem to be NP-hard. That is, we should not expect an efficient general procedure for solving it.

There are algorithmic techniques such as sums-of-squares and semidefinite programming which can in practice certify positivity of many polynomials (globally, or as you want here, on sets such as the positive orthant) quickly, but except in very special cases the efficiency of these methods is not guaranteed.

$\endgroup$
4
  • $\begingroup$ How does it relate to checking positive definiteness of P(x1^2, x2^2, ...), as Laurent Berger suggested? $\endgroup$
    – ccom
    Jun 15, 2011 at 21:03
  • $\begingroup$ After appropriate simplifications to take into account the newly-introduced symmetries (the new polynomial will be invariant under all maps $x_i\mapsto -x_i$), the approaches are essentially equivalent. $\endgroup$
    – Noah Stein
    Jun 16, 2011 at 1:06
  • $\begingroup$ I learned about these things from my advisor Pablo Parrilo's course "Algebraic Techniques and Semidefinite Optimization" (notes at stellar.mit.edu/S/course/6/sp10/6.256). If that link doesn't work (it may require some MIT credentials) I believe he has an older version of the course notes on MIT OCW. $\endgroup$
    – Noah Stein
    Jun 16, 2011 at 9:22
  • $\begingroup$ You're welcome; I'm glad I could help. $\endgroup$
    – Noah Stein
    Jun 16, 2011 at 15:50
3
$\begingroup$

I am not sure what they are called, but let's call them positive for now.

I also don't know if there is a really good criterion for deciding whether a polynomial is positive, but here is what I would try:

Let $f$ be the polynomial in question. If you can determine the zero set of the polynomial, then basically you are in business. This zero set will cut up the space into connected cells (not necessarily bounded) and in each of these cells the sign of the values will be constant. Also, I think there should be only finitely many such cells, so you would have to check only finitely many values to know where your polynomial is positive.

Of course, finding the zero set may not be simple and finding the cell decomposition may be even harder, but if your polynomial is somewhat special you might get lucky.

For example if $f(x,y,z)=xy+z$ then the zero set is $$ Z(f)=\{(x,y,-xy)| (x,y)\in \mathbb R^2\}\subset \mathbb R^3 $$ The corresponding cell decomposition is $$ \mathbb R^3= Z_+\cup Z(f) \cup Z_- $$ where $$ Z_+=\{(x,y,-xy+a)| (x,y)\in \mathbb R^2, a\in\mathbb R_+\}\subset \mathbb R^3 $$and $$ Z_-=\{(x,y,-xy-a)| (x,y)\in \mathbb R^2, a\in\mathbb R_+\}\subset \mathbb R^3 $$ and so it is enough to check that $f(1,1,1)>0$ and $f(1,1,-1)<0$ to see that $f|_{Z_+}>0$ and $f|_{Z_-}<0$. Finally you check that $$ Z_+\supseteq \mathbb {R_+\times R_+ \times R_+} $$


If finding the zeros seems to be too difficult there is one more thing you can try. Fix the value of one variable and see if the one smaller dimensional problem is solvable. Then you "only" have to do it for every positive value of that one variable.

In the above example this would work out like this:

For an $c\in\mathbb R_+$ let $$f_c(x,y):=f(x,y,c)=xy+c$$

Now the zero set of $f_c$ is $$ Z(f_c)=\{(x, -\frac cx) | x\in \mathbb R\}. $$ For this the cell decomposition is easy (left to the reader) and it can be easily seen that $f_c$ is positive for any $c$. I suppose you can iterate this, although it will become increasingly more difficult to see how the value does or does not depend on the fixed variables. In any case, this is at least something to try.

$\endgroup$
1
  • $\begingroup$ Thanks, Sándor. Unfortunately, the zero set is difficult to determine, and fixing a variable, also. They're polynomials of high degree and of many (>10) variables. $\endgroup$
    – ccom
    Jun 15, 2011 at 16:25
2
$\begingroup$

As mentioned, $P(x,y,z)$ being positive for positive x,y,z is the same as $P(x^2,y^2,z^2)$ always being positive, so we can just consider the case of positive polynomials. The single-variable case is a lot easier since a polynomial being non-negative is equivalent to it being a sum of squares, and there are good algorithms for decomposing a polynomial (even multivariate) as a sum of squares. There's an overview of this at: http://junction.stanford.edu/~lall/data/engr210b_0405/sum_of_squares_2004_11_07_01.pdf

In the multivariable case the positivstellensatz (also see: Hilbert's Seventeenth Problem http://en.wikipedia.org/wiki/Hilbert%27s_seventeenth_problem) tells us that the polynomial isn't necessarily a sum of squares, but that if you multiply it by some appropriate square you can get a sum of squares. These polynomials are sometimes called (semi-)definite polynomials.

We have no real good way of recognizing definite polynomials, which is to be expected since this problem is NP-complete (you can encode SAT in terms of arithmetic on variables being 0 or 1)

$\endgroup$
-1
$\begingroup$

In the case of a quadratic form they are called positive definite and you can tell if a homogeneous quadratic form has this property by looking at the eigenvalues of the matrix that defines it. In general for a non homogeneous one you could use calculus.

$\endgroup$
4
  • $\begingroup$ I think you missed the "positive" in "positive real arguments." $\endgroup$ Jun 15, 2011 at 11:14
  • $\begingroup$ O yes I did, i will edit. $\endgroup$
    – Oliver
    Jun 15, 2011 at 11:21
  • $\begingroup$ I'm probably missing something. How do I use calculus in case effectively? Suppose I have a homogeneous polynomial of degree 6 in 12 variables. $\endgroup$
    – ccom
    Jun 15, 2011 at 11:52
  • 1
    $\begingroup$ This property isn't equivalent to positive-definite for quadratic forms. For example, $xy$ has the desired property but is not positive-definite. $\endgroup$ Jun 15, 2011 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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