On the complexity of optimization over the standard simplex

Etienne de Klerk, Dick den Hertog and Gamal Elfadul Elabwabi
Additional contact information
Gamal Elfadul Elabwabi: Tilburg University, Center for Economic Research

No 125, Discussion Paper from Tilburg University, Center for Economic Research

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.]

Keywords: global optimization; standard simplex; PTAS; multivariate Bernstein approximation; semidefinite programming (search for similar items in EconPapers)
JEL-codes: C61 (search for similar items in EconPapers)
Date: Written 2005
View list of references

Downloads: (external link)
http://arno.uvt.nl/show.cgi?fid=53857 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Access Statistics for this paper

More papers in Discussion Paper from Tilburg University, Center for Economic Research
Series data maintained by Corry Stuyts ().