Convex hulls of monomial curves, and a sparse positivstellensatz

Consider the closed convex hull $K$ of a monomial curve given parametrically as $(t^{m_1},\dots ,t^{m_n})$, with the parameter $t$ varying in an interval $I$. We show, using constructive arguments, that $K$ admits a lifted semidefinite description by $\mathcal{O}(d)$ linear matrix inequalities (LMIs), each of size $\lfloor \frac{n}{2}\rfloor +1$, where $d=\max \{m_1,\dots ,m_n\}$ is the degree of the curve. On the dual side, we show that if a univariate polynomial $p(t)$ of degree $d$ with at most $2k+1$ monomials is non-negative on ${\mathbb{R}}_{+}$, then $p$ admits a representation $p=t^0{\sigma }_0+\cdots +t^{d-k}{\sigma }_{d-k}$, where the polynomials ${\sigma }_0,\dots ,{\sigma }_{d-k}$ are sums of squares and $\mathrm{deg}({\sigma }_i)\le 2k$. The latter is a univariate positivstellensatz for sparse polynomials, with non-negativity of $p$ being certified by sos polynomials whose degree only depends on the sparsity of $p$. Our results fit into the general attempt of formulating polynomial optimization problems as semidefinite problems with LMIs of small size. Such small-size descriptions are much more tractable from a computational viewpoint.