2012/04/19 by Kai Kellner, Kellner, Kai, Thorsten Theobald +3
Mathematics · #52A20 (Secondary) #52B55 #90C22 (Primary) 14P10 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG) #Optimization and Control (math.OC) #math.CO #math.MG #math.OC #msc:14P10 #msc:52A20 #msc:52B55 #msc:90C22
paper · pdf · doi:10.48550/arxiv.1204.4313
24 pages; minor corrections; to appear in SIAM J. Opt
arxiv created 2013/03/08 · arxiv updated 2013/03/11
We study the computational question whether a given polytope or spectrahedron SA (as given by the positive semidefiniteness region of a linear matrix pencil A(x)) is contained in another one SB. 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 SA the criteria will always succeed in certifying containment of some scaled spectrahedron νSA in SB.