Optimization over the Hypercube via Sums of Nonnegative Circuit Polynomials
summary
Claims that nonnegativity can be certified by sums of nonnegative circuit polynomials (SONC), gives a converging Positivstellensatz-style hierarchy, and reduces finding a degree-D SONC certificate to a convex relative entropy program of size n^{O(D)}. Over a general constrained hypercube any degree-≤D polynomial nonnegative on the set admits a degree n+T certificate, and there is always a short certificate using at most n^{O(D)} terms. Also proves no general Putinar-style linear-in-constraints representation exists and flags finding short certificates efficiently as open.
AI-written summary · about
chapters (9)
- 0:00Introduction and background
- 3:55Limitations of SOS
- 6:46Circuit polynomials
- 10:18SONC cones and properties
- 14:03Optimization with SONC
- 18:40Hypercube optimization
- 23:22Complexity and proofs
- 31:07Positive standards results
- 34:15Conclusion and open problems
related talks
27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning
01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1
31mA Positivity-First Approach to Sum-of-Squares Over the Hypercube
01h 04mLP/SDP Hierarchies and Sum of Squares Proofs 2
01h 00mAverage-case Complexity for Polynomials, and All That
57mStructure Of Boolean Almost Low Degree Functions On The Biased Cube
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
56mEntropy, Capacity, and Counting