zbMATH — the first resource for mathematics

Theta bodies for polynomial ideals. (English) Zbl 1213.90190
The authors 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. They establish a relationship between theta bodies and Lassere’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’s question to characterize ideals for which the first theta body equals the closure of the convex hull of its real variety is answered for vanishing ideals of finite point sets via several equivalent characterizations. The authors also give a geometric description of the first theta body for all ideals.

90C22 Semidefinite programming
11E25 Sums of squares and representations by other particular quadratic forms
52A27 Approximation by convex sets
90C27 Combinatorial optimization
14P05 Real algebraic sets
Full Text: DOI arXiv