Algèbre, géométrie, topologie

Convex hulls of monomial curves, and a sparse positivstellensatz

by Gennadiy Averkov


Consider the closed convex hull K of a  monomial curve given parametrically as (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) linear matrix inequalities (LMIs), each of size \lfloor n/2 \rfloor +1, where 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 monomials is non-negative on \mathbb{R}_+, then p admits a representation p=t^0\sigma_0+...t^{d-k}\sigma_{d-k} where the polynomials \sigma_i sums of squares and deg(\sigma_i)\leq 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. This is a joint work with Claus Scheiderer.