DPhil Thesis

Abstract

Many large-scale systems have inherent structures that can be exploited to facilitate their analysis and design. This thesis investigates how chordal graph properties can be used to develop scalable methods for solving three classes of problems: sparse semidefinite programs (SDPs), distributed control of networked systems, and sum-of-squares (SOS) programs. By exploiting the properties of chordal graphs and sparse positive semidefinite matrices, we present decomposition methods that are able to scale these problems to much larger instances.

The first part of this thesis proposes a new conversion framework for large-scale SDPs characterized by chordal sparsity. This framework is analogous to standard conversion techniques for interior-point methods, but is more suitable for the application of first-order methods. We develop efficient algorithms based on the alternating direction method of multipliers (ADMM) for sparse SDPs in either primal or dual standard form, and for their homogeneous self-dual embedding. The algorithms are made available in the open-source conic solver CDCS. CDCS is the first open-source first-order solver that exploits chordal decomposition and can detect infeasible problems. We demonstrate the performance of CDCS in standard analysis problems of large-scale networked systems.

The second part of this thesis is concerned with solution scalability and model privacy in distributed control of networked systems. Specifically, we apply chordal decomposition in sparse Lyapunov-type linear matrix inequalities arising from structured stabilization and optimal decentralized control of networked systems. We introduce a sequential method based on the clique-intersection property of a clique tree for structured stabilization. This strategy greatly improves the computational efficiency for large-scale sparse systems. In addition, we propose an ADMM algorithm that can maintain model privacy when solving the optimal decentralized control problem.

Finally, we consider large-scale SOS programs. We identify an inherent partial orthogonality in the formulation when recasting general SOS programs using the standard monomial basis. In addition, we extend the well-established chordal decomposition/completion results for sparse positive semidefinite matrices to a subset of SOS matrices. Using a new graph-theoretic viewpoint, we build an explicit relationship between chordal decomposition in SOS optimization and two other recent techniques  —  DSOS and SDSOS optimization. We demonstrate that chordal decomposition can bring significant speed-ups for large-scale sparse SOS programs.