Polynomials nonnegative on a grid and discrete optimization
Jean Bernard Lasserre · Transactions of the American Mathematical Society · 2001
We characterize the real-valued polynomials on R n \mathbb R^n that are nonnegative (not necessarily strictly positive) on a grid K \mathbb K of points of R n \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 K \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 K \mathbb K -moment problem.