Amoebas, Nonnegative Polynomials and Sums of Squares Supported on Circuits

Algebra Seminar
Monday, October 5, 2015 - 3:05pm for 1 hour (actually 50 minutes)
Skiles 006
Timo de Wolff – Texas A&M University –
Josephine Yu
Deciding nonnegativity of real polynomials is a key question in real algebraic geometry with crucial importance in polynomial optimization. Since this problem is NP-hard, one is interested in finding sufficient conditions (certificates) for nonnegativity, which are easier to check. The standard certificates are sums of squares (SOS), which trace back to Hilbert (see Hilbert’s 17th problem). In this talk we completely characterize sections of the cones of nonnegative polynomials and sums of squares with polynomials supported on circuits, a genuine class of sparse polynomials. In particular, nonnegativity is characterized by an invariant, which can be immediately derived from the initial polynomial. Based on these results, we obtain a completely new class of nonnegativity certificates independent from SOS certificates. Furthermore, nonnegativity of such circuit polynomials f coincides with solidness of the amoeba of f , i.e., the Log-absolute-value image of the algebraic variety V(f) in C^n of f. These results establish a first direct connection between amoeba theory and nonnegativity of polynomials. These results generalize earlier works by Fidalgo, Ghasemi, Kovacec, Marshall and Reznick. The talk is based on joint work with Sadik Iliman.