Polynomials nonnegative on a grid and discrete optimization (Q2759070)

The author characterizes the polynomials \(p\in\mathbb{R}[X_1, \dots, X_n]\) that are non-negative on a `grid' \(K\) in \(\mathbb{R}^n\) where \(K\) is defined by \(g_i(X_1, \dots, X_n)=0\), \(1\leq i\leq n\), and \(g_i= \prod^{2r_i}_{j=1} (X_i-a_{ij})\). The author shows that every polynomial \(p\) of degree \(2r_0\) or \(2r_0-1\), non-negative on \(K\), can be written as a sum of squares of polynomials weighted by the polynomials \(g_i\), and whose degree is bounded by \(r+\max \{r_0-r, \max^n_{i=1} r_i\}\) with \(r=\sum^n_{i=1} (2r_i-1)\), independently of the points in the grid \(K\).NEWLINENEWLINE To prove this result, the author uses a detour to the associated discrete optimization problem \(p\mapsto p^*:= \min_{x\in K}p(x)\). He shows that this discrete problem is equivalent to a continuous convex optimization problem whose size depends on the number of points, but not the points themselves in \(K\). For this, the author defines a sequence of refined, so-called convex semidefinite relaxations of the original discrete optimization problem.