The theta body of a graph introduced by Lovasz in 1979 is one of the first examples of a semidefinite programming relaxation of a discrete optimization problem. Inspired by a connection between Lovasz's theta body of a graph and sums of squares polynomials, we define theta bodies for the real solutions to an arbitrary polynomial ideal. These bodies create a nested sequence of convex relaxations for the convex hull of the real solutions. When the the set of real solutions is finite, we characterize when the first theta body agrees with the connvex hull of real solutions partially answering a question posed by Lovasz. As an application, we derive a new hierarchy of semidefinite programming relaxations for the max cut problem and answer a second question of Lovasz as to which graphs are "cut-perfect" (the first theta body agrees with the cut polytope).
Joint work with Joao Gouveia, Monique Laurent and Pablo Parrilo
Copyright. All Rights Reserved.