Optimization Online


DC Decomposition of Nonconvex Polynomials with Algebraic Techniques

Amir Ali Ahmadi(a_a_a***at***princeton.edu)
Georgina Hall(gh4***at***princeton.edu)

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.

Keywords: Difference of convex programming, conic relaxations, polynomial optimization, algebraic decomposition of polynomials

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Global Optimization

Category 3: Applications -- Science and Engineering (Statistics )

Citation: ORFE, Sherrerd Hall, Princeton University, Princeton, NJ 08540; October 2015

Download: [PDF]

Entry Submitted: 10/09/2015
Entry Accepted: 10/09/2015
Entry Last Modified: 10/09/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society