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

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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 at the points of a sequence of regular grids. In this paper, we provide an alternative proof of the PTAS property. The proof relies on the properties of Bernstein approximation on the simplex. We also refine a known error bound for the scheme for polynomials of degree three. The main contribution of the paper is to provide new insight into the PTAS by establishing precise links with Bernstein approximation and the multinomial distribution.
Original languageEnglish
Pages (from-to)433-457
Number of pages24
JournalMathematical Programming
Volume151
Issue number2
Early online date15 Oct 2014
DOIs
Publication statusPublished - Jul 2015

Fingerprint

Polynomial Time Approximation Scheme
Polynomials
Polynomial
Optimization
Alternatives
Polynomial Evaluation
Maximum Clique Problem
Multinomial Distribution
Approximation
Nonlinear Optimization
Error Bounds
NP-complete problem
Grid
Graph in graph theory

Keywords

  • polynomial optimization over the simplex
  • PTAS
  • Bernstein approximation

Cite this

@article{8405c6ffbc9c4ce6a9ef8674961df0ac,
title = "An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex",
abstract = "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 at the points of a sequence of regular grids. In this paper, we provide an alternative proof of the PTAS property. The proof relies on the properties of Bernstein approximation on the simplex. We also refine a known error bound for the scheme for polynomials of degree three. The main contribution of the paper is to provide new insight into the PTAS by establishing precise links with Bernstein approximation and the multinomial distribution.",
keywords = "polynomial optimization over the simplex, PTAS, Bernstein approximation",
author = "{de Klerk}, E. and M. Laurent and Z. Sun",
year = "2015",
month = "7",
doi = "10.1007/s10107-014-0825-6",
language = "English",
volume = "151",
pages = "433--457",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "2",

}

An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex. / de Klerk, E.; Laurent, M.; Sun, Z.

In: Mathematical Programming, Vol. 151, No. 2, 07.2015, p. 433-457.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

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

AU - de Klerk, E.

AU - Laurent, M.

AU - Sun, Z.

PY - 2015/7

Y1 - 2015/7

N2 - 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 at the points of a sequence of regular grids. In this paper, we provide an alternative proof of the PTAS property. The proof relies on the properties of Bernstein approximation on the simplex. We also refine a known error bound for the scheme for polynomials of degree three. The main contribution of the paper is to provide new insight into the PTAS by establishing precise links with Bernstein approximation and the multinomial distribution.

AB - 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 at the points of a sequence of regular grids. In this paper, we provide an alternative proof of the PTAS property. The proof relies on the properties of Bernstein approximation on the simplex. We also refine a known error bound for the scheme for polynomials of degree three. The main contribution of the paper is to provide new insight into the PTAS by establishing precise links with Bernstein approximation and the multinomial distribution.

KW - polynomial optimization over the simplex

KW - PTAS

KW - Bernstein approximation

U2 - 10.1007/s10107-014-0825-6

DO - 10.1007/s10107-014-0825-6

M3 - Article

VL - 151

SP - 433

EP - 457

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -