Mathematics – Commutative Algebra
Scientific paper
2002-11-28
Journal of Pure and Appl. Algebra, Vol. 192, No. 1-3, pp. 95-128, 2004
Mathematics
Commutative Algebra
38 pages, submitted
Scientific paper
10.1016/j.jpaa.2003.12.011
We investigate the representation of symmetric polynomials as a sum of squares. 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. This result is applied to semidefinite programs arising from the computation of sum of squares decompositions for multivariate polynomials. The results, reinterpreted from an invariant-theoretic viewpoint, provide a novel representation of a class of nonnegative symmetric polynomials. 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.
Gatermann Karin
Parrilo Pablo A.
No associations
LandOfFree
Symmetry groups, semidefinite programs, and sums of squares does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Symmetry groups, semidefinite programs, and sums of squares, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symmetry groups, semidefinite programs, and sums of squares will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-420089