A refined error analysis for fixed-degree polynomial optimization over the simplex
From MaRDI portal
Publication:489141
DOI10.1007/S40305-014-0057-8zbMATH Open1308.90172arXiv1312.5873OpenAlexW2128643477MaRDI QIDQ489141FDOQ489141
Publication date: 27 January 2015
Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)
Abstract: We consider the problem of minimizing a fixed-degree polynomial over the standard 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 revisit a known upper bound obtained by taking the minimum value on a regular grid, and a known lower bound based on P'olya's representation theorem. More precisely, we consider the difference between these two bounds and we provide upper bounds for this difference in terms of the range of function values. Our results refine the known upper bounds in the quadratic and cubic cases, and they asymptotically refine the known upper bound in the general case.
Full work available at URL: https://arxiv.org/abs/1312.5873
Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Semidefinite programming relaxations for semialgebraic problems
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- A new bound for Pólya's theorem with applications to polynomials positive on polyhedra.
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- On the accuracy of uniform polyhedral approximations of the copositive cone
- Error Bounds for Some Semidefinite Programming Approaches to Polynomial Minimization on the Hypercube
- The complexity of optimizing over a simplex, hypercube or sphere: a short survey
- A PTAS for the minimization of polynomials of fixed degree over the simplex
- Rounding on the standard simplex: regular grids for global optimization
- An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
- Analysis of copositive optimization based linear programming bounds on standard quadratic optimization
- On the complexity of optimization over the standard simplex
Cited In (4)
- An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
- Title not available (Why is that?)
- An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution
- Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
This page was built for publication: A refined error analysis for fixed-degree polynomial optimization over the simplex
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489141)
