Convex hulls of monomial curves, and a sparse positivstellensatz

Consider the closed convex hull K of a monomial curve given parametrically as (tm₁,… ,tmₙ) ( t m 1 , … , 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 O(d) O ( d ) linear matrix inequalities (LMIs), each of size n/2 +1 n 2 + 1 , where d= max ₁,… ,mₙ\ d = max { m 1 , … , 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$$ 2 k + 1 monomials is non-negative on R₊ R + , then p admits a representation p = t⁰ σ ₀ + ⋯ + tᵈ⁻ᵏ σ d-k p = t 0 σ 0 + ⋯ + t d - k σ d - k , where the polynomials σ ₀,… ,σ d-k σ 0 , … , σ d - k are sums of squares and (σ ᵢ) ≤ 2k deg ( σ i ) ≤ 2 k . 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.