Complexity analysis of successive convex relaxation methods for nonconvex sets

This paper discusses computational complexity of conceptual successive conv ex relaxation methods proposed by Kojima and Tuncel for approximating a con vex relaxation of a compact subset F = {x is an element of C-o : p(x) :less than or equal to 0 (For Allp (.) is an element of P-F)} of the n-dimension al Euclidean space R-n. Here, C-o denotes a nonempty compact convex subset of R-n, and P-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 e psilon, in terms of epsilon, the diameter of C-o, the diameter of F, and so me other quantities characterizing the Lipschitz continuity, the nonlineari ty, and the nonconvexity of the her P-F of quadratic functions.