Exploiting Algebraic Symmetry in Semidefinite Programs: Theory and Applications
Semidefinite Programming (SDP) may be seen as a generalization of Linear Programming (LP). In particular, one may extend interior point algorithms for LP to SDP, but it has proven much more difficult to exploit structure in the SDP data during computation.
We consider one specific type of structure in SDP data, namely where the data matrices are invariant under the action of a permutation group. Such problems arise in truss topology optimization, particle physics, coding theory, computational geometry, and graph theory.
We will give an overview of existing techniques to exploit this structure in the data. The basic idea is that we may assume that the optimal solution of the SDP lies in the commutant (centralizer ring) of the permutation group. For many applications, the centralizer ring allows a more economical representation than the entire feasible set.
To illustrate this technique, we will consider several applications, including:
- computing lower bounds on the crossing number of complete bipartite graphs
- computing the Lovász theta function for graphs with large symmetry groups
- truss topology optimization problems where the ground structure of nodes has symmetries
- quadratic assignment problems with group symmetric data
Etienne de Klerk, Tilburg University, Netherlands