Conference Program
PLENARY AND SEMIPLENARY TALKS
Tuesday, August 21, 17:00 – 17:50 h, H1058:
Rekha Thomas: Lifts and Factorizations of Convex Sets
Chair: Martin Skutella
Abstract:
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 liftandproject methods in the literature which attempt to find polyhedral or spectrahedral lifts of complicated sets. Given a closed convex cone K and a convex set C, there is an affine slice of K that projects to C if and only if a certain "slack operator" associated to C can be factored through K. 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 liftandproject 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.
Biographical sketch:
Rekha Thomas received a Ph.D. in Operations Research from Cornell University in 1994 under the supervision of Bernd Sturmfels. After holding postdoctoral positions at the Cowles Foundation for Economics at Yale University and ZIB, Berlin, she worked as an assistant professor of Mathematics at Texas A&M University from 1995  2000. Since 2000, she has been at the University of Washington in Seattle where she is now the Robert R. and Elaine F. Phelps Endowed Professor of Mathematics. Her research interests are in optimization and computational algebra.
