TR2016-040

Degeneracy in Maximal Clique Decomposition for Semidefinite Programs

    •  Raghunathan, A.U., Knyazev, A., "Degeneracy in Maximal Clique Decomposition for Semidefinite Programs", American Control Conference (ACC), DOI: 10.1109/​ACC.2016.7526549, July 2016, pp. 5605-5611.
      BibTeX TR2016-040 PDF
      • @inproceedings{Raghunathan2016jul,
      • author = {Raghunathan, Arvind and Knyazev, Andrew},
      • title = {Degeneracy in Maximal Clique Decomposition for Semidefinite Programs},
      • booktitle = {American Control Conference (ACC)},
      • year = 2016,
      • pages = {5605--5611},
      • month = jul,
      • doi = {10.1109/ACC.2016.7526549},
      • url = {https://www.merl.com/publications/TR2016-040}
      • }
  • MERL Contact:
  • Research Area:

    Optimization

Abstract:

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 cliquebased SDP formulation is not unique. Numerical experiments demonstrate that the SDP decomposition results in the schurcomplement matrix of the Interior Point Method (IPM) having higher condition number than for the original SDP formulation.

 

  • Related News & Events