  


Exploiting special structure in semidefinite programming: a survey of theory and applications
Etienne De Klerk (e.deklerkuvt.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 (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 10/03/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  