The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



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

Gijben, L (Rijksuniversiteit Groningen)
Thursday 18 July 2013, 11:30-12:00

Seminar Room 1, Newton Institute


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 < 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.


[pdf ]


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.

Back to top ∧