A main problem in combinatorial optimization is to express the
convex hull of given finite set of points in R^{n} 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^{n}.
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 semiinfinite convex quadratically
constrained relaxations and the semiinfinite semidefinite programming
relaxations of closed, nonconvex sets. We then generalize two
liftandproject 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.
