Polynomials nonnegative on a grid and discrete optimization

We characterize the real-valued polynomials on R(n) that are nonnegative (not necessarily strictly positive) on a grid K of points of R(n), in terms of a weighted sum of squares whose degree is bounded and known in advance. We also show that the minimization of an arbitrary polynomial on K (a discrete optimization problem) reduces to a convex continuous optimization problem of fixed size. The case of concave polynomials is also investigated. The proof is based on a recent result of Curto and Fialkow on the K-moment problem.