A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs Using Positive Definite Matrix Completion

Kazuhide Nakata (knakatame.titech.ac.jp)
Makoto Yamashita (Makoto.Yamashitais.titech.ac.jp)
Katsuki Fujisawa (fujisawar.dendai.ac.jp)
Masakazu Kojima (kojimais.titech.ac.jp)

Abstract: A parallel computational method SDPARA-C is presented for SDPs (semidefinite programs). It combines two methods SDPARA and SDPA-C proposed by the authors who developed a software package SDPA. SDPARA is a parallel implementation of SDPA and it features parallel computation of the elements of the Schur complement equation system and a parallel Cholesky factorization of its coefficient matrix. SDPARA can effectively solve SDPs with a large number of equality constraints, however, it does not solve SDPs with a large scale matrix variable with similar effectiveness. SDPA-C is a primal-dual interior-point method using the positive definite matrix completion technique by Fukuda et al, and it performs effectively with SDPs with a large scale matrix variable, but not with a large number of equality constraints. SDPARA-C benefits from the strong performance of each of the two methods. Furthermore, SDPARA-C is designed to attain a high scalability by considering most of the expensive computations involved in the primal-dual interior-point method. Numerical experiments with the three parallel software packages SDPARA-C, SDPARA and PDSDP by Benson show that SDPARA-C efficiently solve SDPs with a large scale matrix variable as well as a large number of equality constraints with a small amount of memory.

Keywords: Semidefinite Program, Primal-Dual Interior-Point Method, Parallel Computation, Positive Definite Matrix Completion, Numerical Experiment, PC Cluster

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

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: Research Report B-398, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Meguro, Tokyo 152-8552. November 2003.

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 11/17/2003
Entry Accepted: 11/17/2003
Entry Last Modified: 11/17/2003

Modify/Update this entry