Lifts of Convex Sets and Cone Factorizations
From MaRDI portal
Publication:5169664
Abstract: In this paper we address the basic geometric question of when a given convex set is the image under a linear map of an affine slice of a given closed convex cone. Such a representation or 'lift' of the convex set is especially useful if the cone admits an efficient algorithm for linear optimization over its affine slices. We show that the existence of a lift of a convex set to a cone is equivalent to the existence of a factorization of an operator associated to the set and its polar via elements in the cone and its dual. This generalizes a theorem of Yannakakis that established a connection between polyhedral lifts of a polytope and nonnegative factorizations of its slack matrix. Symmetric lifts of convex sets can also be characterized similarly. When the cones live in a family, our results lead to the definition of the rank of a convex set with respect to this family. We present results about this rank in the context of cones of positive semidefinite matrices. Our methods provide new tools for understanding cone lifts of convex sets.
Recommendations
- Lifts of non-compact convex sets and cone factorizations
- Approximate cone factorizations and lifts of polytopes
- Spectrahedral lifts of convex sets
- Lifts of convex sets in optimization
- scientific article; zbMATH DE number 5720480
- scientific article; zbMATH DE number 624756
- Lifting for simplicity: concise descriptions of convex sets
- Lifting inequalities for polytopes
- On convolutions of convex sets and related problems
- Convex decompositions
Cited in
(89)- The matching problem has no small symmetric SDP
- Maximum semidefinite and linear extension complexity of families of polytopes
- Affine reductions for LPs and SDPs
- Learning semidefinite regularizers
- Completely positive semidefinite rank
- Rational and real positive semidefinite rank can be different
- Algorithms for positive semidefinite factorization
- Orbital geometry and group majorisation in optimisation
- Fitting tractable convex sets to support function evaluations
- The set of separable states has no finite semidefinite representation except in dimension \(3\times 2\)
- New limits of treewidth-based tractability in optimization
- Lifts of non-compact convex sets and cone factorizations
- Polygons as sections of higher-dimensional polytopes
- On the linear extension complexity of stable set polytopes for perfect graphs
- The slack realization space of a matroid
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- An upper bound for nonnegative rank
- Approximate cone factorizations and lifts of polytopes
- On representing the positive semidefinite cone using the second-order cone
- Which nonnegative matrices are slack matrices?
- Invariance and efficiency of convex representations
- On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
- Rank functions of tropical matrices
- Quantum learning of classical stochastic processes: the completely positive realization problem
- Matrix convex hulls of free semialgebraic sets
- Two results on the size of spectrahedral descriptions
- Exponential lower bounds for polytopes in combinatorial optimization
- Extension complexity of polytopes with few vertices or facets
- Heuristics for exact nonnegative matrix factorization
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
- Global completability with applications to self-consistent quantum tomography
- Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
- Studying non-negative factorizations with tools from linear algebra over a semiring
- Query complexity in expectation
- Matrices with high completely positive semidefinite rank
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Polytopes of minimum positive semidefinite rank
- A lower bound on the positive semidefinite rank of convex bodies
- Matrices of bounded psd rank are easy to detect
- On ranks of regular polygons
- On polyhedral approximations of the positive semidefinite cone
- Lifting for simplicity: concise descriptions of convex sets
- Theta rank, levelness, and matroid minors
- Relative entropy optimization and its applications
- Four-dimensional polytopes of minimum positive semidefinite rank
- Spectrahedral lifts of convex sets
- On the linear extension complexity of regular n-gons
- Approximate tensor decompositions: disappearance of many separations
- The phaseless rank of a matrix
- Some upper and lower bounds on PSD-rank
- The slack realization space of a polytope
- A matrix Positivstellensatz with lifting polynomials
- Limitations on the Expressive Power of Convex Cones without Long Chains of Faces
- Facially dual complete (nice) cones and lexicographic tangents
- Coordinate shadows of semidefinite and Euclidean distance matrices
- The complexity of positive semidefinite matrix factorization
- Positive semidefinite rank and nested spectrahedra
- Semidefinite Descriptions of the Convex Hull of Rotation Matrices
- Equivariant semidefinite lifts of regular polygons
- Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
- An almost optimal algorithm for computing nonnegative rank
- Second-Order Cone Representation for Convex Sets in the Plane
- Amenable cones are particularly nice
- Communication tasks in operational theories
- Error bounds, facial residual functions and applications to the exponential cone
- Linear optimization over homogeneous matrix cones
- Lifts for Voronoi cells of lattices
- Complex psd-minimal polytopes in dimensions two and three
- On eigenvalues of symmetric matrices with PSD principal submatrices
- Self-Dual Polyhedral Cones and Their Slack Matrices
- Tensor decompositions on simplicial complexes with invariance
- Weighted geometric mean, minimum mediated set, and optimal simple second-order cone representation
- Lifts of convex sets
- Polynomial decompositions with invariance and positivity inspired by tensors
- Multiplicative updates for symmetric-cone factorizations
- Spectral polyhedra
- Sublinear extensions of polygons
- Geometry of low nonnegative rank matrix completion
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Tropical lower bounds for extended formulations
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Lifts of convex sets in optimization
- Positive semidefinite rank
- Worst-case results for positive semidefinite rank
- Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones
This page was built for publication: Lifts of Convex Sets and Cone Factorizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5169664)
