Degeneracy in Maximal Clique Decomposition for Semidefinite Programs

Research paper by Arvind U. Raghunathan, Andrew V. Knyazev

Indexed on: 15 Mar '16Published on: 15 Mar '16Published in: Mathematics - Optimization and Control


Exploiting sparsity in Semidefinite Programs (SDP) is critical to solving large-scale problems. The chordal completion based maximal clique decomposition is the preferred approach for exploiting sparsity in SDPs. In this paper, we show that the maximal clique-based SDP decomposition is primal degenerate when the SDP has a low rank solution. We also derive conditions under which the multipliers in the maximal clique-based SDP formulation is not unique. Numerical experiments demonstrate that the SDP decomposition results in the schur-complement matrix of the Interior Point Method (IPM) having higher condition number than for the original SDP formulation.