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

1 Introduction

• Shor’s 1992 question asks about quartic convexity, the first nontrivial degree because odd-degree convexity is trivial and quadratic convexity reduces to a positive-semidefinite matrix check.Convexity testing matters in global polynomial minimization and in searching over families of convex polynomials.Source: §1 · pp. 1–2
• Deciding convexity of degree-4 polynomials is strongly NP-hard, ruling out polynomial- or pseudo-polynomial-time algorithms unless P=NP.The authors also suggest that exact characterizations of convexity and its variants may therefore be inefficient to check for polynomials.Source: §1 · pp. 2–3
• The hardness results extend to strict convexity, strong convexity, quasiconvexity, and pseudoconvexity, each of which has stated uses in optimization or related applications.For example, quasiconvexity can certify convexity of feasible sets defined by polynomial inequalities, while pseudoconvexity ensures local minima are global.Source: §1 · p. 2

1.1 Related Literature

• Prior work establishes hardness for quartic and biquadratic nonnegativity, while Guo’s work on convexity over simplices does not prove NP-hardness.The paper also relates quartic-form convexity to nonnegativity of a special class of biquadratic forms.Source: §1.1 · p. 3
• SOS-convexity is a semidefinite-program-checkable sufficient condition for convexity, but some convex polynomials are not SOS-convex.The cited counterexample establishes that the sufficient condition does not capture every convex polynomial.Source: §1.1 · p. 4

1.2 Contributions and organization of the paper

• The paper organizes its degree-dependent complexity results across convexity, strict and strong convexity, and quasiconvexity and pseudoconvexity, including polynomial-time tests for odd-degree quasiconvexity and pseudoconvexity.Its main reduction proves quartic-form convexity hardness, which is extended to strict and strong convexity and to quasiconvexity and pseudoconvexity.Source: §1.2 · p. 4

2.1 Definitions and basics

• For computational complexity, polynomial inputs are represented by rational coefficients, and convexity is characterized by a positive semidefinite Hessian.The paper takes rational coefficients as integers after clearing denominators.Source: §2.1 · pp. 4–5

2.2 Degrees that are easy

• Convexity is easy to decide for odd-degree polynomials and quadratics, where it reduces to positive semidefiniteness of a constant matrix.Linear polynomials are convex, while polynomials of odd degree at least three cannot be convex; quadratic convexity is decidable in polynomial time.Source: §2.2 · p. 5

2.3 Degrees that are hard

• Deciding convexity of degree-four polynomials is strongly NP-hard, even when the polynomials are homogeneous.The result extends to every fixed even degree d ≥ 4.Source: §2.3 · pp. 5, 9
• A polynomial matrix need not be a valid Hessian, because mixed third partial derivatives of a polynomial must commute.The reduction addresses this constraint by constructing the polynomial whose Hessian carries the encoded matrix structure.Source: §2.3 · p. 6
• The reduction constructs a quartic form f from a biquadratic form b so that b is nonnegative if and only if f is convex.The construction embeds the relevant matrix structure into a valid Hessian and controls its off-diagonal terms.Source: §2.3 · pp. 6–7
• The same construction links sums of squares biquadratic forms to sos-convex quartic forms and explicitly yields convex quartics that are not sos-convex.The latter construction starts from a positive semidefinite biquadratic form that is not a sum of squares.Source: §2.3 · p. 9
• Hardness also applies to nonnegativity of a structured homogeneous quartic and to deciding convexity of basic closed semialgebraic sets with a degree-four defining polynomial.The first follows from an equivalence with convexity of a quartic; the second uses the epigraph of a quartic polynomial.Source: §2.3 · pp. 9–10

3.2 Degrees that are easy

• For quadratic polynomials, strict convexity and strong convexity are equivalent and can be decided in polynomial time.Strong convexity is equivalent to positive definiteness of the quadratic coefficient matrix.Source: §3.2 · pp. 10–11
• A quadratic polynomial that is not strongly convex cannot be strictly convex: a zero eigenvalue gives a direction along which its restriction is linear.A negative eigenvalue instead makes the polynomial nonconvex.Source: §3.2 · p. 11

3.3 Degrees that are hard

• Deciding strict or strong convexity is NP-hard for polynomials of every fixed even degree d ≥ 4.The reductions extend the quartic convexity hardness result to these properties.Source: §3.3 · p. 11

4.2 Degrees that are easy

• For quadratic polynomials, convexity, pseudoconvexity, and quasiconvexity are equivalent and can be decided in polynomial time.Source: §4.2 · p. 12

4.2.2 Pseudoconvexity of polynomials of odd degree

• For odd-degree polynomials, quasiconvexity requires a monotonic univariate polynomial in the representation, whereas pseudoconvexity requires its derivative to have no real roots.Source: §4.2.1 · p. 14, §4.2.2 · p. 15

4.2.1 Quasiconvexity of polynomials of odd degree

• For any fixed odd degree, quasiconvexity is polynomial-time decidable by testing whether p(x) has the form h(ξT x) for a monotonic univariate polynomial h.The representation uniquely determines ξ and h after normalizing the first nonzero component of ξ to one.Source: §4.2.1 · pp. 13–14

4.2.2 Pseudoconvexity of polynomials of odd degree

• For any fixed odd degree, pseudoconvexity is polynomial-time decidable when p(x) has a univariate representation whose derivative has no real roots.The algorithm modifies the quasiconvexity test to check this derivative condition.Source: §4.2.2 · p. 15

4.3 Degrees that are hard

• For homogeneous even-degree polynomials, convexity, pseudoconvexity, and quasiconvexity are equivalent, yielding NP-hardness for quasiconvexity and pseudoconvexity from degree four onward.The paper extends the hardness results to any fixed even degree d ≥4.Source: §4.3 · pp. 16–17

• Unless P=NP, testing the listed properties for even-degree polynomials of degree four or higher has no polynomial-time or pseudo-polynomial-time algorithm.Source: §5 · p. 17
• The paper asks whether other properties might retain attractive consequences of convexity while being easier to check.Source: §5 · p. 18
• The paper identifies semidefinite-programming relaxations, including sum-of-squares methods, as promising techniques for recognizing convexity, while noting the value of finding cases with exactness or performance guarantees.Source: §5 · p. 18