# Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2016.

## Built on by (most cited first, 8 of 8)

- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [On the Tightness of Semidefinite Relaxations for Rotation Estimation](https://mlsanity.com/paper/2101.02099/) (2021)
- [SoS1: O1 and R1-Like Reasoning LLMs are Sum-of-Square Solvers](https://mlsanity.com/paper/2502.20545/) (2025)
- [Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields](https://mlsanity.com/paper/2107.06028/) (2021)
- [A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy](https://mlsanity.com/paper/2102.08019/) (2021)
- [Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part I: Definitions & Basic Properties](https://mlsanity.com/paper/2208.03622/) (2022)
- [Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part II: Theoretical & Computational Results](https://mlsanity.com/paper/2208.03625/) (2022)
- [Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant](https://mlsanity.com/paper/2209.06175/) (2022)

## Abstract (arXiv)

We provide a sparse version of the bounded degree SOS hierarchy BSOS [7] for polynomial optimization problems. It permits to treat large scale problems which satisfy a structured sparsity pattern. When the sparsity pattern satisfies the running intersection property this Sparse-BSOS hierarchy of semidefinite programs (with semidefinite constraints of fixed size) converges to the global optimum of the original problem. Moreover, for the class of SOS-convex problems, finite convergence takes place at the first step of the hierarchy, just as in the dense version.