Effective algorithm to test positivity

Question

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$?

Answer 1

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.

Answer 2

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.

Answer 3

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.