Introduction
In the field of polynomial optimization, Sum of Squares (SOS) programming has long been the standard for finding global bounds. However, SOS relies on Semidefinite Programming (SDP), which suffers from poor scalability as the number of variables or the degree of the polynomials increases. To mitigate this, Diagonally Dominant (DSOS) and Scaled Diagonally Dominant (SDSOS) polynomials were introduced as more tractable alternatives. These frameworks replace computationally expensive SDP constraints with significantly cheaper Linear Programming (LP) and Second-Order Cone Programming (SOCP) constraints, respectively.
This paper serves as a formal rebuttal to a recent critique that claimed to provide a "counterexample" to the global convergence of DSOS and SDSOS hierarchies. Additionally, the critique argued that these hierarchies are not more tractable than SOS because their constraint count allegedly grows exponentially. This response clarifies the mathematical record, refutes the claim of exponential growth, and re-establishes the practical utility of the (S)DSOS framework.
Clarifying Convergence Claims
A primary point of the critique was the demonstration that naive substitutions of DSOS or SDSOS constraints into standard SOS hierarchies (such as the Lasserre hierarchy) do not necessarily converge to the global optimum. The authors clarify that this is a "strawman" argument; they never claimed that such naive substitutions would be globally convergent in their original 2017 paper or associated presentations.
In fact, the authors had previously published a simple three-variable polynomial example demonstrating this lack of convergence for naive hierarchies, making the critic's new counterexample redundant. The authors maintain that while naive hierarchies may fail, convergent (S)DSOS hierarchies do exist. For instance, by taking existing LP-based hierarchies that are known to be globally convergent and replacing their search over nonnegative scalars with DSOS polynomials, the resulting hierarchy inherits global convergence properties.
Complexity Analysis and Tractability
The second major claim addressed is the assertion that the number of constraints in the dual SDSOS hierarchy grows exponentially, thereby negating its computational advantages. Through a rigorous complexity analysis, the authors prove this claim to be mathematically incorrect.
For a polynomial in $n$ variables of degree $2d$ at hierarchy level $r$, the number of SOCP constraints is shown to be $O(N^2)$, where $N = \binom{n+d+r}{n}$. Specifically, the growth is $O((n + d + r)^{2n})$. Since the number of variables $n$ is fixed for a given optimization problem, the growth of constraints with respect to the hierarchy order $r$ is strictly polynomial, not exponential.
This result reinforces the core value proposition of (S)DSOS: by replacing a single massive $N \times N$ positive semidefinite constraint with $\binom{N}{2}$ smaller, cheaper SOCP constraints, practitioners can achieve orders-of-magnitude speedups. This scalability is essential for high-dimensional problems, such as the control of humanoid robots with 30-dimensional state spaces, where even the first level of a standard SOS hierarchy is computationally prohibitive.
Limitations and Practical Utility
The authors acknowledge that (S)DSOS optimization is inherently more conservative than SOS optimization, meaning it may yield looser bounds. Furthermore, they note a broader limitation in the field: while globally convergent hierarchies are theoretically significant, they often lack concrete, practical bounds on their convergence rates, limiting their immediate utility for practitioners.
However, the (S)DSOS framework remains a powerful tool for large-scale problems where SOS is inapplicable. Future research should focus on:
- Exploiting Structure: Combining (S)DSOS with techniques that leverage problem sparsity or symmetry.
- Iterative Algorithms: Developing methods to mitigate the conservatism of the bounds through iterative refinement.
Conclusion
By correcting the mathematical misconceptions regarding convergence and complexity, this response reaffirms that DSOS and SDSOS hierarchies are highly tractable and scalable alternatives to SOS. They remain a vital component of the optimization toolkit for addressing massive, high-dimensional polynomial problems that lie beyond the reach of traditional semidefinite programming.
Summary updated