Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices

Samuel Burer (samuel-bureruiowa.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 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.

Keywords: Semidefinite programming, sparsity, matrix

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

Citation: Department of Management Sciences, University of Iowa, May 2002. Revised October 2002, January 2003.

Download: [PDF]

Entry Submitted: 05/02/2002
Entry Accepted: 05/02/2002
Entry Last Modified: 01/16/2003

Modify/Update this entry