Optimization Online


Theta Bodies for Polynomial Ideals

Joćo Gouveia (jgouveia***at***math.washington.edu)
Pablo A. Parrilo (parrilo***at***mit.edu)
Rekha R. Thomas (thomas***at***math.washington.edu)

Abstract: Inspired by a question of Lov\'asz, we introduce a hierarchy of nested semidefinite relaxations of the convex hull of real solutions to an arbitrary polynomial ideal, called theta bodies of the ideal. For the stable set problem in a graph, the first theta body in this hierarchy is exactly Lov{\'a}sz's theta body of the graph. We prove that theta bodies are, up to closure, a version of Lasserre's relaxations for real solutions to ideals, and that they can be computed explicitly using combinatorial moment matrices. Theta bodies provide a new canonical set of semidefinite relaxations for the max cut problem. For vanishing ideals of finite point sets, we give several equivalent characterizations of when the first theta body equals the convex hull of the points. We also determine the structure of the first theta body for all ideals.

Keywords: Semidefinite programming, theta bodies, polynomial ideals.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: Preprint, January/09

Download: [PDF]

Entry Submitted: 01/12/2009
Entry Accepted: 01/12/2009
Entry Last Modified: 10/15/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society