- Containment problems for polytopes and spectrahedra Kai Kellner (kellnermath.uni-frankfurt.de) Thorsten Theobald (theobaldmath.uni-frankfurt.de) Christian Trabandt (trabandtmath.uni-frankfurt.de) 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/poly\-tope-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 $\nu S_A$ in $S_B$. Keywords: polyhedron, spectrahedron, containment, relaxation, semidefinite programming, polytope Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 2: Combinatorial Optimization (Polyhedra ) Citation: Submitted to SIAM Journal on Optimization Download: [PDF]Entry Submitted: 04/25/2012Entry Accepted: 04/25/2012Entry Last Modified: 10/22/2012Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.