Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets

. Let F be a compact subset of the n-dimensional Euclidean space R n represented by (finitely or infinitely many) quadratic inequalities. We propose two methods, one based on successive semidefinite programming (SDP) relaxations and the other on successive linear programming (LP) relaxations. Each of our methods generates a sequence of compact convex subsets C k (k = 1; 2; : : : ) of R n such that (a) the convex hull of F ` C k+1 ` C k (monotonicity), (b) " 1 k=1 C k = the convex hull of F (asymptotic convergence). Our methods are extensions of the corresponding Lov'asz-Schrijver lift-and-project procedures with the use of SDP or LP relaxation applied to general Quadratic Optimization Problems (QOP) with infinitely many quadratic inequality constraints. Utilizing descriptions of sets based on cones of matrices and their duals, we establish the exact equivalence of the SDP relaxation and the semiinfinite convex QOP relaxation proposed originally by Fujie-Kojima. Using this equiva..