Decomposed Structured Subsets for Semidefinite Optimization⁎J. Miller and M. Sznaier were partially supported by NSF grants CNS–1646121, CMMI–1638234, IIS–1814631 and ECCSâĂŤ1808381 and AFOSR grant FA9550-19-1-0005. Issue 2 (2020)

• Record Type: Journal Article
• Authors: Miller, Jared; Zheng, Yang; Sznaier, Mario; Papachristodoulou, Antonis
• Is Part Of: IFAC-PapersOnLine. Volume 53:Issue 2(2020)
• Page Start: 7374
• Page End: 7379
• Publication Date: 2020
• Subjects: Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2020.12.1262
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: Semidefinite programs (SDPs) are important computational tools in controls, optimization, and operations research. Standard interior-point methods scale poorly for solving large-scale SDPs. With certain compromise of solution quality, one method for scalability is to use the notion of structured subsets (e.g. diagonally-dominant (DD) and scaled-diagonally dominant (SDD) matrices), to derive inner/outer approximations for SDPs. For sparse SDPs, chordal decomposition techniques have been widely used to derive equivalent SDP reformations with smaller PSD constraints. In this paper, we investigate a notion of decomposed structured subsets by combining chordal decomposition with DD/SDD approximations. This notion takes advantage of any underlying sparsity via chordal decomposition, while embracing the scalability of DD/SDD approximations. We discuss the applications of decomposed structured subsets to semidefinite optimization. Basis pursuit for refining DD/SDD approximations are also incorporated into the decomposed structured subset framework, and numerical performance is improved as compared to standard DD/SDD approximations. These results are demonstrated on H ∞ norm estimation problems for networked systems.