Construction of Lyapunov Functions for Switched Systems using Meshfree Collocation Jay Ward 1 , Nicos Georgiou 1 and Peter Giesl 1 Abstract . Switched systems are a family of dynamical systems where a switching rule indicates which system is “switched on” . This rule can be dependent on time and/or position in the state space. Stability of switched systems is a property that is often investigated using the existence of one (or multiple) Lyapunov function(s). We develop an algorithm using a scattered approximation method to construct a Lyapunov function for switched systems, accompanied with stability results. The construction adapts a previous method for autonomous ODEs that uses meshfree collocation and quadratic programming. † † This research was supported by EPSRC PhD studentship funding. 2020 Mathematics Subject Classification Primary: 93D30, 93-08; Secondary: 34D20, 90C20. 1. Introduction Lyapunov functions characterise the behaviour of a dynamical system. Expressing a dynamical system as a system of differential equations, a (strict) Lyapunov function is a function that decreases along solutions of this system. For a smooth function this is equivalent to it having a negative orbital derivative. Existence of a Lyapunov function implies stability and attractivity of an equilibrium and, moreover, determines the basin of attraction through sublevel sets. For relevant definitions and results see 7 , 16 and 9 . It is therefore a useful endeavour to investigate methods of obtaining a Lyapunov function. 3 introduced a meshfree collocation method to construct Lyapunov functions for autonomous ODEs with equilibrium at the origin by approximating a solution to the PDE DV(\mathbf{x})=-\|\mathbf{x}\|^{2} ; D represents the orbital derivative. In this method, a finitely many collocation points are selected and the goal is to find the norm-minimal function such that the PDE is satisfied at these points. The advantages of this method are numerous ( 4 , 2 ): scattered points can be added, no triangulation of the state space is needed, the approximating function is smooth, the method works in any dimension and the resulting interpolation problem is uniquely solvable when expressed in terms of radial basis functions. 2 extended this approach using quadratic programming to find an approximation that satisfies a system of partial differential inequalities, i.e. DV(\mathbf{x})\leq{0} . We further generalize the method to address switched systems, an important class of dynamical systems where discrete switching events occur between continuous-time systems. These systems arise in a wide range of applications in sciences, engineering and economics, e.g. modeling cellular processes, air traffic control transitions, or thermostat regulation. We define a construction method for a Lyapunov function of a switched system with time- and state-dependent switching using meshfree collocation and quadratic programming. Section 2 reviews types of switched systems and existing construction methods. Section 3 defines a switched system and its Lyapunov function, and presents our construction method, summarised in Algorithm 1 . Theorem 3.1 links Lyapunov functions to asymptotic stability, while Theorem 3.4 confirms that our function satisfies the Lyapunov conditions. Section 4 shows examples using Algorithm 1 for three systems. 2. Switched systems A switched system is a family of dynamical systems where the system that describes the dynamics changes with time and/or the position in the state space. A system where time-dependent uncontrolled switching takes place is referred to as an arbitrary switched system, and a system with state-dependent switching is referred to as a variable structure system. An overview of both can be found in 11 . Results for arbitrary switched systems can be found in 5 , where Lyapunov’s direct method was generalised. We consider switched systems that allow for both time- and state-dependent switching. Systems will be defined on subsets of the state space, with the union of these subsets making up the whole state space. The subsets may overlap; wherever this occurs, the system may switch arbitrarily to a different evolution. In 11 , stability conditions for such a system are described. It states that these conditions are achieved if a Lyapunov function exists for each system in the subset where it is defined. This means that multiple Lyapunov functions can be considered. The method used to prove stability for a similar switched system found in 8 also uses multiple Lyapunov functions; solution trajectories are described as a sequence of switching times paired with the index of the system that is being switched to. The switched system is then stable if there exist functions that decrease wherever their respective system is “switched on” . The method in 5 constructs Lyapunov functions for arbitrary switched systems, with an extension to a variable structure example. In 6 , differential inclusions are used to construct Lyapunov functions for variable structure systems. 3. Construction using Quadratic programming Let \Omega\subset{\mathbb{R}}^{d} be a bounded domain with Lipschitz boundary and define a switched system by autonomous systems of differential equations (1) \dot{\mathbf{x}}(t)=\mathbf{f}_{i}(\mathbf{x}(t))\text{, }i\in{I}:=\{1,\dots,k\} where \mathbf{x}(t)\in\Omega\subset{\mathbb{R}}^{d} . We assume that the functions \mathbf{f}_{i} defined on the domain C_{i}\subset\Omega , \mathbf{0}\in{C_{i}} are locally Lipschitz continuous and have an equilibrium point at the origin. We require that C_{i}=\overline{(C_{i})^{\circ}} and that the sets C_{i} for all i\in{I} are a covering of \Omega . In this paper we consider systems such that sliding modes are avoided, more details on these can be found in 6 . A sliding mode can be interpreted as infinitely fast switching ( 11 ), so we require that for our systems there will be finite switches in finite time. Switching in the system ( 1 ) is when the index i changes. We will use a definition of a switched system which allows both arbitrary and variable structure switching to take place, based on the domains C_{i} of the functions \mathbf{f}_{i} . In any intersections of the domains (see ( 3 )) i can change arbitrarily between the values for which \mathbf{f}_{i} is defined. If the boundary of one of these intersections is reached, i might need to change to reflect the functions defined in this new subset. To illustrate this, consider Figure 1 where two functions \mathbf{f}_{1} , \mathbf{f}_{2} are defined on the domains C_{1} , C_{2} respectively. In the subset C_{1}\cap{C}_{2} the system can switch arbitrarily between i=1,2 , and if for example the boundary of the subset C_{1}\cap{C}_{2}^{c} is reached, then the system will switch to i=1 . Our algorithm will be applied to arbitrary switched, variable structure and combined systems in Examples 4.1 , 4.2 and 4.3 . A Lyapunov function of the switched system ( 1 ) is a function that is non-increasing along the solutions of each differential equation in the system. For our purposes we say that V:\Omega\rightarrow{\mathbb{R}} , V(\mathbf{0})=0 is a Lyapunov function for the system ( 1 ) if and only if for all i\in{I} (2) \nabla{V(\mathbf{x})}\cdot\mathbf{f}_{i}(\mathbf{x})\leq-\gamma(\|\mathbf{x}\|_{2})\text{ and }V(\mathbf{x})>0 for all \mathbf{x}\in{C_{i}}\setminus\{0\} , where \gamma is a function of class {\mathcal{K}} , i.e. \gamma\in{C([0,a),{\mathbb{R}}^{+})} where a>0 , \gamma(0)=0 and it is strictly monotonically increasing ( 9 ). This V is actually a strict Lyapunov function for the system ( 1 ). Using this we can obtain the following stability result. Theorem 3.1 . If there exists a function V\in{C^{1}(\Omega)} that satisfies properties ( 2 ) for all i\in{I} , then the equilibrium \mathbf{x}=\mathbf{0} of system ( 1 ) is asymptotically stable. This can be shown using methods similar to classical Lyapunov proofs that can be found in 7 , 16 and 9 . Now we introduce the algorithm that we will use to construct Lyapunov functions of our systems ( 1 ); a summary of where the details of each step and definitions of any notation used can be found in the following sections is provided underneath. Algorithm 1 Lyapunov functions for Switched Systems 0: State space \Omega and partition P^{\theta} for \theta=1,\dots,\Theta (see Section 3.1 ), functions \mathbf{f}_{i}(\mathbf{x}) ( 1 ), Wendland function \Psi_{0}(r) (see Section 3.2 ) and evaluation points. 1: Fix collocation points X^{\theta}=\{\mathbf{x}^{\ell,\theta}\}_{1\leq\ell\leq N^{\theta}} in each set P^{\theta} , \theta=1,\dots,\Theta . 2: If 0 is selected as a collocation point remove it. 3: For each collocation point \mathbf{x}^{\ell,\theta} compute a basis of the vectors \mathbf{f}_{i}(\mathbf{x}^{\ell,\theta}) and use this to find the values of the coefficients \alpha_{\sigma,i}^{\ell,\theta} ( 10 ). 4: Find Q ( 11 ). 5: Find A ( 15 ). 6: Solve a quadratic programming problem for \beta ( 14 ). 7: Find values of v ( 13 ) at evaluation points and plot. For all i\in{I} find values of the orbital derivatives \nabla{v}\cdot\mathbf{f}_{i} at evaluation points in C_{i} and plot. Section 3.3 contains the definition of the minimisation problem ( 8 ) we are looking to solve in order to construct a Lyapunov function. Details on steps 3 and 4 are found in Section 3.4 , and on steps 5 , 6 and 7 in Section 3.5 , including Theorem 3.4 , which verifies that our function v ( 13 ) is a solution of the minimisation problem ( 8 ). 3.1. Partitioning the State Space We define the following sets for {P}\subseteq{I} , P\neq\varnothing (3) \Omega^{P}:=\bigg(\bigcap_{i\in{P}}C_{i}\bigg)\cap\bigg(\bigcap_{j\in{I\setminus{P}}}C_{j}^{c}\bigg). An example of this partition is shown in Figure 1 . Here we have two functions \mathbf{f}_{1} , \mathbf{f}_{2} defined on the domains C_{1} , C_{2} respectively. In this case, I=\{1,2\} and the possible subsets P are \{1\} , \{2\} and \{1,2\} . \Omega^{P} consists of the three subsets C_{1}\cap{C_{2}^{c}} , C_{1}\cap{C_{2}} and C_{1}^{c}\cap{C_{2}} . Now for use in our algorithm we label these subsets. We will refer to the total number of subsets P as \Theta and label these subsets as P^{\theta} where \theta=1,\dots,\Theta . We can write the elements of each of these sets P^{\theta} as p_{i}^{\theta} , with i=1,\dots,{\mathcal{P}}^{\theta} where {\mathcal{P}}^{\theta}:=|P^{\theta}| . In Figure 1 we have \Theta=3 , P^{1}=\{1\} with p_{1}^{1}=1 , P^{2}=\{1,2\} with p_{1}^{2}=1 and p_{2}^{2}=2 , and P^{3}=\{2\} with p_{1}^{3}=2 . =C_{1}\cap C_{2}=\Omega^{\{1,2\}}=\Omega{{}^{P}}^{2} \Omega =C_{1}\cap C_{2}^{c}=\Omega^{\{1\}}=\Omega{{}^{P}}^{1} =C_{1}^{c}\cap C_{2}=\Omega^{\{2\}}=\Omega{{}^{P}}^{3} Figure 1. An example state space \Omega with two functions \mathbf{f}_{1} and \mathbf{f}_{2} with domains C_{1} and C_{2} , respectively. This divides the whole state space into three separate subsets using definition ( 3 ), the intersection of the two domains and the two sets where either only \mathbf{f}_{1} or only \mathbf{f}_{2} is defined. This tells us that \Theta=3 and we label P^{1}=\{1\} , P^{2}=\{1,2\} and P^{3}=\{2\} . 3.2. Reproducing Kernel Hilbert Spaces We construct a function v as a solution of the minimisation problem ( 8 ). It is the optimal reconstruction of a function V satisfying ( 5 ), which is a Lyapunov function for our system ( 1 ). In the same way as 2 , v will belong to a Reproducing Kernel Hilbert space H with reproducing kernel \Phi:\Omega\times\Omega\rightarrow{\mathbb{R}} . Definition 3.2 . (Reproducing Kernel Hilbert Space (RKHS)) Let \Omega\subseteq{\mathbb{R}}^{d} . A Hilbert space H=H(\Omega) of continuous functions f:\Omega\rightarrow{\mathbb{R}} with inner product \langle\cdot,\cdot\rangle_{H} is called a reproducing kernel Hilbert space, abbreviated RKHS, if there is a function \Phi:\Omega\times\Omega\rightarrow{\mathbb{R}} with (1) \Phi(\cdot,\mathbf{x})\in{H} for all {\mathbf{x}\in\Omega} (2) g(\mathbf{x})=\langle{g(\cdot),\Phi(\cdot,\mathbf{x})}\rangle_{H} for all g\in{H} and all \mathbf{x}\in\Omega . The function \Phi is called the reproducing kernel of H . The reproducing kernel is called positive definite, if for any pair of pairwise distinct points \{x_{1},...,x_{N}\}\subseteq\Omega the matrix (\Phi(x_{i},x_{j}))_{i,j=1,...,N} is positive definite. In our case, the reproducing kernel is given by a radial basis function \Psi_{0} through \Phi(\mathbf{x},\mathbf{y}):=\Psi_{0}(\|\mathbf{x}-\mathbf{y}\|_{2}) . We choose this radial basis function to be a Wendland function \phi_{\ell,k}(cr) ( 13 ; 14 ) where c>0 , k\in{\mathbb{N}} is a smoothness parameter and \ell=\lfloor\frac{d}{2}\rfloor+k+1 . These are smooth functions with compact support, which are polynomials on their support. We can then define recursively \Psi_{i}(r)=\frac{1}{r}\frac{d\Psi_{i-1}(r)}{dr} for i=1,2 and r>0 . Note that \lim_{r\rightarrow{0}}\Psi_{i}(r) exists if the smoothness parameter k of the Wendland function is sufficiently large. 3.3. Minimisation problem Using this set-up, we will construct a Lyapunov function for our switched system using quadratic programming, as done for autonomous ODEs in 2 . There they construct a Lyapunov function for a single system by finding a solution to the system of partial differential inequalities DV(\mathbf{x})\leq{r}(\mathbf{x}) where D denotes the orbital derivative, and r(\mathbf{x}) is negative. This method can be generalised in order to construct a Lyapunov function for a switched system. We define for all \theta=1\dots,\Theta and i=1,\dots,{\mathcal{P}}^{\theta} the linear differential operator (4) D_{p_{i}^{\theta}}V(\mathbf{x}):=\nabla{V}(\mathbf{x})\cdot\mathbf{f}_{p_{i}^{\theta}}(\mathbf{x})\text{ }\forall\mathbf{x}\in\Omega^{P^{\theta}}. Our system of partial differential inequalities is then written as (5) D_{p_{i}^{\theta}}V(\mathbf{x})\leq{b_{p_{i}^{\theta}}}(\mathbf{x}) where b_{p_{i}^{\theta}}(\mathbf{x}) is negative for all \mathbf{x}\in\Omega^{P^{\theta}}\setminus{\{\mathbf{0}\}} , b_{p_{i}^{\theta}}(\mathbf{0})=0 . Finding a function that satisfies these inequalities is then equivalent to finding a Lyapunov function as in ( 2 ). We now discretise our problem by choosing collocation points \mathbf{x}^{1,\theta},\dots,\mathbf{x}^{N^{\theta},\theta}\in\Omega^{P^{\theta}} and values b_{i}^{1,\theta}=b_{p_{i}^{\theta}}(\mathbf{x}^{1,\theta}),\dots,b_{i}^{N^{\theta},\theta}=b_{p_{i}^{\theta}}(\mathbf{x}^{N^{\theta},\theta})\in{\mathbb{R}}_{0}^{+}. We seek to find a function v that satisfies (6) D_{p_{i}^{\theta}}v(\mathbf{x}^{\ell,\theta})\leq b_{i}^{\ell,\theta}\text{ for all }\ell=1,\dots,N^{\theta} for \theta=1,\dots,\Theta and i=1,\dots,{\mathcal{P}}^{\theta} , where N^{\theta} is the number of collocation points chosen in the subset \Omega^{P^{\theta}} . Another way to write this that is more suitable for our purpose would be to say we look to find an appropriate function v\in{H} using the information b_{i}^{\ell,\theta}\in{\mathbb{R}} given by the functionals \lambda_{i}^{\ell,\theta}\in{H}^{*} , i.e. \lambda_{i}^{\ell,\theta}(v)\leq b_{i}^{\ell,\theta} for all \theta=1,\dots,\Theta , i=1,\dots,{\mathcal{P}}^{\theta} and \ell=1,\dots,N^{\theta} . These functionals are defined as our differential operator ( 4 ) applied at a specific collocation point, i.e. (7) (\lambda_{i}^{\ell,\theta})v(\cdot):=(\delta_{\mathbf{x}^{\ell,\theta}}\circ{D_{p_{i}^{\theta}}})v(\cdot)=\nabla{v}(\mathbf{x}^{\ell,\theta})\cdot\mathbf{f}_{p_{i}^{\theta}}(\mathbf{x}^{\ell,\theta}) for all \theta=1,\dots,\Theta , \ell=1,\dots,N^{\theta} and i=1,\dots,{\mathcal{P}}^{\theta} , with \delta being Dirac’s delta distribution. Note that the elements of the set P^{\theta} will be reordered for each collocation point in the following section when we select a basis of the functions \mathbf{f}_{i} at this point, see ( 9 ). The optimal reconstruction of v is given by the solution of the problem (8) \min\{\|v\|_{H}:v\in{H}\text{, }\lambda_{i}^{\ell,\theta}(v)\leq b_{i}^{\ell,\theta}\text{ for all }\theta=1,\dots,\Theta\text{, }\ell=1,\dots,N^{\theta}\text{ and }i=1,\dots,{\mathcal{P}}^{\theta}\} It can be shown that this problem has at most one solution, using a similar proof to that of Lemma 5.1 in 2 . 3.4. Selection of Basis If the functionals are linearly independent, we can use techniques from 15 to find a solution of the problem ( 8 ). However, this is not necessarily the case. We fix a point \mathbf{x}^{\ell,\theta}\in\Omega^{P^{\theta}} , consider whether \mathbf{f}_{p_{i}^{\theta}}(\mathbf{x}^{\ell,\theta}) for i=1,\dots,{\mathcal{P}}^{\theta} are linearly independent, and if not, select a basis of these vectors. To this end, fix \mathbf{x}^{\ell,\theta}\in\Omega^{P^{\theta}} and define the set R^{\ell,\theta}:=\{r_{1}^{\ell,\theta},\dots,r_{\rho^{\ell,\theta}}^{\ell,\theta}\}\subseteq P^{\theta} to be a set of indices such that the vectors \mathbf{f}_{r_{i}^{\ell,\theta}}(\mathbf{x}^{\ell,\theta}) are a basis of (\mathbf{f}_{p_{i}^{\theta}}(\mathbf{x}^{\ell,\theta}))_{p_{i}^{\theta}\in P^{\theta}} (with \rho^{\ell,\theta} being the rank of this matrix). The elements of P^{\theta}\setminus{R^{\ell,\theta}} will be labeled \pi_{s}^{\ell,\theta} where s=1,\dots,{\mathcal{P}}^{\theta}-\rho^{\ell,\theta} . This means we can consider the vector (9) P^{\ell,\theta}=\big(r_{1}^{\ell,\theta},\dots,r_{\rho^{\ell,\theta}}^{\ell,\theta},\pi_{1}^{\ell,\theta},\dots,\pi_{{\mathcal{P}}^{\theta}-\rho^{\ell,\theta}}^{\ell,\theta}\big) and label these coordinates p_{i}^{\ell,\theta}\in P^{\ell,\theta} for i=1,\dots,{\mathcal{P}}^{\theta} . This means we can represent an ordering of the set P^{\theta} for the point \mathbf{x}^{\ell,\theta} , where we have placed the indices that represent the basis at the beginning of the vector. The vector ( 9 ) is found for each of our collocation points \mathbf{x}^{\ell,\theta} for \theta=1,\dots,\Theta and \ell=1,\dots,N^{\theta} . From this point forwards when we refer to the functionals \lambda_{i}^{\ell,\theta} we mean ( 7 ) with p_{i}^{\theta} instead being elements p_{i}^{\ell,\theta} from the vector P^{\ell,\theta} ( 9 ). For notation purposes we define \rho:=\sum_{\theta=1}^{\Theta}\sum_{\ell=1}^{N^{\theta}}\rho^{\ell,\theta}\text{ and }{\mathcal{P}}:=\sum_{\theta=1}^{\Theta}\sum_{\ell=1}^{N^{\theta}}{\mathcal{P}}^{\theta}. By ( 9 ) the functionals \lambda_{i}^{\ell,\theta} for i=1,\dots,\rho^{\ell,\theta} are a basis for the whole set of functionals with i=1,\dots,{\mathcal{P}}^{\theta} . The functionals at the point \mathbf{x}^{\ell,\theta} can be expressed as a linear combination of this basis (10) \lambda_{\sigma}^{\ell,\theta}=\sum_{i=1}^{\rho^{\ell,\theta}}\alpha_{\sigma,i}^{\ell,\theta}\lambda_{i}^{\ell,\theta} for all \sigma=1,\dots,{\mathcal{P}}^{\theta} , for some appropriate \alpha_{\sigma,i}^{\ell,\theta}\in{\mathbb{R}} . We assemble the coefficients of all collocation points \mathbf{x}^{\ell,\theta} as elements of a matrix Q\in{\mathbb{R}}^{{\mathcal{P}}\times\rho} in the following way (11) Q:=\left(\begin{array}[]{c}I\\ \tilde{Q}\end{array}\right) where I is the \rho\times\rho identity matrix (accounting for the elements \alpha_{s,i}^{\ell,\theta} for \theta=1,\dots,\Theta , \ell=1,\dots,N^{\theta} , s,i=1,\dots,\rho^{\ell,\theta} ) and \tilde{Q} is a block diagonal matrix (12) \tilde{Q}:=\diag(\tilde{Q}^{1,1},\dots,\tilde{Q}^{N^{1},1},\dots,\tilde{Q}^{1,\Theta},\dots,\tilde{Q}^{N^{\Theta},\Theta}) where the matrices \tilde{Q}^{\ell,\theta} have entries q^{\ell,\theta}_{s,i}:=\alpha_{s+\rho^{\ell,\theta},i}^{\ell,\theta} for \theta=1,\dots,\Theta , \ell=1,\dots,N^{\theta} , s=1,\dots,{\mathcal{P}}^{\theta}-\rho^{\ell,\theta} and i=1,\dots,\rho^{\ell,\theta} . 3.5. Quadratic Programming Problem We show that the solution of ( 8 ) is of the form (13) v(\mathbf{x})=\sum_{\theta=1}^{\Theta}\sum_{\ell=1}^{N^{\theta}}\sum_{i=1}^{\rho^{\ell,\theta}}\beta_{i}^{\ell,\theta}(\lambda_{i}^{\ell,\theta})^{\mathbf{y}}\Phi(\mathbf{x},\mathbf{y}) with (\lambda_{i}^{\ell,\theta})^{\mathbf{y}}\Phi(\mathbf{x},\mathbf{y})=\nabla_{\mathbf{y}}({\Phi}(\mathbf{x},\mathbf{y}))\big|_{\mathbf{y}=\mathbf{x}^{\ell,\theta}}\cdot\mathbf{f}_{p_{i}^{\ell,\theta}}(\mathbf{x}^{\ell,\theta}) , where the coefficients \beta_{i}^{\ell,\theta} satisfy (14) \begin{cases}\text{\rm{minimise }}\beta^{T}A\beta\\ \text{\rm{subject to }}QA\beta\leq\mathbf{b}\end{cases} To find these matrices, we have applied the functionals to our proposed solution ( 13 ) and used the inequalities in ( 8 ). The elements of the matrix A\in{\mathbb{R}}^{\rho\times\rho} are (15) \displaystyle a_{i,j}^{\theta,\eta;\ell,m} \displaystyle:= \displaystyle(\delta_{\mathbf{x}^{m,\eta}}\circ{D_{p_{j}^{m,\eta}}})^{\mathbf{x}}(\delta_{\mathbf{x}^{\ell,\theta}}\circ{D_{p_{i}^{\ell,\theta}}})^{\mathbf{y}}\Phi(\mathbf{x},\mathbf{y}) \displaystyle= \displaystyle\langle(\lambda_{j}^{m,\eta})^{\mathbf{y}}\Phi(\cdot,\mathbf{y}),(\lambda_{i}^{\ell,\theta})^{\mathbf{x}}\Phi(\cdot,\mathbf{x})\rangle_{H} for \theta,\eta=1,\dots,\Theta , \ell=1,\dots,N^{\theta} , m=1,\dots,N^{\eta} , i=1,\dots,\rho^{\ell,\theta} and j=1,\dots,\rho^{m,\eta} . The symmetric matrix A accounts for the linearly independent functionals, and we apply the matrix Q as the other functionals are expressed as linear combinations of the independent ones ( 10 ). The elements of the vector \mathbf{b} are the values b_{i}^{\ell,\theta} from the minimisation problem ( 8 ) for \theta=1,\dots,\Theta , \ell=1,\dots,N^{\theta} and i=1,\dots,{\mathcal{P}}^{\theta} . Similarly to 2 , minimising \beta^{T}A\beta is the same as minimising \|v\|_{H} . The following lemma contributes to Theorem 3.4 . Lemma 3.3 . If there is a feasible solution to the problem ( 14 ), then this solution is unique. Proof. Given the definition of Q as in ( 11 ), we can rewrite problem ( 14 ) as follows (16) \begin{cases}\text{\rm{minimise }}\beta^{T}A\beta\\ \text{\rm{subject to }}A\beta=:\mathbf{r}\leq\mathbf{c}\\ \phantom{xxxxxxxx}\tilde{Q}A\beta=:\tilde{\mathbf{r}}\leq\tilde{\mathbf{c}}\end{cases} where, for \theta=1,\dots,\Theta and \ell=1,\dots,N^{\theta} , elements of \mathbf{c} are b_{i}^{\ell,\theta} for i=1,\dots,\rho^{\ell,\theta} , and elements of \tilde{\mathbf{c}} are b_{s+\rho^{\ell,\theta}}^{\ell,\theta} for s=1,\dots,{\mathcal{P}}^{\theta}-\rho^{\ell,\theta} . The matrix A is positive definite since the functionals included in the values of its elements ( 15 ) are linearly independent. As A is also symmetric, we have \beta^{T}A\beta=\mathbf{r}^{T}A^{-1}\mathbf{r} and, using that \tilde{Q}\mathbf{r}=\tilde{\mathbf{r}} , we can rewrite ( 16 ) as (17) \begin{cases}\text{\rm{minimise }}\mathbf{r}^{T}A^{-1}\mathbf{r}\\ \text{\rm{subject to }}\mathbf{r}-\mathbf{c}\leq\mathbf{0}\\ \phantom{xxxxxxxx}\tilde{Q}\mathbf{r}-\tilde{\mathbf{c}}\leq{\mathbf{0}}\end{cases} The functions g_{1}(\mathbf{r}):=\mathbf{r}-\mathbf{c} and g_{2}(\mathbf{r}):=\tilde{Q}\mathbf{r}-\tilde{\mathbf{c}} which correspond to the constraints of ( 17 ) are both affine and therefore convex. As A^{-1} is positive definite, the function h(\mathbf{r})=\mathbf{r}^{T}A^{-1}\mathbf{r} is strictly convex. Overall this means, using the definition of a convex optimisation problem from 1 , that ( 17 ) has a unique solution if it is feasible. ∎ The main result of this section is then as follows. Theorem 3.4 . If there is a feasible solution to the problem ( 14 ), then the unique minimiser of the problem ( 8 ) is of the form ( 13 ) where the coefficients \beta_{i}^{\ell,\theta} are determined by the solution of the problem ( 14 ). Proof. Define v by ( 13 ) where the coefficients are determined by ( 14 ) (see Lemma 3.3 ). Let s\in{H} be any function satisfying the constraints of the minimisation problem ( 8 ). We wish to show that \|v\|_{H}\leq\|s\|_{H} . We know that s satisfies (18) \lambda_{i}^{\ell,\theta}(s)=:r_{i}^{\ell,\theta}\leq b_{i}^{\ell,\theta} for all \theta=1,\dots,\Theta , \ell=1,\dots,N^{\theta} and i=1,\dots,{\mathcal{P}}^{\theta} . For the rest of the lemma we set elements of \mathbf{r} to be r_{i}^{\ell,\theta} for i=1,\dots,\rho^{\ell,\theta} , and elements of \tilde{\mathbf{r}} to be r_{s+\rho^{\ell,\theta}}^{\ell,\theta} for s=1,\dots,{\mathcal{P}}^{\theta}-\rho^{\ell,\theta} . Consider the new minimisation problem \begin{cases}\text{\rm{minimise }}\|v\|_{H}\\ \text{\rm{subject to }}\lambda_{i}^{\ell,\theta}(v)=r_{i}^{\ell,\theta}\text{, }\forall\theta=1,\dots,\Theta\text{, }\ell=1,\dots,N^{\theta}\\ \phantom{ccccccccccccccccccccccccc}\text{ and }i=1,\dots,\rho^{\ell,\theta}\end{cases} Now using Theorem 16.1 from 15 we can see that the solution of this problem is given by \tilde{s}(\mathbf{x})=\sum_{\theta=1}^{\Theta}\sum_{\ell=1}^{N^{\theta}}\sum_{i=1}^{\rho^{\ell,\theta}}\tilde{\beta}_{i}^{\ell,\theta}(\lambda_{i}^{\ell,\theta})^{\mathbf{y}}\Phi(\cdot,\mathbf{y}) where A\tilde{\beta}=\mathbf{r} , A has entries ( 15 ), and \tilde{\beta} has the same structure as \beta from ( 14 ). We will show that these \tilde{\beta} satisfy \tilde{Q}A\tilde{\beta}=\tilde{\mathbf{r}} , which is equivalent to showing that \tilde{Q}\mathbf{r}=\tilde{\mathbf{r}} . Indeed, using ( 10 ) we can rewrite the equations in ( 18 ) for \sigma=\rho^{\ell,\theta}+1,\dots,{\mathcal{P}}^{\theta} as \sum_{i=1}^{\rho^{\ell,\theta}}\alpha_{\sigma,i}^{\ell,\theta}\lambda_{i}^{\ell,\theta}(s)=r_{\sigma}^{\ell,\theta}\Rightarrow\sum_{i=1}^{\rho^{\ell,\theta}}\alpha_{\sigma,i}^{\ell,\theta}r_{i}^{\ell,\theta}=r_{\sigma}^{\ell,\theta}\Rightarrow\tilde{Q}\mathbf{r}=\tilde{\mathbf{r}} using the definition of the elements of \tilde{Q} . Therefore \tilde{s} is also the minimiser for the problem \begin{cases}\text{\rm{minimise }}\|v\|_{H}\\ \text{\rm{subject to }}\lambda_{i}^{\ell,\theta}(v)=r_{i}^{\ell,\theta}\text{, }\forall\theta=1,\dots,\Theta\text{, }\ell=1,\dots,N^{\theta}\\ \phantom{ccccccccccccccccccccccccc}\text{ and }i=1,\dots,{\mathcal{P}}^{\theta}\end{cases} which shows that \|\tilde{s}\|_{H}\leq\|s\|_{H} . Now both v and \tilde{s} are of the form ( 13 ) and the coefficients \beta and \tilde{\beta} both satisfy the constraints of problem ( 14 ). However, the coefficients \beta of v minimise \beta^{T}A\beta=\|v\|_{H}^{2} so that \|v\|_{H}^{2}\leq\|\tilde{s}\|_{H}^{2}=\tilde{\beta}^{T}A\tilde{\beta} . Therefore altogether we have that \|v\|_{H}\leq\|\tilde{s}\|_{H}\leq\|s\|_{H}. Since the minimiser is unique (see statement after ( 8 )), v is the minimiser. ∎ This means that the function v from ( 13 ) is an approximation of a function that solves the system of partial differential inequalities in ( 5 ). If the matrix Q is just the \rho\times\rho identity matrix, then we are able to verify that the problem ( 14 ) is feasible, this is shown in 2 . 4. Examples This section contains three examples that show how our algorithm can be applied to systems that use different switching rules. For arbitrary switched see Example 4.1 , for variable structure see Example 4.2 , and for a mix of the two see Example 4.3 . In each of these examples the Wendland functions that we use in the implementation of Algorithm 1 is \phi_{4,2} from 4 which means that we have (19) \Psi_{0}(r)=(1-cr)^{6}_{+}[35(cr)^{2}+18cr+3] from which \Psi_{1} and \Psi_{2} can be calculated. We use c=\frac{5}{6} . The collocation points are selected to be \frac{1}{6}{\mathbb{Z}}^{2}\cap\Omega , where \Omega is [-0.5,0.5]^{2} . This means we have 49 collocation points in total. The computational complexity is of the order N^{2} where N is the number of collocation points. Figure 2. Lyapunov functions constructed for the following three examples. The left function is for Example 4.1 , the middle is for Example 4.2 and the right is for Example 4.3 . The left and right functions took 3 minutes to compute, and the middle 45 seconds. Example 4.1 . (Arbitrary Switched) Using \mathbf{f}_{1} and \mathbf{f}_{2} from Example 9.2 in 5 , we consider the autonomous systems \mathbf{\dot{x}}=\mathbf{f}_{1}(\mathbf{x})\text{, where }\mathbf{f}_{1}(x,y):=\left(\begin{array}[]{c}-y\\ x-y(1-x^{2}+0.1x^{4})\end{array}\right) and \mathbf{\dot{x}}=\mathbf{f}_{2}(\mathbf{x})\text{, where }\mathbf{f}_{2}(x,y):=\left(\begin{array}[]{c}-y+x(x^{2}+y^{2}-1)\\ x+y(x^{2}+y^{2}-1)\end{array}\right)\text{.} These are both asymptotically stable systems, and we switch between them arbitrarily over the whole state space \Omega . This can be expressed using the following system (20) \dot{\mathbf{x}}=\mathbf{f}_{p}(\mathbf{x})\text{, }p\in\{1,2\}. We set C_{1}=C_{2}=\Omega , and find that \Theta=1 , P^{1}=\{1,2\} with \Omega^{P^{1}}=\Omega . The Lyapunov function produced for this system can be seen on the left of Figure 2 and its orbital derivatives in Figure 3 , which are negative apart from the origin. Figure 3. Plots of the orbital derivatives of the Lyapunov function displayed on the left of Figure 2 : \nabla{v}(x,y)\cdot\mathbf{f}_{1}(x,y) (left) and \nabla{v}(x,y)\cdot\mathbf{f}_{2}(x,y) (right). In both figures the plane \{z=0\} has been plotted to illustrate that the constraints in ( 8 ) have been met. Example 4.2 . (Variable Structure) Here we consider the example found in 10 (also studied in 5 ), with the two unstable linear systems \mathbf{\dot{x}}=A_{1}\mathbf{x} and \mathbf{\dot{x}}=A_{2}\mathbf{x} , where (21) A_{1}:=\left(\begin{array}[]{cc}0.1&-1\\ 2&0.1\end{array}\right)\text{ and }A_{2}:=\left(\begin{array}[]{cc}0.1&-2\\ 1&0.1\end{array}\right). We can switch between these systems in such a way that we can produce a variable structure system where trajectories are asymptotically attracted to the equilibrium. This occurs when we define the following quadrants \displaystyle Q_{1} \displaystyle:= \displaystyle\{(x,y):x>0\text{ and }y\geq{0}\}\cap\{(0,0)\} \displaystyle Q_{2} \displaystyle:= \displaystyle\{(x,y):x\leq{0}\text{ and }y>0\}\cap\{(0,0)\} \displaystyle Q_{3} \displaystyle:= \displaystyle\{(x,y):x<0\text{ and }y\leq{0}\}\cap\{(0,0)\} \displaystyle Q_{4} \displaystyle:= \displaystyle\{(x,y):x\geq{0}\text{ and }y<0\}\cap\{(0,0)\} and switch when the solution trajectory enters a new quadrant. We define (22) \mathbf{\dot{x}}=\mathbf{f}_{p}(\mathbf{x})=A_{p}\mathbf{x}\text{, }p\in\{1,2\} where p=1 for \mathbf{x}\in{Q_{2}\cup{Q_{4}}} and p=2 for \mathbf{x}\in{Q_{1}\cup{Q_{3}}} . We can apply our algorithm to this example with C_{1}=Q_{2}\cup{Q_{4}} and C_{2}=Q_{1}\cup{Q_{3}} , i.e. \Theta=2 , P^{1}=\{1\} and P^{2}=\{2\} , with \Omega^{P^{1}}=Q_{2}\cup{Q_{4}} and \Omega^{P^{2}}=Q_{1}\cup{Q_{3}} . Note that there is no intersection between our sets C_{1} and C_{2} . The algorithm produces the plot for the Lyapunov function for this system as seen in the middle of Figure 2 , as well as plots for its orbital derivatives in Figure 4 , which are negative apart from the origin. Figure 4. Plots of the orbital derivatives of the Lyapunov function displayed in the middle of Figure 2 : \nabla{v}(x,y)\cdot\mathbf{f}_{1}(x,y) (left) and \nabla{v}(x,y)\cdot\mathbf{f}_{2}(x,y) (right). The orbital derivatives are plotted in the quadrants where their respective function is defined. In both figures the plane \{z=0\} has been plotted to illustrate that the constraints in ( 8 ) have been met. Example 4.3 . (Arbitrary and Variable Structure system) This example implements both time and state dependent switching. To do this we use the first system \mathbf{f}_{1} from Example 4.1 , and the two systems ( 22 ) from Example 4.2 . For ease of notation we label \mathbf{f}_{2}(\mathbf{x}):=A_{1}\mathbf{x} and \mathbf{f}_{3}(\mathbf{x}):=A_{2}\mathbf{x} . Here we will be switching between \mathbf{f}_{1} and \mathbf{f}_{2} in the quadrants where \mathbf{f}_{2} is defined, and between \mathbf{f}_{1} and \mathbf{f}_{3} in the quadrants where \mathbf{f}_{3} is defined. These quadrants are specified in Example 4.2 . This can be described by the following system (23) \dot{\mathbf{x}}=\mathbf{f}_{p}(\mathbf{x})\text{, }p\in\{1,2,3\} where p switches arbitrarily between 1 and 2 when \mathbf{x}\in{Q_{2}\cup{Q_{4}}} , and similarly between 1 and 3 when \mathbf{x}\in{Q_{1}\cup{Q_{3}}} . Our algorithm is applicable here with C_{1}=\Omega , C_{2}=Q_{2}\cup{Q_{4}} and C_{3}=Q_{1}\cup{Q_{3}} . This then partitions our space with \Theta=2 , P^{1}=\{1,2\} and P^{2}=\{1,3\} , which means that \Omega^{P^{1}}=Q_{2}\cup{Q_{4}} and \Omega^{P^{2}}=Q_{1}\cup{Q_{3}} . The algorithm produces the plot for the Lyapunov function for this system as seen on the right of Figure 2 , as well as plots for its orbital derivatives in Figure 5 . These final two figures show that the constraints in ( 8 ) have been met. Figure 5. Plots of the orbital derivatives of the Lyapunov function displayed on the right of Figure 2 : \nabla{v}(x,y)\cdot\mathbf{f}_{2}(x,y) (top left), \nabla{v}(x,y)\cdot\mathbf{f}_{3}(x,y) (top right) and \nabla{v}(x,y)\cdot\mathbf{f}_{1}(x,y) (bottom). For the systems \mathbf{f}_{2} and \mathbf{f}_{3} the orbital derivatives are plotted in the quadrants where their respective function is defined. The planes \{z=0\} have been plotted to illustrate that the constraints in ( 8 ) have been met. 5. Conclusion This paper presents a new method for the construction of a Lyapunov function for switched systems. The method is applicable to both arbitrary switched and variable structure systems, as well as systems that employ both time- and state-dependent switching. We have shown that the existence of a Lyapunov function implies that the origin is an asymptotically stable equilibrium point of the switched system. An algorithm to construct a Lyapunov function is presented which finds an approximate solution to a system of partial differential inequalities using meshfree collocation and quadratic programming. Future work ( 12 ) will prove the existence of a Lyapunov function, and therefore the feasibility of problem ( 14 ). Moreover, we will study the convergence of the algorithm presented in this paper, i.e. we will show that the sequence of functions v_{n} strongly converges to a solution V of the original system of partial differential inequalities ( 5 ). Here, v_{n} is the solution of the discretised problem with N_{n} collocation points, such that the appropriate fill distances converge to zero.