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

被引：36
|
作者：
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
相关论文
共 50 条
  • [1] ERROR BOUNDS FOR POLYNOMIAL MINIMIZATION OVER THE HYPERCUBE-SIMPLOIDS
    Zhang, Yue
    Jia, Zhi-Qiang
    Zhu, Chun-Gang
    PACIFIC JOURNAL OF OPTIMIZATION, 2018, 14 (02): : 193 - 210
  • [2] Error bounds for polynomial optimization over the hypercube using putinar type representations
    Magron, Victor
    OPTIMIZATION LETTERS, 2015, 9 (05) : 887 - 895
  • [3] Error bounds for polynomial optimization over the hypercube using putinar type representations
    Victor Magron
    Optimization Letters, 2015, 9 : 887 - 895
  • [4] ON THE LASSERRE HIERARCHY OF SEMIDEFINITE PROGRAMMING RELAXATIONS OF CONVEX POLYNOMIAL OPTIMIZATION PROBLEMS
    De Klerk, Etienne
    Laurent, Monique
    SIAM JOURNAL ON OPTIMIZATION, 2011, 21 (03) : 824 - 832
  • [5] Computable Error Bounds for Semidefinite Programming
    Sien Deng
    Hui Hu
    Journal of Global Optimization, 1999, 14 : 105 - 115
  • [6] Computable error bounds for semidefinite programming
    Deng, S
    Hu, H
    JOURNAL OF GLOBAL OPTIMIZATION, 1999, 14 (02) : 105 - 115
  • [7] ERROR BOUNDS AND SINGULARITY DEGREE IN SEMIDEFINITE PROGRAMMING
    Sremac, Stefan
    Woerdeman, Hugo J.
    Wolkowicz, Henry
    SIAM JOURNAL ON OPTIMIZATION, 2021, 31 (01) : 812 - 836
  • [8] RIGOROUS ERROR BOUNDS FOR THE OPTIMAL VALUE IN SEMIDEFINITE PROGRAMMING
    Jansson, Christian
    Chaykin, Denis
    Keil, Christian
    SIAM JOURNAL ON NUMERICAL ANALYSIS, 2007, 46 (01) : 180 - 200
  • [9] Certified Roundoff Error Bounds Using Semidefinite Programming
    Magron, Victor
    Constantinides, George
    Donaldson, Alastair
    ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2017, 43 (04):
  • [10] Semidefinite programming based approaches to the break minimization problem
    Miyashiro, R
    Matsui, T
    COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (07) : 1975 - 1982
12345