Deciding positivity of multisymmetric polynomials. (May 2016)

• Record Type: Journal Article
• Authors: Görlach, Paul; Riener, Cordian; Weißer, Tillmann
• Is Part Of: Journal of symbolic computation. Volume 74(2016)
• Page Start: 603
• Page End: 616
• Publication Date: 2016-05
• Subjects: Multi-symmetric function -- Positivity -- Convexity; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.10.001
• Languages: English
• ISSNs: 0747-7171

Abstract

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 inTimofte (2003), Riener (2012) by adapting the method of proof developed inRiener (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 ).