spectrahedron

Containment problems for polytopes and spectrahedra

  • Kai Kellner
  • Thorsten Theobald
  • Christian Trabandt
    • Categories Polyhedra, Semi-definite Programming Tags , , , , ,

    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 … Read more

    An exact duality theory for semidefinite programming based on sums of squares

  • Igor Klep
  • Markus Schweighofer
    • Categories Semi-definite Programming Tags , , , , , , , ,

    Farkas’ lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix inequalities. We provide nonlinear algebraic certificates for all infeasible linear matrix inequalities in the spirit of real algebraic geometry: A linear matrix inequality … Read more