Approximate cone factorizations and lifts of polytopes

作者：Gouveia Joo; Parrilo Pablo A; Thomas Rekha R^*

来源：Mathematical Programming, 2015, 151(2): 613-637.

DOI：10.1007/s10107-014-0848-z

• Approximations
• Polytopes
• Cone factorizations
• Slack matrix

In this paper we show how to construct inner and outer convex approximations of a polytope from an approximate cone factorization of its slack matrix. This provides a robust generalization of the famous result of Yannakakis that polyhedral lifts of a polytope are controlled by (exact) nonnegative factorizations of its slack matrix. Our approximations behave well under polarity and have efficient representations using second order cones. We establish a direct relationship between the quality of the factorization and the quality of the approximations, and our results extend to generalized slack matrices that arise from a polytope contained in a polyhedron.

• 出版日期2015-7
• 单位MIT