Semidefinite relaxations for copositive optimization

Abstract

Linear optimization over the copositive cone C*, (i.e. the cone of quadratic forms which are nonnegative on the positive orthant) has applications in polynomial optimization, graph theory and data analysis. Although convex, this problem is unfortunately not tractable. In this work we study two nested sequences of spectrahedral cones that approximate C*. One formulated by Barvinok, Veomett and Laserre {BVLn}n?N and the other proposed by Parrilo {SOSn}n?N. Since these approximations are one from above and one from below, they can be used to cal- culate upper and lower bounds on the solution of copositive programs efficiently. This proves particularly useful in bounding the independence number of a graph ?(G). In this case, the fact that ?(G) is an integer means the lower and upper bounds need not meet to find the optimal value of the problem. This work is divided in four parts, first, we give a comprehensive description of the geometry of the copositive cone, second, we describe its semidefinite approximations, third, we survey the applications of copositive programming, fourth, we give new results on the BVL hierarchy when applied to calculating lower bounds of ?(G), propose an algorithm for obtaining large independence sets on G, and evaluate its empirical performance on Hamming and DeBruijn graphs