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:

 

Etienne de Klerk, Tilburg University, Netherlands

 

Renew SIAM · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube