# Can we test whether a polynomial only takes non-negative values on the non-negative orthant?

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?

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

$$\{x\in\mathbb{R}^n:f(x)<0,x_1\geq0,x_2\geq0,\dots,x_n\geq0\}$$

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.