×

Complexity analysis of successive convex relaxation methods for nonconvex sets. (English) Zbl 1073.90580

Summary: This paper discusses computational complexity of conceptual successive convex relaxation methods proposed by M. Kojima and L. Tunçel [SIAM J. Optim. 10, No. 3, 750–778 (2000; Zbl 0966.90062)] for approximating a convex relaxation of a compact subset \[ F=\{x\in C_0\colon p(x)\leq 0\quad \forall p(\cdot)\in{\mathcal P}_F\}. \] of the \(n\)-dimensional Euclidean space \(\mathbb R^n\). Here, \(C_0\) denotes a nonempty compact convex subset of \(\mathbb R^n\), and \({\mathcal 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 \(\varepsilon\), in terms of \(\varepsilon\), the diameter of \(C_0\), the diameter of \(F\), and some other quantities characterizing the Lipschitz continuity, the nonlinearity, and the nonconvexity of the set \({\mathcal P}_F\) of quadratic functions.

MSC:

90C60 Abstract computational complexity for mathematical programming problems
68Q25 Analysis of algorithms and problem complexity
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)

Citations:

Zbl 0966.90062
PDFBibTeX XMLCite
Full Text: DOI Link