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