Name
Title | ||
|---|---|---|
Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework |
Abstract | ||
|---|---|---|
A critical disadvantage of primal-dual interior-point methods compared to dual interior-point methods for large scale semidefinite programs (SDPs) has been that the primal positive semidefinite matrix variable becomes fully dense in general even when all data matrices are sparse. Based on some fundamental results about positive semidefinite matrix completion, this article proposes a general method of exploiting the aggregate sparsity pattern over all data matrices to overcome this disadvantage. Our method is used in two ways. One is a conversion of a sparse SDP having a large scale positive semidefinite matrix variable into an SDP having multiple but smaller positive semidefinite matrix variables to which we can effectively apply any interior-point method for SDPs employing a standard block-diagonal matrix data structure. The other way is an incorporation of our method into primal-dual interior-point methods which we can apply directly to a given SDP. In Part II of this article, we will investigate an implementation of such a primal-dual interior-point method based on positive definite matrix completion, and report some numerical results. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1137/S1052623400366218 | SIAM Journal on Optimization |
Keywords | Field | DocType |
dual interior-point method,positive semidefinite matrix completion,matrix completion,positive semidefinite matrix variable,standard block-diagonal matrix data,semidefinite programming,primal-dual interior-point method,positive definite matrix completion,primal positive semidefinite matrix,exploiting sparsity,general framework,matrix completion problem,chordal graph,smaller positive semidefinite matrix,general method,data matrix,data structure,positive definite matrix,positive semidefinite matrix,interior point method | Discrete mathematics,Sparse PCA,Mathematical optimization,Matrix completion,Quadratically constrained quadratic program,Matrix (mathematics),Positive-definite matrix,Large margin nearest neighbor,Semidefinite embedding,Mathematics,Semidefinite programming | Journal |
Volume | Issue | ISSN |
11 | 3 | 1052-6234 |
Citations | PageRank | References |
103 | 9.70 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mituhiro Fukuda | 1 | 197 | 18.59 |
| Masakazu Kojima | 2 | 1603 | 222.51 |
| Kazuo Murota | 3 | 975 | 133.88 |
| Kazuhide Nakata | 4 | 216 | 24.12 |