DC decomposition of nonconvex polynomials with algebraic techniques

Amir Ali Ahmadi; Georgina Hall

doi:10.1007/s10107-017-1144-5

DC decomposition of nonconvex polynomials with algebraic techniques

Amir Ali Ahmadi, Georgina Hall

Research output: Contribution to journal › Article › peer-review

24 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 language	English (US)
Pages (from-to)	69-94
Number of pages	26
Journal	Mathematical Programming
Volume	169
Issue number	1
DOIs	https://doi.org/10.1007/s10107-017-1144-5
State	Published - May 1 2018

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Keywords

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

Access to Document

10.1007/s10107-017-1144-5

Cite this

@article{dc948bb5f0ef48b4abaa37e4c9595691,

title = "DC decomposition of nonconvex polynomials with algebraic techniques",

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.",

keywords = "Algebraic decomposition of polynomials, Conic relaxations, Difference of convex programming, Polynomial optimization",

author = "Ahmadi, {Amir Ali} and Georgina Hall",

note = "Publisher Copyright: {\textcopyright} 2017, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.",

year = "2018",

month = may,

day = "1",

doi = "10.1007/s10107-017-1144-5",

language = "English (US)",

volume = "169",

pages = "69--94",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1",

}

TY - JOUR

T1 - DC decomposition of nonconvex polynomials with algebraic techniques

AU - Ahmadi, Amir Ali

AU - Hall, Georgina

PY - 2018/5/1

Y1 - 2018/5/1

N2 - 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.

AB - 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.

KW - Algebraic decomposition of polynomials

KW - Conic relaxations

KW - Difference of convex programming

KW - Polynomial optimization

UR - http://www.scopus.com/inward/record.url?scp=85017434785&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85017434785&partnerID=8YFLogxK

U2 - 10.1007/s10107-017-1144-5

DO - 10.1007/s10107-017-1144-5

M3 - Article

AN - SCOPUS:85017434785

SN - 0025-5610

VL - 169

SP - 69

EP - 94

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -

DC decomposition of nonconvex polynomials with algebraic techniques

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this