A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs Using Positive Definite Matrix Completion
Kazuhide Nakata (knakatame.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.
Entry Submitted: 11/17/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|