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

DOI10.1007/s10107-014-0825-6zbMath1328.90146arXiv1311.0173OpenAlexW2106875569MaRDI QIDQ2349131

Zhao Sun, Monique Laurent, Etienne de Klerk

Publication date: 19 June 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.0173

zbMATH Keywords

PTASBernstein approximationpolynomial optimization over a simplex

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30)

Related Items (8)

Improved approximation results on standard quartic polynomial optimization ⋮ A refined error analysis for fixed-degree polynomial optimization over the simplex ⋮ LP Formulations for Polynomial Optimization Problems ⋮ Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization ⋮ On the convergence rate of grid search for polynomial optimization over the simplex ⋮ Approximating the existential theory of the reals ⋮ Approximating the existential theory of the reals ⋮ An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analysis of copositive optimization based linear programming bounds on standard quadratic optimization
• Bounding the Lebesgue function for Lagrange interpolatin in a simplex
• On the complexity of optimization over the standard simplex
• Inverse theorems for multidimensional Bernstein operators
• Optimal approximation class for multivariate Bernstein operators
• Korovkin-type approximation theory and its applications
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• The complexity of approximating a nonlinear program
• Rounding on the standard simplex: regular grids for global optimization
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Global Optimization with Polynomials and the Problem of Moments
• On the accuracy of uniform polyhedral approximations of the copositive cone
• Error Bounds for Some Semidefinite Programming Approaches to Polynomial Minimization on the Hypercube
• Closed-form Expressions for the Moments of the Binomial Probability Distribution
• Maxima for Graphs and a New Proof of a Theorem of Turán

This page was built for publication: An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex