Preprocessing sparse semidefinite programs via matrix completion
Katsuki Fujisawa (fujisawar.dendai.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.
Entry Submitted: 03/16/2004
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|