# Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 72 references that are in the map.
- First posted on arXiv 13 Sep 2022.

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

- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [JuMP 1.0: Recent improvements to a modeling language for mathematical optimization](https://mlsanity.com/paper/2206.03866/) (2022)
- [DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization](https://mlsanity.com/paper/1706.02586/) (2017)
- [Semialgebraic Representation of Monotone Deep Equilibrium Models and Applications to Certification](https://mlsanity.com/paper/2106.01453/) (2021)
- [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)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity](https://mlsanity.com/paper/1607.01151/) (2016)
- [A bounded degree SOS hierarchy for polynomial optimization](https://mlsanity.com/paper/1501.06126/) (2015)
- [CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization](https://mlsanity.com/paper/2005.02828/) (2020)
- [l2 Induced Norm Analysis of Discrete-Time LTI Systems for Nonnegative Input Signals and Its Application to Stability Analysis of Recurrent Neural Networks](https://mlsanity.com/paper/2011.12726/) (2020)
- [A hierarchy of spectral relaxations for polynomial optimization](https://mlsanity.com/paper/2007.09027/) (2020)
- [A Sublevel Moment-SOS Hierarchy for Polynomial Optimization](https://mlsanity.com/paper/2101.05167/) (2021)
- [Sum-of-squares optimization without semidefinite programming](https://mlsanity.com/paper/1712.01792/) (2017)
- [A second order cone characterization for sums of nonnegative circuits](https://mlsanity.com/paper/1906.06179/) (2019)
- [Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization](https://mlsanity.com/paper/1911.12859/) (2019)
- [Converging outer approximations to global attractors using semidefinite programming](https://mlsanity.com/paper/2005.03346/) (2020)
- [SONC Optimization and Exact Nonnegativity Certificates via Second-Order Cone Programming](https://mlsanity.com/paper/2012.07903/) (2020)
- [Exploiting constant trace property in large-scale polynomial optimization](https://mlsanity.com/paper/2012.08873/) (2020)
- [Sparse non-SOS Putinar-type Positivstellens"atze](https://mlsanity.com/paper/2110.10079/) (2021)
- [An Approach to Constrained Polynomial Optimization via Nonnegative Circuit Polynomials and Geometric Programming](https://mlsanity.com/paper/1602.06180/) (2016)
- [A Positivstellensatz for Sums of Nonnegative Circuit Polynomials](https://mlsanity.com/paper/1607.06010/) (2016)
- [Exploiting Sparsity for Semi-Algebraic Set Volume Computation](https://mlsanity.com/paper/1902.02976/) (2019)
- [Inner approximations of the maximal positively invariant set for polynomial dynamical systems](https://mlsanity.com/paper/1903.04798/) (2019)
- [Signomial and Polynomial Optimization via Relative Entropy and Partial Dualization](https://mlsanity.com/paper/1907.00814/) (2019)
- [Approximating regions of attraction of a sparse polynomial differential system *](https://mlsanity.com/paper/1911.09500/) (2019)
- [Positivity certificates and polynomial optimization on non-compact semialgebraic sets](https://mlsanity.com/paper/1911.11428/) (2019)
- [On sums of squares of k-nomials](https://mlsanity.com/paper/1912.01371/) (2019)
- [Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software](https://mlsanity.com/paper/2001.11348/) (2020)
- [On the complexity of Putinar-Vasilescu's Positivstellensatz](https://mlsanity.com/paper/2104.11606/) (2021)

## Abstract (arXiv)

We consider polynomial optimization problems (POP) on a semialgebraic set contained in the nonnegative orthant (every POP on a compact set can be put in this format by a simple translation of the origin). Such a POP can be converted to an equivalent POP by squaring each variable. Using even symmetry and the concept of factor width, we propose a hierarchy of semidefinite relaxations based on the extension of P'olya's Positivstellensatz by Dickinson-Povh. As its distinguishing and crucial feature, the maximal matrix size of each resulting semidefinite relaxation can be chosen arbitrarily and in addition, we prove that the sequence of values returned by the new hierarchy converges to the optimal value of the original POP at the rate O(varepsilon-c) if the semialgebraic set has nonempty interior. When applied to (i) robustness certification of multi-layer neural networks and (ii) computation of positive maximal singular values, our method based on P'olya's Positivstellensatz provides better bounds and runs several hundred times faster than the standard Moment-SOS hierarchy.