13
$\begingroup$

Let $f(x_1,\ldots, x_n)$ be a real polynomial in several variables. Is there an effective algorithm to test whether $f$ is positive (or nonnegative) on the whole of ${\mathbb{R}}^n$?

$\endgroup$
4
  • 2
    $\begingroup$ By "effective" you mean "reasonably fast" or simply "in theory there is an algorithm"? Also, it is difficult to feed a real number to a computer: do you really want real coefficients or would rational coefficients be enough? $\endgroup$
    – damiano
    Aug 25, 2010 at 8:00
  • 4
    $\begingroup$ The existence of an effective algorithm follows from Tarski's theorem on decidability in real-closed fields. Whether there's a practcial algorithm is another matter. $\endgroup$ Aug 25, 2010 at 9:27
  • 4
    $\begingroup$ There is an algorithm, by Tarski's theorem. My usual reference for practical aspects of this sort of thing is "Algorithms in Real Algebraic Geometry" books.google.com/books?id=ecwGevUijK4C $\endgroup$ Aug 25, 2010 at 11:36
  • 1
    $\begingroup$ Thanks everyone for their comments. I'm aware that nonnegative f are sums of squares of rational functions, but i was looking for whether the positivity of f could be checked via some other method not subscribing to sums of squares. $\endgroup$
    – user2529
    Aug 26, 2010 at 12:55

3 Answers 3

14
$\begingroup$

If by effective you mean "is this computable", then yes, the computational versions of Tarski-Seidenberg such as cylindrical algebraic decomposition give you a finite algorithm. (I suppose this is assuming your polynomial has rational coefficients, or at least algebraic coefficients each given by a polynomial they satisfy along with an interval isolating them from other roots. I would guess the problem is not computable if your coefficients are given by Turing machines which compute [successively better approximations to] the reals in question, but I'm guessing that's not the problem you're asking about.)

If by effective you mean "can this be done in polynomial time", the answer is probably not; the problem is NP-hard. In particular, a matrix $A$ is defined to be copositive if $x^T A x\geq 0$ for all elementwise nonnegative column vectors $x$. That is to say, $A$ is copositive if and only if $\left[\begin{smallmatrix}x_1^2 & \cdots & x_n^2\end{smallmatrix}\right]A\left[\begin{smallmatrix}x_1^2 & \cdots & x_n^2\end{smallmatrix}\right]^T\geq 0$ for all real $x$, so checking copositivity is a particular example of the kind of problem you have mentioned. Murty and Kabadi's 1987 paper shows that checking if an integer matrix is not copositive is NP-complete. In particular this means that checking nonnegativity is NP-hard even in the degree four case.

If by effective you mean "are there polynomial-time methods that work well in practice", the answer is yes. In particular one can check sufficient conditions like whether $f$ is a sum of squares of polynomials (and a hierarchy of tighter conditions) in polynomial time using semidefinite programming, and often this allows one to solve such problems. Such methods often enable one to compute the global minimum of a polynomial and so can often even give a "no" answer despite the fact that they are a priori just sufficient conditions for nonnegativity. If you are interested in such techniques I would recommend the papers by Parrilo, Lasserre, Nie, etc. and in particular Parrilo's course on MIT OpenCourseWare.

$\endgroup$
1
  • $\begingroup$ i will check out what is cylindrical algebraic decomposition. $\endgroup$
    – user2529
    Aug 26, 2010 at 12:55
4
$\begingroup$

In practice, the biggest issue is whether your polynomial is a sum of squares (of polynomials) or not. (It's always a sum of squares of rational functions, but that's not helping.) If it's the case, then the methods of Parrilo et al. can really cut down on the computation time. It's all very well explained on the MIT OpenCourseWare.

Equally valid though would be to produce one point in each connected component of $\{f \neq 0\}$ by cylindrical algebraic decomposition or variants, and test the sign of $f$ on each sample point.

On the other hand, if you want a theoretical result (say for a sequence of polynomials), there is no reasonable general method.

$\endgroup$
2
$\begingroup$

If you could find an upper bound for degrees of polynomials used in Positivstellensatz I guess you can create an algorithm for this.

You would like to take a look at Positivstellensatz, for instance in the book of Bochnak-Coste-Roy "Real Algebraic Geometry" under Corollary 4.4.3 (this corollary combines Positivstellnsatz, Negativstellensatz and Nullstellensatz for real closed fields). A more abstract form can be found in a German book "Einführung in die Reelle Algebra" by Knebusch and Scheiderer (the book is now freely available for download from the university of Regensburg library: here). You would also like to see the works by Schmüdgen and Putinar on various forms of Positivstellensätze.

$\endgroup$
2
  • 2
    $\begingroup$ Aren't the degree bounds horrible, though? $\endgroup$ Nov 17, 2011 at 15:37
  • $\begingroup$ I believe Schmüdgen, Schweighofer and Prestel were addressing this at some point. I think in a paper Schweighofer even introduced some algorithms and discussed the complexity involved. But as this is not my area of expertise, I can't really say much more than this. $\endgroup$
    – Jose Capco
    Nov 17, 2011 at 19:57

Your Answer

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