ptas

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

    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