### Lifts of Convex Sets and Cone Factorizations

- Series
- School of Mathematics Colloquium
- Time
- Thursday, October 4, 2012 - 11:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Rekha Thomas – University of Washington

A basic strategy for linear optimization over a complicated convex set is
to try to express the set as the projection of a simpler convex set that
admits efficient algorithms. This philosophy underlies all
"lift-and-project" methods in
optimization which attempt to find polyhedral or spectrahedral lifts of
complicated sets. In this talk I will explain how the existence of a lift
is equivalent to the ability to factorize a certain operator associated to
the convex set through a cone.
This theorem extends a result of Yannakakis who showed that polyhedral
lifts of polytopes are controlled by the nonnegative factorizations of the
slack matrix of the polytope. The connection between cone lifts and cone
factorizations of convex sets yields a uniform framework within which to
view all lift-and-project methods, as well as offers new tools for
understanding convex sets. I will survey this evolving area and the main
results that have emerged thus far.