On the complexity of optimization over the standard simplex

被引：16

作者：

de Klerk, E. ^{[1
]}

den Hertog, D. ^{[1
]}

Elabwabi, G. ^{[1
]}

机构：

[1] Tilburg Univ, CentER, NL-5000 LE Tilburg, Netherlands

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2008年 / 191卷 / 03期

关键词：

global optimization; standard simplex; PTAS; multivariate Bernstein approximation; multivariate Lagrange interpolation; linear programming;

D O I：

10.1016/j.ejor.2007.01.055

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：773 / 785

页数：13

共 31 条

[1]

Acerbi C., 2002, EC NOTES BANCA MONTE, V31, P379, DOI [10.1111/1468-0300.00091, DOI 10.1111/1468-0300.00091]

[2]

ALTOMARE F, 1994, GUYTER STUDIES MATH, V17

[3]

[Anonymous], APPROXIMATION THEORY

[4]

[Anonymous], FRONTIERS GLOBAL OPT

[5] STRUCTURE PRESERVING REDUCTIONS AMONG CONVEX-OPTIMIZATION PROBLEMS [J].

AUSIELLO, G ;

DATRI, A ;

PROTASI, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1980, 21 (01) :136-153

[6] Global minimization of increasing positively homogeneous functions over the unit simplex [J].

Bagirov, AM ;

Rubinov, AM .

ANNALS OF OPERATIONS RESEARCH, 2000, 98 (1-4) :171-187

[7]

Beliakov G, 2002, ADV SOFT COMP, P79

[8] THE COMPLEXITY OF APPROXIMATING A NONLINEAR PROGRAM [J].

BELLARE, M ;

ROGAWAY, P .

MATHEMATICAL PROGRAMMING, 1995, 69 (03) :429-441

[9]

Bertsimas D., 2004, J ECON DYN CONTROL, V28, P1227

[10] Solving standard quadratic optimization problems via linear, semidefinite and copositive programming [J].

Bomze, IM ;

De Klerk, E .

JOURNAL OF GLOBAL OPTIMIZATION, 2002, 24 (02) :163-185

← 1 2 3 4 →