Optimization Online


Parallel solver for semidefinite programming problem having sparse Schur complement matrix

Makoto Yamashita(Makoto.Yamashita***at***is.titech.ac.jp)
Katsuki Fujisawa(fujisawa***at***indsys.chuo-u.ac.jp)
Mituhiro Fukuda(mituhiro***at***is.titech.ac.jp)
Kazuhide Nakata(nakata.k.ac***at***m.titech.ac.jp)
Maho Nakata(maho***at***riken.jp)

Abstract: SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical programming. SDP provides a practical computation framework for many research fields. Some applications, however, require solving large-scale SDPs whose size exceeds the capacity of a single processor in terms of computational time and available memory. SDPARA (SemiDefinite Programming Algorithm paRAllel version) developed by Yamashita et al. was designed to solve such large-scale SDPs. Its parallel performance is remarkable for general SDPs in most cases. However, the parallel implementation is less successful in some sparse SDPs from the latest applications such as for Polynomial Optimization Problems (POPs) or Sensor Network Location (SNL) problems, since the previous SDPARA can not directly handle sparse Schur complement matrices (SCMs). In this paper, we focus on the sparsity of the SCM and propose new parallel implementations, the formula-cost-based distribution, and the replacement of the dense Cholesky factorization. Through numerical results, we confirm that these features are keys to solve SDPs having sparse SCMs faster on parallel computer systems, and they are further enhanced by multi-threading. In fact, SDPARA is implemented in order to explore parallelism in two fronts: MPI-based and multi-threading of CPU cores. The new SDPARA attains a good scalability in general, and found solutions of extremely large-scale SDPs arising from POPs which other solvers could not obtain before.

Keywords: SemiDefinite Programming, Parallel Computing, Primal-Dual Interior-Point Methods

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

Citation: Research Report B-463, Dept. of Math. and Comp. Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, September 2010.

Download: [PDF]

Entry Submitted: 09/14/2010
Entry Accepted: 09/14/2010
Entry Last Modified: 09/14/2010

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