On the complexity of optimization over the standard simplex

E. de Klerk, D. den Hertog, G.E.E. Elfadul

Research output: Contribution to journalArticleScientificpeer-review

11 Citations (Scopus)

Abstract

We review complexity results for minimizing polynomials over the standard simplex and unit hypercube. In addition, we derive new results on the computational complexity of approximating the minimum of some classes of functions (including Lipschitz continuous functions) on the standard simplex. The main tools used in the analysis are Bernstein approximation and Lagrange interpolation on the simplex combined with an earlier result by de Klerk et al. [A PTAS for the minimization of polynomials of fixed degree over the simplex, Theoretical Computer Science 361 (2–3) (2006) 210–225].
Original languageEnglish
Pages (from-to)773-785
JournalEuropean Journal of Operational Research
Volume191
Publication statusPublished - 2008

Fingerprint Dive into the research topics of 'On the complexity of optimization over the standard simplex'. Together they form a unique fingerprint.

  • Cite this