Ing. Milan Korda, Ph.D.

We present a decomposition of the Koopman and Perron-Frobenius operator based on the sparse structure of the underlying dynamical system, allowing one to consider the system as a family of subsystems interconnected by a graph. Using the intrinsic properties of the Koopman operator, we show that eigenfunctions for the subsystems induce eigenfunctions for the whole system. The use of principal eigenfunctions allows us to reverse this result. Similarly for the adjoint operator, the Perron-Frobenius operator, invariant measures for the dynamical system induce invariant measures of the subsystems, while constructing invariant measures from invariant measures of the subsystems is less straightforward. We address this question and show that under necessary compatibility as-sumptions such an invariant measure exists. Based on these results we demonstrate that the a priori knowledge of a decomposition of a dynamical system allows for a reduction of the computational cost on the examples of the dynamic mode decomposition and invariant measure computation.

This letter presents a method for calculat- ing Region of Attraction of a target set (not necessar- ily an equilibrium) for controlled polynomial dynamical systems, using a hierarchy of semidefinite programming problems (SDPs). Our approach builds on previous work and addresses its main issue, the fast-growing memory demands for solving large-scale SDPs. The main idea in this work is in dissecting the original resource-demanding problem into multiple smaller, interconnected, and easier to solve problems. This is achieved by spatio-temporal split- ting akin to methods based on partial differential equations. We show that the splitting procedure retains the conver- gence and outer-approximation guarantees of the previous work, while achieving higher precision in less time and with smaller memory footprint.

This letter makes several contributions on stability and performance verification of nonlinear dynamical systems controlled by neural networks. First, we show that the stability and performance of a polynomial dynamical system controlled by a neural network with semialgebraically representable activation functions (e.g., ReLU) can be certified by convex semidefinite programming. The result is based on the fact that the semialgebraic representation of the activation functions and polynomial dynamics allows one to search for a Lyapunov function using polynomial sum-of-squares methods. Second, we remark that even in the case of a linear system controlled by a neural network with ReLU activation functions, the problem of verifying asymptotic stability is undecidable. Finally, under additional assumptions, we establish a converse result on the existence of a polynomial Lyapunov function for this class of systems. Numerical results with code available online on examples of state-space dimension up to 50 and neural networks with several hundred neurons and up to 30 layers demonstrate the method.

This paper develops a method for obtaining guaranteed outer approximations for global attractors of continuous and discrete time nonlinear dynamical systems. The method is based on a hierarchy of semidefinite programming problems of increasing size with guaranteed convergence to the global attractor. The approach taken follows an established line of reasoning, where we first characterize the global attractor via an infinite dimensional linear programming problem (LP) in the space of Borel measures. The dual to this LP is in the space of continuous functions and its feasible solutions provide guaranteed outer approximations to the global attractor. For systems with polynomial dynamics, a hierarchy of finite-dimensional sum-of-squares tightenings of the dual LP provides a sequence of outer approximations to the global attractor with guaranteed convergence in the sense of volume discrep-ancy tending to zero. The method is very simple to use and based purely on convex optimization. Numerical examples with the code available online demonstrate the method. (C) 2021 Published by Elsevier Ltd.

We propose a convex-optimization-based framework for computation of invariant measures of polynomial dynamical systems and Markov processes, in discrete and continuous time. The set of all invariant measures is characterized as the feasible set of an infinite-dimensional linear program (LP). The objective functional of this LP is then used to single out a specific measure (or a class of measures) extremal with respect to the selected functional such as physical measures, ergodic measures, atomic measures (corresponding to, e.g., periodic orbits) or measures absolutely continuous w.r.t. to a given measure. The infinite-dimensional LP is then approximated using a standard hierarchy of finite-dimensional semidefinite programming problems, the solutions of which are truncated moment sequences, which are then used to reconstruct the measure. In particular, we show how to approximate the support of the measure as well as how to construct a sequence of weakly converging absolutely continuous approximations. As a by-product, we present a simple method to certify the nonexistence of an invariant measure, which is an important question in the theory of Markov processes. The presented framework, where a convex functional is minimized or maximized among all invariant measures, can be seen as a generalization of and a computational method to carry out the so-called ergodic optimization, where linear functionals are optimized over the set of invariant measures. Finally, we also describe how the presented framework can be adapted to compute eigenmeasures of the Perron-Frobenius operator.

