Complexity Analysis of Successive Convex Relaxation Methods for Nonconvex Sets

This paper discusses computational complexity of conceptual successive convex relaxation methods proposed by Kojima and Tunçel for approximating a convex relaxation of a compact subset F = {x ∈ C₀ : p(x) ≤ 0 (∀p(·) ∈ 𝒫_F)} of the n-dimensional Euclidean space Rⁿ. Here, C₀ denotes a nonempty compact convex subset of Rⁿ, and 𝒫_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 ε, in terms of ε, the diameter of C₀, the diameter of F, and some other quantities characterizing the Lipschitz continuity, the nonlinearity, and the nonconvexity of the set 𝒫_F of quadratic functions.