A bound on the minimum of a real positive polynomial over the standard simplex

2009/02/19 by Saugata Basu, Basu, Saugata, Richard Leroy +4
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #cs.SC #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.0902.3304

arxiv created 2009/02/19 · openalex publication_date 2009/02/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of bounding away from 0 the minimum value m taken by a polynomial P of Z[X₁,...,X_k] over the standard simplex, assuming that m>0. Recent algorithmic developments in real algebraic geometry enable us to obtain a positive lower bound on m in terms of the dimension k, the degree d and the bitsize of the coefficients of P. The bound is explicit, and obtained without any extra assumption on P, in contrast with previous results reported in the literature.

Related

• On the minimum of a positive polynomial over the standard simplex
• Deciding lower-boundedness of polynomials
• A refined error analysis for fixed-degree polynomial optimization over the simplex
• Upper Bounds on Resolvent Degree via Sylvester's Obliteration Algorithm
• Polynomial minimum root separation