Friday, 22 September 2006

polynomials - Effective algorithm to test positivity

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 xgeq 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^2end{smallmatrix}right]Aleft[begin{smallmatrix}x_1^2 & cdots & x_n^2end{smallmatrix}right]^Tgeq 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.

No comments:

Post a Comment