Polyhedral Computation for Differential System Analysis and Control

In this thesis we investigate the use of polyhedra in the analysis and design of dynamical systems. The main motivation behind the use of polyhedra in this context is that they can, in principle, provide arbitrarily tight conditions on stability, monotonicity, and some system gains for a large class of systems. However, finding a suitable polyhedron is a difficult problem. This is to a large extent inevitable, since many of the above problems are known to be computationally intractable. Despite this, the conditions that a polyhedron must satisfy in the above problems have a strong geometric intuition and a fundamental connection to Linear Programming (LP), allowing for the development of effective and sound heuristics. These can be very valuable because they allow us to better leverage all computational power available and because for many practical scenarios, especially those involving design, tight results might not be necessary but any improvements over existing relaxations are still beneficial. The main contribution of this thesis is the development, presentation, and evaluation of such heuristics for variations of the aforementioned problems. A central idea is the use of LP not only to verify conditions for a given polyhedron, but also to iteratively refine a candidate polyhedron through a local optimisation procedure. This allows for a fine-tuned trade-off between conservativeness and computational tractability and can be used for both analysis and design. For each of the problems considered we also include numerical case studies that demonstrate the effectiveness of this idea in practice. However, more work is necessary to establish theoretical guarantees about the performance and convergence of this approach. We also provide a unified exposition on polyhedra with a focus on computational considerations and the differences between their two representations, including a novel characterisation of the subdifferential of polyhedral functions in one of the representations that leads to novel dissipativity conditions for bounding the L1 gain of systems. Differential analysis is used throughout to link the conditions on the polyhedra to the resulting system behaviour. We hope that this research broadens the applicability of polyhedral computation in systems and control theory and opens a promising avenue for future research.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2023

Author dc:creator

• Kousoulidis, Dimitris

Advisor dc:contributor.advisor

• Forni, Fulvio

• convex analysis
• differential positivity
• incremental gains
• incremental stability
• L1
• linear programming
• Linf
• monotonicity
• polyhedra

Licence

• https://www.repository.cam.ac.uk/bitstreams/d6bd86a3-18a8-46df-8d7a-e7bd65a598e6/download
• https://creativecommons.org/licenses/by/4.0/

Language dc:language

eng

Author Identifier

0000-0002-1508-2403

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/367366