VA & Opt Webinar: James Saunderson (Monash)

Title: Lifting for simplicity: concise descriptions of convex sets

Speaker: James Saunderson (Monash University)

Date and Time: July 15th, 2020, 17:00 AEST (Register here for remote connection via Zoom)

Abstract: This talk will give a selective tour through the theory and applications of lifts of convex sets. A lift of a convex set is a higher-dimensional convex set that projects onto the original set. Many interesting convex sets have lifts that are dramatically simpler to describe than the original set. Finding such simple lifts has significant algorithmic implications, particularly for associated optimization problems. We will consider both the classical case of polyhedral lifts, which are described by linear inequalities, as well as spectrahedral lifts, which are defined by linear matrix inequalities. The tour will include discussion of ways to construct lifts, ways to find obstructions to the existence of lifts, and a number of interesting examples from a variety of mathematical contexts. (Based on joint work with H. Fawzi, J. Gouveia, P. Parrilo, and R. Thomas).