Lifts of Non-Compact Convex Sets and Cone Factorizations

  • PDF / 347,189 Bytes
  • 24 Pages / 595.276 x 841.89 pts (A4) Page_size
  • 105 Downloads / 185 Views

DOWNLOAD

REPORT


Lifts of Non-Compact Convex Sets and Cone Factorizations∗ WANG Chu · ZHI Lihong

DOI: 10.1007/s11424-020-9050-y Received: 18 February 2019 c The Editorial Office of JSSC & Springer-Verlag GmbH Germany 2020 Abstract This paper generalizes the factorization theorem of Gouveia, Parrilo and Thomas to a broader class of convex sets. Given a general convex set, the authors define a slack operator associated to the set and its polar according to whether the convex set is full dimensional, whether it is a translated cone and whether it contains lines. The authors strengthen the condition of a cone lift by requiring not only the convex set is the image of an affine slice of a given closed convex cone, but also its recession cone is the image of the linear slice of the closed convex cone. The authors show that the generalized lift of a convex set can also be characterized by the cone factorization of a properly defined slack operator. Keywords Cone factorization, convex set, lift, nonnegative rank, polyhedron, positive semidefinite rank, recession cone.

1

Introduction

Given a linear programming problem, how to reformulate it to a standard form with fewer constraints is an important problem. In [1], Yannakakis proved that the nonnegative rank of a slack matrix of a polytope P is the minimum number k such that P is the linear image of an affine slice of the nonnegative quadrant Rk+ . In [2, 3], Yannakakis’s result was generalized to decide whether a convex body C (a compact convex set containing the origin in its interior) is the linear image of an affine slice of a given convex cone K (K-lift) via cone factorizations of slack operators. Although it was claimed that results in [3] hold for all convex sets, we WANG Chu Beijing Jinghang Computation and Communication Research Institute, Beijing 100074, China. Email: [email protected]. ZHI Lihong (Corresponding author) KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; University of Chinese Academy of Sciences, Beijing 100049, China. Email: [email protected]. ∗ This paper was supported by Equipment Pre-Research Field Fund under Grant Nos. JZX7Y20190258055501, JZX7Y20190243016801, the National Natural Science Foundation of China under Grant No. 11901544, the National Key Research Project of China under Grant No. 2018YFA0306702 and the National Natural Science Foundation of China under Grant No. 11571350. This work is also supported by National Institute for Mathematical Sciences 2014 Thematic Program on Applied Algebraic Geometry in Daejeon, South Korea.  This paper was recommended for publication by Editor-in-Chief GAO Xiao-Shan.

2

WANG CHU · ZHI LIHONG

notice that it is more complicated to identify whether a non-compact convex set C containing no lines has a K-lift since C could be generated by not only extreme points but also extreme directions. Moreover, if a convex set contains lines, then it has no extreme points or extreme directions. Furthermore, if the convex set does not contain the origin in its interior, linear funct