Conference Program


 (Add to Calendar)  Tuesday, August 21, 17:00 – 17:50 h, H1058:

Rekha Thomas: Lifts and Factorizations of Convex Sets

Chair: Martin Skutella



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 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 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.


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.

  USA Payday Loans Online. In rare cases, the smarting in eyes, the tumefaction of eyelids, nausea and headaches can happen. In case of long term Levitra Soft online administration the side effects become less perceptible or disappear at all.