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.
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)
Article
View A conic interior point decomposition approach for large scale semidefinite programming