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).
Document type :
Preprints, Working Papers, ...
Rapport LAAS n° 16491. 2016
Liste complète des métadonnées

Cited literature [6 references]  Display  Hide  Download

https://hal.laas.fr/hal-01415327
Contributor : Didier Henrion <>
Submitted on : Monday, December 12, 2016 - 11:37:54 PM
Last modification on : Thursday, January 11, 2018 - 6:26:20 AM
Document(s) archivé(s) le : Monday, March 27, 2017 - 9:25:28 PM

Files

convergevol.pdf
Files produced by the author(s)

Identifiers

  • 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〉

Share

Metrics

Record views

130

Files downloads

25