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 primal-dual path-following 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 primal-dual 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.
Citation
Department of Management Sciences, University of Iowa, May 2002. Revised October 2002, January 2003.