Fast implementation for semidefinite programs with positive matrix completion

Solving semidefinite programs (SDP) in a short time is the key to managing various mathematical optimization problems in practical time. The matrix-completion primal-dual interior-point method (MC-PDIPM) extracts a structural sparsity of input SDP by factorizing the variable matrices, and it shrinks the computation time. In this paper, we propose a new factorization based on the inverse of the variable matrix to enhance the performance of the MC-PDIPM. We also combine multithreaded parallel computing to resolve the major bottlenecks in the MC-PDIPM. The numerical results show that the new factorization and the multithreaded computing successfully reduce the computation time for the SDPs that posses the structural sparsity.

Citation

Research Report B-474, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology

Article

Download

View Fast implementation for semidefinite programs with positive matrix completion