Sum of squares certificates for containment of H-polytopes in V-polytopes

DOI10.1137/15M1013341zbMATH Open1347.90066arXiv1409.5008OpenAlexW2204983263MaRDI QIDQ2804545FDOQ2804545

Kai Kellner, Thorsten Theobald

Publication date: 29 April 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Given an $mathcalH$-polytope $P$ and a $mathcalV$-polytope $Q$, the decision problem whether $P$ is contained in $Q$ is co-NP-complete. This hardness remains if $P$ is restricted to be a standard cube and $Q$ 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 $P$ is contained in a large $mathcalV$-polytope $Q$ (in a well-defined sense), then containment is certified by the first step of the hierarchy.

Full work available at URL: https://arxiv.org/abs/1409.5008

Recommendations

• Containment problems for polytopes and spectrahedra
• On the complexity of four polyhedral set containment problems
• A semidefinite hierarchy for containment of spectrahedra
• \(\mathbb N\mathbb P\)-hardness of largest contained and smallest containing simplices for \(V\)- and \(H\)-polytopes
• On the complexity of some basic problems in computational convexity. I. Containment problems

zbMATH Keywords

polytopesum of squaresPositivstellensatzcontainmentbilinear programmingsemidefinite hierarchy

Mathematics Subject Classification ID

Quadratic programming (90C20) Semidefinite programming (90C22) (n)-dimensional polytopes (52B11) Semialgebraic sets and related spaces (14P10)

Cites Work

• Title not available (Why is that?)
• Lectures on Polytopes
• Global optimization with polynomials and the problem of moments
• Title not available (Why is that?)
• Sums of squares, moment matrices and optimization over polynomials
• Positivity and sums of squares: a guide to recent results
• Polynomial algorithms in linear programming
• Title not available (Why is that?)
• Nonlinear Programming
• The maximum numbers of faces of a convex polytope
• Generating all vertices of a polyhedron is hard
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Title not available (Why is that?)
• Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
• Globally solving nonconvex quadratic programming problems via completely positive programming
• A cutting plane algorithm for solving bilinear programs
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• On the complexity of four polyhedral set containment problems
• Convex hulls, oracles, and homology
• On the complexity of some basic problems in computational convexity. I. Containment problems
• How good are convex hull algorithms?
• Which nonnegative matrices are slack matrices?
• A Quantifier Elimination Algorithm for Linear Real Arithmetic
• Bilinear programming: An exact algorithm
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial-time approximation of largest simplices in \(V\)-polytopes.
• Largest \(j\)-simplices in \(n\)-polytopes
• Containment problems for polytopes and spectrahedra
• A Semidefinite Hierarchy for Containment of Spectrahedra
• Verification: Theory and Practice
• An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming

Cited In (3)

• On the complexity of four polyhedral set containment problems
• Spectrahedral Containment and Operator Systems with Finite-Dimensional Realization
• Some Recent Developments in Spectrahedral Computation

Uses Software

• QuadProgBB

This page was built for publication: Sum of squares certificates for containment of \(\mathcal{H}\)-polytopes in \(\mathcal{V}\)-polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2804545)