A refined error analysis for fixed-degree polynomial optimization over the simplex

DOI10.1007/S40305-014-0057-8MaRDI QIDQ489141zbMATH OpenOpenAlexFDO

Authors Zhao Sun

Publication date 27 January 2015

Published in Journal of the Operations Research Society of China (Search for Journal in Brave)

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

zbMATH Keywords

global optimizationnonlinear optimizationpolynomial optimization over the simplex

Mathematics Subject Classification ID

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

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.

Recommendations

• An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
• On the complexity of optimization over the standard simplex
• scientific article; zbMATH DE number 7305739

Cites work

• A PTAS for the minimization of polynomials of fixed degree over the simplex
• A new bound for Pólya's theorem with applications to polynomials positive on polyhedra.
• 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
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On the accuracy of uniform polyhedral approximations of the copositive cone
• On the complexity of optimization over the standard simplex
• Rounding on the standard simplex: regular grids for global optimization
• Semidefinite programming relaxations for semialgebraic problems
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey

Cited in

(7)

• scientific article; zbMATH DE number 7305739 (Why is no real title available?)
• Error Estimates in the Optimization of Degree Two Polynomials on a Discrete Hypercube
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution
• An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
• 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

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)