Conference Program

PLENARY AND SEMI-PLENARY TALKS

 (Add to Calendar)  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 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.

  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Cheap Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.