Exploiting symmetries in SDP-relaxations for polynomial optimization

Abstract

In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semi definite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization problems, show how the degree principle for the symmetric group can be computationally exploited and also propose some methods to efficiently compute in the geometric quotient.

(v3) Minor revision. To appear in Math. of Operations Research

References in corpus (4)

• Symmetry groups, semidefinite programs, and sums of squares
• Symmetry in semidefinite programs
• On the degree and half degree principle for symmetric polynomials
• Invariant semidefinite programs

Cited by in corpus (17)

• Semidefinite programming relaxations for quantum correlations
• Sparse Noncommutative Polynomial Optimization
• Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization
• Optimization over trace polynomials
• Dimension-free entanglement detection in multipartite Werner states
• Sum-of-squares chordal decomposition of polynomial matrix inequalities
• Bounding the Distance to Unsafe Sets with Convex Optimization
• Certifying ground-state properties of quantum many-body systems
• Conic Optimization Theory: Convexification Techniques and Numerical Algorithms
• Exploiting Term Sparsity in Moment-SOS hierarchy for Dynamical Systems
• 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
• Optimizing hypergraph-based polynomials modeling job-occupancy in queueing with redundancy scheduling
• Symmetry reduction to optimize a graph-based polynomial from queueing theory
• Faster real root decision algorithm for symmetric polynomials
• On symmetry adapted bases in trigonometric optimization
• Symmetric Ideals and Invariant Hilbert Schemes