Convex Hulls of Algebraic Sets

Details Convex Hulls of Algebraic Sets Convex Hulls of Algebraic Sets

2010-07-07

arxiv.org/abs/1007.1191v1

Mathematics

Optimization and Control

This article was written for the "Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and

Scientific paper

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. The convexification process can be seen as an incarnation of Lasserre's hierarchy of convex relaxations of a semialgebraic set in R^n. When the defining ideal is real radical the results become especially nice. We provide several examples of the method and discuss convergence issues. Finite convergence, especially after the first step of the method, can be described explicitly for finite point sets.

Affiliated with

Also associated with

No associations

Rating

Convex Hulls of Algebraic Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Convex Hulls of Algebraic Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convex Hulls of Algebraic Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-345964