A main problem in combinatorial optimization is to express the convex hull of given finite set of points in Rⁿ as the intersection of half spaces (in an efficient manner). In the late 1980's, Lovasz and Schrijver proposed a method to compute the convex hull of any subset of the extreme points of the unit cube in Rⁿ. Their method is very elegant and it was a very important breakthrough for combinatorial optimization using the cones of semidefinite matrices. In this talk, I will present a generalization of this method. The generalized method can be used to compute the convex hull of the set of solutions of any system of polynomial inequalities in n variables.

We first show the exact equivalence of semi-infinite convex quadratically constrained relaxations and the semi-infinite semidefinite programming relaxations of closed, nonconvex sets. We then generalize two lift-and-project methods of Lovasz and Schrijver to compute the convex hull of any compact set in an Euclidean Space (therefore, our algorithms in principle, can be used to solve any optimization problem in an Euclidean Space). We create a hierarchy of valid inequalities for compact sets and then determine the class of valid inequalities for which the strongest convergence results apply. We show that our convergence results are the best possible within this hierarchy of valid inequalities. Even though our algorithms are conceptual, we can show that via a discretization procedure, they can all be implemented on a computer without sacrificing much of the theoretical convergence properties. These implementable versions use only standard linear programming algorithms or standard semidefinite programming algorithms as subroutines.