Optimization Online


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

Milan Korda(milan.korda***at***engineering.ucsb.edu)
Didier Henrion(henrion***at***laas.fr)

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)$.

Keywords: moment relaxations, polynomial sums of squares, convergence rate, semidefinite programming, approximation theory

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Infinite Dimensional Optimization (Other )


Download: [PDF]

Entry Submitted: 12/12/2016
Entry Accepted: 12/13/2016
Entry Last Modified: 12/12/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society