# Sparse Polynomial Optimization: Theory and Practice

arXiv: https://arxiv.org/abs/2208.11158 · HTML: https://mlsanity.com/paper/2208.11158/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 38 of its 191 references that are in the map.
- First posted on arXiv 23 Aug 2022.

## Builds on (most cited first, 30 of 38)

- [Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach](https://mlsanity.com/paper/1801.10578/) (2018)
- [The Power Grid Library for Benchmarking AC Optimal Power Flow Algorithms](https://mlsanity.com/paper/1908.02788/) (2019)
- [JuMP: A Modeling Language for Mathematical Optimization](https://mlsanity.com/paper/1508.01982/) (2015)
- [Limitations of the Lipschitz constant as a defense against adversarial examples](https://mlsanity.com/paper/1807.09705/) (2018)
- [One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers](https://mlsanity.com/paper/2006.06769/) (2020)
- [Semialgebraic Representation of Monotone Deep Equilibrium Models and Applications to Certification](https://mlsanity.com/paper/2106.01453/) (2021)
- [Evaluating Robustness of Neural Networks with Mixed Integer Programming](https://mlsanity.com/paper/1711.07356/) (2017)
- [TSSOS: A Moment-SOS hierarchy that exploits term sparsity](https://mlsanity.com/paper/1912.08899/) (2019)
- [Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension](https://mlsanity.com/paper/2003.03210/) (2020)
- [Sparse Polynomial Optimisation for Neural Network Verification](https://mlsanity.com/paper/2202.02241/) (2022)
- [CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization](https://mlsanity.com/paper/2005.02828/) (2020)
- [On Sound Compilation of Reals](https://mlsanity.com/paper/1309.2511/) (2013)
- [Mathematical Programming formulations for the Alternating Current Optimal Power Flow problem](https://mlsanity.com/paper/2007.05334/) (2020)
- [A hierarchy of spectral relaxations for polynomial optimization](https://mlsanity.com/paper/2007.09027/) (2020)
- [Lasserre hierarchy for large scale polynomial optimization in real and complex variables](https://mlsanity.com/paper/1709.04376/) (2017)
- [A Sublevel Moment-SOS Hierarchy for Polynomial Optimization](https://mlsanity.com/paper/2101.05167/) (2021)
- [Optimal Power Flow as a Polynomial Optimization Problem](https://mlsanity.com/paper/1404.3626/) (2014)
- [A second order cone characterization for sums of nonnegative circuits](https://mlsanity.com/paper/1906.06179/) (2019)
- [SparseJSR: A Fast Algorithm to Compute Joint Spectral Radius via Sparse SOS Decompositions](https://mlsanity.com/paper/2008.11441/) (2020)
- [Exploiting term sparsity in Noncommutative Polynomial Optimization](https://mlsanity.com/paper/2010.06956/) (2020)
- [SONC Optimization and Exact Nonnegativity Certificates via Second-Order Cone Programming](https://mlsanity.com/paper/2012.07903/) (2020)
- [Exploiting Sparsity in Complex Polynomial Optimization](https://mlsanity.com/paper/2103.12444/) (2021)
- [Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients](https://mlsanity.com/paper/2107.11825/) (2021)
- [A semidefinite programming hierarchy for packing problems in discrete geometry](https://mlsanity.com/paper/1311.3789/) (2013)
- [Moment/Sum-of-Squares Hierarchy for Complex Polynomial Optimization](https://mlsanity.com/paper/1508.02068/) (2015)
- [New upper bounds for the density of translative packings of three-dimensional convex bodies with tetrahedral symmetry](https://mlsanity.com/paper/1510.02331/) (2015)
- [On the Robustness and Scalability of Semidefinite Relaxation for Optimal Power Flow Problems](https://mlsanity.com/paper/1806.08620/) (2018)
- [An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization](https://mlsanity.com/paper/1808.08431/) (2018)
- [A New Sparse SOS Decomposition Algorithm Based on Term Sparsity](https://mlsanity.com/paper/1809.10848/) (2018)
- [A unified framework of SAGE and SONC polynomials and its duality theory](https://mlsanity.com/paper/1903.08966/) (2019)

## Abstract (arXiv)

The problem of minimizing a polynomial over a set of polynomial inequalities is an NP-hard non-convex problem. Thanks to powerful results from real algebraic geometry, one can convert this problem into a nested sequence of finite-dimensional convex problems. At each step of the associated hierarchy, one needs to solve a fixed size semidefinite program, which can be in turn solved with efficient numerical tools. On the practical side however, there is no-free lunch and such optimization methods usually encompass severe scalability issues. Fortunately, for many applications, we can look at the problem in the eyes and exploit the inherent data structure arising from the cost and constraints describing the problem, for instance sparsity or symmetries. This book presents several research efforts to tackle this scientific challenge with important computational implications, and provides the development of alternative optimization schemes that scale well in terms of computational complexity, at least in some identified class of problems. The presented algorithmic framework in this book mainly exploits the sparsity structure of the input data to solve large-scale polynomial optimization problems. We present sparsity-exploiting hierarchies of relaxations, for either unconstrained or constrained problems. By contrast with the dense hierarchies, they provide faster approximation of the solution in practice but also come with the same theoretical convergence guarantees. Our framework is not restricted to static polynomial optimization, and we expose hierarchies of approximations for values of interest arising from the analysis of dynamical systems. We also present various extensions to problems involving noncommuting variables, e.g., matrices of arbitrary size or quantum physic operators.