Preprocessing sparse semidefinite programs via matrix completion

Considering that preprocessing is an important phase in linear programming, it should be systematically more incorporated in semidefinite programming solvers. The conversion method proposed by the authors (SIAM Journal on Optimization, vol.~11, pp.~647--674, 2000, and Mathematical Programming, Series B, vol.~95, pp.~303--327, 2003) is a preprocessing of sparse semidefinite programs 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 very sparse semidefinite programs of certain classes.


IMA Preprint Series \# 1969, Institute for Mathematics and its Applications, University of Minnesota, 514 Vincent Hall, 206 Church Street S. E., Minneapolis, MN 55455-0436 USA, and also issued as Research Report B-401, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-okayama Meguro, Tokyo, 152-8552, Japan, March 2004, revised July 2004.



View Preprocessing sparse semidefinite programs via matrix completion