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

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

Introduction

In the field of mathematical optimization, convexity is often described as the "holy grail." When a problem is convex, local minima are guaranteed to be global minima, and efficient algorithms like gradient descent or interior-point methods can reliably find optimal solutions. However, a fundamental computational question has persisted: how difficult is it to determine if a given function is actually convex?

While the answer is trivial for linear functions and computationally simple for quadratic functions, higher-degree polynomials present a significant challenge. This paper addresses a long-standing open question posed by N.Z. Shor in 1992 regarding the complexity of determining the convexity of degree-four (quartic) polynomials. The authors provide a definitive answer, proving that this task is "strongly NP-hard."

The Complexity Landscape

To understand the significance of this result, one must look at the hierarchy of polynomial degrees:

  • Degree 1 (Linear): Always convex; checking is trivial.
  • Degree 2 (Quadratic): Convexity depends on whether the Hessian (a constant matrix of second derivatives) is positive semidefinite (PSD). This can be checked in polynomial time.
  • Odd Degrees (3, 5, etc.): A non-constant polynomial of odd degree cannot be globally convex, as it necessarily tends toward negative infinity in at least one direction.
  • Degree 4 (Quartic): This is the first non-trivial case where global convexity is possible but not guaranteed. The Hessian of a quartic polynomial is a matrix whose entries are quadratic polynomials, making the verification of the PSD condition significantly more complex.

Methodology: The "Valid Hessian" Challenge

The authors prove NP-hardness through a reduction from the problem of deciding the nonnegativity of biquadratic forms. A biquadratic form $b(x;y)$ is a specific quartic polynomial that is quadratic in two separate sets of variables.

The core mathematical difficulty in this reduction is that not every matrix of polynomials is a valid Hessian. A Hessian matrix must satisfy the symmetry of mixed partial derivatives (e.g., the derivative with respect to $x$ then $y$ must equal the derivative with respect to $y$ then $x$). The authors' breakthrough involves an "embedding" technique that constructs a specific quartic polynomial $f(x,y)$ such that its Hessian encodes the biquadratic form while adhering to the structural constraints required of a second-derivative matrix.

Furthermore, by proving strong NP-hardness, the authors demonstrate that the problem remains intractable even if the coefficients of the polynomial are restricted to small integers, ruling out the existence of pseudo-polynomial time algorithms.

Key Results and Taxonomy

The paper provides a comprehensive classification of the complexity involved in deciding convexity and its variants across different polynomial degrees:

Property Degree 1 Degree 2 Odd Degree $\ge 3$ Even Degree $\ge 4$
Convexity Trivial (Yes) Polynomial (P) Trivial (No) Strongly NP-hard
Strict/Strong Convexity Trivial (No) Polynomial (P) Trivial (No) Strongly NP-hard
Quasiconvexity Trivial (Yes) Polynomial (P) Polynomial (P) Strongly NP-hard
Pseudoconvexity Trivial (Yes) Polynomial (P) Polynomial (P) Strongly NP-hard

Key Theoretical Findings:

  • Theorem 2.1: Deciding the convexity of quartic polynomials is strongly NP-hard.
  • Odd-Degree Quasiconvexity: While convexity is impossible for odd degrees, checking quasiconvexity (whether the sublevel sets are convex) is actually solvable in polynomial time. The authors show that odd-degree quasiconvex polynomials have a very restricted structure, essentially acting as monotonic univariate polynomials.
  • Homogeneity: For homogeneous polynomials (where all terms have the same degree), the paper proves that convexity, pseudoconvexity, and quasiconvexity are all equivalent and remain NP-hard to verify.

Implications and Practical Alternatives

The proof that checking convexity is NP-hard implies that there is no general-purpose, efficient algorithm to certify convexity for all quartic polynomials. This has significant implications for automated optimization modeling and control theory.

However, the authors highlight a tractable alternative: Sum of Squares (SOS) convexity. While not every convex polynomial is SOS-convex, SOS-convexity is a sufficient condition that can be verified efficiently using Semidefinite Programming (SDP). For many practical applications in robotics and engineering, SOS-convexity serves as a powerful proxy for global convexity.

Future research may focus on identifying specific subclasses of polynomials relevant to industry that bypass these hardness results or developing better approximation algorithms to certify convexity in near-optimal time.

Summary updated

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.
BibTeX
@article{ahmadi2013np,
  author = {Amir Ali Ahmadi and Alexander Olshevsky and Pablo A. Parrilo and John N. Tsitsiklis},
  title = {{NP-hardness of deciding convexity of quartic polynomials and related problems}},
  journal = {Math. Program.},
  year = {2013},
  doi = {10.1007/s10107-011-0499-2},
}
Figure