Journal
SIAM JOURNAL ON OPTIMIZATION
Volume 20, Issue 4, Pages 2097-2118Publisher
SIAM PUBLICATIONS
DOI: 10.1137/090746525
Keywords
semidefinite programming; theta bodies; polynomial ideals; sums of squares; moment matrices
Categories
Funding
- NSF Focused Research Group [DMS-0757371, DMS-0757207]
- Fundacao para a Ciencia e Tecnologia
Ask authors/readers for more resources
Inspired by a question of Lovasz, 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. These relaxations generalize Lovasz's construction of the theta body of a graph. We establish a relationship between theta bodies and Lasserre's relaxations for real varieties which allows, in many cases, for theta bodies to be expressed as feasible regions of semidefinite programs. Examples from combinatorial optimization are given. Lovasz asked to characterize ideals for which the first theta body equals the closure of the convex hull of its real variety. We answer this question for vanishing ideals of finite point sets via several equivalent characterizations. We also give a geometric description of the first theta body for all ideals.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available