A refined error analysis for fixed-degree polynomial optimization over the simplex
Zhao Sun (z.sunuvt.nl)
Abstract: 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.
Keywords: Polynomial optimization over a simplex, Global optimization
Category 1: Global Optimization (Theory )
Citation: Technical report, Tilburg University, the Netherlands, December 2013.
Entry Submitted: 12/22/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|