Response to "Counterexample to global convergence of DSOS and SDSOS hierarchies"

Amir Ali Ahmadi, Anirudha MajumdararXiv 2017 · arXiv

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

Abstract

In a recent note [8], the author provides a counterexample to the global convergence of what his work refers to as "the DSOS and SDSOS hierarchies" for polynomial optimization problems (POPs) and purports that this refutes claims in our extended abstract [4] and slides in [3]. The goal of this paper is to clarify that neither [4], nor [3], and certainly not our full paper [5], ever defined DSOS or SDSOS hierarchies as it is done in [8]. It goes without saying that no claims about convergence properties of the hierarchies in [8] were ever made as a consequence. What was stated in [4,3] was completely different: we stated that there exist hierarchies based on DSOS and SDSOS optimization that converge. This is indeed true as we discuss in this response. We also emphasize that we were well aware that some (S)DSOS hierarchies do not converge even if their natural SOS counterparts do. This is readily implied by an example in our prior work [5], which makes the counterexample in [8] superfluous. Finally, we provide concrete counterarguments to claims made in [8] that aim to challenge the scalability improvements obtained by DSOS and SDSOS optimization as compared to sum of squares (SOS) optimization. [3] A. A. Ahmadi and A. Majumdar. DSOS and SDSOS: More tractable alternatives to SOS. Slides at the meeting on Geometry and Algebra of Linear Matrix Inequalities, CIRM, Marseille, 2013. [4] A. A. Ahmadi and A. Majumdar. DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization. In proceedings of the 48th annual IEEE Conference on Information Sciences and Systems, 2014. [5] A. A. Ahmadi and A. Majumdar. DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization. arXiv:1706.02586, 2017. [8] C. Josz. Counterexample to global convergence of DSOS and SDSOS hierarchies. arXiv:1707.02964, 2017.
BibTeX
@misc{ahmadi2017response,
  author = {Amir Ali Ahmadi and Anirudha Majumdar},
  title = {{Response to "Counterexample to global convergence of DSOS and SDSOS hierarchies"}},
  year = {2017},
  eprint = {1710.02901},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1710.02901},
}
Figure