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

Kartik Krishnan Sivaramakrishnan (kksivarancsu.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. Original version: December 2006, Revised in August 2007 and April 2008. 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: 04/25/2008

Modify/Update this entry