Convex hulls of monomial curves, and a sparse positivstellensatz

Consider the closed convex hull K of a monomial curve given parametrically as (tm1,…,tmn), with the parameter t varying in an interval I. We show, using constructive arguments, that K admits a lifted semidefinite description by O(d) linear matrix inequalities (LMIs), each of size ⌊n2⌋+1, where d=max{m1,…,mn} 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 ℝ+, then p admits a representation p=t0σ0+⋯+td−kσd−k, where the polynomials σ0,…,σd−k are sums of squares and deg(σi)≤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.

arxiv.org/abs/2303.03826