Symmetry groups, semidefinite programs, and sums of squares

Karin Gatermann, Pablo A. ParriloJournal of Pure and Applied Algebra 2004 · DOI · arXiv

Abstract

This paper presents a robust framework for addressing the computational bottlenecks in large-scale optimization by exploiting mathematical symmetry. By integrating group representation theory with semidefinite programming (SDP), the authors demonstrate a method to decompose massive Sum of Squares (SOS) problems into smaller, independent sub-problems. This approach significantly reduces the "curse of dimensionality" associated with polynomial non-negativity certificates, leading to dramatic speedups and enhanced numerical stability.

Introduction

In fields such as control theory, robotics, and combinatorial optimization, a fundamental challenge is verifying the non-negativity of multivariate polynomials. Proving that a system is stable or that a cost function is always positive often requires demonstrating that a polynomial $p(x)$ is non-negative for all $x$. While this is generally an NP-hard problem, a common computational "shortcut" is to check if the polynomial can be expressed as a Sum of Squares (SOS). If $p(x) = \sum q_i(x)^2$, then $p(x)$ is guaranteed to be non-negative.

Finding an SOS decomposition is typically mapped to a Semidefinite Program (SDP). However, as the number of variables ($n$) or the degree of the polynomial ($d$) increases, the size of the matrices in the SDP grows combinatorially. For a dense polynomial, the matrix size is $\binom{n+d}{d}$. This scaling makes problems involving more than a few variables computationally infeasible for standard solvers. This paper addresses this limitation by leveraging the inherent symmetries often found in real-world polynomials.

Theoretical Framework: Symmetry and Convexity

The authors bridge the gap between group representation theory and convex optimization. Their methodology relies on the observation that many optimization problems possess symmetries—for instance, the objective function and constraints may remain invariant if variables are permuted or rotated.

The Reynolds Operator and Invariant SDPs

The authors formally define "invariant semidefinite programs" where the problem structure is preserved under the action of a finite group. A critical insight is that the feasible region of an SDP is a convex set. Because of this convexity, the authors prove that if any solution to an invariant SDP exists, a symmetric solution must also exist. By applying the Reynolds operator—an averaging process over the group action—the search space can be restricted to a much smaller "fixed-point" subspace without losing optimality.

Block Diagonalization via Schur’s Lemma

The core technical contribution is the systematic "shattering" of large matrices. Using Schur’s Lemma from representation theory, the authors show that a symmetric matrix can be transformed into a block-diagonal form. Instead of solving one monolithic matrix inequality, the problem is decomposed into several smaller, independent inequalities. This process acts like a prism, splitting a high-dimensional problem into its constituent "frequencies" (irreducible representations) that can be processed in parallel or simply more efficiently.

Integration with Invariant Theory

To further optimize the representation of symmetric polynomials, the authors utilize the Hironaka decomposition, which involves primary and secondary invariants. A key result of the paper is Theorem 6.2, which establishes that a symmetric SOS polynomial can be represented as a sum of inner products between SOS matrices and specific "invariant matrices" ($\Pi_i$) derived from the group's irreducible representations. This provides a structured way to construct the simplified SDP blocks directly from the group's algebraic properties.

Computational Results

To validate the framework, the authors tested the method on several historically difficult polynomial forms:

  • Robinson and Choi Forms: Classic polynomials used to study the gap between non-negative polynomials and SOS.
  • Shapiro and Shapiro Conjecture: Quartic forms in four variables exhibiting full symmetric group ($S_4$) symmetry.
  • Even Forms: Homogeneous polynomials related to the study of copositive matrices.

Scaling and Performance

The reduction in computational complexity is substantial. For example, in the case of an $S_4$ quartic polynomial, a standard $10 \times 10$ SDP with 20 variables was reduced to two coupled SDPs of sizes $4 \times 4$ and $3 \times 3$, using only 5 variables.

In higher-degree cases, the scaling is even more pronounced. For a degree 8 polynomial in 10 variables, the standard approach requires a massive $715 \times 715$ matrix. The symmetry-aware method breaks this down into one $55 \times 55$ block, forty-five $10 \times 10$ blocks, and 210 scalar ($1 \times 1$) constraints. This reduction not only speeds up computation but also improves numerical reliability, as smaller matrices are less susceptible to the precision issues that often plague SDP solvers when dealing with large-scale problems.

Conclusion and Future Work

By exploiting symmetry, the authors have turned the "curse of dimensionality" into a manageable algebraic task for a wide class of problems. While the current framework is limited to finite groups, it provides a clear roadmap for future extensions into continuous groups (such as $SO(n)$). The work also hints at deeper connections between these techniques and the Positivstellensatz on orbit spaces, suggesting that symmetry-aware optimization will remain a vital area of research for real algebraic geometry and its applications in engineering.

Summary updated

BibTeX
@article{gatermann2004symmetry,
  author = {Karin Gatermann and Pablo A. Parrilo},
  title = {{Symmetry groups, semidefinite programs, and sums of squares}},
  journal = {Journal of Pure and Applied Algebra},
  year = {2004},
  doi = {10.1016/j.jpaa.2003.12.011},
}
Figure