Scaling relationship between the copositive cone and a hierarchy of semidefinite approximations
Seminar Room 1, Newton Institute
AbstractSeveral 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 < 5 the zero order Parrilo cone equals the copositive cone. In this talk we will investigate the relation between the hierarchy and the copositive cone for 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.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.