Symmetry groups, semidefinite programs, and sums of squares

2002/11/28 by Karin Gatermann, Pablo A. Parrilo · 366 citations
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Algebra over a field #Algebraic number #Combinatorics #Discrete mathematics #Explained sum of squares #Formal Methods in Verification #Generalization #Invariant (physics) #Mathematical analysis #Mathematical optimization #Mathematics #Matrix (chemical analysis) #Matrix polynomial #Polynomial #Polynomial and algebraic computation #Polynomial matrix #Pure mathematics #Semidefinite programming #math.AC #math.OC #msc:13A50 #msc:14P99 #msc:26C05 #msc:68W30 #msc:90C22

paper · pdf · doi:10.1016/j.jpaa.2003.12.011

published in Journal of Pure and Applied Algebra 192(1-3), 95-128 (Elsevier BV) · 38 pages, submitted

arxiv created 2002/11/28 · openalex publication_date 2004/03/19 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

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.

Cited by

• Semidefinite programming relaxations for semialgebraic problems
• A Counterexample to the Optimality Conjecture in Convex Quantum Channel Optimization
• Convexity and SOS-Convexity of Sum of Separable and Biquadratic Quartic Polynomials and Optimization
• Tailoring Bell inequalities to the qudit toric code and self testing
• Exploiting Term Sparsity in Symmetry-Adapted Basis for Polynomial Optimization
• Characterizing the Universal Rigidity of Generic Tensegrities
• On symmetry adapted bases in trigonometric optimization
• Linear Programming Hierarchies Collapse under Symmetry
• Sum-of-squares decompositions for a family of CHSH-like inequalities and their application to self-testing
• 2-Coloring Cycles in One Round
• Engineering and Business Applications of Sum of Squares Polynomials
• Exactness in SDP relaxations of QCQPs: Theory and applications
• Computation of attractor dimension and maximal sums of Lyapunov exponents using polynomial optimization
• Computation of minimal periods for ordinary differential equations
• Symmetry in Turán Sums of Squares Polynomials from Flag Algebras
• Improving Efficiency and Scalability of Sum of Squares Optimization: Recent Advances and Limitations
• Polynomial Optimization via Random Projection and Consensus
• An Inexact Tensor-Train Primal-Dual Interior-Point Method for Semidefinite Programs
• Parallel Optimization of Polynomials for Large-scale Problems in Stability and Control
• On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• Perturbation Analysis for Matrix Joint Block Diagonalization
• Positive semidefinite approximations to the cone of copositive kernels
• Stochastic Optimal Control via Measure Relaxations
• Optimal Control of Hybrid Systems via Measure Relaxations
• Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis
• SOSOPT: A Toolbox for Polynomial Optimization
• On Flattenability of Graphs
• Enumeration of monochromatic three term arithmetic progressions in two-colorings of cyclic groups
• An Inequality for Circle Packings Proved by Semidefinite Programming
• Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming
• A Graph Partitioning Approach to Predict Patterns in Lateral Inhibition Systems
• A Semidefinite Representation for some Minimum Cardinality Problems
• Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
• Low Dimensional Test Sets for Nonnegativity of Even Symmetric Forms
• Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs
• Sum of Squares Method for Sensor Network Localization
• Group Symmetry and Covariance Regularization
• Quantum control of a single qubit
• Symmetric Extensions of Quantum States and Local Hidden Variable Theories
• Alternative SDP and SOCP approximations for polynomial optimization
• A Complete Characterization of the Gap between Convexity and SOS-Convexity

Related

• Symmetry in semidefinite programs
• Symbolic Computation with Symmetric Polynomials in Real Algebraic Geometry
• Symmetric Sums of Squares over k-Subset Hypercubes
• Column symmetric polynomials
• Lectures on Nonnegative Polynomials and Sums of Squares