ICCOPT 2013 Talk, Room 1.1, Tuesday, July 30, 16:30-18:00

 Speaker: Luuk Gijben, University of Groningen, The Netherlands
 Title: Scaling relationships between the copositive cone and the cone of sum of squares polynomials
 Co-authors: Peter J. C. Dickinson, Mirjam Dür, Roland Hildebrand

 Abstract:
Scientific Program

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 these cones can be checked by deciding whether a certain polynomial can be written as a sum of squares, which can be done via semidefinite programming. It is known that for matrices of order n < 5 the zero order Parrilo cone is equal to 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 the copositive cone and the semidefinite cone of that order.


 Talk in: Organized Session Tue.C.11 Algebraic geometry and semidefinite programming III
 Cluster: Conic and polynomial optimization


 Go to: Tue.C
 Go to: unframed Scientific Program

 Go to: ICCOPT 2013 Main Webpage