Polynomials nonnegative on a grid and discrete optimization

Abstract:

We characterize the real-valued polynomials on $\mathbb R^n$ that are nonnegative (not necessarily strictly positive) on a grid $\mathbb K$ of points of $\mathbb R^n$, in terms of a weighted sum of squares whose degree is bounded and known in advance. We also show that the mimimization of an arbitrary polynomial on $\mathbb 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 $\mathbb K$-moment problem.