BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Lifts of Convex Sets and Cone Factorizations - Rekha R. Thomas\, U
 niversity of Washington\, Seattle
DTSTART:20130802T140000Z
DTEND:20130802T150000Z
UID:TALK46513@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:The representation of a convex set is crucial for the efficien
 cy of linear optimization algorithms.  A common idea to optimize a linear 
 function over a complicated convex set is to express the set as the projec
 tion of a much simpler convex set in a higher dimension\, called\na ``lift
 '' of the original set. In the early 1990s Yannakakis showed that there is
  a remarkable connection between the size of the smallest polyhedral lift 
 of a polytope and the nonnegative rank of the slack\nmatrix of the polytop
 e. I will show how this theorem can be generalized to convex sets via cone
  factorizations of nonnegative operators. In practice\, one usually only h
 as a numerical approximation to a cone factorization. I will also show how
  such\napproximate factorizations can be used to construct efficient appro
 ximations of polytopes\, and mention some of the many open questions in th
 is area.\n\nJoint work with Joao Gouveia (University of Coimbra) and Pablo
  Parrilo\n(MIT)\n
LOCATION:Microsoft Research Ltd\, 21 Station Road\, Cambridge\, CB1 2FB
END:VEVENT
END:VCALENDAR