On the Complexity of Optimization over the Standard Simplex

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

Research output: Working paper › Discussion paper › Other research output

235 Downloads (Pure)

Abstract

We review complexity results for minimizing polynomials over the standard simplex and unit hypercube.In addition, we show that there exists a polynomial time approximation scheme (PTAS) for minimizing Lipschitz continuous functions and functions with uniformly bounded Hessians over the standard simplex.This extends an earlier result by De Klerk, Laurent and Parrilo [A PTAS for the minimization of polynomials of fixed degree over the simplex, Theoretical Computer Science, to appear.]
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages13
Volume2005-125
Publication statusPublished - 2005

Publication series

NameCentER Discussion Paper
Volume2005-125

Keywords

  • global optimization
  • standard simplex
  • PTAS
  • multivariate Bernstein approximation
  • semidefinite programming

Access to Document

  • 125Final published version, 345 KB

    Fingerprint Dive into the research topics of 'On the Complexity of Optimization over the Standard Simplex'. Together they form a unique fingerprint.

    • Cite this

    de Klerk, E., den Hertog, D., & Elfadul, G. E. E. (2005). On the Complexity of Optimization over the Standard Simplex. (CentER Discussion Paper; Vol. 2005-125). Operations research.