Convex optimization is the foundational engine of modern machine learning and control systems. As highlighted in Convex optimization for the design of learning machines by Johan Suykens et al., framing an optimization problem as convex provides a powerful guarantee: any local minimum is automatically a global minimum. This property allows practitioners to bypass brittle, ad-hoc heuristics and deploy robust numerical solvers with confidence.
However, this paradigm relies on a critical, often unstated assumption: we must be able to verify that our objective function is actually convex. For linear and quadratic functions, this verification is trivial, reducing to checking whether a constant matrix is positive semidefinite. But as soon as we move to higher-degree polynomials or more complex non-linear functions, we hit a sharp computational wall. Verifying convexity is not just difficult; it is fundamentally intractable.
Why Degree Four Changes Everything
To build intuition for why this problem is so hard, consider the classical calculus definition of convexity. A twice-differentiable function is convex if and only if its Hessian matrix—the matrix of second-order partial derivatives—is positive semidefinite (PSD) across its entire domain.
When we analyze a polynomial of degree four (a quartic polynomial), its Hessian matrix contains entries that are quadratic polynomials. To prove that this function is convex, we must show that for every possible input vector $x$, the quadratic form $v^T H(x) v$ is non-negative for all vectors $v$. Because $H(x)$ depends quadratically on $x$, the expression $v^T H(x) v$ is a multivariate polynomial of degree four.
This reveals a deep connection between convexity and the classic mathematical challenge of proving polynomial non-negativity. In NP-hardness of deciding convexity of quartic polynomials and related problems, Amir Ali Ahmadi et al. proved that deciding the global convexity of a quartic polynomial is strongly NP-hard. This means that even if the polynomial has small integer coefficients, no pseudo-polynomial time algorithm can reliably verify its convexity. The "convexity watershed" is absolute: quadratics are computationally effortless, but quartics are blind to general verification.
The Gap Between Geometry and Algebra
Since exact verification is impossible for general high-degree functions, how do optimization frameworks proceed? The standard workaround is to replace the strict geometric requirement of non-negativity with a more tractable algebraic surrogate: the Sum of Squares (SOS) condition. If a polynomial can be written as a sum of squared polynomials, it is obviously non-negative everywhere. When applied to the Hessian, this tractability condition is known as SOS-convexity, and it can be efficiently checked using semidefinite programming (SDP).
In On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials, Amir Ali Ahmadi et al. analyzed various algebraic relaxations for polynomial convexity, demonstrating that the Hessian-based SOS approach is mathematically equivalent to other definitions and vastly superior in computational efficiency.
Yet, a critical question remained: does SOS-convexity perfectly capture all convex polynomials, or do we lose something in translation? The authors answered this in A convex polynomial that is not sos-convex, providing the first explicit counterexample of a polynomial that is globally convex but demonstrably not SOS-convex. This gap was fully mapped out in A complete characterization of the gap between convexity and SOS-Convexity by Amir Ali Ahmadi et al., who showed that the equivalence between convexity and SOS-convexity holds only in a very narrow set of dimensions and degrees. This mirrors Hilbert's famous 17th problem regarding the gap between non-negative polynomials and sums of squares, proving that algebraic relaxations will always leave a blind spot of valid convex functions that they cannot certify.
The Ripple Effect Across Optimization and Learning
The computational barrier of convexity verification is not an isolated theoretical curiosity; it imposes strict limits across multiple areas of optimization and machine learning:
- Higher-Order Local Optimality: In non-convex optimization, escaping saddle points is essential. While modern algorithms can efficiently find third-order local optima, Animashree Anandkumar et al. showed in Efficient approaches for escaping higher order saddle points in non-convex optimization that verifying a fourth-order local optimum is NP-hard. The mathematical bottleneck is identical: it requires verifying the non-negativity of a degree-four polynomial.
- Automated Regularizer Design: In online linear optimization, achieving optimal regret bounds depends on selecting a regularizer that satisfies strict strong convexity requirements. In Computing Optimal Regularizers for Online Linear Optimization, Jon Schneider et al. proved that verifying whether a candidate regularizer is sufficiently strongly convex for a specific problem geometry is NP-hard, explaining why automated algorithm design in this space is so difficult.
- Convexification and Constraints: When dealing with complex constraints, researchers often try to find the tightest convex lower bounds. In Convexification of Learning from Constraints, Bjoern Andres et al. noted that calculating the tightest convex extension via the Legendre-Fenchel biconjugate is NP-hard. Similarly, in A Numerical Method for Variational Problems with Convexity Constraints, Adam Oberman highlighted that enforcing exact convexity constraints is computationally intractable due to the lack of a clean mathematical characterization of the cone of convex functions, necessitating polyhedral cone approximations. To avoid these NP-hard subproblems in computer vision, Hossam Isack et al. introduced a more flexible, overlapping $k$-convexity shape prior in K-convexity Shape Priors for Segmentation.
Bypassing the Barrier with Symbolic and Geometric Tools
How do we build practical systems in the face of these theoretical limits? The answer lies in trading off absolute generality for structured, automated verification.
In robotics and computer graphics, Amir Ali Ahmadi et al. demonstrated in Geometry of 3D Environments and Sum of Squares Polynomials that sublevel sets of SOS polynomials can be used to construct certifiably convex bounding volumes for complex 3D shapes, enabling millisecond-level collision resolution via semidefinite programming.
Meanwhile, in software optimization, tools traditionally rely on Disciplined Convex Programming (DCP) to verify convexity via a strict library of composition rules. To expand the scope of what can be verified automatically, Julien Klaus et al. introduced a new paradigm in Convexity Certificates from Hessians. By performing automated symbolic analysis directly on a function's Hessian matrix, their approach can certify convexity for a much wider class of differentiable machine learning models without requiring manual hints. While the general problem remains NP-hard, these structural and symbolic tools allow us to push the boundaries of what is practically verifiable.
Key Foundational Work
Convex optimization for the design of learning machines (2007) — contributed 1 concept elements to this direction.
On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials (2010) — contributed 1 concept elements to this direction.