Complexity Analysis of Conceptual Successive Convex Relaxation of Nonconvex Set

Masakazu Kojima and Akiko Takeda

This paper discusses computational complexity of conceptual successive convex relaxation methods proposed by Kojima and Tun\c{c}el for computing a convex relaxation of a compact subset $F = \{ \x \in C_0 : p(\x) \leq 0 \ (\forall p(\cdot) \in \PC_F) \}$ of the $n$-dimensional Euclidean space $R^n$. Here $C_0$ denotes a nonempty compact convex subset of $R^n$, and $\PC_F$ a set of finitely or infinitely many quadratic functions. We evaluate the number of iterations which the successive convex relaxation methods require to attain a convex relaxation of $F$ with a given accuracy $\epsilon$ in terms of $\epsilon$, the diameter of $C_0$, the diameter of $F$, and some other quantities characterizing the Lipschitz continuity, the nonconvexity, and the nonlinearity of the set $\PC_F$ of quadratic functions.

Research Report B-350, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku, Tokyo 152, April 1999.