A sparse noncommutative Positivstellensatz and sparse GNS extraction are proved, giving converging SDP hierarchies for eigenvalue and trace optimization under a running-intersection sparsity pattern.
TSSOS: A Moment-SOS hierarchy that exploits term sparsity
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
math.OC 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Sparse Noncommutative Polynomial Optimization
A sparse noncommutative Positivstellensatz and sparse GNS extraction are proved, giving converging SDP hierarchies for eigenvalue and trace optimization under a running-intersection sparsity pattern.