Optimization Online


Containment problems for polytopes and spectrahedra

Kai Kellner (kellner***at***math.uni-frankfurt.de)
Thorsten Theobald (theobald***at***math.uni-frankfurt.de)
Christian Trabandt (trabandt***at***math.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/2012
Entry Accepted: 04/25/2012
Entry Last Modified: 10/22/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society