Symmetry groups, semidefinite programs, and sums of squares
arXiv:math/0211450 · doi:10.1016/j.jpaa.2003.12.011
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.
38 pages, submitted
Cited by in corpus (98)
- Stability and Robustness Analysis of Nonlinear Systems via Contraction Metrics and SOS Programming
- Sum-of-squares decompositions for a family of CHSH-like inequalities and their application to self-testing
- Local Hidden Variable Theories for Quantum States
- Fastest mixing Markov chain on graphs with symmetries
- Exploiting symmetries in SDP-relaxations for polynomial optimization
- Quantum Control of a Single Qubit
- Mutually unbiased bases and symmetric informationally complete measurements in Bell experiments
- Symmetry in semidefinite programs
- Improved bounds for the crossing numbers of K_m,n and K_n
- A Complete Characterization of the Gap between Convexity and SOS-Convexity
- Semidefinite descriptions of the convex hull of rotation matrices
- Enabling computation of correlation bounds for finite-dimensional quantum systems via symmetrisation
- Semidefinite programming relaxations for quantum correlations
- Algorithms for Highly Symmetric Linear and Integer Programs
- A convex polynomial that is not sos-convex
- Bounds on mean energy in the Kuramoto-Sivashinsky equation computed using semidefinite programming
- On semidefinite programming relaxations of the traveling salesman problem
- Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials
- SOSOPT: A Toolbox for Polynomial Optimization
- Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization
- Invariant semidefinite programs
- Bounding averages rigorously using semidefinite programming: mean moments of the Lorenz system
- Experimental robust self-testing of the state generated by a quantum network
- Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis
- Symmetric extension in two-way quantum key distribution
- Quantum key distribution rates from semidefinite programming
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming
- Exploiting Symmetry in Integer Convex Optimization using Core Points
- Quantum-Inspired Hierarchy for Rank-Constrained Optimization
- New bounds for the max--cut and chromatic number of a graph
- New upper bounds for the density of translative packings of three-dimensional convex bodies with tetrahedral symmetry
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Solving Large-Scale Robust Stability Problems by Exploiting the Parallel Structure of Polya's Theorem
- Exploiting Sparsity in the Coefficient Matching Conditions in Sum-of-Squares Programming using ADMM
- Sum-of-squares chordal decomposition of polynomial matrix inequalities
- Fast ADMM for sum-of-squares programs using partial orthogonality
- Block Factor-width-two Matrices and Their Applications to Semidefinite and Sum-of-squares Optimization
- Dimension reduction for semidefinite programs via Jordan algebras
- Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization
- Heat transport bounds for a truncated model of Rayleigh-Bénard convection via polynomial optimization
- RepLAB: a computational/numerical approach to representation theory
- Improved lower bounds on book crossing numbers of complete graphs
- Adaptive advantage in entanglement-assisted communications
- A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
- Semidefinite programming and eigenvalue bounds for the graph partition problem
- A geometric inequality for circle packings
- Lecture notes: Semidefinite programs and harmonic analysis
- Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials
- Certificates of quantum many-body properties assisted by machine learning
- Improved lower bounds for the 2-page crossing numbers of K_{m,n} and K_n via semidefinite programming
- Alternative SDP and SOCP Approximations for Polynomial Optimization
- SymDPoly: symmetry-adapted moment relaxations for noncommutative polynomial optimization
- Moment methods in energy minimization: New bounds for Riesz minimal energy problems
- Failure of the simultaneous block diagonalization technique applied to complete and cluster synchronization of random networks
- Recht-Ré Noncommutative Arithmetic-Geometric Mean Conjecture is False
- Decomposition and Completion of Sum-of-Squares Matrices
- Bound entangled states are useful in prepare-and-measure scenarios
- A convex form that is not a sum of squares
- Solving clustered low-rank semidefinite programs arising from polynomial optimization
- Engineering and Business Applications of Sum of Squares Polynomials
- Optimizing hypergraph-based polynomials modeling job-occupancy in queueing with redundancy scheduling
- Symmetry reduction to optimize a graph-based polynomial from queueing theory
- Quantum Bell inequalities from Information Causality -- tight for Macroscopic Locality
- New bounds for truthful scheduling on two unrelated selfish machines
- Positive semidefinite approximations to the cone of copositive kernels
- On Symmetry Groups of Some Quadratic Programming Problems
- Improving Efficiency and Scalability of Sum of Squares Optimization: Recent Advances and Limitations
- Polynomial decompositions with invariance and positivity inspired by tensors
- Perturbation Analysis for Matrix Joint Block Diagonalization
- Automorphisms of rank-one generated hyperbolicity cones and their derivative relaxations
- On symmetry adapted bases in trigonometric optimization
- Radii minimal projections of polytopes and constrained optimization of symmetric polynomials
- Faster real root decision algorithm for symmetric polynomials
- Low Dimensional Test Sets for Nonnegativity of Even Symmetric Forms
- Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
- On Flattenability of Graphs
- Characterizing the Universal Rigidity of Generic Tensegrities
- An Algebraic Approach to Non-Orthogonal General Joint Block Diagonalization
- Enumeration of monochromatic three term arithmetic progressions in two-colorings of cyclic groups
- Solving General Joint Block Diagonalization Problem via Linearly Independent Eigenvectors of a Matrix Polynomial
- A Semidefinite Representation for some Minimum Cardinality Problems
- Semidefinite Relaxations of Products of Nonnegative Forms on the Sphere
- Multiplicity of nontrivial zeros of primitive L-functions via higher-level correlations
- Group Symmetry and Covariance Regularization
- Mutually unbiased bases: polynomial optimization and symmetry
- Parallel Optimization of Polynomials for Large-scale Problems in Stability and Control
- Enumeration of three term arithmetic progressions in fixed density sets
- A method for computing lowest eigenvalues of symmetric polynomial differential operators by semidefinite programming
- Sums of squares and moment problems in equivariant situations
- Sum of Squares Method for Sensor Network Localization
- Semidefinite programming and linear equations vs. homomorphism problems
- Two results on the Convex Algebraic Geometry of sets with continuous symmetries
- Additive and Multiplicative Coinvariant Spaces of Weyl Groups in the Light of Harmonics and Graded Transfer
- Quantum Entanglement, Symmetric Nonnegative Quadratic Polynomials and Moment Problems
- Exactness in SDP relaxations of QCQPs: Theory and applications
- A Graph Partitioning Approach to Predict Patterns in Lateral Inhibition Systems
- On a polynomial positivity question of Collins, Dykema, and Torres-Ayala related to the Bessis-Moussa-Villani Conjecture