Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Stokes, Gibbs, and Volume Computation of Semi-Algebraic Sets
 
research article

Stokes, Gibbs, and Volume Computation of Semi-Algebraic Sets

Tacchi, Matteo  
•
Lasserre, Jean Bernard
•
Henrion, Didier
December 22, 2022
Discrete & Computational Geometry

We consider the problem of computing the Lebesgue volume of compact basic semi-algebraic sets. In full generality, it can be approximated as closely as desired by a converging hierarchy of upper bounds obtained by applying the Moment-SOS (sums of squares) methodology to a certain infinite-dimensional linear program (LP). At each step one solves a semidefinite relaxation of the LP which involves pseudo-moments up to a certain degree. Its dual computes a polynomial of same degree which approximates from above the discontinuous indicator function of the set, hence with a typical Gibbs phenomenon which results in a slow convergence of the associated numerical scheme. Drastic improvements have been observed by introducing in the initial LP additional linear moment constraints obtained from a certain application of Stokes' theorem for integration on the set. However and so far there was no rationale to explain this behavior. We provide a refined version of this extended LP formulation. When the set is the smooth super-level set of a single polynomial, we show that the dual of this refined LP has an optimal solution which is a continuous function. Therefore in this dual one now approximates a continuous function by a polynomial, hence with no Gibbs phenomenon, which explains and improves the already observed drastic acceleration of the convergence of the hierarchy. Interestingly, the technique of proof involves recent results on Poisson's partial differential equation (PDE).

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1007/s00454-022-00462-0
Web of Science ID

WOS:000903162000001

Author(s)
Tacchi, Matteo  
Lasserre, Jean Bernard
Henrion, Didier
Date Issued

2022-12-22

Publisher

SPRINGER

Published in
Discrete & Computational Geometry
Subjects

Computer Science, Theory & Methods

•

Mathematics

•

Computer Science

•

numerical methods for multivariate integration

•

real algebraic geometry

•

convex optimization

•

stokes' theorem

•

gibbs phenomenon

•

optimization

•

attraction

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LA3  
Available on Infoscience
January 30, 2023
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/194460
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés