Coercive polynomials: Stability, order of growth, and Newton polytopes

In this article we introduce a stability concept for the coercivity of multivariate polynomials $f \in \mathbb{R}[x]$. In particular, we consider perturbations of $f$ by polynomials up to the so-called degree of stable coercivity, and we analyze this stability concept in terms of the corresponding Newton polytopes at infinity. For coercive polynomials $f \in \mathbb{R}[x]$ we also introduce the order of coercivity as a measure expressing the order of growth of $f$, and we identify a broad class of multivariate polynomials $f \in \mathbb{R}[x]$ for which the order of coercivity and the degree of stable coercivity coincide. For these polynomials we give a geometric interpretation of this phenomenon in terms of their Newton polytopes at infinity, which we call the degree of convenience. Using our techniques, the problem of determining the degree of stable coercivity or the order of coercivity of a multivariate polynomial can often be reduced to the analysis of its Newton polytope at infinity. We relate our results to the existing literature and we illustrate them with some examples. As applications we show that the gradient maps corresponding to a broad class of polynomials are always surjective, we establish H\"older type global error bounds for such polynomials, and we link our results to the existence of solutions in the calculus of variations.


Optimization, 2018, DOI 10.1080/02331934.2018.1426585