Deciding positivity of multisymmetric polynomials

DOI10.1016/J.JSC.2015.10.001zbMATH Open1347.05244arXiv1409.2707OpenAlexW1527405697MaRDI QIDQ898286FDOQ898286

Authors: Paul Görlach, Cordian Riener, Tillmann Weisser 

Publication date: 8 December 2015

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

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.

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

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

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)

Cites Work

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

Cited In (6)

• 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
• On the positivity of symmetric polynomial functions. I: General results
• Quantum entanglement, symmetric nonnegative quadratic polynomials and moment problems
• On Nonnegativity of Symmetric Polynomials
• Symmetry Reduction to Optimize a Graph-based Polynomial From Queueing Theory

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)