Preprocessing sparse semidefinite programs via matrix completion

Katsuki Fujisawa (fujisawar.dendai.ac.jp)
Mituhiro Fukuda (mituhirocims.nyu.edu)
Kazuhide Nakata (knakatame.titech.ac.jp)

Abstract: 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.

Keywords: semidefinite programming, preprocessing, sparsity, matrix completion, clique tree, numerical experiments

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: 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.

Download: [Compressed Postscript][PDF]

Entry Submitted: 03/16/2004
Entry Accepted: 03/16/2004
Entry Last Modified: 07/02/2004

Modify/Update this entry