EDIT: Feel free to replace "non-negative on the non-negative orthant" with "non-negative on a convex set, cone, or any other class of sets that includes the orthant".

A popular way to establish that a polynomial only takes non-negative values, or is non-negative, is to check whether it can be expressed in as a sum of squares. This can be done numerically using some convex program.

However, as discussed in here, there are many polynomials which are non-negative but cannot be expressed as a sum of squares. Furthermore, many polynomials which are not non-negative everywhere are non-negative on the non-negative orthant, for example, any odd polynomial with positive coefficients.

My questions are (sorry that they overlap a bit):

$1$- What is known about polynomials with real coefficients, $f:\mathbb{R}^n\rightarrow\mathbb{R}$, that satisfy

$$x\in\{y\in\mathbb{R}^n:y_i\geq 0\quad\forall i=1,\dots,n\}\Rightarrow f(x)\geq0?$$

$2$- Are there any tractable ways to test whether a given polynomial satisfies the above?

Thanks in advanced.


It is possible to come up with such a computationally tractable$-$sufficient, but not necessary$-$test.

We can rephrase "does the polynomial $f$ always return a non-negative real number when evaluated on the non-negative orthant?" as "is the semialgebraic set


empty?". As discussed in here, a sufficient test whether the above set$-$or, indeed, whether any semialgebraic set$-$is empty can be carried out in polynomial time. I'll just quickly summarise the main idea:

Consider the following theorem proved by Stengle in 1974:

Theorem (Stengle's Positivstellensatz). Let $\{f_j\},\{g_k\},\{h_l\}\subseteq\mathbb{R}[x_1,x_2\dots,x_n]$ be finite sets of polynomials with real valued coefficients. Let $P$ be the cone generated by $\{f_j\}$, $M$ the multiplicative monoid generated by $\{g_k\}$, and $I$ the ideal generated by $\{h_l\}$$-$for precise definitions, see Section 4 of the paper. Then,

$$\{x\in\mathbb{R}^n : f_j(x)\geq 0,\quad g_k(x)\neq 0,\quad h_l(x)=0, \quad\quad\forall i,j,k\}$$

is empty if and only if there exists $f\in P$, $g\in M$ and, $h\in I$ such that $f+g^2+h=0$.

The triplet $(f,g,h)$ is called an infeasibility certificate or a refutation. As discussed in section 5 of the paper, a sufficient condition for the existence such certificates is that a given semidefinite program is feasible$-$this actually builds on the tool mentioned in the question that can test whether a given polynomial is a sum of squares. Once the program is solved, the certificate can be recovered from its solution. There is even a free Matlab package that has been developed exclusively for this purpose.

ASIDE: This is the first time I've answered my own question. I came across the above a bit after posting the question and I thought it was worth mentioning in case it's of any use to anyone else.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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