Search

We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre, and a related hierarchy by de Klerk, Hess, and Laurent. For polynomial optimization over the hypercube, we show a refined convergence analysis for the first hierarchy. We also show lower bounds on the convergence rate for both hierarchies on a class of examples. These lower bounds match the upper bounds and thus establish the true rate of convergence on these examples. Interestingly, these convergence rates are determined by the distribution of extremal zeroes of certain families of orthogonal polynomials. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing a continuous function f over a compact set $${\mathbf {K}}$$ . We analyze a hierarchy of upper bounds proposed by Lasserre (SIAM J Optim 21(3):864-885, 2011), obtained by searching for an optimal probability density function h on $${\mathbf {K}}$$ which is a sum of squares of polynomials, so that the expectation $$\int _{{\mathbf {K}}} f(x)h(x)dx$$ is minimized. We show that the rate of convergence is no worse than $$O(1/\sqrt{r})$$ , where 2 r is the degree bound on the density function. This analysis applies to the case when f is Lipschitz continuous and $${\mathbf {K}}$$ is a full-dimensional compact set satisfying some boundary condition (which is satisfied, e.g., for convex bodies). The rth upper bound in the hierarchy may be computed using semidefinite programming if f is a polynomial of degree d, and if all moments of order up to $$2r+d$$ of the Lebesgue measure on $${\mathbf {K}}$$ are known, which holds, for example, if $${\mathbf {K}}$$ is a simplex, hypercube, or a Euclidean ball. [ABSTRACT FROM AUTHOR]

The problem of minimizing a polynomial over the standard simplex is one of the basic NP-hard nonlinear optimization problems-it contains the maximum clique problem in graphs as a special case. It is known that the problem allows a polynomial-time approximation scheme (PTAS) for polynomials of fixed degree, which is based on polynomial evaluations at the points of a sequence of regular grids. In this paper, we provide an alternative proof of the PTAS property. The proof relies on the properties of Bernstein approximation on the simplex. We also refine a known error bound for the scheme for polynomials of degree three. The main contribution of the paper is to provide new insight into the PTAS by establishing precise links with Bernstein approximation and the multinomial distribution. [ABSTRACT FROM AUTHOR]