On the Finite Convergence of Successive SDP Relaxation Methods

Masakazu Kojima and Levent Tuncel

Let $F$ be a subset of the $n$-dimensional Euclidean space $R^n$ represented in terms of a compact convex subset $C_0$ and a set $\PC_F$ of finitely or infinitely many quadratic functions on $R^n$ such that $F = \{ \x \in C_0 : p(\x) \leq 0 \ (\forall p(\cdot) \in \PC_F) \}$. In this paper, we investigate some fundamental properties related to the finite convergence of the successive SDP (semidefinite programming) relaxation method proposed by the authors for approximating the convex hull of $F$.

Research Report B-354, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Meguro, Tokyo 152-8552, Japan, August 1999. Also issued as Research Report CORR 99-36, Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada

Contact: kojma@is.titech.ac.jp