On the minimum of a positive polynomial over the standard simplex

DOI10.1016/J.JSC.2010.01.001MaRDI QIDQ2269694zbMATH OpenOpenAlexFDO

Authors Gabriela Jeronimo, Daniel Perrucci

Publication date 17 March 2010

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0906.4377, http://hdl.handle.net/11336/98653

zbMATH Keywords

optimization on polyhedrapositivity of polynomials

Mathematics Subject Classification ID

Real algebra (13J30) Semialgebraic sets and related spaces (14P10) Polynomials, rational functions in real analysis (26C99) Nonconvex programming, global optimization (90C26)

Abstract: We present a new positive lower bound for the minimum value taken by a polynomial P with integer coefficients in k variables over the standard simplex of R^k, assuming that P is positive on the simplex. This bound depends only on the number of variables, the degree and the bitsize of the coefficients of P and improves all previous bounds for arbitrary polynomials which are positive over the simplex.

Recommendations

• 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.
• A quantitative Pólya's Theorem with corner zeros
• On the complexity of optimization over the standard simplex
• Effective Pólya semi-positivity for non-negative polynomials on the simplex

Cites work

• A new bound for Pólya's theorem with applications to polynomials positive on polyhedra.
• Algorithms in real algebraic geometry
• An effective version of Pólya's theorem on positive definite forms
• Effective Łojasiewicz inequalities in semialgebraic geometry
• scientific article; zbMATH DE number 1601019 (Why is no real title available?)
• scientific article; zbMATH DE number 4029737 (Why is no real title available?)
• scientific article; zbMATH DE number 1296286 (Why is no real title available?)
• scientific article; zbMATH DE number 1057750 (Why is no real title available?)
• On sign conditions over real multivariate polynomials
• On the complexity of Schmüdgen's Positivstellensatz
• Solving zero-dimensional systems through the rational univariate representation
• The DMM bound: multivariate (aggregate) separation bounds

Cited in

(13)

• An effective bound on the gap between the control polytype and the graph of a real polynomial on a simplex
• On exact Reznick, Hilbert-Artin and Putinar's representations
• Separation bounds for polynomial systems
• Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\)
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Unconstrained Parametric Minimization of a Polynomial: Approximate and Exact
• A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
• Fixed points, Nash equilibria, and the existential theory of the reals
• Convergence of the simplicial rational Bernstein form
• Bounds on the number of steps of WDS required for checking the positivity of integral forms
• Bounding the radii of balls meeting every connected component of semi-algebraic sets
• Beyond the Existential Theory of the Reals
• On classifying continuous constraint satisfaction problems

Describes a project that uses

Uses Software

• ISOLATE

This page was built for publication: On the minimum of a positive polynomial over the standard simplex

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2269694)