Theta Bodies for Polynomial Ideals

Details Theta Bodies for Polynomial Ideals Theta Bodies for Polynomial Ideals

2008-09-20

arxiv.org/abs/0809.3480v3

SIAM J. Optim. Volume 20, Issue 4, pp. 2097-2118 (2010)

Mathematics

Optimization and Control

26 pages, 3 figures

Scientific paper

10.1137/090746525

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\'asz'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.

Affiliated with

Also associated with

No associations

Rating

Theta Bodies for Polynomial Ideals does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Theta Bodies for Polynomial Ideals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Theta Bodies for Polynomial Ideals will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-311374