Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets

Abstract : Moment-sum-of-squares hierarchies of semidefinite programs can be used to approximate the volume of a given compact basic semialgebraic set K. The idea consists of approximating from above the indicator function of K with a sequence of polynomials of increasing degree d, so that the integrals of these polynomials generate a convergence sequence of upper bounds on the volume of K. We show that the asymptotic rate of this convergence is at least O(1/ log log d).
Type de document :
Pré-publication, Document de travail
Rapport LAAS n° 16491. 2016
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.laas.fr/hal-01415327
Contributeur : Didier Henrion <>
Soumis le : lundi 12 décembre 2016 - 23:37:54
Dernière modification le : vendredi 26 octobre 2018 - 10:46:01
Document(s) archivé(s) le : lundi 27 mars 2017 - 21:25:28

Fichiers

convergevol.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01415327, version 1
  • ARXIV : 1612.04146

Citation

Milan Korda, Didier Henrion. Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets. Rapport LAAS n° 16491. 2016. 〈hal-01415327〉

Partager

Métriques

Consultations de la notice

199

Téléchargements de fichiers

41