Deciding positivity of multisymmetric polynomials

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 given in Timofte (2003), Riener (2012) by adapting the method of proof developed in Riener (2013). 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 deduce that in the case of a fixed degree it is possible to derive a method to test for convexity which makes use of the special structure of (multi-)symmetric polynomials. In particular it follows that we are able to drastically simplify the algorithmic complexity of this question in the presence of symmetry. This is not to be expected in the general (i.e. non-symmetric) case, where it is known that testing for convexity is NP-hard already in the case of polynomials of degree 4 (Ahmadi et al., 2013).