Convex Hulls of Algebraic Sets

Understand

This article describes a method to compute successive convex approximations of the convex hull of a set of points in R^n that are the solutions to a system of polynomial equations over the reals.

• The method relies on sums of squares of polynomials and the dual theory of moment matrices.
• The main feature of the technique is that all computations are done modulo the ideal generated by the polynomials defining the set to the convexified.
• This work was motivated by questions raised by Lov\'asz concerning extensions of the theta body of a graph to arbitrary real algebraic varieties, and hence the relaxations described here are called theta bodies.