TL;DR
This paper completely characterizes when convex polynomials are also "SOS-convex" (a computationally tractable sufficient condition for convexity). They prove that this equivalence holds precisely in the same cases where non-negative polynomials are sums of squares, a classic result by Hilbert. This provides a fundamental link between geometric and algebraic properties of polynomials.
What Problem Does This Paper Address?
In mathematics and engineering, we often deal with polynomials. Two key properties are convexity and non-negativity. Convexity is crucial for optimization problems, as it guarantees that any local minimum is also a global minimum. Non-negativity is important in various applications, from control theory to signal processing.
A major challenge is that checking if a general polynomial is convex is computationally hard (NP-hard). Similarly, determining if a polynomial is non-negative is also NP-hard for degrees four and higher.
To overcome this, mathematicians have developed "SOS relaxations." SOS (sum of squares) means a polynomial can be written as a sum of squares of other polynomials. While not all non-negative polynomials are SOS, all SOS polynomials are non-negative. Crucially, checking if a polynomial is SOS can be done efficiently using semidefinite programming (SDP).
This paper focuses on a similar relaxation for convexity called SOS-convexity. A polynomial is SOS-convex if its Hessian matrix (a matrix of its second derivatives) is an SOS-matrix. SOS-convexity is a sufficient condition for convexity, and it's computationally tractable. The core problem this paper addresses is: When does this computationally tractable condition (SOS-convexity) perfectly capture the true geometric property of convexity for polynomials?
Methods
The authors establish three equivalent algebraic conditions for SOS-convexity, all of which can be checked via SDP. These are:
- A specific polynomial related to the first-order definition of convexity being SOS.
- A specific polynomial related to the second-order definition of convexity (involving the gradient) being SOS.
- The Hessian matrix of the polynomial being an SOS-matrix (the original definition of SOS-convexity).
They then systematically investigate the equivalence between true convexity and SOS-convexity for polynomials and homogeneous polynomials (forms) across different numbers of variables ($n$) and degrees ($d$). This involves:
- Algebraic manipulation and limit arguments: To show the equivalence of the three SOS-convexity conditions.
- The "biform theorem": A key result stating that certain quadratic forms in two sets of variables are positive semidefinite if and only if they are SOS. This is crucial for proving equivalence in specific cases (like bivariate polynomials).
- Explicit construction of counterexamples: For cases where convexity and SOS-convexity do not align, the authors construct minimal examples of convex polynomials that are not SOS-convex. This is a significant part of their contribution, as finding such examples is non-trivial.
- Symmetry arguments and dehomogenization: Techniques used to simplify proofs and relate results for polynomials to results for forms.
Datasets
Not discussed in the paper. The paper deals with theoretical properties of polynomials and does not rely on empirical datasets.
Key Insights and Ideas
- The gap mirrors Hilbert's result: The most striking insight is that the conditions under which convexity is equivalent to SOS-convexity are exactly the same as the conditions under which non-negativity is equivalent to sum of squares. This suggests a deep, unifying principle.
- SOS-convexity is a good relaxation: While not always equivalent to convexity, SOS-convexity is a strong sufficient condition that is computationally feasible.
- Minimal counterexamples are key: Finding the smallest (in terms of degree and number of variables) convex polynomials that are not SOS-convex was a major challenge and a significant part of the paper's contribution. These examples are crucial for proving that the equivalence does not hold universally.
- Hessian-based condition is efficient: The paper highlights that the SOS-convexity condition based on the Hessian matrix is computationally more efficient due to its structure.
Key Results
The paper provides a complete characterization of when convexity and SOS-convexity are equivalent:
- For general polynomials: $C_{n,d} = \tilde{C}_{n,d}$ (convexity equals SOS-convexity) if and only if $n=1$ or $d=2$ or $(n,d)=(2,4)$.
- For homogeneous polynomials (forms): $\Sigma C_{n,d} = \tilde{C}_{n,d}$ if and only if $n=2$ or $d=2$ or $(n,d)=(3,4)$.
The paper also presents explicit examples of convex polynomials/forms that are not SOS-convex for cases outside these equivalences, such as polynomials in $C_{2,6} \setminus \tilde{C}_{2,6}$ and forms in $C_{3,6} \setminus \Sigma C_{3,6}$.
Limitations and Future Work
- Homogenization/Dehomogenization: Unlike the non-negativity/SOS case, convexity and SOS-convexity do not always behave nicely under homogenization. This means results for polynomials and forms are not always directly interchangeable, requiring separate treatments.
- Direct argument for $C_{n,d} = \tilde{C}_{n,d}$ equivalence: The authors pose an open problem: can one find a direct argument proving that $C_{n,d} = \tilde{C}_{n,d}$ if and only if $C_{n+1,d} = \tilde{C}_{n+1,d}$? This would simplify proofs, especially for the $(3,4)$ case.
- Convex forms that are not SOS: The paper mentions that while convex forms that are not SOS-convex exist, finding a convex form that is not a sum of squares remains an open problem. This is a more fundamental question about the relationship between geometric and algebraic properties.
- Optimization implications: The existence of convex polynomials that are not SOS-convex implies that SOS relaxations for minimizing polynomials are not always exact, even for convex functions. This is an important consideration for practical optimization.
Summary updated