Optimization Online


Approximate cone factorizations and lifts of polytopes

João Gouveia(jgouveia***at***mat.uc.pt)
Pablo A. Parrilo(parrilo***at***mit.edu)
Rekha R. Thomas(rrthomas***at***uw.edu)

Abstract: 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.

Keywords: cone factorization, polytope lift, slack matrix, nonnegative matrix

Category 1: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 08/09/2013
Entry Accepted: 08/09/2013
Entry Last Modified: 08/09/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society