Optimization Online


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

Tomas Bajbar (bajbar***at***kit.edu)
Oliver Stein (stein***at***kit.edu)

Abstract: 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.

Keywords: Newton polytope, coercivity, stability, order of growth, error bound, convenient polynomials.

Category 1: Global Optimization (Theory )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: Optimization, 2018, DOI 10.1080/02331934.2018.1426585


Entry Submitted: 10/13/2015
Entry Accepted: 10/13/2015
Entry Last Modified: 01/19/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society