Optimization Online


A Semidefinite Hierarchy for Containment of 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: A spectrahedron is the positivity region of a linear matrix pencil, thus defining the feasible set of a semidefinite program. We propose and study a hierarchy of sufficient semidefinite conditions to certify the containment of a spectrahedron in another one. This approach comes from applying a moment relaxation to a suitable polynomial optimization formulation. The hierarchical criterion is stronger than a solitary semidefinite criterion discussed earlier by Helton, Klep, and McCullough as well as by the authors. Moreover, several exactness results for the solitary criterion can be brought forward to the hierarchical approach. The hierarchy also applies to the (equivalent) question of checking whether a map between matrix (sub-)spaces is positive. In this context, the solitary criterion checks whether the map is completely positive, and thus our results provide a hierarchy between positivity and complete positivity.

Keywords: spectrahedra, containment, moment relaxation, positive map, complete positivity, semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 08/23/2013
Entry Accepted: 08/23/2013
Entry Last Modified: 03/20/2015

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