Optimization Online


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

Etienne De Klerk (e.deklerk***at***uvt.nl)

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 structure 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.

Keywords: Semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 10/03/2008
Entry Accepted: 10/03/2008
Entry Last Modified: 01/21/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society