Source-linked AI summary
Theta Bodies for Polynomial Ideals
João Gouveia, Pablo A. Parrilo, Rekha R. Thomas
TL;DR
The paper asks how to represent or approximate convex hulls of real solutions to polynomial systems and when sum-of-squares certificates give exact descriptions. It introduces theta bodies as nested semidefinite relaxations, relates them to Lasserre relaxations, and studies their computation and exactness. The results establish algebraic-geometric equivalences for real radical ideals and characterize important applications, while some moment-matrix relaxations need not be closed.
Problem
Optimization often requires computing or approximating the convex hull of the real variety of a polynomial ideal, while Lovász’s question asks which ideals admit bounded-degree sum-of-squares certificates for nonnegative linear polynomials.
Method
The paper defines theta bodies by imposing linear inequalities that are sums of squares modulo an ideal, yielding a nested semidefinite hierarchy connected to Lasserre relaxations and combinatorial moment matrices.
Results
For real radical ideals, (1,k)-sos is equivalent to THk-exactness, while the hierarchy supports explicit semidefinite representations and applications to stable set, max cut, and finite point sets.
Takeaways & Limitations
Theta bodies provide a canonical framework for studying and computing semidefinite relaxations of convex hulls arising from polynomial ideals.
Takeaways & Limitations
The theta-body relaxation can be strictly larger than cl(conv(VR(I))) when nonnegative polynomials on VR(I) are not sums of squares modulo I.
Abstract
from arXiv · showhide
Inspired by a question of Lovász, 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á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.
1. Introduction
The paper introduces theta bodies, a nested hierarchy of semidefinite relaxations for convex hulls of real varieties, motivated by sum-of-squares certificates and Lovász’s question. It connects algebraic exactness to geometric exactness and develops applications, computation methods, and structural results across polynomial ideals.
- Algebraic motivation: The paper studies when nonnegative polynomials on VR(I) admit bounded-degree sum-of-squares certificates modulo I, formalizing Lovász’s question about (1,k)-sos ideals.The hierarchy bounds the degrees of polynomials used in the sum-of-squares representations.
- Theta bodies: The k-th theta body THk(I) consists of points satisfying every affine-linear inequality that is k-sos modulo I.An ideal is THk-exact when this body equals cl(conv(VR(I))).
- Theta bodies: Theta bodies are nested closed convex relaxations satisfying TH1(I) ⊇ TH2(I) ⊇ ··· ⊇ conv(VR(I)), converging at most to cl(conv(VR(I))).The closure is necessary because conv(VR(I)) may not itself be closed.
- Semidefinite representations: Under a technical hypothesis, theta bodies are closures of projections of spectrahedra, connect to Lasserre relaxations, and admit explicit combinatorial moment-matrix representations.Semidefinite programs provide the computational framework for these relaxations.
- Applications and structure: The paper applies the hierarchy to stable set and maximum cut, characterizes TH1-exactness for finite vanishing ideals, and describes TH1(I) intrinsically using convex quadrics.For finite point sets, the results include structural consequences for 0/1-polytopes and perfect-graph stable set polytopes; analogous descriptions for higher theta bodies remain open.
2. Theta Bodies
Theta bodies form nested closed semidefinite relaxations of the convex hull of an ideal’s real variety, and connect to modified Lasserre relaxations through truncated quadratic modules. For real radical ideals, these relaxations coincide up to closure and admit explicit moment-matrix SDP representations, with exactness and convergence governed by algebraic and geometric conditions.
- Theta bodies are nested closed convex relaxations satisfying THk(I) ⊇ THk+1(I) ⊇ conv(VR(I)).
- The modified Lasserre relaxation Qk(I) contains conv(VR(I)), is nested in k, and satisfies cl(Qk(I)) ⊆ THk(I).
- If Mk(I) is closed, then cl(Qk(I)) = THk(I); in particular, this equality holds for every real radical ideal.
- For real radical ideals, THk-exactness is equivalent to every nonnegative linear polynomial on VR(I) being k-sos modulo I.
- Finite real varieties achieve exactness at some finite level, compact varieties converge asymptotically to cl(conv(VR(I))), while noncompact cases are harder and require additional positivity results.
- The relaxations have explicit semidefinite representations: Qk(I) consists of normalized moment vectors y with MBk(y) ⪰ 0, and linear optimization over them is an SDP.
3. Combinatorial Examples
The paper applies theta bodies to stable set and max cut problems, showing how graph structure yields nested semidefinite relaxations and exactness results. For stable sets, the first theta body recovers Lovász’s theta body, while max cut receives a new canonical hierarchy.
- Combinatorial applications: The theta body hierarchy extends graph relaxations to polynomial ideals and provides a new mechanism for semidefinite relaxations in combinatorial optimization.The framework is applied to stable set and maximum cut problems, with graph structure incorporated directly into the ideal-based formulation.
- The maximum stable set problem: The first theta body of IG has an explicit combinatorial moment-matrix description whose constraints encode normalization, vertex coordinates, nonedges, and stability of unions.The stable-set monomial basis indexes the matrix, and the resulting first-level matrix description coincides with Lovász’s semidefinite formulation.
- The maximum stable set problem: For a graph G, TH1(IG) equals Lovász’s theta body TH(G), and TH1(IG) equals STAB(G) exactly when G is perfect.Perfectness is also equivalent to IG being (1,1)-sos.
- The maximum stable set problem: The usual Lasserre hierarchy for stable sets is exactly the theta body hierarchy, despite using inequality constraints in its standard formulation and only the ideal in the theta-body formulation.This equivalence provides algebraic tools for proving inequalities valid over the relaxations.
- The maximum stable set problem: Odd cycles have theta-rank two, so TH2(IG) satisfies all odd-cycle inequalities, while no constant level is exact for all graphs.For an odd cycle with at least five vertices, IG is (1,2)-sos; more generally, TH2(IG) satisfies odd-cycle, odd-antihole, and odd-wheel inequalities.
- Cuts in graphs: For max cut, theta bodies give canonical semidefinite relaxations exploiting graph structure, but first-level exactness holds only for bipartite graphs in the discussed formulation.The theta-rank is bounded above by the maximum cut size, and no constant level is exact for all graphs.
4. Vanishing ideals of finite sets of points
For finite point sets, the first theta body equals the convex hull precisely under several equivalent algebraic and geometric conditions, yielding structural consequences for exact sets and related 0/1-polytopes.
- Characterizations: For finite S, exactness, (1,1)-sos representability, linear 1-sos descriptions, idempotent facet inequalities, and two-level facet values are equivalent.These conditions characterize when TH1(I(S)) equals conv(S).
- Theta-rank bounds: Finite real radical vanishing ideals have finite theta-rank, with the bound theta-rank ≤ |VC(I)| − 1; sharper bounds follow when facet inequalities take at most t+1 values.The latter condition implies THt-exactness.
- Structural consequences: Exact finite sets are stable under taking vertices of faces and Cartesian products, and their polytopes are affinely equivalent to 0/1-polytopes.Thus exact finite varieties can essentially be studied among subsets of {0,1}^n.
- Examples: Examples exact in every dimension include hypercubes, regular cross polytopes, hypersimplices, joins of 2-level polytopes, and stable set polytopes of perfect graphs.These families provide broad classes of finite sets with TH1-exact vanishing ideals.
- Polyhedral bounds: An exact d-dimensional finite set has at most 2d facets and vertices, with both bounds sharp; the facet bound is attained by cross-polytopes.The refined characterization identifies simplices and regular cross-polytopes as equality cases for face-pair and facet bounds.
- Graph-theoretic consequence: For stable-set polytopes, exactness is equivalent to the graph being perfect, equivalently to the polytope being 2-level.For full-dimensional down-closed 0/1-polytopes, exactness is likewise equivalent to being the stable set polytope of a perfect graph.
5. Arbitrary TH1-exact Ideals
The first theta body of an arbitrary ideal is governed by convex quadrics contained in the ideal, enabling exactness results beyond finite or zero-dimensional varieties.
- Nontriviality criterion: TH1(I) is nontrivial exactly when I contains a convex quadric.If no convex quadric lies in I, the first theta body is all of R^n.
- Structural reduction: For any ideal I, TH1(I) equals the intersection of TH1(<F>) over all convex quadrics F in I.This reduces the first theta body to principal ideals generated by convex quadrics.
- Convex quadrics: For a convex quadratic F(x)=x^T A x+b^T x+c with A ⪰ 0, TH1(<F>) equals conv(VR(F)).The proof uses tangent hyperplanes when the real zero set is nonsingular and factors F into sums of squares in the singular case.
- Example: The non-principal ideal <x^2−z, y^2−z> is TH1-exact, despite having a high-dimensional real variety.Its theta body is identified through the inequalities x^2≤z and y^2≤z.
- Example 5.6: Example 5.6 computes TH1 for four points by restricting the admissible quadratic forms to a parameter interval and intersecting the resulting convex regions.The endpoint inequalities determine the intersection shown in Figure 3.