TR2016-040
Degeneracy in Maximal Clique Decomposition for Semidefinite Programs
-
- "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}
- }
,
- "Degeneracy in Maximal Clique Decomposition for Semidefinite Programs", American Control Conference (ACC), DOI: 10.1109/ACC.2016.7526549, July 2016, pp. 5605-5611.
-
MERL Contact:
-
Research Area:
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
-
NEWS MERL makes a strong showing at the American Control Conference Date: July 6, 2016 - July 8, 2016
Where: American Control Conference (ACC)
MERL Contacts: Scott A. Bortoff; Petros T. Boufounos; Stefano Di Cairano; Abraham Goldsmith; Christopher R. Laughman; Daniel N. Nikovski; Arvind Raghunathan; Yebin Wang; Avishai Weiss
Research Areas: Control, Dynamical Systems, Machine LearningBrief- The premier American Control Conference (ACC) takes place in Boston July 6-8. This year MERL researchers will present a record 20 papers(!) at ACC, with several contributions, especially in autonomous vehicle path planning and in Model Predictive Control (MPC) theory and applications, including manufacturing machines, electric motors, satellite station keeping, and HVAC. Other important themes developed in MERL's presentations concern adaptation, learning, and optimization in control systems.