Optimization Online


A PARALLEL interior point decomposition algorithm for block-angular semidefinite programs

Kartik Krishnan Sivaramakrishnan (kksivara***at***ncsu.edu)

Abstract: We present a two phase interior point decomposition framework for solving semidefinite (SDP) relaxations of sparse maxcut, stable set, and box constrained quadratic programs. In phase 1, we suitably modify the {\em matrix completion} scheme of Fukuda et al. \cite{fukuda_et_al} to preprocess an existing SDP into an equivalent SDP in the block-angular form. In phase 2, we solve the resulting block-angular SDP using a {\em regularized interior point decomposition} algorithm, in an iterative fashion between a master problem (a quadratic program); and decomposed and distributed subproblems (smaller SDPs) in a parallel and distributed high performance computing environment. We compare our MPI implementation of the decomposition algorithm on the distributed {\em Henry2} cluster with the OpenMP version of CSDP \cite{borchers_young} on the IBM Power5 shared memory system at NC State University. Our computational results indicate that the decomposition algorithm a) solves large SDPs to 2-3 digits of accuracy where CSDP runs out of memory; b) returns competitive solution times with the OpenMP version of CSDP, and c) attains a good parallel scalability. Comparing our results with Fujisawa et al. \cite{fujisawa_et_al}, we also show that a suitable modification of the matrix completion scheme can be used in the solution of larger SDPs than was previously possible.

Keywords: Block-angular semidefinite programs, matrix completion, decomposition and nonsmooth optimization, interior point methods

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

Category 2: Convex and Nonsmooth Optimization

Category 3: Linear, Cone and Semidefinite Programming

Citation: Technical Report, Department of Mathematics, North Carolina State University, Raleigh, NC, 27695, April 2008. Accepted for publication in "Computational Optimization and Applications". Also available at http://www4.ncsu.edu/~kksivara/publications/parallel-conic-blockangular.pdf

Download: [PDF]

Entry Submitted: 12/04/2006
Entry Accepted: 12/04/2006
Entry Last Modified: 05/24/2008

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