A refined error analysis for fixed-degree polynomial optimization over the simplex

We consider fixed-degree polynomial optimization over the 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 consider a known upper bound by taking the minimum value on a regular grid, and a known lower bound based on Polya's representation theorem. More precisely, we mainly focus on the difference between these two bounds and provide upper bounds for this difference in terms of the range of function values. Our results refine the known upper bounds for the quadratic and cubic cases, and asymptotically refine the known upper bound for the general case.

Citation

Technical report, Tilburg University, the Netherlands, December 2013.

Article

Download

View A refined error analysis for fixed-degree polynomial optimization over the simplex