Approximate cone factorizations and lifts of polytopes

• 成果类型: Article
• 署名作者: Gouveia, Joo; Parrilo, Pablo A.; Thomas, Rekha R.
• 署名单位: Universidade de Coimbra; Massachusetts Institute of Technology (MIT); University of Washington; University of Washington Seattle
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0848-z
• 发表日期: 2015
• 页码: 613-637
• 关键词: convex; PROGRAMS

摘要

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.