Source-linked AI summary
Lifts of convex sets and cone factorizations
João Gouveia, Pablo A. Parrilo, Rekha Thomas
TL;DR
The paper asks when a convex set can be represented as a linear image of an affine slice of a closed convex cone. It characterizes such lifts through cone factorizations of slack operators, including symmetric lifts, and develops cone-rank results for positive semidefinite cones.
Problem
The paper addresses when a convex set admits a lift as the linear image of an affine slice of a specified closed convex cone.
Method
The authors generalize nonnegative matrix factorizations to cone factorizations of convex-set slack operators and characterize ordinary and symmetric cone lifts.
Results
The paper proves lift–factorization equivalences, defines cone ranks, and derives rank gaps and bounds for nonnegative and positive semidefinite ranks.
Takeaways & Limitations
These results provide tools for analyzing cone lifts, including limits on semidefinite lifts and applications to convex approximations such as theta bodies.
Takeaways & Limitations
The main lift characterization assumes a proper lift, and removing this assumption is not straightforward for a general closed convex cone.
Abstract
from arXiv · showhide
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.
1. Introduction
The introduction motivates cone lifts as efficient representations for optimizing over complicated convex sets and formulates questions about their existence and minimum size. It presents the paper’s main characterization via cone factorizations and previews results on symmetry, cone ranks, polytopes, stable-set polytopes, and algebraic lifts.
- Motivation: Cone lifts can make optimization tractable by representing a complicated convex set as the projection of an affine slice of a cone supporting efficient optimization algorithms.The cross-polytope illustrates this idea: its lifted representation enables optimization over a simpler feasible region.
- Questions: The paper asks when a convex set C equals π(K ∩ L) for a closed convex cone K, and what smallest member of a cone family can provide such a lift.A representation C = π(K ∩ L) is called a K-lift of C.
- Main contribution: The main theorem extends Yannakakis’ result by characterizing cone lifts for arbitrary closed convex cones and convex sets through cone factorizations of slack operators.This generalizes nonnegative matrix factorizations to the cone setting.
- Symmetric lifts and polytopes: The paper also characterizes symmetric cone lifts, generalizes Yannakakis’ polytope theorem [30] to arbitrary closed convex cones, and identifies geometric operations preserving cone lifts.Symmetry is shown to impose strong restrictions on lift size in related results [24].
- Cone ranks: For ordered cone families, the paper defines cone rank as the least family index admitting a lift or factorization, and studies gaps and bounds involving rank, psd rank, and nonnegative rank.The analysis includes lower bounds from face-lattice antichains, upper bounds on facets for fixed psd rank, and arbitrarily large rank gaps.
- Applications: Applications show that stable-set polytopes require no S_k^+ lift for k ≤ n, while rational algebraic lifts translate positive semidefinite factorizations into sums-of-squares polynomials and rational maps.The stable-set result concerns the theta-body construction, which is exact for perfect graphs.
2. Cone lifts of convex bodies
This section defines cone lifts and the slack operator of a convex body, then characterizes lifts through factorizations of that operator over a cone and its dual. It extends the characterization to nonproper lifts for nice cones, establishes closure properties of lifts, and gives an analogous result for symmetric lifts.
- Cone lifts and factorizations: A proper K-lift of C exists exactly when the slack operator S_C(x,y)=1−⟨x,y⟩ admits a K-factorization, with the converse yielding a possibly nonproper K-lift.The factorization uses maps from ext(C) to K and from ext(C◦) to K∗ whose inner product equals S_C.
- Cone lifts and factorizations: For nice cones, every K-lift, including a nonproper one, implies that S_C has a K-factorization; polyhedral, second-order, and real symmetric positive semidefinite cones are nice.Niceness means K∗+F⊥ is closed for every face F of K, allowing a factorization through a face to be transferred to K.
- Closure properties: K-lifts are preserved under linear images, polarity, exposed faces, Cartesian products, Minkowski sums, convex hulls of two lifted bodies, and compact projective transformations.The first six operations use K1, K1∗, or K1×K2 as specified, while a compact projective image retains the original cone K.
- Symmetric lifts: If C has a proper (G,H)-symmetric K-lift, then S_C has a (G,H)-symmetric K-factorization, and conversely.The symmetric characterization parallels the nonsymmetric lift–factorization equivalence.
3. Cone lifts of polytopes
For polytopes, cone lifts are characterized exactly by factorizations of slack matrices through the cone and its dual. Examples show that lift size can depend on geometry beyond facial combinatorics, while symmetry can impose substantially stronger size requirements.
- A full-dimensional polytope has a proper K-lift if and only if one of its slack matrices admits a K-factorization.The slack matrix records facet-inequality values at vertices, and K-factorization generalizes nonnegative matrix factorization from nonnegative orthants to arbitrary closed convex cones.
- A regular hexagon admits an R^5-lift, improving on the trivial polyhedral lift into R^6.The lift follows from an R^5-factorization of its canonical slack matrix and can be realized as a three-dimensional slice of R^5 projected onto the hexagon.
- An irregular hexagon with the same facial combinatorics has no R^5-lift, demonstrating that lift existence depends on more than facial structure.The obstruction is that its slack matrix admits no R^5-factorization with any of the possible zero-pattern decompositions.
- Symmetric lifts: For regular polygons with n sides, a symmetric R^k-lift requires k ≥ n when n is prime or a prime power.A symmetric lift induces an injective homomorphism from the polytope’s automorphism group into the coordinate-permutation group, so |Aut(P)| must divide k!.
- Symmetric lifts: Regular n-gons admit non-symmetric R^k-lifts with k = O(log n), creating an exponential gap from the symmetric requirement.This combines the result of Ben-Tal and Nemirovski [6] with Proposition 3.5; the regular hexagon’s R^5-lift is itself non-symmetric.
4. Cone ranks of convex bodies
This section defines cone ranks for convex bodies relative to closed cone families and proves that cone rank exactly equals the smallest cone dimension admitting a lift. It then develops separations among ordinary, nonnegative, and psd ranks and derives structural lower bounds for polytopes.
- Cone families: A closed cone family requires every face of Ki to be isomorphic to some Kj with j ≤ i, whereas the copositive-matrix family is not closed.Closedness is what rules out nonproper lifts to lower-dimensional faces when proving the rank–lift equivalence.
- Cone ranks: For a closed cone family K, rankK(C) is the smallest index i for which the convex body C has a Ki-lift.Equivalently, rankK(C) is the smallest i such that the slack operator of C has a Ki-factorization.
- Rank comparisons: 3 = rank(Mn) while rank+(Mn) ≥ log2 n for Mn with entries (i−j)^2, showing ordinary rank does not bound nonnegative rank.Thus nonnegative rank can grow with matrix size even when ordinary rank remains constant.
- Rank comparisons: For a nonnegative matrix M, squaring entries preserves the ordinary-rank upper bound for psd rank: rankpsd(M′) ≤ rank(M), including 0/1 matrices.The section also establishes that gaps between ordinary, nonnegative, and psd ranks can each be arbitrarily large in suitable families.
- Polytope bounds: If a full-dimensional polytope has slack-matrix psd rank k, it has at most k^O(k^2n) facets, while regular n-gons have psd rank tending to infinity despite ordinary rank 3.These results show that ordinary rank cannot bound psd rank even for polytope slack matrices.
5. Applications
The applications show how cone-factorization methods characterize optimal semidefinite lifts of stable set polytopes and connect polynomial lifts with sum-of-squares certificates and theta bodies. Stable set polytopes also admit uniformly small completely positive lifts, although these are not currently computationally practical.
- Stable set polytopes: For every graph G with n vertices, STAB(G) does not admit an S_n^+-lift, while perfect graphs have an S_{n+1}^+-lift; thus Lovász’s lift is optimal in size.The lower bound follows by analyzing a slack-matrix substructure through the factorization theorem; the perfect-graph lift is obtained by slicing and projecting S_{n+1}^+.
- Stable set polytopes: The lower-bound argument extends to any n-dimensional polytope with a vertex locally resembling a nonnegative orthant, which has no S_n^+-lift.The paper also notes that n-dimensional polytopes with 0/1 slack matrices have small semidefinite lifts, using the slack-matrix rank bound.
- Completely positive lifts: Every stable set polytope STAB(G) has a C_{n+1}^*-lift using the same linear constraints as the semidefinite construction, but completely positive programming lacks known efficient algorithms.These lifts work for all graphs and are of very small size, but their practical computational interest is limited.
- Polynomial lifts: For a convex radical ideal I with compact conv(VR(I)) containing the origin, rational slack factorizations are equivalent to sum-of-squares certificates modulo I for linear polynomials nonnegative on the variety.The factorization uses A(x) = 1/p(x)^2 w(x)w(x)^T, with the sum-of-squares terms formed from linear combinations of entries of w(x).
- Polynomial lifts: Polynomial slack factorizations with degree-bounded w characterize exact theta-body representations: degree at most k is equivalent to TH_k(I) = conv(Z).A similar approach applies to polynomial inequalities, although the resulting lift uses a product of positive semidefinite cones.