Sum of squares certificates for containment of H-polytopes in V-polytopes
From MaRDI portal
Publication:2804545
Abstract: Given an -polytope and a -polytope , the decision problem whether is contained in is co-NP-complete. This hardness remains if is restricted to be a standard cube and 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 is contained in a large -polytope (in a well-defined sense), then containment is certified by the first step of the hierarchy.
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
Cites work
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 1961535 (Why is no real title available?)
- scientific article; zbMATH DE number 1755731 (Why is no real title available?)
- A Quantifier Elimination Algorithm for Linear Real Arithmetic
- A cutting plane algorithm for solving bilinear programs
- A semidefinite hierarchy for containment of spectrahedra
- An iterative scheme for valid polynomial inequality generation in binary polynomial programming
- Bilinear programming: An exact algorithm
- Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
- Containment problems for polytopes and spectrahedra
- Convex hulls, oracles, and homology
- Generating all vertices of a polyhedron is hard
- Global optimization with polynomials and the problem of moments
- Globally solving nonconvex quadratic programming problems via completely positive programming
- How good are convex hull algorithms?
- Largest \(j\)-simplices in \(n\)-polytopes
- Lectures on Polytopes
- Moments, positive polynomials and their applications
- Nonlinear Programming
- On the complexity of four polyhedral set containment problems
- On the complexity of some basic problems in computational convexity. I. Containment problems
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Polynomial algorithms in linear programming
- Polynomial-time approximation of largest simplices in \(V\)-polytopes.
- Positive polynomials and sums of squares
- Positivity and sums of squares: a guide to recent results
- Qualitative theorem proving in linear constraints
- Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
- Sums of squares, moment matrices and optimization over polynomials
- The maximum numbers of faces of a convex polytope
- Which nonnegative matrices are slack matrices?
Cited in
(3)
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)
