Optimization Online


Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs

Makoto Yamashita (Makoto.Yamashita***at***ie.kanagawa-u.ac.jp)
Katsuki Fujisawa (fujisawa***at***rnc.r.dendai.ac.jp)
Mituhiro Fukuda (mituhiro***at***is.titech.ac.jp)
Masakazu Kojima (kojima***at***is.titech.ac.jp)
Kazuhide Nakata (knakata***at***me.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society