Name
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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1137/S105262340240851X | SIAM Journal on Optimization |
Keywords | Field | DocType |
existing algorithm,new search direction,initial duality gap,existing implementation,duality gap,partial symmetric matrix,partial positive semidefinite matrices,primal-dual path-following algorithm,semidefinite programming,partial positive semidefinite matrix,sdp problem,proposed algorithm,symmetric matrices,sparsity | Discrete mathematics,Mathematical optimization,Combinatorics,Duality gap,Quadratically constrained quadratic program,Matrix completion,Matrix (mathematics),Positive-definite matrix,Large margin nearest neighbor,Semidefinite embedding,Semidefinite programming,Mathematics | Journal |
Volume | Issue | ISSN |
14 | 1 | 1052-6234 |
Citations | PageRank | References |
18 | 1.30 | 18 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Burer | 1 | 1148 | 73.09 |