  Recently, the second and the third author 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 article 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, semi-algebraic 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
against 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.
