Theta Bodies for Polynomial Ideals

Abstract

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.

26 pages, 3 figures

References in corpus (1)

• Semidefinite Characterization and Computation of Real Radical Ideals

Cited by in corpus (27)

• The Convex Geometry of Linear Inverse Problems
• Computational and Statistical Tradeoffs via Convex Relaxation
• Lifts of convex sets and cone factorizations
• Semidefinite programming relaxations for quantum correlations
• On the local stability of semidefinite relaxations
• Bounding the set of classical correlations of a many-body system
• No quantum realization of extremal no-signaling boxes
• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
• Spectral bounds for the independence ratio and the chromatic number of an operator
• Detecting Bell correlations in multipartite non-Gaussian spin states
• Computation with Polynomial Equations and Inequalities arising in Combinatorial Optimization
• Lifting for Simplicity: Concise Descriptions of Convex Sets
• Toric rings and ideals of stable set polytopes
• Equivariant semidefinite lifts and sum-of-squares hierarchies
• Reverse lexicographic squarefree initial ideals and Gorenstein Fano polytopes
• Two results on the size of spectrahedral descriptions
• The tropical analogue of the Helton-Nie conjecture is true
• Deriving three-outcome permutationally invariant Bell inequalities
• Monogamy of entanglement between cones
• All two-party facet Bell inequalities are violated by Almost Quantum correlations
• An Axiomatic Duality Framework for the Theta Body and Related Convex Corners
• Towards a Computational Proof of Vizing's Conjecture using Semidefinite Programming and Sums-of-Squares
• Equivariant semidefinite lifts of regular polygons
• Perfectly contractile graphs and quadratic toric rings
• An Effective Positivstellensatz over the Rational Numbers for Finite Semialgebraic Sets
• Whitney Stratification of Algebraic Boundaries of Convex Semi-algebraic Sets
• Sum-of-Squares Certificates for Vizing's Conjecture via Determining Gröbner Bases