TSSOS: A Moment-SOS hierarchy that exploits term sparsity. 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.

References in zbMATH (referenced in 17 articles , 1 standard article )

Showing results 1 to 17 of 17.
Sorted by year (citations)

  1. Chen, Tong; Lasserre, Jean-Bernard; Magron, Victor; Pauwels, Edouard: A sublevel moment-SOS hierarchy for polynomial optimization (2022)
  2. Gribling, Sander; Laurent, Monique; Steenkamp, Andries: Bounding the separable rank via polynomial optimization (2022)
  3. Klep, Igor; Magron, Victor; Povh, Janez: Sparse noncommutative polynomial optimization (2022)
  4. Lasserre, Jean B.: Optimization on the Euclidean unit sphere (2022)
  5. Miller, Jared; Zheng, Yang; Sznaier, Mario; Papachristodoulou, Antonis: Decomposed structured subsets for semidefinite and sum-of-squares optimization (2022)
  6. Moustrou, Philippe; Naumann, Helen; Riener, Cordian; Theobald, Thorsten; Verdure, Hugues: Symmetry reduction in AM/GM-based optimization (2022)
  7. Wang, Jie: Nonnegative polynomials and circuit polynomials (2022)
  8. Wang, Jie; Magron, Victor: Exploiting sparsity in complex polynomial optimization (2022)
  9. Katthän, Lukas; Naumann, Helen; Theobald, Thorsten: A unified framework of SAGE and SONC polynomials and its duality theory (2021)
  10. Lakshmi, Mayur V.; Fantuzzi, Giovanni; Chernyshenko, Sergei I.; Lasagna, Davide: Finding unstable periodic orbits: a hybrid approach with polynomial optimization (2021)
  11. Lasserre, Jean Bernard; Magron, Victor; Marx, Swann; Zahm, Olivier: Minimizing rational functions: a hierarchy of approximations via pushforward measures (2021)
  12. Wang, Jie; Magron, Victor: Exploiting term sparsity in noncommutative polynomial optimization (2021)
  13. Wang, Jie; Magron, Victor; Lasserre, Jean-Bernard: TSSOS: a moment-SOS hierarchy that exploits term sparsity (2021)
  14. Wang, Jie; Magron, Victor; Lasserre, Jean-Bernard: Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension (2021)
  15. Lasserre, Jean B.; Magron, Victor: Computing the Hausdorff boundary measure of semialgebraic sets (2020)
  16. Wang, Jie; Magron, Victor: A second order cone characterization for sums of nonnegative circuits (2020)
  17. Jie Wang, Victor Magron, Jean-Bernard Lasserre: TSSOS: A Moment-SOS hierarchy that exploits term sparsity (2019) arXiv