Peak estimation bounds extreme values of a function of state along trajectories of a dynamical system. This paper focuses on extending peak estimation to continuous and discrete settings with time-independent and time-dependent uncertainty. Techniques from optimal control are used to incorporate uncertainty into an existing occupation measure-based peak estimation framework, which includes special consideration for handling switching-type (polytopic) uncertainties. The resulting infinite-dimensional linear programs can be solved approximately with Linear Matrix Inequalities arising from the moment-SOS hierarchy.

This work presents a data-driven method for approximation of the maximum positively invariant (MPI) set and the maximum controlled invariant (MCI) set for nonlinear dynamical systems. The method only requires knowledge of a finite collection of one-step transitions of the discrete-time dynamics, without the requirement of segments of trajectories or the control inputs that effected the transitions to be available. The approach uses a novel characterization of the MPI and MCI sets as the solution to an infinite-dimensional linear programming (LP) problem in the space of continuous functions, with the optimum being attained by a (Lipschitz) continuous function under mild assumptions. The infinite-dimensional LP is then approximated by restricting the decision variable to a finite-dimensional subspace and by imposing the nonnegativity constraint of this LP only on the available data samples. This leads to a single finite-dimensional LP that can be easily solved using off-the-shelf solvers. We analyze the convergence rate and sample complexity, proving probabilistic as well as hard guarantees on the volume error of the approximations. The approach is very general, requiring minimal underlying assumptions. In particular, the dynamics is not required to be polynomial or even continuous (forgoing some of the theoretical results). Detailed numerical examples up to state-space dimension 10 with code available online demonstrate the method.

This chapter presents a class of linear predictors for nonlinear controlled dynamical systems. The basic idea is to lift (or embed) the nonlinear dynamics into a higher dimensional space where its evolution is approximately linear. This is achieved by extending the Koopman operator framework to controlled dynamical systems and applying the extended dynamic mode decomposition (EDMD) with a particular choice of basis functions leading to a predictor in the form of a finite-dimensional linear controlled dynamical system. In numerical examples, the linear predictors obtained in this way exhibit a performance superior to existing linear predictors such as those based on local linearization or the so-called Carleman linearization. Importantly, the procedure to construct these linear predictors is completely data-driven and extremely simple—it boils down to a nonlinear transformation of the data (the lifting) and a linear least-squares problem in the lifted space that can be readily solved for large datasets. These linear predictors can be readily used to design controllers for the nonlinear dynamical system using linear controller design methodologies. We focus in particular on model predictive control (MPC) and show that MPC controllers designed in this way enjoy computational complexity of the underlying optimization problem comparable to that of MPC for a linear dynamical system with the same number of control inputs and the same dimension of the state space. Importantly, linear inequality constraints on the state and control inputs as well as nonlinear constraints on the state can be imposed in a linear fashion in the proposed MPC scheme. Similarly, cost functions nonlinear in the state variable can be handled in a linear fashion. We treat the full-state measurement case as well as the input–output case and demonstrate the approach with numerical examples.

This paper continues in the work from Cibulka et al. (2019) where a nonlinear vehicle model was approximated in a purely data-driven manner by a linear predictor of higher order, namely the Koopman operator. The vehicle system typically features a lot of nonlinearities such as rigid-body dynamics, coordinate system transformations and most importantly the tire. These nonlinearities are approximated in a predefined subset of the state-space by the linear Koopman operator and used for a linear Model Predictive Control (MPC) design in the highdimension state space where the nonlinear system dynamics evolve linearly. The result is a nonlinear MPC designed by linear methodologies. It is demonstrated that the Koopman-based controller is able to recover from a very unusual state of the vehicle where all the aforementioned nonlinearities are dominant. The controller is compared with a controller based on a classic local linearization and shortcomings of this approach are discussed.

