TITLE: A parallel two-stage interior point decomposition algorithm for large scale structured semidefinite programs

SPEAKER: Dr. Kartik Sivaramakrishnan (Researh Div., Axioma,Inc.)

ABSTRACT:

Semidefinite programming (SDP) is referred to as "linear programming for the 21st century" and has a variety of applications in science and engineering. Primal-dual interior point algorithms are currently the most popular techniques for solving large scale SDPs. However, these algorithms are fairly limited in the size of SDPs that they can solve in practice.

We present a two stage decomposition algorithm to solve large scale structured semidefinite programs (SDPs). In the first stage, we exploit the sparsity and/or the symmetry in an underlying SDP in order to process it into an equivalent problem having a "block-angular" structure. We will illustrate the procedure with simple examples in the talk. In the 2nd stage, we solve the resulting "block-angular" SDP in an iterative fashion between a master problem and "decomposed" and "distributed" subproblems in a parallel computing environment. We will give the details of our decomposition algorithm and also highlight some of our enhancements that improve the convergence of the algorithm. We will also report our computational experiences with the algorithm on the distributed "Henry2" cluster at NC State University. Finally, we compare our algorithm with the OpenMP version of CSDP that is available via the COIN-OR interface.