University of Cambridge > > Microsoft Research Machine Learning and Perception Seminars > Lifts of Convex Sets and Cone Factorizations

Lifts of Convex Sets and Cone Factorizations

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

This event may be recorded and made available internally or externally via Microsoft will own the copyright of any recordings made. If you do not wish to have your image/voice recorded please consider this before attending

The representation of a convex set is crucial for the efficiency of linear optimization algorithms. A common idea to optimize a linear function over a complicated convex set is to express the set as the projection of a much simpler convex set in a higher dimension, called a ``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 matrix of the polytope. I will show how this theorem can be generalized to convex sets via cone factorizations of nonnegative operators. In practice, one usually only has a numerical approximation to a cone factorization. I will also show how such approximate factorizations can be used to construct efficient approximations of polytopes, and mention some of the many open questions in this area.

Joint work with Joao Gouveia (University of Coimbra) and Pablo Parrilo (MIT)

This talk is part of the Microsoft Research Machine Learning and Perception Seminars series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2020, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity