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

zbMATH Keywords

convexitypositivityalgorithmic complexitydecison problemsdegree principle

Mathematics Subject Classification ID

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

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.

Recommendations

• Symmetric semi-algebraic sets and non-negativity of symmetric polynomials
• On algorithms testing positivity of real symmetric polynomials
• On the positivity of symmetric polynomial functions. I: General results
• On Nonnegativity of Symmetric Polynomials
• Certifying Polynomial Nonnegativity via Hyperbolic Optimization

Cites work

• scientific article; zbMATH DE number 1096865 (Why is no real title available?)
• scientific article; zbMATH DE number 1827070 (Why is no real title available?)
• Invariants of Finite Groups Generated by Reflections
• Multisymmetric functions
• NP-hardness of deciding convexity of quartic polynomials and related problems
• On the degree and half-degree principle for symmetric polynomials
• On the positivity of symmetric polynomial functions. I: General results
• Positive symmetric functions
• Real even symmetric ternary forms
• Some NP-complete problems in quadratic and nonlinear programming
• Symmetric semi-algebraic sets and non-negativity of symmetric polynomials
• The ring of multisymmetric functions.
• When is the algebra of multisymmetric polynomials generated by the elementary multisymmetric polynomials?

Cited in

(11)

• Symmetry reduction to optimize a graph-based polynomial from queueing theory
• Symmetric semi-algebraic sets and non-negativity of symmetric polynomials
• Test sets for nonnegativity of polynomials invariant under a finite reflection group
• On the degree and half-degree principle for symmetric polynomials
• Multi-degree bounds on the Betti numbers of real varieties and semi-algebraic sets and applications
• A fast numerical test of multivariate polynomial positiveness with applications.
• On the positivity of symmetric polynomial functions. I: General results
• Quantum entanglement, symmetric nonnegative quadratic polynomials and moment problems
• On algorithms testing positivity of real symmetric polynomials
• On Nonnegativity of Symmetric Polynomials
• Symmetries in polynomial optimization

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)