We introduce a family of symmetric convex bodies called generalized ellipsoids of degree \(d\) (GE-\(d\)s), with ellipsoids corresponding to the case of \(d=0\). Generalized ellipsoids (GEs) retain many geometric, algebraic, and algorithmic properties of ellipsoids. We show that the conditions that the parameters of a GE must satisfy can be checked in strongly polynomial time, … Read more
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
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