Exploiting Sparsity in Semidefinite Programming via
Matrix Completion I: General Framework
Mituhiro Fukuda, Masakazu Kojima, Kazuo Murota and Kazuhide Nakata
A critical disadvantage of primal-dual interior-point methods against
dual interior-point methods for large scale SDPs (semidefinite
programs) has been that the primal positive semidefinite variable
matrix 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
variable matrix into an SDP having multiple but smaller size positive
semidefinite variable matrices 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.
Research Report B-358, Department of Mathematical and
Computing Sciences, Tokyo Institute of Technology,
Tokyo 152-8552, Japan. (Also issued as RIMS Preprint
No. 1264, Research Institute for Mathematical Sciences,
Kyoto University, Kyoto 606-8502, Japan.) December 1999.
Contact: [email protected]