TL;DR
This paper tackles the question of whether a polynomial being convex is equivalent to it being "sos-convex" (a computationally tractable condition related to sums of squares). The authors provide the first explicit counterexample: a specific polynomial that is convex but demonstrably not sos-convex, settling a long-standing open question. This finding has implications for optimization and algebraic geometry, suggesting that convexity of polynomials is a more complex property than previously assumed.
What Problem Does This Paper Address?
In applied mathematics and optimization, determining if a polynomial is convex is crucial. Convexity guarantees that local minima are global minima, simplifying optimization problems. While a sufficient condition for convexity is that the polynomial's Hessian matrix is positive semidefinite (PSD), a computationally tractable relaxation called "sos-convexity" has emerged. A polynomial is sos-convex if its Hessian can be expressed as a sum of squares of polynomial matrices. This condition is attractive because checking it can be reduced to solving a semidefinite program (SDP), a well-studied class of convex optimization problems solvable efficiently.
The core question this paper addresses is whether sos-convexity is not just a sufficient but also a necessary condition for a polynomial to be convex. In other words, can a polynomial be convex without its Hessian being sos-convex? While many believed this might be the case due to the structural properties of Hessians, no explicit counterexample had been found, making it difficult to definitively answer this question. This paper aims to resolve this by providing the first concrete example of a convex polynomial that fails the sos-convexity test.
Methods
The authors leverage the power of sum of squares (sos) programming and semidefinite programming (SDP) duality. The key idea is to search for a polynomial that satisfies the definition of convexity (its Hessian is PSD) but fails the sos-convexity criterion.
- Sos-Convexity Definition: A polynomial $p(x)$ is sos-convex if its Hessian matrix $H(x)$ is an "sos-matrix." An sos-matrix is a symmetric polynomial matrix that can be factored as $M(x)^T M(x)$ for some polynomial matrix $M(x)$. This is equivalent to checking if $y^T H(x) y$ is a sum of squares in the polynomial ring $R[x; y]$.
- SDP Formulation: Checking if a polynomial is an sos-matrix can be formulated as an SDP feasibility problem. This allows for efficient computational analysis.
- Duality for Counterexample Search: The paper's main contribution lies in using the duality theory of SDPs. If a polynomial (or in this case, a component of the Hessian) is not an sos-polynomial, there exists a "dual functional" that can separate it from the cone of sos-polynomials. The authors construct a specific dual functional that, when applied to a component of the Hessian, yields a negative value, proving that this component is not an sos-polynomial.
- Constructing the Counterexample: The search for the counterexample involves formulating an sos-program. This program parameterizes a polynomial $p(x)$, computes its Hessian $H(x)$, and imposes two main constraints:
- $(x_1^2+x_2^2+x_3^2)^r y^T H(x) y$ is sos (for a suitable $r$, ensuring $H(x)$ is PSD).
- A specific principal minor of $H(x)$ (namely $H_{1,1}(x)$) is separated from the cone of sos-polynomials by a carefully chosen dual functional.
- Computational Tools: The authors utilized software packages like SOSTOOLS and the SDP solver SeDuMi to find the explicit coefficients of the counterexample polynomial and its Hessian.
Datasets
Not discussed in the paper. The paper focuses on theoretical construction and computational search for a mathematical object (a polynomial), rather than empirical evaluation on datasets.
Key Insights and Ideas
- Convexity vs. Sos-Convexity is Not Equivalent: The most significant insight is the definitive proof that a polynomial can be convex without being sos-convex. This settles a question that had been open for some time and challenges the intuition that the computationally tractable sos-convexity condition might fully capture polynomial convexity.
- The Power of SDP Duality for Counterexample Construction: The paper elegantly demonstrates how the duality theory of SDPs can be used not just for optimization but also for proving non-existence or finding counterexamples. The concept of a separating hyperplane (dual functional) is crucial here.
- Hessian Structure is Not Enough: While Hessians have a special structure (being symmetric and related to second derivatives), this structure alone does not guarantee that a PSD Hessian is an sos-matrix. The paper's counterexample highlights this gap.
- Computational Search Guided by Theory: The authors successfully combined theoretical insights (SDP duality, Reznick's theorem) with computational tools (sos programming solvers) to discover their counterexample. This showcases a powerful paradigm for mathematical discovery.
Key Results
The paper's primary result is Theorem 3.2, which states the existence of a polynomial that is convex but not sos-convex. Specifically, they provide an explicit example of a trivariate homogeneous polynomial of degree 8:
$p(x) = 32x_1^8 + 118x_1^6x_2^2 + 40x_1^6x_3^2 + 25x_1^4x_2^4 - 43x_1^4x_2^2x_3^2 - 35x_1^4x_3^4 + 3x_1^2x_2^6 - 16x_1^2x_2^4x_3^2 + 24x_1^2x_2^2x_3^4 + 16x_1^2x_3^6 + 44x_2^8 + 70x_2^6x_3^2 + 60x_2^4x_3^4 + 30x_2^2x_3^6$
They prove that this polynomial is convex (its Hessian is PSD) but not sos-convex by showing that a specific principal minor of its Hessian ($H_{1,1}(x)$) is not an sos-polynomial. The paper also provides the explicit rational SOS decomposition of the Hessian of this polynomial, which is a significant computational result in itself.
Limitations and Future Work
- Minimality of the Counterexample: The authors note that their example is a trivariate form of degree 8. They suggest that a dehomogenized version in two variables is also convex but not sos-convex. They do not know if an example with a lower degree exists, but they state that a bivariate form of degree 4 cannot be convex but not sos-convex.
- Homogenization and Sos-Convexity: They point out that sos-convexity is not necessarily preserved under homogenization, providing an example where a dehomogenized polynomial is sos-convex, but its homogenized version is not.
- Future Work: The methodology used to find this counterexample can be employed to search for other instances of polynomials that are PSD but not sos, or to optimize over restricted families of polynomials. The paper also suggests that further research could clarify the relationships between geometric and algebraic aspects of positivity and convexity. The existence of such counterexamples might imply that testing for polynomial convexity is indeed a hard problem, as initially suspected.
Summary updated