Lifting for simplicity: concise descriptions of convex sets

DOI10.1137/20M1324417zbMATH Open1500.52002arXiv2002.09788OpenAlexW3008048690MaRDI QIDQ5044992FDOQ5044992

Hamza Fawzi, João Gouveia, James Saunderson, Rekha Thomas, Pablo A. Parrilo

Publication date: 3 November 2022

Published in: SIAM Review (Search for Journal in Brave)

Abstract: 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 optimization problems. We consider both the classical case of polyhedral lifts, described by linear inequalities, as well as spectrahedral lifts, defined by linear matrix inequalities, with a focus on recent developments related to spectrahedral lifts. Given a convex set, ideally we would either like to 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.

Full work available at URL: https://arxiv.org/abs/2002.09788

Recommendations

• Spectrahedral lifts of convex sets
• Lifts of Convex Sets and Cone Factorizations
• Lifts of non-compact convex sets and cone factorizations
• Lifts of convex sets in optimization
• Limitations on the Expressive Power of Convex Cones without Long Chains of Faces

zbMATH Keywords

convex setspositive semidefinite conecone factorizationpolyhedral liftsslack operatorspectrahedral lifts

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Cites Work

• Slice sampling. (With discussions and rejoinder)
• Title not available (Why is that?)
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• On the Complexity of Nonnegative Matrix Factorization
• Graph-Based Algorithms for Boolean Function Manipulation
• Semidefinite Programming
• Convex Analysis
• Title not available (Why is that?)
• Some NP-complete problems in quadratic and nonlinear programming
• Two poset polytopes
• Resolution of singularities of an algebraic variety over a field of characteristic zero. I
• Global optimization with polynomials and the problem of moments
• Title not available (Why is that?)
• Sparse nonnegative solution of underdetermined linear equations by linear programming
• Expressing combinatorial optimization problems by linear programs
• Geometric algorithms and combinatorial optimization.
• Semidefinite programming relaxations for semialgebraic problems
• On the geometric interpretation of the nonnegative rank
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Algorithmic graph theory and perfect graphs
• On the copositive representation of binary and continuous nonconvex quadratic programs
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Title not available (Why is that?)
• Polytopes of minimum positive semidefinite rank
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Hyperbolic Polynomials and Interior Point Methods for Convex Programming
• Branching Programs and Binary Decision Diagrams
• Semidefinite Optimization and Convex Algebraic Geometry
• On Polyhedral Approximations of the Second-Order Cone
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Lifts of Convex Sets and Cone Factorizations
• A tutorial on geometric programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the computational complexity of membership problems for the completely positive cone and its dual
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial bounds on nonnegative rank and extended formulations
• The Matching Polytope has Exponential Extension Complexity
• On the linear extension complexity of regular \(n\)-gons
• Smallest compact formulation for the permutahedron
• Algebraic boundaries of convex semi-algebraic sets
• Positive Polynomials and Projections of Spectrahedra
• Eigenvalues of sums of Hermitian matrices
• Title not available (Why is that?)
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Extended formulations in combinatorial optimization
• Positive semidefinite rank
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• Theta Bodies for Polynomial Ideals
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• Stable bundles, representation theory and Hermitian operators
• Exponential lower bounds for polytopes in combinatorial optimization
• Relative entropy relaxations for signomial optimization
• Lifting Markov chains to speed up mixing
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Matrices with high completely positive semidefinite rank
• The honeycomb model of $GL_n(\mathbb C)$ tensor products I: Proof of the saturation conjecture
• Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets
• Semidefinite representation of convex sets
• The Hironaka theorem on resolution of singularities (Or: A proof we always wanted to understand)
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Relaxations of vertex packing
• Honeycombs and sums of Hermitian matrices.
• A complete characterization of the gap between convexity and sos-convexity
• Convex sets with semidefinite representation
• SPECTRAHEDRAL LIFTS OF CONVEX SETS
• Which nonnegative matrices are slack matrices?
• Convex Hulls of Algebraic Sets
• Relative entropy optimization and its applications
• Four-dimensional polytopes of minimum positive semidefinite rank
• Mixed integer linear programming formulation techniques
• Semidefinite representation of convex hulls of rational varieties
• The Complexity of Positive Semidefinite Matrix Factorization
• On the OBDD-representation of general Boolean functions
• Symmetry Matters for Sizes of Extended Formulations
• Resolution of singularities of an algebraic variety over a field of characteristic zero. II
• The set of separable states has no finite semidefinite representation except in dimension \(3\times 2\)
• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
• A Lower Bound on the Positive Semidefinite Rank of Convex Bodies
• Spectrahedral Shadows
• A Positivstellensatz for Sums of Nonnegative Circuit Polynomials
• On representing the positive semidefinite cone using the second-order cone
• Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Limitations on the Expressive Power of Convex Cones without Long Chains of Faces

Cited In (5)

• Lifts of Convex Sets and Cone Factorizations
• On cone-based decompositions of proper Pareto-optimality in multi-objective optimization
• Spectrahedral Regression
• Optimal Self-Concordant Barriers for Quantum Relative Entropies
• Weighted geometric mean, minimum mediated set, and optimal simple second-order cone representation

This page was built for publication: Lifting for simplicity: concise descriptions of convex sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5044992)