Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization

Jie Wang 1 Victor Magron 1 Jean Lasserre 1 Ngoc Hoang Anh Mai 1
1 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : This work proposes a new moment-SOS hierarchy, called CS-TSSOS, for solving large-scale sparse polynomial optimization problems. Its novelty is to exploit simultaneously correlative sparsity and term sparsity by combining advantages of two existing frameworks for sparse polynomial optimization. The former is due to Waki et al. while the latter was initially proposed by Wang et al. and later exploited in the TSSOS hierarchy. In doing so we obtain CS-TSSOS -- a two-level hierarchy of semidefinite programming relaxations with (i), the crucial property to involve quasi block-diagonal matrices and (ii), the guarantee of convergence to the global optimum. We demonstrate its efficiency on several large-scale instances of the celebrated Max-Cut problem and the important industrial optimal power flow problem, involving up to several thousands of variables and ten thousands of constraints.
Complete list of metadata
Contributor : Victor Magron <>
Submitted on : Thursday, May 7, 2020 - 9:38:27 AM
Last modification on : Thursday, June 10, 2021 - 3:04:01 AM

Links full text


  • HAL Id : hal-02566472, version 1
  • ARXIV : 2005.02828


Jie Wang, Victor Magron, Jean Lasserre, Ngoc Hoang Anh Mai. CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization. 2020. ⟨hal-02566472⟩



Record views