Optimization Online


Markov inequalities, Dubiner distance, norming meshes and polynomial optimization on convex bodies

Federico Piazzon(fpiazzon***at***math.unipd.it)
Marco Vianello(marcov***at***math.unipd.it )

Abstract: We construct norming meshes for polynomial optimization by the classical Markov inequality on general convex bodies in R^d, and by a tangential Markov inequality via an estimate of Dubiner distance on smooth convex bodies. These allow to compute a (1−eps)-approximation to the minimum of any polynomial of degree not exceeding n by O((n/sqrt(eps))^(ad)) samples, with a=2 in the general case, and a=1 in the smooth case. Such constructions are based on three cornerstones of convex geometry, Bieberbach volume inequality and Leichtweiss inequality on the affine breadth eccentricity, and the Rolling Ball Theorem, respectively.

Keywords: polynomial optimization, norming mesh, Markov inequality, tangential Markov inequality, Dubiner distance, convex bodies

Category 1: Global Optimization (Other )

Citation: Preprint, August 2018

Download: [PDF]

Entry Submitted: 08/02/2018
Entry Accepted: 08/03/2018
Entry Last Modified: 08/02/2018

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