# DC Decomposition of Nonconvex Polynomials with Algebraic Techniques

arXiv: https://arxiv.org/abs/1510.01518 · HTML: https://mlsanity.com/paper/1510.01518/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2015.

## Built on by (most cited first, 6 of 6)

- [Higher-Order Newton Methods with Polynomial Work per Iteration](https://mlsanity.com/paper/2311.06374/) (2023)
- [Sums of Separable and Quadratic Polynomials](https://mlsanity.com/paper/2105.04766/) (2021)
- [Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence](https://mlsanity.com/paper/2109.04228/) (2021)
- [On Approximate Computation of Critical Points](https://mlsanity.com/paper/2601.21917/) (2026)
- [RA-DCA: A Randomized Active-Set DCA for Directional Stationarity in Max-Structured DC Programs](https://mlsanity.com/paper/2605.23550/) (2026)
- [Difference of Convex Programming in the Wasserstein Space with Applications to MMD Optimization](https://mlsanity.com/paper/2606.27767/) (2026)

## Abstract (arXiv)

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.