On the complexity of optimization over the standard simplex

E. de Klerk, Dick Den Hertog () and G. Elabwabi

European Journal of Operational Research, 2008, vol. 191, issue 3, pages 773-785

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

View citations in EconPapers

Downloads: (external link)
http://www.sciencedirect.com/science/article/B6VCT ... 37303fb4b4aa4fb6ba99
Full text for ScienceDirect subscribers only

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

Access Statistics for this article

European Journal of Operational Research is edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Series data maintained by Heidi Boesdal ().