A Positivstellensatz for Sums of Nonnegative Circuit Polynomials

2016/07/20 by Dressler, Mareike, Iliman, Sadik, de Wolff, Timo · 5 citations
#52B20 #90C25 #Algebraic Geometry (math.AG) #FOS: Mathematics #Optimization and Control (math.OC) #Primary: 14P10 #Secondary: 12D05

paper · doi:10.48550/arxiv.1607.06010

Abstract

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.

Cited by

• Exposed extreme rays of the SONC cone
• Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
• Non-SOS Positivstellensätze for semi-algebraic sets defined by polynomial matrix inequalities
• Non-negative polynomials without hyperbolic certificates of non-negativity
• Dual certificates of primal cone membership

Related

• On Supports of Sums of Nonnegative Circuit Polynomials
• Nonnegative Polynomials and Circuit Polynomials
• Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
• The dual cone of sums of non-negative circuit polynomials
• A Generalized Muirhead Inequality and Symmetric Sums of Nonnegative Circuits