Preprocessing sparse semidefinite programs via matrix completion
Considering that preprocessing is an important phase in linear programing, it should be more systematically incorporated in semidefinite programing ( SDP) solvers. The conversion method proposed by the authors [Fukuda, M., Kojima, M., Murota, K. and Nakata, K., 2000, SIAM Journal on Optimization, 11, 647 - 674 and Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M. and Murota, K., 2003, Mathematical Programming ( Series B), 95, 303 - 327] is a preprocessing method for sparse SDPs based on matrix completion. This article proposed a new version of the conversion method, which employs a flop estimation function inside its heuristic procedure. Extensive numerical experiments are included showing the advantage of preprocessing by the conversion method for certain classes of very sparse SDPs.
preprocessing semidefinite programing matrix completion numerical experiments sparsity clique tree