Sum of Squares Certificates for Containment of H\mathcal{H}-polytopes in V\mathcal{V}-polytopes

preprint2016arXivOpen access

Abstract

Given an H\mathcal{H}-polytope PP and a V\mathcal{V}-polytope QQ, the decision problem whether PP is contained in QQ is co-NP-complete. This hardness remains if PP is restricted to be a standard cube and QQ is restricted to be the affine image of a cross polytope. While this hardness classification by Freund and Orlin dates back to 1985, for general dimension there seems to be only limited progress on that problem so far. Based on a formulation of the problem in terms of a bilinear feasibility problem, we study sum of squares certificates to decide the containment problem. These certificates can be computed by a semidefinite hierarchy. As a main result, we show that under mild and explicitly known preconditions the semidefinite hierarchy converges in finitely many steps. In particular, if PP is contained in a large V\mathcal{V}-polytope QQ (in a well-defined sense), then containment is certified by the first step of the hierarchy.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.