Mathematics – Optimization and Control
Scientific paper
2012-04-19
Mathematics
Optimization and Control
22 pages
Scientific paper
We study the computational questions 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. We then study in detail two sufficient semidefinite conditions to certify containedness, whose study was initiated by Ben-Tal, Nemirovski and Helton, Klep, McCullough. We prove that these sufficient conditions even provide exact semidefinite characterizations for containment in several important cases. As a main result, we show that the criteria are exact for containment of a spectrahedron in a polyhedron. Moreover, we show that in the case of bounded $S_A$ the criteria will always succeed in certifying containedness of some scaled spectrahedron $\nu S_A$ in $S_B$.
Kellner Kai
Theobald Thorsten
Trabandt Christian
No associations
LandOfFree
Containment problems for polytopes and spectrahedra does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Containment problems for polytopes and spectrahedra, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Containment problems for polytopes and spectrahedra will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-34828