Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs

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.


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



View Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs