On the Complexity of Optimization Over the Standard Simplex
On the Complexity of Optimization Over the Standard Simplex
复制标题
关于标准单纯形优化的复杂性
DOI：
--
复制
发表时间：
2005
影响因子：
6.4
通讯作者：
G. Elabwabi
中科院分区：
文献类型：
--
作者：
E. Klerk;D. Hertog;G. Elabwabi
本文回顾了标准单纯形和单位超立方体上极小化多项式的复杂性结果，并证明了标准单纯形上极小化Lipschitz连续函数和一致有界Hessian函数的多项式时间近似方案（PTAS），推广了De Klerk，Laurent和Parrilo [A PTAS for minimization of polynomials of fixed degrees over the simplex，理论计算机科学，出现。
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.]