Journal
JOURNAL OF PURE AND APPLIED ALGEBRA
Volume 192, Issue 1-3, Pages 95-128Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.jpaa.2003.12.011
Keywords
-
Categories
Ask authors/readers for more resources
We investigate the representation of multivariate symmetric polynomials as sum of squares, as well as the effective computation of this decomposition. Since this task is solved using semidefinite programming tools we explore the geometric, algebraic, and computational implications of the presence of discrete symmetries in semidefinite programs. It is shown that symmetry exploitation allows a significant reduction in both matrix size and number of decision variables. The results, reinterpreted from an invariant-theoretic viewpoint, provide a novel representation of a class of nonnegative symmetric polynomials. For this, we introduce a common generalization of sum of squares polynomials and positive semidefinite matrices, termed sum of squares matrices. The main theorem states that an invariant sum of squares polynomial is a sum of inner products of pairs of matrices, whose entries are invariant polynomials. In these pairs, one of the matrices is computed based on the real irreducible representations of the group, and the other is a sum of squares matrix. The reduction techniques enable the numerical solution of large-scale instances, otherwise computationally infeasible to solve. (C) 2003 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available