convex bodies – 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

Approximation algorithms for trilinear optimization with nonconvex constraints and its extensions

Published: 2011/04/02, Updated: 2013/05/29

Yuning Yang

Qingzhi Yang

Semi-definite Programming approximation solution, biquadratic optimization, convex bodies, semidefinite relaxation, trilinear optimization

In this paper, we study trilinear optimization problems with nonconvex constraints under some assumptions. We first consider the semidefinite relaxation (SDR) of the original problem. Then motivated by So \cite{So2010}, we reduce the problem to that of determining the $L_2$-diameters of certain convex bodies, which can be approximately solved in deterministic polynomial-time. After the relaxed … Read more