Chordal sparsity, decomposing SDPs and the Lyapunov equation
Analysis questions in control theory are often formulated as Linear Matrix Inequalities and solved using convex optimisation algorithms. For large LMIs it is important to exploit structure and sparsity within the problem in order to solve the associated Semidefinite Programs efficiently. In this pap...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Institute of Electrical and Electronics Engineers Inc.
2014
|
| _version_ | 1797053924869406720 |
|---|---|
| author | Mason, R Papachristodoulou, A |
| author_facet | Mason, R Papachristodoulou, A |
| author_sort | Mason, R |
| collection | OXFORD |
| description | Analysis questions in control theory are often formulated as Linear Matrix Inequalities and solved using convex optimisation algorithms. For large LMIs it is important to exploit structure and sparsity within the problem in order to solve the associated Semidefinite Programs efficiently. In this paper we decompose SDPs by taking advantage of chordal sparsity, and apply our method to the problem of constructing Lyapunov functions for linear systems. By choosing Lyapunov functions with a chordal graphical structure we convert the semidefinite constraint in the problem into an equivalent set of smaller semidefinite constraints, thereby facilitating the solution of the problem. The approach has the potential to be applied to other problems such as stabilising controller synthesis, model reduction and the KYP lemma. © 2014 American Automatic Control Council. |
| first_indexed | 2024-03-06T18:50:23Z |
| format | Conference item |
| id | oxford-uuid:1004c25d-e122-4eb5-a287-6917fb660766 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:50:23Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers Inc. |
| record_format | dspace |
| spelling | oxford-uuid:1004c25d-e122-4eb5-a287-6917fb6607662022-03-26T09:54:11ZChordal sparsity, decomposing SDPs and the Lyapunov equationConference itemhttp://purl.org/coar/resource_type/c_5794uuid:1004c25d-e122-4eb5-a287-6917fb660766Symplectic Elements at OxfordInstitute of Electrical and Electronics Engineers Inc.2014Mason, RPapachristodoulou, AAnalysis questions in control theory are often formulated as Linear Matrix Inequalities and solved using convex optimisation algorithms. For large LMIs it is important to exploit structure and sparsity within the problem in order to solve the associated Semidefinite Programs efficiently. In this paper we decompose SDPs by taking advantage of chordal sparsity, and apply our method to the problem of constructing Lyapunov functions for linear systems. By choosing Lyapunov functions with a chordal graphical structure we convert the semidefinite constraint in the problem into an equivalent set of smaller semidefinite constraints, thereby facilitating the solution of the problem. The approach has the potential to be applied to other problems such as stabilising controller synthesis, model reduction and the KYP lemma. © 2014 American Automatic Control Council. |
| spellingShingle | Mason, R Papachristodoulou, A Chordal sparsity, decomposing SDPs and the Lyapunov equation |
| title | Chordal sparsity, decomposing SDPs and the Lyapunov equation |
| title_full | Chordal sparsity, decomposing SDPs and the Lyapunov equation |
| title_fullStr | Chordal sparsity, decomposing SDPs and the Lyapunov equation |
| title_full_unstemmed | Chordal sparsity, decomposing SDPs and the Lyapunov equation |
| title_short | Chordal sparsity, decomposing SDPs and the Lyapunov equation |
| title_sort | chordal sparsity decomposing sdps and the lyapunov equation |
| work_keys_str_mv | AT masonr chordalsparsitydecomposingsdpsandthelyapunovequation AT papachristodouloua chordalsparsitydecomposingsdpsandthelyapunovequation |