- | ||||
|
![]()
|
Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
Samuel Burer (samuel-burer 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 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 | |
![]() |