Lifting for Simplicity: Concise Descriptions of Convex Sets

This paper presents a selected 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 convex sets have lifts that are dramatically simpler to describe than the original set. Finding such simple lifts has significant algorithmic implications, particularly for op-timization problems. We consider both the classical case of polyhedral lifts, described by linear inequalities, as well as that of spectrahedral lifts, defined by linear matrix inequali-ties, with a focus on recent developments related to spectrahedral lifts.Given a convex set, ideally we would like to either find a (low-complexity) polyhedral or spectrahedral lift or find an obstruction proving that no such lift is possible. To this end, we explain the connection between the existence of lifts of a convex set and certain structured factorizations of its associated slack operator. Based on this characterization, we describe a uniform approach, via sums of squares, to the construction of spectrahedral lifts of convex sets and illustrate the method on several families of examples. Finally, we discuss two flavors of obstruction to the existence of lifts: one related to facial structure, and the other related to algebraic properties of the set in question.Rather than being exhaustive, our aim is to illustrate the richness of the area. We touch on a range of different topics related to the existence of lifts and present many examples of lifts from different areas of mathematics and its applications.

Automated summary

This paper presents a survey of the theory and applications of lifts of convex sets, focusing on polyhedral lifts and spectrahedral lifts. It explains the connection between the existence of lifts and structured factorizations of the associated slack operator, and provides a unified approach for constructing spectrahedral lifts using sums of squares. The paper also discusses two types of obstructions to the existence of lifts: facial structure obstruction and algebraic properties obstruction. It aims to illustrate the richness of the area by providing various examples of lifts from different areas of mathematics and its applications.