Approximate cone factorizations and lifts of polytopes

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