Optimization Online


On Newton(like) inequalities for multivariate homogeneous polynomials

Leonid Gurvits(gurvits***at***lanl.gov)

Abstract: Let $p(x_1,...,x_m) = \sum_{r_1 + \cdots + r_m = n} a_{r_1,...,r_m} \prod_{1 \leq i \leq m } x_i^{r_{i}}$ be a homogeneous polynomial of degree $n$ in $m$ variables. We call such polynomial {\bf H-Stable} if $p(z_1,...,z_m) \neq 0$ provided that the real parts $Re(z_i) > 0: 1 \leq i \leq m$. It can be assumed WLOG that the coefficients $a_{r_1,...,r_m} := a_{R} \geq 0$.\\ This notion from {\it Control Theory} is closely related to the notion of {\it Hyperbolicity} intensively used in the {\it PDE} theory.\\ Let $R_0; R_1,...,R_k$ are integer vectors and $R_0 = \sum_{1 \leq j \leq k} a_j R_j$, where the real numbers $a_j \geq 0: 1 \leq i \leq k$ and $\sum_{1 \leq j \leq k} a_j = 1$. We define, for an integer vector $R = (r_1,...,r_m)$, $R! =: \prod_{1 \leq i \leq m } r_{i}!$.\\ We prove that $\log(a_{R} R!) \geq \sum_{1 \leq j \leq k} a_j \log(a_{R} R_{j}!) - n \alpha_n$, where $\frac{1}{2} \log(2) \leq \alpha_n \leq \log(\frac{n^n}{n!})$ and get better bounds on $\alpha_n$ for sparse polynomials. We relax a notion of {\bf H-Stability} by introducing two classes of homogeneous polynomials: Alexandrov-Fenchel polynomials and Strongly Log-Concave polynomials, prove analogous inequalities for those classes and use them to prove $L$-convexity of the supports of polynomials from those classes.\\ We also present a new view on the standard, i.e. when $m =2$, Newton inequalities and pose some open problems. Our results provide new necessary conditions for {\bf H-Stability} and can be used for the identification of multivariate stable linear system, i.e. for the interpolation of {\bf H-Stable} polynomials.

Keywords: polynomial, log-concavity, matroid

Category 1: Combinatorial Optimization

Citation: MTNS-2008 accepted paper

Download: [PDF]

Entry Submitted: 06/04/2008
Entry Accepted: 06/05/2008
Entry Last Modified: 06/04/2008

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 Programming Society