## Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets

### Masakazu Kojima and Levent Tuncel

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$ of $R^n$ $(k=1,2,\ldots \ )$ such that \begin{description} \item{(a) } the
convex hull of $F \subseteq C_{k+1} \subseteq C_k$ (monotonicity), \item{(b) }
$\cap_{k=1}^{k^*} C_k = \emptyset$ for some finite number ${k^*}$ if $F = \emptyset$
(detecting infeasibility), \item{(c) } $\cap_{k=1}^{\infty} C_k = \ \mbox{the convex hull
of } F$ otherwise (asymptotic convergence). \end{description} Our methods are extensions
of the corresponding Lov\'{a}sz-Schrijver lift-and-project procedures with the use of SDP
or LP relaxation applied to general QPs (quadratic programs) 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
semi-infinite convex QP relaxation proposed originally by Fujie-Kojima. Using this
equivalence, we investigate some fundamental features of the two methods including (a),
(b) and (c) above.

Research Report B-338, Dept. of Mathematical Sciences, Tokyo Institute of Technology,
Oh-Okayama, Meguoro, Tokyo 152, March 1998

Contact: kojima@is.titech.ac.jp