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

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Lifts of Convex Sets and Cone Factorizations

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 http://research.microsoft.com. 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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Meade Room, Faculty of Economics, Cambridge Bateman Auditorium, Gonville & Caius College, Cambridge, CB2 1TA Machine learning theory

Other talks

Title TBC CSAR lecture: In a post-Ozempic world, have we cured obesity? Title to be confirmed Title to be confirmed Tea and Coffee Break The United States of America at 250: Reflections on the Past, Present and Future of Independence
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity