Lifts of Convex Sets and Cone Factorizations
From MaRDI portal
Publication:5169664
DOI10.1287/MOOR.1120.0575zbMath1291.90172DBLPjournals/mor/GouveiaPT13arXiv1111.3164OpenAlexW3123950972WikidataQ95138335 ScholiaQ95138335MaRDI QIDQ5169664
Rekha R. Thomas, Pablo A. Parrilo, João Gouveia
Publication date: 11 July 2014
Published in: Mathematics of Operations Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1111.3164
Related Items (81)
Rank functions of tropical matrices ⋮ Heuristics for exact nonnegative matrix factorization ⋮ Lifting for Simplicity: Concise Descriptions of Convex Sets ⋮ Studying Non-negative Factorizations with Tools from Linear Algebra over a Semiring ⋮ Query Complexity in Expectation ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies ⋮ Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone ⋮ Global completability with applications to self-consistent quantum tomography ⋮ Matrices with high completely positive semidefinite rank ⋮ Sparse sums of squares on finite abelian groups and improved semidefinite lifts ⋮ A Lower Bound on the Positive Semidefinite Rank of Convex Bodies ⋮ Polytopes of minimum positive semidefinite rank ⋮ Matrices of Bounded Psd Rank are Easy to Detect ⋮ The matching problem has no small symmetric SDP ⋮ On representing the positive semidefinite cone using the second-order cone ⋮ 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 Ranks of Regular Polygons ⋮ On eigenvalues of symmetric matrices with PSD principal submatrices ⋮ The Complexity of Positive Semidefinite Matrix Factorization ⋮ Self-Dual Polyhedral Cones and Their Slack Matrices ⋮ On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones ⋮ Tensor decompositions on simplicial complexes with invariance ⋮ Maximum semidefinite and linear extension complexity of families of polytopes ⋮ Which nonnegative matrices are slack matrices? ⋮ Positive semidefinite rank and nested spectrahedra ⋮ Affine reductions for LPs and SDPs ⋮ Lifts of non-compact convex sets and cone factorizations ⋮ Mixed states in one spatial dimension: Decompositions and correspondence with nonnegative matrices ⋮ Polynomial decompositions with invariance and positivity inspired by tensors ⋮ Multiplicative updates for symmetric-cone factorizations ⋮ Learning semidefinite regularizers ⋮ Approximate tensor decompositions: Disappearance of many separations ⋮ Theta rank, levelness, and matroid minors ⋮ Relative entropy optimization and its applications ⋮ Four-dimensional polytopes of minimum positive semidefinite rank ⋮ The Phaseless Rank of a Matrix ⋮ On the linear extension complexity of regular \(n\)-gons ⋮ Some upper and lower bounds on PSD-rank ⋮ Polygons as sections of higher-dimensional polytopes ⋮ Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization ⋮ An Almost Optimal Algorithm for Computing Nonnegative Rank ⋮ Orbital geometry and group majorisation in optimisation ⋮ Quantum learning of classical stochastic processes: The completely positive realization problem ⋮ Weighted geometric mean, minimum mediated set, and optimal simple second-order cone representation ⋮ The Slack Realization Space of a Polytope ⋮ Matrix convex hulls of free semialgebraic sets ⋮ Completely positive semidefinite rank ⋮ Rational and real positive semidefinite rank can be different ⋮ Two Results on the Size of Spectrahedral Descriptions ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Algorithms for positive semidefinite factorization ⋮ A Matrix Positivstellensatz with Lifting Polynomials ⋮ Fitting tractable convex sets to support function evaluations ⋮ 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 ⋮ Positive semidefinite rank ⋮ Worst-case results for positive semidefinite rank ⋮ The set of separable states has no finite semidefinite representation except in dimension \(3\times 2\) ⋮ Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones ⋮ Limitations on the Expressive Power of Convex Cones without Long Chains of Faces ⋮ On the linear extension complexity of stable set polytopes for perfect graphs ⋮ The slack realization space of a matroid ⋮ Facially Dual Complete (Nice) Cones and Lexicographic Tangents ⋮ Extension Complexity of Polytopes with Few Vertices or Facets ⋮ Lower bounds on matrix factorization ranks via noncommutative polynomial optimization ⋮ Semidefinite Descriptions of the Convex Hull of Rotation Matrices ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices ⋮ Second-Order Cone Representation for Convex Sets in the Plane ⋮ An upper bound for nonnegative rank ⋮ Coordinate Shadows of Semidefinite and Euclidean Distance Matrices ⋮ Approximate cone factorizations and lifts of polytopes ⋮ Amenable Cones Are Particularly Nice ⋮ Communication tasks in operational theories ⋮ On Polyhedral Approximations of the Positive Semidefinite Cone ⋮ New limits of treewidth-based tractability in optimization
This page was built for publication: Lifts of Convex Sets and Cone Factorizations
