Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 191, Issue 3, Pages 773-785Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2007.01.055
Keywords
global optimization; standard simplex; PTAS; multivariate Bernstein approximation; multivariate Lagrange interpolation; linear programming
Ask authors/readers for more resources
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]. (C) 2007 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available