Stability: A Search for Structure

Abstract¶

In this thesis we study stability from several viewpoints. After covering the practical importance, the rich history and the ever-growing list of manifestations of stability, we study the following. (i) (Statistical identification of stable dynamical systems): Understanding stability of identified systems is of great practical- and theoretical importance. Even the simplest case, that of characterizing spectral properties of the least-squares estimator of a linear dynamical system has been largely open. To that end, we propose a principled method for projecting a system matrix to the nonconvex set of Schur stable matrices. Leveraging large deviations theory, we show that this projection is optimal in an information-theoretic sense and that the projection can be approximated, up to arbitrary precision, by simply adding a feedback term corresponding to the optimal gain matrix of a linear quadratic regulator problem. The estimator resulting through this projection is constructed from a single trajectory of state measurements, is guaranteed to be stable and offers non-asymptotic statistical bounds on the estimation error. Going one step beyond stability, we further exploit large deviations theory to identify the topological class of an unknown stable system, again from a single trajectory of data. We prove that the probability of misclassification decays exponentially with the number of samples at a rate that is proportional to the square of the smallest singular value of the unknown matrix. (ii) (Spaces of stable dynamical systems): Various technical domains are aided by better understanding spaces of stable dynamical systems. For instance, in many identification and optimal control problems we effectively try to optimize over such a space and thus understanding its properties is important. First, we study the linear quadratic regulator problem and finally provide an operational meaning for cross terms in the stage cost. In particular, we show that the topological class of the closed-loop system is invariant under a change of the stage cost, as long as no cross term is introduced, that is, when restricting system matrices to the general linear group, closed-loop matrices can jump to the opposite path-connected component of this group if and only if a particular cross term is introduced. Hence, formally speaking, one can only “tune” the closed-loop behaviour by introducing a cross term. Secondly, motivated by the learning community often employing convex Lyapunov functions to obtain stability certificates, we study the ramifications of the convexity assumption. We show that continuous dynamical systems, on Euclidean space, equipped with convex Lyapunov functions, asserting that the origin is globally asymptotically stable, can always be homotoped to each other such that along this homotopy stability is preserved. This means that the space of those dynamical systems is path-connected, which in its turn leads to obstructions and the necessity of rethinking convexity assumptions. (iii) (Numerical stability): Besides stability of attractors and structural stability under perturbations, which are all classical topics of study, we also look at stability of the implementation of certain dynamical systems. Specifically, we look at zeroth-order optimization algorithms, a widely applicable class of algorithms understood as discrete-time dynamical systems on Euclidean space. Most zeroth-order optimization algorithms mimic a first-order algorithm, that is, a discretized gradient flow, but replace the gradient of the objective with some estimator that can be computed from a number of function evaluations. This estimator is typically constructed randomly, and its expectation matches the gradient of a smooth approximation of the objective whose quality improves as some underlying smoothing parameter, usually a finite-difference parameter, is reduced. As such, most zeroth-order algorithms require this smoothing parameter to decay to zero as the algorithm proceeds. While estimators based on just a single function evaluation can be obtained via Stokes’ theorem, their variance is unbounded. Then, estimators based on multiple function evaluations, overcome the exploding variance, yet, they suffer from numerical cancellation once the smoothing parameter is sufficiently small. To combat both effects simultaneously, we extend the objective function to the complex domain and leverage the complex-step derivative to construct a new randomized estimator. This new estimator is immune to cancellation as it requires only one function evaluation, in addition, its variance remains bounded. We prove that zeroth-order algorithms that use our estimator offer the same theoretical convergence guarantees as the state-of-the-art methods. At the cost of complex lifting, our results remain true after implementation, the algorithm is numerically stable. (iv) (Topological obstructions to stability and stabilization): Letting go of stylized structural assumptions, we study necessary conditions for stability and stabilizability of dynamical control system defined on topological spaces. We provide new insights in multistability and odd-dimensional dynamical systems, generalize the obstruction for continuous feedback to globally asymptotically stabilize a point on a fiber bundle, to the stabilization of embedded submanifolds and we fully characterize when a compact attractor is a strong deformation retract of its domain of attraction. Results of this nature display the synergy between topology and dynamical systems. All of these studies focus on understanding the interplay between underlying structure and desiderata. Naturally emerging future directions close the thesis.

Summary¶

Studies how dynamical-system structure constrains stability and stabilization. Connects stable system identification and large deviations, topology of stable systems and LQR costs, convex Lyapunov certificates, numerically stable complex-step optimization, and topological obstructions to feedback stabilization.

Links¶

Tags¶

Similar Papers¶