Polynomial optimization—finding the global minimum of a polynomial subject to polynomial constraints—is a cornerstone of modern computational science, yet it remains notoriously difficult (NP-hard). The standard approach, the Lasserre hierarchy, transforms these problems into a sequence of Semidefinite Programs (SDPs) that provide increasingly tight lower bounds. However, this method faces a "curse of dimensionality": for a problem with $n$ variables and a relaxation of order $k$, the matrix size grows at $O(n^k)$.
This foundational 2012 paper provides a roadmap for breaking this curse by leveraging the mathematical power of symmetry.
The Challenge: Scaling the Lasserre Hierarchy
The primary bottleneck in polynomial optimization is the size of the "moment matrices" generated by the Lasserre hierarchy. As the number of variables $n$ increases, these matrices become computationally intractable for even the most advanced solvers. The authors ask a critical question: If a problem is symmetric—for instance, if swapping variables doesn't change the objective or constraints—can we simplify the mathematics before the solver even starts?
Methods for Symmetry Exploitation
The researchers propose three primary strategies to reduce computational complexity:
1. Symmetry-Adapted Block Decomposition
Using group representation theory, the authors demonstrate that large moment matrices can be decomposed into a block-diagonal structure. Instead of solving one massive matrix inequality, the problem is broken into several much smaller ones. For the symmetric group $S_n$ (all permutations of variables), they utilize a specialized basis called generalized Specht polynomials. These polynomials are indexed by combinatorial objects known as Young Tableaux.
2. The Degree Principle
Based on the work of Timofte, this principle suggests that the minimum of a symmetric polynomial of degree $d$ can be found by examining points where the number of distinct variable values is small (proportional to $d$, not $n$). This allows an $n$-variable problem to be reduced to a set of problems with significantly fewer variables.
3. Orbit Space Approach
The authors map the optimization problem into an "orbit space"—a lower-dimensional geometric quotient where each point represents an entire set of symmetric points. This transformation results in a Polynomial Matrix Inequality (PMI), which can often lower the effective degree of the polynomials involved.
Key Insights and Results
- Independence from $n$: The authors prove that for the symmetric group $S_n$, once the number of variables $n$ exceeds twice the relaxation order ($n \ge 2k$), the number and size of the blocks in the SDP stop growing. This implies that a 1,000-variable symmetric problem could potentially be solved with the same computational effort as a 10-variable one.
- Finite Convergence for Quartics: For symmetric polynomials of degree 4, the degree principle allows for a reduction to two-variable problems that can be solved exactly using Sum of Squares (SOS) methods, guaranteeing finite convergence to the global minimum.
- Computational Speedup: In practical examples, exploiting symmetry (such as the cyclic group $C_4$) can reduce a $5 \times 5$ matrix constraint into four diagonal blocks, significantly easing the solver's workload.
Conclusion
The paper successfully unifies representation theory, invariant theory, and real algebraic geometry into a cohesive framework. While the pre-computation required for block decomposition is non-trivial and often requires specialized algebraic software like GAP, the theoretical speedups are immense. Future work focuses on automating these "manual" algebraic setups and generalizing the degree principle to a wider array of symmetry groups.
This summary is based on the 2012 paper by researchers from the University of Konstanz, Goethe-Universität, Umeå University, and LAAS-CNRS.
Summary updated