Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs

Makoto Yamashita (Makoto.Yamashitaie.kanagawa-u.ac.jp)
Katsuki Fujisawa (fujisawarnc.r.dendai.ac.jp)
Mituhiro Fukuda (mituhirois.titech.ac.jp)
Masakazu Kojima (kojimais.titech.ac.jp)
Kazuhide Nakata (knakatame.titech.ac.jp)

Abstract: The Semidefinite Program (SDP) is a fundamental problem in mathematical programming. It covers a wide range of applications, such as combinatorial optimization, control theory, polynomial optimization, and quantum chemistry. Solving extremely large-scale SDPs which could not be solved before is a significant work to open up a new vista of future applications of SDPs. Our two software packages SDPARA and SDPARA-C based on strong parallel computation and efficient algorithms have a high potential to solve large-scale SDPs and to accomplish the work. The SDPARA (SemiDefinite Programming Algorithm paRAllel version) is designed for general large SDPs, while the SDPARA-C (SDPARA with the positive definite matrix Completion) is appropriate for sparse large-scale SDPs arising from combinatorial optimization. The first sections of this paper serves as a user guide of the packages, and then some details on the primal-dual interior-point method and the positive definite matrix completion clarify their sophisticated techniques to enhance the benefits of parallel computation. Numerical results are also provided to show their high performance.

Keywords: SemiDefinite Programs, Parallel Computation, Primal-Dual Interior-Point Methods, Positive Semidefinite Completion

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

Citation: B-415, Tokyo Institute of Technology, 2-12-1, Oh-okayama, Meguro-ku, Tokyo, Japan, March 2005

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

Entry Submitted: 03/14/2005
Entry Accepted: 03/14/2005
Entry Last Modified: 03/17/2005

Modify/Update this entry