A conic interior point decomposition approach for large scale semidefinite programming

Kartik Krishnan Sivaramakrishnan (kksivarancsu.edu)
Gema Plaza (gemaoptlab.mcmaster.ca)
Tamas Terlaky (terlakymcmaster.ca)

Abstract: We describe a conic interior point decomposition approach for solving a large scale semidefinite programs (SDP) whose primal feasible set is bounded. The idea is to solve such an SDP using existing primal-dual interior point methods, in an iterative fashion between a {\em master problem} and a {\em subproblem}. In our case, the master problem is a mixed conic problem over linear and smaller sized semidefinite cones. The subproblem is a smaller structured semidefinite program that either returns a column or a small sized matrix depending on the multiplicity of the minimum eigenvalue of the dual slack matrix associated with the semidefinite cone. We motivate and develop our conic decomposition methodology on semidefinite programs and also discuss various issues involved in an efficient implementation. Computational results on several well known classes of semidefinite programs are presented.

Keywords: Conic and Semidefinite Programming, Column and Matrix Generation, Nonsmooth Optimization, Interior Point Methods

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

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Technical Report, Department of Mathematics, North Carolina State University, Raleigh, NC, 27695, December 2005. Also available at http://www4.ncsu.edu/~kksivara/publications/conic-ipm-decomposition.pdf (final version submitted for publication)

Download: [PDF]

Entry Submitted: 11/28/2005
Entry Accepted: 11/28/2005
Entry Last Modified: 12/15/2005

Modify/Update this entry