TSSOS: A Moment-SOS hierarchy that exploits term sparsity

Understand

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.