Lifting for simplicity: concise descriptions of convex sets
From MaRDI portal
Publication:5044992
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1046019 (Why is no real title available?)
- scientific article; zbMATH DE number 3223483 (Why is no real title available?)
- scientific article; zbMATH DE number 3078983 (Why is no real title available?)
- scientific article; zbMATH DE number 3095897 (Why is no real title available?)
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A Positivstellensatz for sums of nonnegative circuit polynomials
- A complete characterization of the gap between convexity and sos-convexity
- A lower bound on the positive semidefinite rank of convex bodies
- A tutorial on geometric programming
- Advances in convex optimization: conic programming
- Algebraic boundaries of convex semi-algebraic sets
- Algorithmic graph theory and perfect graphs
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
- Branching Programs and Binary Decision Diagrams
- Combinatorial bounds on nonnegative rank and extended formulations
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Convex Analysis
- Convex hulls of algebraic sets
- Convex sets with semidefinite representation
- Eigenvalues of sums of Hermitian matrices
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Exponential lower bounds for polytopes in combinatorial optimization
- Expressing combinatorial optimization problems by linear programs
- Extended formulations in combinatorial optimization
- Four-dimensional polytopes of minimum positive semidefinite rank
- Geometric algorithms and combinatorial optimization.
- Global optimization with polynomials and the problem of moments
- Graph-Based Algorithms for Boolean Function Manipulation
- Honeycombs and sums of Hermitian matrices.
- Hyperbolic Polynomials and Interior Point Methods for Convex Programming
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Lifting Markov chains to speed up mixing
- Lifts of Convex Sets and Cone Factorizations
- Limitations on the Expressive Power of Convex Cones without Long Chains of Faces
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- Lower bounds on the size of semidefinite programming relaxations
- Matrices with high completely positive semidefinite rank
- Mixed integer linear programming formulation techniques
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- On Polyhedral Approximations of the Second-Order Cone
- On representing the positive semidefinite cone using the second-order cone
- On the OBDD-representation of general Boolean functions
- On the complexity of nonnegative matrix factorization
- 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
- On the computational complexity of membership problems for the completely positive cone and its dual
- On the copositive representation of binary and continuous nonconvex quadratic programs
- On the geometric interpretation of the nonnegative rank
- On the linear extension complexity of regular \(n\)-gons
- Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
- Polytopes of minimum positive semidefinite rank
- Positive polynomials and projections of spectrahedra
- Positive semidefinite rank
- Relative entropy optimization and its applications
- Relative entropy relaxations for signomial optimization
- Relaxations of vertex packing
- Resolution of singularities of an algebraic variety over a field of characteristic zero. I
- Resolution of singularities of an algebraic variety over a field of characteristic zero. II
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite Programming
- Semidefinite programming relaxations for semialgebraic problems
- Semidefinite representation of convex hulls of rational varieties
- Semidefinite representation of convex sets
- Slice sampling. (With discussions and rejoinder)
- Smallest compact formulation for the permutahedron
- Some NP-complete problems in quadratic and nonlinear programming
- Sparse nonnegative solution of underdetermined linear equations by linear programming
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Spectrahedral lifts of convex sets
- Spectrahedral shadows
- Stable bundles, representation theory and Hermitian operators
- Sufficient and necessary conditions for semidefinite representability of convex hulls and sets
- Symmetry Matters for Sizes of Extended Formulations
- The Hironaka theorem on resolution of singularities (Or: A proof we always wanted to understand)
- The complexity of positive semidefinite matrix factorization
- The honeycomb model of $GL_n(\mathbb C)$ tensor products I: Proof of the saturation conjecture
- The set of separable states has no finite semidefinite representation except in dimension \(3\times 2\)
- Theta bodies for polynomial ideals
- Two poset polytopes
- Which nonnegative matrices are slack matrices?
Cited in
(8)- Lifts of Convex Sets and Cone Factorizations
- On cone-based decompositions of proper Pareto-optimality in multi-objective optimization
- Lifts of convex sets
- Spectrahedral Regression
- Optimal Self-Concordant Barriers for Quantum Relative Entropies
- Weighted geometric mean, minimum mediated set, and optimal simple second-order cone representation
- Lifts of non-compact convex sets and cone factorizations
- Spectrahedral lifts of convex sets
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)
