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

223 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

Fingerprint

Polynomial Time Approximation Scheme
Optimization
Polynomial
Lipschitz Function
Hypercube
Continuous Function
Computer Science
Unit
Standards
Review

Keywords

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

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). Tilburg: Operations research.
de Klerk, E. ; den Hertog, D. ; Elfadul, G.E.E. / On the Complexity of Optimization over the Standard Simplex. Tilburg : Operations research, 2005. (CentER Discussion Paper).
@techreport{3789955a65334a4eaca26dd7244fab83,
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 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",
author = "{de Klerk}, E. and {den Hertog}, D. and G.E.E. Elfadul",
note = "Subsequently published in the European Journal of Operational Research, 2008 Pagination: 13",
year = "2005",
language = "English",
volume = "2005-125",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

de Klerk, E, den Hertog, D & Elfadul, GEE 2005 'On the Complexity of Optimization over the Standard Simplex' CentER Discussion Paper, vol. 2005-125, Operations research, Tilburg.

On the Complexity of Optimization over the Standard Simplex. / de Klerk, E.; den Hertog, D.; Elfadul, G.E.E.

Tilburg : Operations research, 2005. (CentER Discussion Paper; Vol. 2005-125).

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

TY - UNPB

T1 - On the Complexity of Optimization over the Standard Simplex

AU - de Klerk, E.

AU - den Hertog, D.

AU - Elfadul, G.E.E.

N1 - Subsequently published in the European Journal of Operational Research, 2008 Pagination: 13

PY - 2005

Y1 - 2005

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

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

KW - global optimization

KW - standard simplex

KW - PTAS

KW - multivariate Bernstein approximation

KW - semidefinite programming

M3 - Discussion paper

VL - 2005-125

T3 - CentER Discussion Paper

BT - On the Complexity of Optimization over the Standard Simplex

PB - Operations research

CY - Tilburg

ER -

de Klerk E, den Hertog D, Elfadul GEE. On the Complexity of Optimization over the Standard Simplex. Tilburg: Operations research. 2005. (CentER Discussion Paper).

Access to Document

  • 125Final published version, 344 KB