Optimization Online


NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems

Amir Ali Ahmadi(a_a_a***at***mit.edu)
Alex Olshevsky(alex_o***at***mit.edu)
Pablo A Parrilo(parrilo***at***mit.edu)
John N. Tsitsiklis(jnt***at***mit.edu)

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: convexity, complexity, NP-hard, quasiconvexity

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Global Optimization (Theory )

Citation: LIDS technical report 2855, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology.

Download: [PDF]

Entry Submitted: 12/12/2010
Entry Accepted: 12/12/2010
Entry Last Modified: 12/12/2010

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 Programming Society