NP-hardness of deciding convexity of quartic polynomials and related problems

Amir Ali Ahmadi; Alex Olshevsky; Pablo A. Parrilo; John N. Tsitsiklis

doi:10.1007/s10107-011-0499-2

NP-hardness of deciding convexity of quartic polynomials and related problems

Amir Ali Ahmadi, Alex Olshevsky, Pablo A. Parrilo, John N. Tsitsiklis

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

79 Scopus citations

Abstract

We show that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic polynomials. We also prove that deciding strict convexity, strong convexity, quasiconvexity, and pseudoconvexity of polynomials of even degree four or higher is strongly NP-hard. By contrast, we show that quasiconvexity and pseudoconvexity of odd degree polynomials can be decided in polynomial time.

Original language	English (US)
Pages (from-to)	453-476
Number of pages	24
Journal	Mathematical Programming
Volume	137
Issue number	1-2
DOIs	https://doi.org/10.1007/s10107-011-0499-2
State	Published - Feb 2013
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Keywords

68Q25 Analysis of algorithms & problem complexity
90C60 Abstract computational complexity for mathematical programming problems
Mathematics Subject Classification (2000): 90C25 Convex programming

Access to Document

10.1007/s10107-011-0499-2

Cite this

@article{2e111161d19341819e3b629df5ac43df,

title = "NP-hardness of deciding convexity of quartic polynomials and related problems",

abstract = "We show that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic polynomials. We also prove that deciding strict convexity, strong convexity, quasiconvexity, and pseudoconvexity of polynomials of even degree four or higher is strongly NP-hard. By contrast, we show that quasiconvexity and pseudoconvexity of odd degree polynomials can be decided in polynomial time.",

keywords = "68Q25 Analysis of algorithms & problem complexity, 90C60 Abstract computational complexity for mathematical programming problems, Mathematics Subject Classification (2000): 90C25 Convex programming",

author = "Ahmadi, {Amir Ali} and Alex Olshevsky and Parrilo, {Pablo A.} and Tsitsiklis, {John N.}",

year = "2013",

month = feb,

doi = "10.1007/s10107-011-0499-2",

language = "English (US)",

volume = "137",

pages = "453--476",

journal = "Mathematical Programming",

issn = "0025-5610",

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

number = "1-2",

}

TY - JOUR

T1 - NP-hardness of deciding convexity of quartic polynomials and related problems

AU - Ahmadi, Amir Ali

AU - Olshevsky, Alex

AU - Parrilo, Pablo A.

AU - Tsitsiklis, John N.

PY - 2013/2

Y1 - 2013/2

N2 - We show that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic polynomials. We also prove that deciding strict convexity, strong convexity, quasiconvexity, and pseudoconvexity of polynomials of even degree four or higher is strongly NP-hard. By contrast, we show that quasiconvexity and pseudoconvexity of odd degree polynomials can be decided in polynomial time.

AB - We show that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic polynomials. We also prove that deciding strict convexity, strong convexity, quasiconvexity, and pseudoconvexity of polynomials of even degree four or higher is strongly NP-hard. By contrast, we show that quasiconvexity and pseudoconvexity of odd degree polynomials can be decided in polynomial time.

KW - 68Q25 Analysis of algorithms & problem complexity

KW - 90C60 Abstract computational complexity for mathematical programming problems

KW - Mathematics Subject Classification (2000): 90C25 Convex programming

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

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

U2 - 10.1007/s10107-011-0499-2

DO - 10.1007/s10107-011-0499-2

M3 - Article

AN - SCOPUS:84878602784

SN - 0025-5610

VL - 137

SP - 453

EP - 476

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -

NP-hardness of deciding convexity of quartic polynomials and related problems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this