- | ||||
|
![]()
|
A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs Using Positive Definite Matrix Completion
Kazuhide Nakata (knakata 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 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |