TSSOS: A Moment-SOS hierarchy that exploits term sparsity

2019/12/18 by Jie Wang, Victor Magron, Wang, Jie +3 · 9 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1912.08899

openalex publication_date 2019/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

This paper is concerned with polynomial optimization problems. We show how to exploit term (or monomial) sparsity of the input polynomials to obtain a new converging hierarchy of semidefinite programming relaxations. The novelty (and distinguishing feature) of such relaxations is to involve block-diagonal matrices obtained in an iterative procedure performing completion of the connected components of certain adjacency graphs. The graphs are related to the terms arising in the original data and not to the links between variables. Our theoretical framework is then applied to compute lower bounds for polynomial optimization problems either randomly generated or coming from the networked systems literature.

Citations

• Application of Polynomial Optimization to Electricity Transmission\n Networks
• CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization

Cited by

• Global optimization of low-rank polynomials
• Exploiting Term Sparsity in Symmetry-Adapted Basis for Polynomial Optimization
• Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers
• Most incompatible measurements and sum-of-squares optimisation
• Time evolution of controlled many-body quantum systems with matrix product operators
• Moment-SOS hierarchies for arrow-type polynomial matrix inequalities with applications to structural optimization
• Set-membership identification of continuous-time MIMO systems via Tustin discretization
• Control Closure Certificates
• Unitary Gate Synthesis via Polynomial Optimization

Related

• Refined TSSOS
• CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization
• TSSOS: a Julia library to exploit sparsity for large-scale polynomial optimization
• A bounded degree SOS hierarchy for polynomial optimization
• Finite convergence of the Moment-SOS hierarchy for polynomial matrix optimization