Relative Entropy Relaxations for Signomial Optimization

Applied and Computational Mathematics Seminar
Tuesday, October 27, 2015 - 12:30
1 hour (actually 50 minutes)
Skiles 005
Cal Tech
Due to its favorable analytical properties, the relative entropy function plays a prominent role in a variety of contexts in information theory and in statistics. In this talk, I'll discuss some of the beneficial computational properties of this function by describing a class of relative-entropy-based convex relaxations for obtaining bounds on signomials programs (SPs), which arise commonly in many problems domains.  SPs are non-convex in general, and families of NP-hard problems can be reduced to SPs.  By appealing to representation theorems from real algebraic geometry, we show that sequences of bounds obtained by solving increasingly larger relative entropy programs converge to the global optima for broad classes of SPs.  The central idea underlying our approach is a connection between the relative entropy function and efficient proofs of nonnegativity via the arithmetic-geometric-mean inequality. (Joint work with Parikshit Shah.)