Optimization Online


Fast implementation for semidefinite programs with positive matrix completion

Makoto Yamashita(Makoto.Yamashita***at***is.titech.ac.jp)
Kazuide Nakata(nakata.k.ac***at***m.titech.ac.jp)

Abstract: Solving semidefinite programs (SDP) in a short time is the key to managing various mathematical optimization problems in practical time. The matrix-completion primal-dual interior-point method (MC-PDIPM) extracts a structural sparsity of input SDP by factorizing the variable matrices, and it shrinks the computation time. In this paper, we propose a new factorization based on the inverse of the variable matrix to enhance the performance of the MC-PDIPM. We also combine multithreaded parallel computing to resolve the major bottlenecks in the MC-PDIPM. The numerical results show that the new factorization and the multithreaded computing successfully reduce the computation time for the SDPs that posses the structural sparsity.

Keywords: Semidefinite programs, Interior-point methods, Matrix completion, Multithreaded computing

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

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: Research Report B-474, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology

Download: [PDF]

Entry Submitted: 10/25/2013
Entry Accepted: 10/28/2013
Entry Last Modified: 10/25/2013

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 Optimization Society