Journal article
Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
SIAM journal on optimization, Vol.14(1), pp.139-172
01/01/2003
DOI: 10.1137/S105262340240851X
Abstract
We build upon the work of Fukuda et al. [SIAM J. Optim., 11 (2001), pp. 647--674] and Nakata et al. [Math. Program., 95 (2003), pp. 303--327], in which the theory of partial positive semidefinite matrices was applied to the semidefinite programming (SDP) problem as a technique for exploiting sparsity in the data. In contrast to their work, which improved an existing algorithm based on a standard 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.
Details
- Title: Subtitle
- Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
- Creators
- Samuel Burer - University of Iowa
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.14(1), pp.139-172
- Publisher
- Society for Industrial and Applied Mathematics
- DOI
- 10.1137/S105262340240851X
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Language
- English
- Date published
- 01/01/2003
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380452002771