Source-linked AI summary
Lifts of convex sets and cone factorizations
João Gouveia, Pablo A. Parrilo, Rekha Thomas
TL;DR
이 논문은 convex set을 closed convex cone의 affine slice의 선형상으로 표현할 수 있는 조건을 묻는다. 이러한 lift를 slack operator의 cone factorization으로 특성화하고, symmetric lift를 포함해 positive semidefinite cone에 대한 cone-rank 결과를 전개한다.
문제
이 논문은 convex set이 주어진 closed convex cone의 affine slice의 선형상으로 lift될 수 있는 조건을 다룬다.
방법
저자들은 nonnegative matrix factorization을 convex set의 slack operator에 대한 cone factorization으로 일반화하고, ordinary 및 symmetric cone lift를 특성화한다.
결과
논문은 lift–factorization equivalence를 증명하고, cone rank를 정의하며, nonnegative rank와 positive semidefinite rank에 대한 rank gap과 bound를 도출한다.
핵심 시사점 및 한계
이 결과는 cone lift를 분석하기 위한 도구를 제공하며, semidefinite lift의 한계와 theta body 같은 convex approximation에 대한 응용을 포함한다.
핵심 시사점 및 한계
주요 lift 특성화는 proper lift를 가정하며, 일반적인 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. 서론
서론에서는 복잡한 convex set에 대한 최적화를 효율적으로 수행하기 위한 표현으로서 cone lift를 동기화하고, 그 존재 여부와 최소 크기에 관한 질문을 정식화한다. 또한 cone factorization을 통한 논문의 핵심 특성화를 제시하고, symmetry, cone rank, polytope, stable-set polytope, algebraic lift에 관한 결과를 미리 소개한다.
- 동기: Cone lift는 복잡한 convex set을 효율적인 최적화 알고리즘을 지원하는 cone의 affine slice의 projection으로 표현함으로써 최적화를 tractable하게 만들 수 있다.cross-polytope는 이 아이디어를 보여주는 예로, lift된 표현을 통해 더 단순한 feasible region에서 최적화를 수행할 수 있다.
- 질문: 이 논문은 closed convex cone K에 대해 convex set C가 π(K ∩ L)과 같아지는 조건과, 이러한 lift를 제공할 수 있는 cone family의 smallest member가 무엇인지 묻는다.C = π(K ∩ L)이라는 표현을 C의 K-lift라고 한다.
- 주요 기여: 핵심 정리는 Yannakakis의 결과 를 확장하여, slack operator의 cone factorization을 통해 임의의 closed convex cone과 convex set에 대한 cone lift를 특성화한다.이는 nonnegative matrix factorization을 cone setting으로 일반화한다.
- Symmetric lift와 polytope: 또한 symmetric cone lift를 특성화하고, Yannakakis의 polytope 정리 를 임의의 closed convex cone으로 일반화하며, cone lift를 보존하는 geometric operation을 식별한다.관련 결과 [24]에서는 symmetry가 lift size에 강한 제약을 가함을 보인다.
- Cone rank: ordered cone family에 대해 이 논문은 lift 또는 factorization을 허용하는 최소 family index를 cone rank로 정의하고, rank, psd rank, nonnegative rank 사이의 gap과 bound를 연구한다.분석에는 face-lattice antichain에서 얻는 lower bound, 고정된 psd rank에 대한 facet의 upper bound, 그리고 arbitrarily large rank gap이 포함된다.
- 응용: 응용 결과는 stable-set polytope가 k ≤ n에 대해 no S_k^+ lift를 필요로 하며, rational algebraic lift가 positive semidefinite factorization을 sums-of-squares polynomial과 rational map으로 변환함을 보인다.stable-set 결과는 perfect graph에서 exact한 theta-body construction과 관련된다.
2. 볼록체의 Cone lift
이 절에서는 볼록체의 cone lift와 slack operator를 정의한 뒤, 해당 operator의 cone 및 dual cone에 대한 factorization을 통해 lift를 특성화한다. 또한 nice cone에 대한 nonproper lift로 특성화를 확장하고, lift의 closure property를 정립하며, symmetric lift에 대한 유사한 결과를 제시한다.
- Cone lift와 factorization: C의 proper K-lift가 존재하는 것은 slack operator S_C(x,y)=1−⟨x,y⟩가 K-factorization을 갖는 것과 정확히 동치이며, 역은 possibly nonproper K-lift를 준다.이 factorization은 ext(C)에서 K로 가는 map과 ext(C◦)에서 K∗로 가는 map을 사용하며, 두 map의 inner product가 S_C와 같다.
- Cone lift와 factorization: nice cone에서는 nonproper lift를 포함한 모든 K-lift가 S_C의 K-factorization을 함의한다. polyhedral cone, second-order cone, real symmetric positive semidefinite cone은 nice하다.Niceness란 K의 모든 face F에 대해 K∗+F⊥가 closed라는 뜻이며, face를 통한 factorization을 K로 옮길 수 있게 한다.
- Closure property: K-lift는 linear image, polarity, exposed face, Cartesian product, Minkowski sum, 두 lifted body의 convex hull, compact projective transformation 아래에서 보존된다.앞의 여섯 연산에서는 명시된 대로 K1, K1∗ 또는 K1×K2를 사용하며, compact projective image는 원래 cone K를 유지한다.
- Symmetric lift: C가 proper (G,H)-symmetric K-lift를 가지면 S_C는 (G,H)-symmetric K-factorization을 가지며, 그 역도 성립한다.이 symmetric characterization은 nonsymmetric lift–factorization equivalence와 평행을 이룬다.
3. 다면체의 Cone lift
다면체의 경우, Cone lift는 slack matrix를 cone과 그 dual을 통해 factorization하는 것으로 정확히 특성화된다. 예시들은 lift size가 facial combinatorics를 넘어선 기하에 의존할 수 있음을 보이며, symmetry가 훨씬 더 강한 size 제약을 부과할 수 있음을 보여준다.
- full-dimensional polytope가 proper K-lift를 가질 필요충분조건은 그 slack matrix 중 하나가 K-factorization을 허용하는 것이다.slack matrix는 vertex에서의 facet-inequality 값을 기록하며, K-factorization은 nonnegative orthant에서 arbitrary closed convex cone으로 nonnegative matrix factorization을 일반화한다.
- regular hexagon은 R^5-lift를 가지며, 이는 자명한 polyhedral lift인 R^6으로의 lift보다 개선된 결과다.이 lift는 canonical slack matrix의 R^5-factorization에서 따르며, R^5의 three-dimensional slice를 hexagon에 사영하는 방식으로 실현할 수 있다.
- 같은 facial combinatorics를 갖는 irregular hexagon은 no R^5-lift를 가지며, lift의 존재가 facial structure만으로 결정되지 않음을 보인다.그 obstruction은 slack matrix가 가능한 zero-pattern decomposition 중 어느 것에 대해서도 R^5-factorization을 허용하지 않는다는 점이다.
- Symmetric lifts: n개의 변을 갖는 regular polygon에서, n이 prime 또는 prime power이면 symmetric R^k-lift는 k ≥ n을 요구한다.symmetric lift는 polytope의 automorphism group에서 coordinate-permutation group으로의 injective homomorphism을 유도하므로, |Aut(P)|는 k!을 나누어야 한다.
- 대칭적 lift: 정규 n각형은 비대칭 R^k-lifts를 허용하며, k = O(log n)이고 대칭성 요구사항과 지수적 격차를 만든다.이는 Ben-Tal과 Nemirovski [6]의 결과를 Proposition 3.5와 결합한 것이다. 정규 육각형의 R^5-lift 자체도 비대칭이다.
4. 볼록체의 cone rank
이 절에서는 closed cone family에 대한 볼록체의 cone rank를 정의하고, cone rank가 lift를 허용하는 최소 cone dimension과 정확히 같음을 증명한다. 이어 ordinary rank, nonnegative rank, psd rank 사이의 분리를 전개하고 polytope에 대한 구조적 하한을 도출한다.
- Cone family: closed cone family는 Ki의 모든 face가 j ≤ i인 어떤 Kj와 isomorphic이어야 하지만, copositive-matrix family는 closed하지 않다.rank–lift equivalence를 증명할 때 lower-dimensional face로의 nonproper lift를 배제하는 것은 closedness다.
- Cone rank: closed cone family K에 대해 rankK(C)는 convex body C가 Ki-lift를 갖게 하는 최소 index i다.동치로, rankK(C)는 C의 slack operator가 Ki-factorization을 갖게 하는 최소 i다.
- Rank 비교: (i−j)^2를 원소로 갖는 Mn에 대해 3 = rank(Mn)인 반면 rank+(Mn) ≥ log2 n이므로, ordinary rank가 nonnegative rank를 bound하지 않음을 보인다.따라서 ordinary rank가 일정하게 유지되어도 matrix size가 커짐에 따라 nonnegative rank는 증가할 수 있다.
- Rank 비교: nonnegative matrix M에 대해 원소를 제곱하면 psd rank의 ordinary-rank upper bound가 보존된다: rankpsd(M′) ≤ rank(M). 여기에는 0/1 matrix도 포함된다.또한 이 절에서는 적절한 family에서 ordinary, nonnegative, psd rank 사이의 gap이 각각 임의로 커질 수 있음을 보인다.
- Polytope bound: full-dimensional polytope의 slack-matrix psd rank가 k이면 facet 수는 최대 k^O(k^2n)이고, regular n-gon은 ordinary rank가 3임에도 psd rank tending to infinity를 보인다.이 결과는 polytope slack matrix에 대해서도 ordinary rank가 psd rank를 bound할 수 없음을 보인다.
5. 응용
응용 사례는 cone-factorization 방법이 stable set polytope의 최적 semidefinite lift를 어떻게 특징짓고, polynomial lift를 sum-of-squares certificate 및 theta body와 어떻게 연결하는지 보여준다. Stable set polytope는 uniformly small completely positive lift도 허용하지만, 현재로서는 계산상 실용적이지 않다.
- Stable set polytope: n개의 꼭짓점을 갖는 모든 graph G에 대해 STAB(G)는 S_n^+-lift를 갖지 않지만, perfect graph는 S_{n+1}^+-lift를 갖는다. 따라서 Lovász의 lift는 크기 면에서 최적이다.하한은 factorization theorem을 통해 slack-matrix substructure를 분석하여 얻으며, perfect-graph lift는 S_{n+1}^+를 slicing하고 projecting하여 구성된다.
- Stable set polytope: 하한 논증은 꼭짓점이 국소적으로 nonnegative orthant와 유사한 모든 n-dimensional polytope로 확장되며, 이러한 polytope는 S_n^+-lift를 갖지 않는다.논문은 또한 0/1 slack matrix를 갖는 n-dimensional polytope가 slack-matrix rank bound를 이용해 작은 semidefinite lift를 갖는다고 지적한다.
- Completely positive lift: 모든 stable set polytope STAB(G)는 semidefinite construction과 동일한 linear constraint를 사용하는 C_{n+1}^*-lift를 갖지만, completely positive programming에는 알려진 효율적 알고리즘이 없다.이 lift는 모든 graph에 적용되고 크기도 매우 작지만, 실제 계산에서의 관심은 제한적이다.
- Polynomial lift: 원점을 포함하는 compact conv(VR(I))를 갖는 convex radical ideal I에 대해, rational slack factorization은 variety 위에서 nonnegative인 linear polynomial에 대한 I modulo sum-of-squares certificate와 동치다.factorization은 A(x) = 1/p(x)^2 w(x)w(x)^T를 사용하며, sum-of-squares 항은 w(x)의 entry들의 linear combination으로 구성된다.
- Polynomial lift: degree-bounded w를 사용하는 polynomial slack factorization은 exact theta-body representation을 특징짓는다. 즉 degree at most k는 TH_k(I) = conv(Z)와 동치다.유사한 접근을 polynomial inequality에도 적용할 수 있지만, 그 결과로 얻는 lift는 positive semidefinite cone의 product를 사용한다.