Containment problems for polytopes and spectrahedra

DOI10.1137/120874898zbMATH Open1296.68177arXiv1204.4313OpenAlexW2962695108MaRDI QIDQ2848183FDOQ2848183

Authors: Kai Kellner, Christian Trabandt, Thorsten Theobald 

Publication date: 25 September 2013

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: We study the computational question whether a given polytope or spectrahedron $S_A$ (as given by the positive semidefiniteness region of a linear matrix pencil $A(x)$) is contained in another one $S_B$. First we classify the computational complexity, extending results on the polytope/polytope-case by Gritzmann and Klee to the polytope/spectrahedron-case. For various restricted containment problems, NP-hardness is shown. We then study in detail semidefinite conditions to certify containment, building upon work by Ben-Tal, Nemirovski and Helton, Klep, McCullough. In particular, we discuss variations of a sufficient semidefinite condition to certify containment of a spectrahedron in a spectrahedron. It is shown that these sufficient conditions even provide exact semidefinite characterizations for containment in several important cases, including containment of a spectrahedron in a polyhedron. Moreover, in the case of bounded $S_A$ the criteria will always succeed in certifying containment of some scaled spectrahedron $u{S}_A$ in $S_B$.

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

Recommendations

• A semidefinite hierarchy for containment of spectrahedra
• Extremal polygon containment problems
• Containment and inscribed simplices
• New phenomena in the containment problem for simplicial arrangements
• The containment problem and a rational simplicial arrangement
• scientific article; zbMATH DE number 1182566
• On some polyhedra covering problems
• Polytope Containment and Determination by Linear Probes
• Containment and circumsribing simplices
• A problem of packing homothetic convex polytopes

zbMATH Keywords

semidefinite programmingpolyhedrarelaxationcontainmentspectrahedra

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)

Cited In (17)

• The tracial Hahn-Banach theorem, polar duals, matrix convex sets, and projections of free spectrahedra
• On the complexity of four polyhedral set containment problems
• A semidefinite hierarchy for containment of spectrahedra
• Conic stability of polynomials and positive maps
• Extremal polygon containment problems
• Deciding polyhedrality of spectrahedra
• Spectrahedral Containment and Operator Systems with Finite-Dimensional Realization
• Dilations, Linear Matrix Inequalities, the Matrix Cube Problem and Beta Distributions
• Deciding robust feasibility and infeasibility using a set containment approach: an application to stationary passive gas network operations
• The containment problem and a rational simplicial arrangement
• On set containment characterizations for sets described by set-valued maps with applications
• Polytope Containment and Determination by Linear Probes
• Sum of squares certificates for containment of \(\mathcal{H}\)-polytopes in \(\mathcal{V}\)-polytopes
• Finding minimum volume circumscribing ellipsoids using generalized copositive programming
• On the co-NP-completeness of the zonotope containment problem
• Some recent developments in spectrahedral computation
• A matrix Positivstellensatz with lifting polynomials

This page was built for publication: Containment problems for polytopes and spectrahedra

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