Exploiting Sparsity for Semi-Algebraic Set Volume Computation *

Abstract : We provide a systematic deterministic numerical scheme to approximate the volume (i.e. the Lebesgue measure) of a basic semi-algebraic set whose description follows a sparsity pattern. As in previous works (without sparsity), the underlying strategy is to consider an infinite-dimensional linear program on measures whose optimal value is the volume of the set. This is a particular instance of a generalized moment problem which in turn can be approximated as closely as desired by solving a hierarchy of semidefinite relaxations of increasing size. The novelty with respect to previous work is that by exploiting the sparsity pattern we can provide a sparse formulation for which the associated semidefinite relaxations are of much smaller size. In addition, we can decompose the sparse relaxations into completely decoupled subproblems of smaller size, and in some cases computations can be done in parallel. To the best of our knowledge, it is the first contribution that exploits sparsity for volume computation of semi-algebraic sets which are possibly high-dimensional and/or non-convex and/or non-connected.
Type de document :
Pré-publication, Document de travail
Rapport LAAS n° 19030. 2019
Liste complète des métadonnées

Contributeur : Didier Henrion <>
Soumis le : mercredi 6 février 2019 - 22:00:53
Dernière modification le : lundi 11 février 2019 - 10:46:02


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-02010175, version 1
  • ARXIV : 1902.02976


Matteo Tacchi, Tillmann Weisser, Jean-Bernard Lasserre, Didier Henrion. Exploiting Sparsity for Semi-Algebraic Set Volume Computation *. Rapport LAAS n° 19030. 2019. 〈hal-02010175〉



Consultations de la notice


Téléchargements de fichiers