Optimization Online


Coercive polynomials and their Newton polytopes

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

Abstract: Many interesting properties of polynomials are closely related to the geometry of their Newton polytopes. In this article we analyze the coercivity on $\mathbb{R}^n$ of multivariate polynomials $f\in \mathbb{R}[x]$ in terms of their Newton polytopes. In fact, we introduce the broad class of so-called gem regular polynomials and characterize their coercivity via conditions imposed on the vertex set of their Newton polytopes. These conditions solely contain information about the geometry of the vertex set of the Newton polytope, as well as sign conditions on the corresponding polynomial coefficients. For all other polynomials, the so-called gem irregular polynomials, we introduce sufficient conditions for coercivity based on those from the regular case. For some special cases of gem irregular polynomials we establish necessary conditions for coercivity, too. Using our techniques, the problem of deciding the coercivity of a polynomial can be reduced to the analysis of its Newton polytope. We relate our results to the context of the polynomial optimization theory and the existing literature therein, and we illustrate our results with several examples.

Keywords: Newton polytope, coercivity, polynomial optimization, non-compact semi-algebraic sets

Category 1: Global Optimization (Theory )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: SIAM Journal on Optimization, Vol. 25 (2015), 1542-1570.


Entry Submitted: 08/02/2014
Entry Accepted: 08/03/2014
Entry Last Modified: 08/07/2015

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