polynomial optimization over a simplex

A refined error analysis for fixed-degree polynomial optimization over the simplex

  • Zhao Sun
    • Categories Global Optimization Theory Tags ,

    We consider fixed-degree polynomial optimization over the simplex. This problem is well known to be NP-hard, since it contains the maximum stable set problem in combinatorial optimization as a special case. In this paper, we consider a known upper bound by taking the minimum value on a regular grid, and a known lower bound based … Read more

    An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex

  • Etienne de Klerk
  • Monique Laurent
  • Zhao Sun
    • Categories Nonlinear Optimization Tags , ,

    The problem of minimizing a polynomial over the standard simplex is one of the basic NP-hard nonlinear optimization problems — it contains the maximum clique problem in graphs as a special case. It is known that the problem allows a polynomial-time approximation scheme (PTAS) for polynomials of fixed degree, which is based on polynomial evaluations … Read more