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

Zhao Sun

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)

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 P\'olya'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.
Original languageEnglish
Pages (from-to)379-393
JournalJournal of the Operations Research Society of China
Volume2
Issue number3
DOIs
Publication statusPublished - 11 Sep 2014

Keywords

  • polynomial optimization over the simplex
  • global optimization
  • nonlinear optimization
  • 90C30
  • 90C60

Fingerprint Dive into the research topics of 'A refined error analysis for fixed-degree polynomial optimization over the simplex'. Together they form a unique fingerprint.

  • Cite this