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

DOI10.1137/15M1013341zbMath1347.90066arXiv1409.5008OpenAlexW2204983263MaRDI QIDQ2804545

Kai Kellner, Thorsten Theobald

Publication date: 29 April 2016

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

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

zbMATH Keywords

polytopebilinear programmingPositivstellensatzsum of squarescontainmentsemidefinite hierarchy

Mathematics Subject Classification ID

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

Related Items

Some Recent Developments in Spectrahedral Computation, Spectrahedral Containment and Operator Systems with Finite-Dimensional Realization

Uses Software

• QuadProgBB

Cites Work

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