  


Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
Samuel Burer (samuelbureruiowa.edu) Abstract: We build upon the work of Fukuda et al.\ \cite{FuKoMuNa01} and Nakata et al.\ \cite{NaFuFuKoMu01}, in which the theory of partial positive semidefinite matrices has been applied to the semidefinite programming (SDP) problem as a technique for exploiting sparsity in the data. In contrast to their work, which improves an existing algorithm that is based on the HRVW/KSH/M search direction, we present a primaldual pathfollowing algorithm that is based on a new search direction, which, roughly speaking, is defined completely within the space of partial symmetric matrices. We show that the proposed algorithm computes a primaldual solution to the SDP problem having duality gap less than a fraction $\varepsilon > 0$ of the initial duality gap in ${\cal O}(n \log(\varepsilon^{1}))$ iterations, where $n$ is the size of the matrices involved. Moreover, we present computational results showing that the algorithm possesses several advantages over other existing implementations. Keywords: Semidefinite programming, sparsity, matrix Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Department of Management Sciences, University of Iowa, May 2002. Revised October 2002, January 2003. Download: [PDF] Entry Submitted: 05/02/2002 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  