Deciding positivity of multisymmetric polynomials

DOI10.1016/J.JSC.2015.10.001MaRDI QIDQ898286zbMATH OpenOpenAlexFDO

Authors Paul Görlach, Cordian Riener, Tillmann Weisser

Publication date 8 December 2015

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.2707

algorithmic complexity convexity decison problems degree principle positivity

Symmetric functions and generalizations (05E05) Computational aspects and applications of commutative rings (13P99) Real algebraic and real-analytic geometry (14P99) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: The question how to certify non-negativity of a polynomial function lies at the heart of Real Algebra and also has important applications to Optimization. In this article we investigate the question of non-negativity in the context of multisymmetric polynomials. In this setting we generalize the characterization of non-negative symmetric polynomials by adapting the method of proof developed by the second author. One particular case where our results can be applied is the question of certifying that a (multi-)symmetric polynomial defines a convex function. As a direct corollary of our main result we are able to derive that in the case of (multi-)symmetric polynomials of a fixed degree testing for convexity can be done in a time which is polynomial in the number of variables. This is in sharp contrast to the general case, where it is known that testing for convexity is NP-hard already in the case of quartic polynomials.

Review text

A simple form of the half degree principle, discovered by \textit{V. Timofte} [J. Math. Anal. Appl. 284, No. 1, 174--190 (2003; Zbl 1031.05130)], says that nonnegativity on \(\mathbb{R}^n\) of a polynomial \(f\) of degree\(\geq 4\) in the ring \(\mathbb{R}[X_1,\dots,X_n]^{S_n}\) of symmetric polynomials, is guaranteed if it is nonnegative on all real \(n\)-tuples with not more than \( \deg f/2\) distinct components. A particularly nice proof of this was found by \textit{C. Riener} [J. Pure Appl. Algebra 216, No. 4, 850--856 (2012; Zbl 1242.05272)]. In the present paper, results of this type are found for multisymmetric polynomials. They are applied to give favorable upper bounds for the computational complexity of testing nonnegativity and convexity in the class of multisymmetric polynomials polynomials. In the general nonsymmetric case, these problems are NP-hard; see [\textit{A. A. Ahmadi} et al., Math. Program. 137, No. 1--2 (A), 453--476 (2013; Zbl 1274.90516)]. Let \(V=\mathbb{R}^n\) and denote by \(\mathbb{R}[V^k]\) the family of all real polynomials in \(nk\) variables named \(X_{11}, \dots, X_{nk}.\) Think of these as arranged of in an \(n\times k\) matrix. Then, a polynomial \(f\in \mathbb{R}[V^k] \) is \(k\)-symmetric if (after suitable renaming of its variables) it is invariant under permutations of the rows. These we denote by \(X_{i\cdot},\) while the columns are abbreviated \(X_{\cdot j},\) \(i=1,\dots,n; j=1,\dots,k.\) A monomial in \(\mathbb{R}[V^k]\) has the form \(X_{1\cdot }^{\alpha(1)} X_{2\cdot}^{\alpha(1)} \cdots X_{n\cdot}^{\alpha(n)},\) where \(\alpha(i)=(\alpha_1(i),\dots, \alpha_k(i))\in \mathbb{Z}_{\geq 0}^k\) and \(X_{i\cdot}^{\alpha(i)}=X_{i1}^{\alpha_1(i)} \cdots X_{ik}^{\alpha_k(i)}.\) Let \(w\in \mathbb{Z}_{\geq 1}^k.\) Then, the \(w\)-degree of the monomial is defined as \(\sum_{i=1}^n\sum_{j=1}^k w_j \alpha_j(i)\) and for \(f\in \mathbb{R}[V^k]\), \(\deg_w f\) is simply the maximum \(w\)-degree of its monomials. A special role among the \(k\)-symmetric polynomials is played by the polynomials \(p_{\alpha}=\text{sym}(X_{1.}^\alpha),\) where `sym' denotes the evident symmetrization operator. The \(p_\alpha\) are the natural generalization of the classical powersums to multiples of which they revert for \(k=1.\) Let \(N_d:=\{\alpha\in \mathbb{Z}_{\geq 0}: \alpha \cdot w \leq d\}.\) It can be shown, see [\textit{J. Dalbec}, Beitr. Algebra Geom. 40, No. 1, 27--51 (1999; Zbl 0953.05077)], that for a \(k\)-symmetric \(f\) of \(w\)-degree \(\leq d\) there exists a polynomial \(F\) such that \(f=F(\{p_{\alpha}\}_{\alpha \in N^d} ).\) Denote by \(A_m\) the set of matrices in \(\mathbb{R}^{n\times k}\) with at most \(m\) distinct rows. \(A_m\) is the union of less than \(n^m\) \(mk\)-dimensional subspaces of \(\mathbb{R}^{n\times k}.\) For \(r>0\), let \(B_r\) be the euclidean 0-centered ball of radius \(r\) in \(\mathbb{R}^{n\times k}\) and for \(f\in \mathbb{R}[V^k]\) let \(\kappa(f)\) be the smallest \(m\) such that for all \(r>0\), \(\min_{x\in A_m} f(x)=\min_{x\in B_r\cap A_m} f(x).\) The main theorem is Theorem 14: If \(f\in\mathbb{R}[V^k]^{S_n},\) and \(\deg_w f \leq d \geq \max\{2w_j:j=1,\dots,k\},\) then \(\kappa(f) \leq \prod_{j=1}^k \lfloor d/w_j \rfloor.\) The proof of this theorem uses above polynomial representation of \(f\) via the \(p_\alpha\) and gives in dependence of \(F\) often much better information. Furthermore, using the characterization of the \(A_{\kappa(f)}\) above, it follows that for the class of polynomials in \(\mathbb{R}[V^k]^{S_n},\) the complexity of testing positivity grows only polynomially in the number of variables. Subjecting a polynomial \(f\in \mathbb{R}[V^k]\) to the morphism defined by \(\varphi(X_{ij})=Y_j,\) one gets a polynomial in \(\mathbb{R}[Y_1,\dots,Y_k]\) whose monomials define \(k\)-tuples exponents. Letting \(E_f\) be the set of these k-tuples, one can deduce that if \(E_f\subset \text{conv}(0,a_1e_1,\dots,a_ke_k),\) (with rationals \(a_i\) and \(e_i\) the standard vectors) then \(\kappa(f)\leq \prod_{j=1}^k \lfloor a_j \rfloor,\) which is the number of lattice points in \([0,a_1-1]\times \cdots \times [0,a_k-1].\) The authors use this to give as their second main result a bound for \(\kappa(g_f)\) where \(g_f\) means the `quadratic' form associated to the Hessian matrix of \(f.\) (As the Hessian is a matrix whose entries are of degree up to \(d-2\), \(g_f\) is in fact a polynomial of degree up to \(d.\)) For example, a simple corollary is that if \(f\in\mathbb{R}[V^k]^{S_n},\) has (usual) degree \(d\), then \(\kappa(g_f) \leq 6^k (d-2)^k.\) Such bounds imply that the complexity of deciding convexity in the class of \(k\)-symmetric polynomial of degree \(\leq d\) grows polynomially in the number of variables.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Deciding positivity of multisymmetric polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898286)