Exploiting special structure in semidefinite programming: A survey of theory and applications

Research output: Contribution to journalArticleScientificpeer-review

33 Citations (Scopus)

Abstract

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 survey three types of special structures in SDP data:

1. A common ‘chordal’ sparsity pattern of all the data matrices. This structure arises in applications in graph theory, and may also be used to deal with more general sparsity patterns in a heuristic way.

2. Low rank of all the data matrices. This structure is common in SDP relaxations of combinatorial optimization problems, and SDP approximations of polynomial optimization problems.

3. The situation where the data matrices are invariant under the action of a permutation group, or, more generally, where the data matrices belong to a low dimensional matrix algebra. 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 these structures in the data. Most of the paper will be devoted to the third situation, since it has received the least attention in the literature so far.
Original languageEnglish
Pages (from-to)1-10
JournalEuropean Journal of Operational Research
Volume201
Issue number1
Publication statusPublished - 2010

Fingerprint Dive into the research topics of 'Exploiting special structure in semidefinite programming: A survey of theory and applications'. Together they form a unique fingerprint.

Cite this