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
$$\{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.