Containment problems for polytopes and spectrahedra

DOI10.1137/120874898MaRDI QIDQ2848183zbMATH OpenOpenAlexFDO

Authors Kai Kellner, Christian Trabandt, Thorsten Theobald

Publication date 25 September 2013

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

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

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)

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$.

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

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
• Extremal polygon containment problems
• Conic stability of polynomials and positive maps
• 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)