ABSTRACT. 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 Lovász and Schrijver (1991) 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.
This talk is based on joint work with M. Kojima (Tokyo Institute of Technology).