We characterize the real-valued polynomials on R-n that are nonnegative (no
t 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 pr
oof is based on a recent result of Curto and Fialkow on the K-moment proble
m.