Symmetry groups, semidefinite programs, and sums of squares
By Karin Gatermann, Pablo A. Parrilo. 2002
409 citations recorded by the source corpus.
Abstract 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.
Subfields: Computational Theory and Mathematics, Numerical Analysis
View Paper: https://www.semanticscholar.org/paper/019dbff54a8f07682e9f18ea896bf0207216da81
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Stephen Prajna
- I. Itenberg
- Didier Henrion
- Antonis Papachristodoulou
- Arnold Neumaier
- Viatcheslav Kharlamov
- Stephen P. Boyd
- Eugenii Shustin
In Numerical Analysis
- Stephen Prajna
- Antonis Papachristodoulou
- Didier Henrion
- Arnold Neumaier
- Stephen P. Boyd
- Kazuo Murota
- Takanori Maehara
- Fen Wu
Citations in the corpus
- Distributed average consensus with least-mean-square deviation (2007, background): “In the first line, we use the fact that if a symmetric matrix X depends on a parameter t, then *X −1 *t = − X −1 *X *t X”
- Detecting global optimality and extracting solutions in GloptiPoly (2003, methodology): “This can be seen as a (heuristic) alternative to the (systematic) algebraic reduction techniques of [7].”
- Exploiting group symmetry in truss topology optimization (2009, methodology): “This is in the spirit of work by Schrijver (1979), Gatermann and Parrilo (2004) , de Klerk et al. (2006, 2007), and others, who have shown how ‘group symmetric’ SDP problems may be reduced in size using representation theory.”
- Complete search in continuous global optimization and constraint satisfaction (2004, background): “There are significant applications in cluster optimization (The Cambridge Cluster Database 1997), packing problems, and the optimal design of experiments (Sloane 2003).”
- A numerical algorithm for block-diagonal decomposition of matrix *-algebras with general irreducible components (2010, methodology): “Both frameworks have been utilized in the literature [1, 4, 5, 6, 7] cited above.”
- Real algebraic geometry (2013, methodology): “precise description of how the construction can be performed algorithmically can be found in [17].”
- Nonlinear control synthesis by sum of squares optimization: a Lyapunov-based approach (2004, background): “A special case for which this implication holds is when n =1 [ 7 ].”