DC Decomposition of Nonconvex Polynomials with Algebraic Techniques

2015/10/06 by Amir Ali Ahmadi, Ahmadi, Amir Ali, Georgina Hall +1 · 2 citations
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Optimization and Control (math.OC) #cs.DS #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1510.01518

arxiv created 2018/09/12 · arxiv updated 2018/09/13

Abstract

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.

Cited by

• Sum of Squares Submodularity
• Exact DC Representation of Multi-Tier Offloading Product in SAGINs via Quantifier Elimination

Related

• On Difference-of-SOS and Difference-of-Convex-SOS Decompositions for Polynomials
• A Boosted-DCA with Power-Sum-DC Decomposition for Linearly Constrained Polynomial Programs
• Multi-objective convex polynomial optimization and semidefinite programming relaxations
• A novel exact approach to polynomial optimization
• Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming