Complexity analysis of successive convex relaxation methods for nonconvex sets

• 成果类型: Article
• 署名作者: Kojima, M; Takeda, A
• 署名单位: Institute of Science Tokyo; Tokyo Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.26.3.519.10580
• 发表日期: 2001
• 页码: 519-542
• 关键词: Hierarchy; matrices; cones

摘要

This paper discusses computational complexity of conceptual successive convex relaxation methods proposed by Kojima and Tuncel for approximating a convex 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-dimensional 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 epsilon, in terms of epsilon, the diameter of C-o, the diameter of F, and some other quantities characterizing the Lipschitz continuity, the nonlinearity, and the nonconvexity of the her P-F of quadratic functions.