skip to content

Scaling relationship between the copositive cone and a hierarchy of semidefinite approximations

Presented by: 
L Gijben Rijksuniversiteit Groningen
Thursday 18th July 2013 - 11:30 to 12:00
INI Seminar Room 1
Several NP-complete problems can be turned into convex problems by formulating them as optimization problems over the copositive cone. Unfortunately checking membership in the copositive cone is a co-NP-complete problem in itself. To deal with this problem, several approximation schemes have been developed. One of them is a hierarchy of cones introduced by P. Parrilo, membership of which can be checked via semidefinite programming. In some sense this hierarchy forms a bridge between the semidefinite cone and the copositive cone. Starting off from the cone of semidefinite plus nonnegative matrices, the sets in the hierarchy grow ever closer to the copositive cone. We know that for matrices of order n 4. In particular a surprising result is found for the case n = 5, establishing a direct link between coposit ive programming and semidefinite programming for problems of that order.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons