DC decomposition of nonconvex polynomials with algebraic techniques

Amir Ali Ahmadi, Georgina Hall

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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. We prove, however, that optimizing over the entire set of dcds is NP-hard.

Original languageEnglish (US)
Pages (from-to)69-94
Number of pages26
JournalMathematical Programming
Volume169
Issue number1
DOIs
StatePublished - May 1 2018

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Algebraic decomposition of polynomials
  • Conic relaxations
  • Difference of convex programming
  • Polynomial optimization

Fingerprint Dive into the research topics of 'DC decomposition of nonconvex polynomials with algebraic techniques'. Together they form a unique fingerprint.

Cite this