DC Decomposition of Nonconvex Polynomials with Algebraic Techniques
This addresses a computational challenge in nonconvex optimization for researchers and practitioners, though it is incremental as it focuses on specific algebraic methods and highlights inherent complexity limits.
The paper tackles the problem of decomposing multivariate polynomials into differences of convex polynomials, introducing algebraic techniques that reduce the task to linear, second order cone, and semidefinite programming, enabling optimization over subsets of decompositions to speed up the convex-concave procedure, but proves that optimizing over all decompositions is NP-hard.
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 (CCP). We prove, however, that optimizing over the entire set of dcds is NP-hard.