Optimization Online


Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices

Samuel Burer (samuel-burer***at***uiowa.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

  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