A Positivstellensatz for Sums of Nonnegative Circuit Polynomials

Recently, the second and third authors developed sums of nonnegative circuit polynomials (SONC) as a new certificate of nonnegativity for real polynomials, which is independent of sums of squares. In this paper we show that the SONC cone is full-dimensional in the cone of nonnegative polynomials. We establish a Positivstellensatz which guarantees that every polynomial which is positive on a given compact, semialgebraic set can be represented by the constraints of the set and SONC polynomials. Based on this Positivstellensatz, we provide a hierarchy of lower bounds converging to the minimum of a polynomial on a given compact set $K$. Moreover, we show that these new bounds can be computed efficiently via interior point methods using results about relative entropy functions.