multivariate bernstein approximation

Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube

  • Etienne de Klerk
  • Monique Laurent
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    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 Schmuedgen (1991). The main tool we employ is Bernstein approximations of polynomials, which also gives constructive proofs and degree bounds for positivity certificates … Read more

    On the complexity of optimization over the standard simplex

  • Etienne de Klerk
  • Dick den Hertog
  • Gamal Elabwabi
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming Tags , , , ,

    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 some classes of functions (including Lipschitz continuous functions) over the standard simplex. The main tools used in the analysis are Bernstein approximation and Lagrange interpolation on … Read more