In this thesis we investigate how the properties of chordal graphs can be used to exploit sparsity in several optimisation problems that arise in control theory. In particular, we focus on analysis and synthesis problems that involve semidefinite constraints and can be formulated as semidefinite programming (SDP) problems. Using a relationship between chordal graphs and sparse semidefinite matrices, we decompose the semidefinite constraints in the associated SDP problems into multiple, smaller semidefinite constraints along with some additional equality constraints. The benefit of this approach is that for sparse dynamical systems we can solve significantly larger analysis and synthesis problems than is possible using traditional dense methods. We begin by considering the properties of chordal graphs and their connection to sparse positive semidefinite matrices. We then turn our attention to the problem of constructing Lyapunov functions for linear time-invariant (LTI) systems. From this starting point, we derive methods of exploiting chordal sparsity in other analysis problems found in control theory. In particular, this approach is applied to the problem of bounding the input-output properties of systems via the KYP lemma for both continuous and discrete-time systems. We then consider how the properties of chordal graphs can be exploited in the SDPs that arise in static state feedback controller synthesis problems for LTI systems. We show that the sparse inverse property of the maximum determinant completion of a partial positive matrix can be used to design controllers with a pre-specified sparsity pattern. We then consider how to exploit chordal sparsity when designing a static state feedback controller to minimise the H-infinity norm of an LTI system. Next we shift from linear systems to nonlinear systems and develop a chordal sparsity approach to scalable stability analysis of systems with polynomial dynamics using the Sums of Squares (SOS) technique. We develop a method of exploiting chordal sparsity that avoids the computationally costly step of forming the coefficient matrix in the SOS problem. We then apply this method to the problem of constructing Lyapunov functions for systems with correlatively sparse polynomial vector fields. Finally, we conclude by discussing some directions for future research.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:730575 |
| Date | January 2015 |
| Creators | Mason, Richard |
| Contributors | Papachristodoulou, Antonis |
| Publisher | University of Oxford |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | https://ora.ox.ac.uk/objects/uuid:c4a978aa-185e-4029-a887-6aa2ab9efb37 |
Page generated in 0.0022 seconds