Marco Vianello – Optimization Online

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

Published: 2018/08/02

Global Optimization convex bodies, dubiner distance, markov inequality, norming mesh, polynomial optimization, tangential markov inequality

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 … Read more

Polynomial Optimization on Chebyshev-Dubiner Webs of Starlike Polygons

Published: 2018/07/30

Marco Vianello

Global Optimization chebyshev points, dubiner distance, norming mesh, polynomial optimization, starlike polygon

We construct web-shaped norming meshes on starlike polygons, by radial and boundary Chebyshev points. Via the approximation theoretic notion of Dubiner distance, we get a (1-eps)-approximation to the minimum of an arbitrary polynomial of degree n by O(n^2/eps) sampling points. Citation Preprint, July 2018 Article Download View Polynomial Optimization on Chebyshev-Dubiner Webs of Starlike Polygons