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

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