Abstract:

We consider the problem of minimizing a fixed-degree polynomial over
the standard simplex. This problem is well known to be NP-hard, since it contains
the maximum stable set problem in combinatorial optimization as a special case. In
this paper, we revisit a known upper bound obtained by taking the minimum value
on a regular grid, and a known lower bound based on Po´lya’s representation theorem.
More precisely, we consider the difference between these two bounds and we
provide upper bounds for this difference in terms of the range of function values.
Our results refine the known upper bounds in the quadratic and cubic cases, and they
asymptotically refine the known upper bound in the general case.

Key words: Polynomial optimization over the simplex ,  Global optimization ,  Nonlinear optimization