## 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.

Contact: kojima@is.titech.ac.jp