DC decomposition of nonconvex polynomials with algebraic techniques

• 成果类型: Article
• 署名作者: Ahmadi, Amir Ali; Hall, Georgina
• 署名单位: Princeton University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1144-5
• 发表日期: 2018
• 页码: 69-94
• 关键词: Optimization; convexity; minimization

摘要

We consider the problem of decomposing a multivariate polynomial as the difference of two convex polynomials. We introduce algebraic techniques which reduce this task to linear, second order cone, and semidefinite programming. This allows us to optimize over subsets of valid difference of convex decompositions (dcds) and find ones that speed up the convex-concave procedure. We prove, however, that optimizing over the entire set of dcds is NP-hard.