ERROR BOUNDS FOR SOME SEMIDEFINITE PROGRAMMING APPROACHES TO POLYNOMIAL MINIMIZATION ON THE HYPERCUBE

被引：35

作者：

de Klerk, Etienne ^{[1
]}

Laurent, Monique ^{[1
,2
]}

机构：

[1] Tilburg Univ, Dept Econometr & Operat Res, NL-5000 LE Tilburg, Netherlands

[2] Ctr Wiskunde & Informat, NL-1098 XG Amsterdam, Netherlands

来源：

SIAM JOURNAL ON OPTIMIZATION | 2010年 / 20卷 / 06期

关键词：

Positivstellensatz; positive polynomial; sum of squares of polynomials; bound constrained optimization of polynomials; multivariate Bernstein approximation; semidefinite programming; SEMI-ALGEBRAIC SETS; OPTIMIZATION; COMPLEXITY; POSITIVSTELLENSATZ; MOMENTS; SIMPLEX; THEOREM; SQUARES;

D O I：

10.1137/100790835

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We consider the problem of minimizing a polynomial on the hypercube [0, 1](n) and derive new error bounds for the hierarchy of semidefinite programming approximations to this problem corresponding to the Positivstellensatz of Schmudgen [Math. Ann., 289 (1991), pp. 203-206]. The main tool we employ is Bernstein approximations of polynomials, which also gives constructive proofs and degree bounds for positivity certificates on the hypercube.

引用

页码：3104 / 3120

页数：17

共 29 条

[1]

[Anonymous], ARCH MATH B IN PRESS

[2] 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

[3] The complexity of optimizing over a simplex, hypercube or sphere: a short survey [J].

de Klerk, Etienne .

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 2008, 16 (02) :111-125

[4] A PTAS for the minimization of polynomials of fixed degree over the simplex [J].

de Klerk, Etienne ;

Laurent, Monique ;

Parrilo, Pablo A. .

THEORETICAL COMPUTER SCIENCE, 2006, 361 (2-3) :210-225

[5] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J].

Goemans, MX ;

Williamson, DP .

JOURNAL OF THE ACM, 1995, 42 (06) :1115-1145

[6] REPRESENTING POLYNOMIALS BY POSITIVE LINEAR FUNCTIONS ON COMPACT CONVEX POLYHEDRA [J].

HANDELMAN, D .

PACIFIC JOURNAL OF MATHEMATICS, 1988, 132 (01) :35-62

[7] Some optimal inapproximability results [J].

Håstad, J .

JOURNAL OF THE ACM, 2001, 48 (04) :798-859

[8] Clique is hard to approximate within n1-ε [J].

Håstad, J .

ACTA MATHEMATICA, 1999, 182 (01) :105-142

[9] CLOSED-FORM EXPRESSIONS FOR THE MOMENTS OF THE BINOMIAL PROBABILITY DISTRIBUTION [J].

Knoblauch, Andreas .

SIAM JOURNAL ON APPLIED MATHEMATICS, 2008, 69 (01) :197-204

[10] An explicit equivalent positive semidefinite program for nonlinear 0-1 programs [J].

Lasserre, JB .

SIAM JOURNAL ON OPTIMIZATION, 2002, 12 (03) :756-769

← 1 2 3 →