Symmetry in semidefinite programs

Abstract

This paper is a tutorial in a general and explicit procedure to simplify semidefinite programs which are invariant under the action of a symmetry group. The procedure is based on basic notions of representation theory of finite groups. As an example we derive the block diagonalization of the Terwilliger algebra of the binary Hamming scheme in this framework. Here its connection to the orthogonal Hahn and Krawtchouk polynomials becomes visible.

10 pages (v3) minor changes, to appear in Linear Algebra and Its Applications

References in corpus (2)

• Symmetry groups, semidefinite programs, and sums of squares
• New upper bounds for kissing numbers from semidefinite programming

Cited by in corpus (22)

• Symmetries, Cluster Synchronization, and Isolated Desynchronization in Complex Networks
• Exploiting symmetries in SDP-relaxations for polynomial optimization
• Commutative association schemes
• Invariant semidefinite programs
• Quantum-Inspired Hierarchy for Rank-Constrained Optimization
• Semidefinite programming, harmonic analysis and coding theory
• Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization
• Dimension reduction for semidefinite programs via Jordan algebras
• Bounds for projective codes from semidefinite programming
• RepLAB: a computational/numerical approach to representation theory
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• Lecture notes: Semidefinite programs and harmonic analysis
• Block diagonalization for algebra's associated with block codes
• Symmetry reduction to optimize a graph-based polynomial from queueing theory
• Automorphisms of rank-one generated hyperbolicity cones and their derivative relaxations
• On symmetry adapted bases in trigonometric optimization
• Semidefinite programming bounds for error-correcting codes
• Tight relative $t$-designs on two shells in hypercubes, and Hahn and Hermite polynomials
• On a polynomial positivity question of Collins, Dykema, and Torres-Ayala related to the Bessis-Moussa-Villani Conjecture
• Group Symmetry and Covariance Regularization
• Two results on the Convex Algebraic Geometry of sets with continuous symmetries
• Certifying Numerical Decompositions of Compact Group Representations