On the complexity of optimization over the standard simplex

Etienne De Klerk (E.deKlerkuvt.nl)
Dick Den Hertog (D.denHertoguvt.nl)
Gamal Elabwabi (G.Elabwabiuvt.nl)

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 some classes of functions (including Lipschitz continuous functions) over 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, 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, multivariate Lagrange interpolation

Category 1: Global Optimization (Theory )

Category 2: Linear, Cone and Semidefinite Programming

Citation: CentER Discussion paper 2005-125, Tilburg University.

Download: [PDF]

Entry Submitted: 01/27/2006
Entry Accepted: 02/01/2006
Entry Last Modified: 07/15/2006

Modify/Update this entry