Optimization Online


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

Zhao Sun (z.sun***at***uvt.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.

Download: [PDF]

Entry Submitted: 12/22/2013
Entry Accepted: 01/01/2014
Entry Last Modified: 01/01/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society