On the complexity of optimization over the standard simplex

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

On the complexity of optimization over the standard simplex

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

Research output: Contribution to journal › Article › Scientific › peer-review

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 language	English
Pages (from-to)	773-785
Journal	European Journal of Operational Research
Volume	191
Publication status	Published - 2008

Cite this

@article{bd6a1bf635f5410b8b611429d9d9fbe8,

title = "On the complexity of optimization over the standard simplex",

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

author = "{de Klerk}, E. and {den Hertog}, D. and G.E.E. Elfadul",

note = "Appeared earlier as CentER DP 2005-125",

year = "2008",

language = "English",

volume = "191",

pages = "773--785",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - On the complexity of optimization over the standard simplex

AU - de Klerk, E.

AU - den Hertog, D.

AU - Elfadul, G.E.E.

N1 - Appeared earlier as CentER DP 2005-125

PY - 2008

Y1 - 2008

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

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

M3 - Article

SN - 0377-2217

VL - 191

SP - 773

EP - 785

JO - European Journal of Operational Research

JF - European Journal of Operational Research

ER -

On the complexity of optimization over the standard simplex

Abstract

Fingerprint

Cite this