positive polynomial

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

    A PTAS for the minimization of polynomials of fixed degree over the simplex

  • Etienne de Klerk
  • Monique Laurent
  • Pablo A. Parrilo
    • Categories Approximation Algorithms, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    We consider the problem of computing the minimum value $p_{\min}$ taken by a polynomial $p(x)$ of degree $d$ over the standard simplex $\Delta$. This is an NP-hard problem already for degree $d=2$. For any integer $k\ge 1$, by minimizing $p(x)$ over the set of rational points in $\Delta$ with denominator $k$, one obtains a hierarchy … Read more