The Moment-SOS hierarchy is a powerful methodology that is used to solve the Generalized Moment Problem (GMP) where the list of applications in various areas of Science and Engineering is almost endless. Initially designed for solving polynomial optimization problems (the simplest example of the GMP), it applies to solving any instance of the GMP whose description only involves semi-algebraic functions and sets. It consists of solving a sequence (a hierarchy) of convex relaxations of the initial problem, and each convex relaxation is a semidefinite program whose size increases in the hierarchy.The goal of this book is to describe in a unified and detailed manner how this methodology applies to solving various problems in different areas ranging from Optimization, Probability, Statistics, Signal Processing, Computational Geometry, Control, Optimal Control and Analysis of a certain class of nonlinear PDEs. For each application, this unconventional methodology differs from traditional approaches and provides an unusual viewpoint. Each chapter is devoted to a particular application, where the methodology is thoroughly described and illustrated on some appropriate examples.The exposition is kept at an appropriate level of detail to aid the different levels of readers not necessarily familiar with these tools, to better know and understand this methodology.

This article presents a novel data-driven framework for constructing eigenfunctions of the Koopman operator geared toward prediction and control. The method leverages the richness of the spectrum of the Koopman operator away from attractors to construct a set of eigenfunctions such that the state (or any other observable quantity of interest) is in the span of these eigenfunctions and hence predictable in a linear fashion. The eigenfunction construction is optimization-based with no dictionary selection required. Once a predictor for the uncontrolled part of the system is obtained in this way, the incorporation of control is done through a multistep prediction error minimization, carried out by a simple linear least-squares regression. The predictor so obtained is in the form of a linear controlled dynamical system and can be readily applied within the Koopman model predictive control (MPC) framework of (M. Korda and I. Mezić, 2018) to control nonlinear dynamical systems using linear MPC tools. The method is entirely data-driven and based predominantly on convex optimization. The novel eigenfunction construction method is also analyzed theoretically, proving rigorously that the family of eigenfunctions obtained is rich enough to span the space of all continuous functions. In addition, the method is extended to construct generalized eigenfunctions that also give rise Koopman invariant subspaces and hence can be used for linear prediction. Detailed numerical examples demonstrate the approach, both for prediction and feedback control.

We characterize the maximum controlled invariant (MCI) set for discrete- as well as continuous-time nonlinear dynamical systems as the solution of an infinite-dimensional linear programming problem. For systems with polynomial dynamics and compact semialgebraic state and control constraints, we describe a hierarchy of finite-dimensional linear matrix inequality (LMI) relaxations whose optimal values converge to the volume of the MCI set; dual to these LMI relaxations are sum-of-squares (SOS) problems providing a converging sequence of outer approximations to the MCI set. The approach is simple and readily applicable in the sense that the approximations are the outcome of a single semidefinite program with no additional input apart from the problem description. A number of numerical examples illustrate the approach.

This paper deals with the finite horizon stochastic optimal control problem with the expectation of the 1-norm as the objective function and jointly Gaussian, although not necessarily independent, disturbances. We develop an approximation strategy that solves the problem in a certain class of nonlinear feedback policies, while ensuring satisfaction of hard input constraints. A bound on suboptimality of the proposed strategy in the class of aforementioned nonlinear feedback policies is given as well as a simple proof of mean-square stability of a receding horizon implementation provided that the system matrix is Schur stable

In this article we develop a systematic approach to enforce strong feasibility of probabilistically constrained stochastic model predictive control problems for linear discretetime systems under affine disturbance feedback policies. Two approaches are presented, both of which capitalize and extend the machinery of invariant sets to a stochastic environment. The first approach employs an invariant set as a terminal constraint, whereas the second one constrains the first predicted state. Consequently, the second approach turns out to be completely independent of the policy in question and moreover it produces the largest feasible set amongst all admissible policies. As a result, a trade-off between computational complexity and performance can be found without compromising feasibility properties. Our results are demonstrated by means of two numerical examples