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

Tillmann Weisser (1) , Jean-Bernard Lasserre (2, 1) , Kim-Chuan Toh (3)

1 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
2 IMT - Institut de Mathématiques de Toulouse UMR5219
3 NUS - National University of Singapore

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.

Mots clés: Positivity Certificates; Global Optimization; Semidefinite Programming; Convex Relaxations; Sparsity; Large Scale Problems

Domaines: Optimisation et contrôle [math.OC]

Tillmann Weisser, Jean-Bernard Lasserre, Kim-Chuan Toh. Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity. 2017. ⟨hal-01341931v2⟩