\documentclass[reqno]{amsart} \usepackage{graphicx} \usepackage{hyperref} \AtBeginDocument{{\noindent\small {\em Electronic Journal of Differential Equations}, Monograph 08, 2007, (101 pages).\newline ISSN: 1072-6691. URL: http://ejde.math.txstate.edu or http://ejde.math.unt.edu \newline ftp ejde.math.txstate.edu (login: ftp)} \thanks{\copyright 2007 Texas State University - San Marcos.} \vspace{9mm}} \begin{document} \title[\hfilneg EJDE-2007/Mon. 08\hfil Lyapunov functions] {An algorithm for constructing\\ Lyapunov functions} \author[S. F. Hafstein\hfil EJDE-2007/Mon. 08\hfilneg] {Sigurdur Freyr Hafstein} \address{Sigurdur Freyr Hafstein \newline School of Science and Engineering\\ Reykjavik University\\ Reykjavik, Iceland} \email{sigurdurh@ru.is} \thanks{Submitted August 29, 2006. Published August 15, 2007.} \subjclass[2000]{35J20, 35J25} \keywords{Lyapunov functions; switched systems; converse theorem; \hfill\break\indent piecewise affine functions} \begin{abstract} In this monograph we develop an algorithm for constructing Lyapunov functions for arbitrary switched dynamical systems $\dot{\mathbf{x}} = \mathbf{f}_\sigma(t,\mathbf{x})$, possessing a uniformly asymptotically stable equilibrium. Let $\dot{\mathbf{x}}=\mathbf{f}_p(t,\mathbf{x})$, $p\in\mathcal{P}$, be the collection of the ODEs, to which the switched system corresponds. The number of the vector fields $\mathbf{f}_p$ on the right-hand side of the differential equation is assumed to be finite and we assume that their components $f_{p,i}$ are $\mathcal{C}^2$ functions and that we can give some bounds, not necessarily close, on their second-order partial derivatives. The inputs of the algorithm are solely a finite number of the function values of the vector fields $\mathbf{f}_p$ and these bounds. The domain of the Lyapunov function constructed by the algorithm is only limited by the size of the equilibrium's region of attraction. Note, that the concept of a Lyapunov function for the arbitrary switched system $\dot{\mathbf{x}} = \mathbf{f}_\sigma(t,\mathbf{x})$ is equivalent to the concept of a common Lyapunov function for the systems $\dot{\mathbf{x}}=\mathbf{f}_p(t,\mathbf{x})$, $p\in\mathcal{P}$, and that if $\mathcal{P}$ contains exactly one element, then the switched system is just a usual ODE $\dot{\mathbf{x}}=\mathbf{f}(t,\mathbf{x})$. We give numerous examples of Lyapunov functions constructed by our method at the end of this monograph. \end{abstract} \maketitle \tableofcontents \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{definition}[theorem]{Definition} \newtheorem{SwS}[theorem]{Switched System} \newtheorem{procedure}[theorem]{Procedure} \allowdisplaybreaks \newcommand{\diff}[2]{\frac{d{#1}}{d{#2}}} \newcommand{\pdiff}[2]{\frac{\partial{#1}}{\partial{#2}}} \section{Introduction} Let $\mathcal{P}$ be a nonempty set and equip it with the discrete metric, let $\mathcal{U}\subset \mathbb{R}^n$ be a domain containing the origin, and let $\|\cdot\|$ be a norm on $\mathbb{R}^n$. For every $p\in\mathcal{P}$ assume that $\mathbf{f}_p: \mathbb{R}_{\geq0}\times \mathcal{U} \to \mathbb{R}^n$ satisfies the local Lipschitz condition: for every compact $\mathcal{C}\in\mathbb{R}_{\geq0}\times \mathcal{U}$ there is a constant $L_{p,\mathcal{C}}$ such that $(t,\mathbf{x}),(t,\mathbf{y})\in \mathcal{C}$ implies $\|\mathbf{f}_p(t,\mathbf{x}) - \mathbf{f}_p(t,\mathbf{y})\|\leq L_{p,\mathcal{C}}\|\mathbf{x}-\mathbf{y}\|$. Define $\mathcal{B}_{\|\cdot\|,R}:= \{\mathbf{x}\in\mathbb{R}^n : \|\mathbf{x}\|0$. We consider the switched system $\dot{\mathbf{x}}=\mathbf{f}_\sigma(t,\mathbf{x})$, where $\sigma$ is an arbitrary right-continuous mapping $\mathbb{R}_{\geq0} \to\mathcal{P}$ of which the discontinuity-points form a discrete set. In this monograph we establish the claims made in the abstract in the following three steps: First, we show that the origin is a uniformly asymptotically stable equilibrium of the arbitrary switched system $\dot{\mathbf{x}}=\mathbf{f}_\sigma(t,\mathbf{x})$, whenever there exists a common Lyapunov function for the systems $\dot{\mathbf{x}}=\mathbf{f}_p(t,\mathbf{x})$, $p\in\mathcal{P}$, and we show how to derive a lower bound on the equilibrium's region of attraction from such a Lyapunov function. Second, we show that if $\mathcal{B}_{\|\cdot\|,R}\subset\mathcal{U}$ is a subset of the region of attraction of the arbitrary switched system $\dot{\mathbf{x}}=\mathbf{f}_\sigma(t,\mathbf{x})$ and the vector fields $\mathbf{f}_p$, $p\in\mathcal{P}$, satisfy the Lipschitz condition: there exists a constant $L$ such that for every $p\in\mathcal{P}$ and every $(s,\mathbf{x}),(t,\mathbf{y})\in \mathbb{R}_{\geq 0} \times \mathcal{B}_{\|\cdot\|,R}$ the inequality $\|\mathbf{f}_p(s,\mathbf{x}) - \mathbf{f}_p(t,\mathbf{y})\|\leq L(|s-t|+\|\mathbf{x}-\mathbf{y}\|)$ holds; then for every $00} \times \mathcal{U}$. Further, note that if $\sigma,\varsigma \in \mathcal{S}_\mathcal{P}$, $\sigma \neq \varsigma$, then in general $\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})$ is not equal to $\boldsymbol{\phi}_\varsigma(t,t_0,\boldsymbol{\xi})$ and that if the Switched System \ref{POLYSYS} is autonomous, that is, none of the vector fields $\mathbf{f}_p$, $p\in\mathcal{P}$, does depend on the time $t$, then $$ \boldsymbol{\phi}_\sigma(t,t',\mathbf{x}) = \boldsymbol{\phi}_\gamma(t-t',0,\boldsymbol{\xi}),\quad \text{where $\gamma(s) := \sigma(s+t')$ for all $s\geq 0$}, $$ for all $t\geq t'\geq0$ and all $\boldsymbol{\xi}\in\mathcal{U}$. Therefore, we often suppress the middle argument of the solution to an autonomous system and simply write $\boldsymbol{\phi}_\sigma(t,\boldsymbol{\xi})$. We later need the following generalization of Theorem \ref{APPLEMMA} to switched systems. \begin{theorem} \label{APPLEMMASW} Consider the Switched System \ref{POLYSYS}, let $\|\cdot\|$ be a norm on $\mathbb{R}^n$, and assume that the functions $\mathbf{f}_p$ satisfy the Lipschitz condition: there exists a constant $L$ such that $$ \|\mathbf{f}_p(t,\mathbf{x})-\mathbf{f}_p(t,\mathbf{y})\| \leq L\|\mathbf{x}-\mathbf{y}\| $$ for all $t\geq 0$, all $\mathbf{x},\mathbf{y}\in\mathcal{U}$, and all $p\in\mathcal{P}$. Let $t_0 \geq 0$, let $\boldsymbol{\xi},\boldsymbol{\eta}\in\mathcal{U}$, let $\sigma,\varsigma\in\mathcal{S}_\mathcal{P}$, and assume there is a constant $\delta\geq 0$ such that $$ \|\mathbf{f}_{\sigma(t)}(t,\mathbf{x})-\mathbf{f}_{\varsigma(t)}(t,\mathbf{x})\| \leq \delta $$ for all $t\geq 0$ and all $\mathbf{x}\in\mathcal{U}$. Denote the solution to the initial value problem $$ \dot{\mathbf{x}} = \mathbf{f}_{\sigma}(t,\mathbf{x}),\quad \mathbf{x}(s_0) = \boldsymbol{\xi}, $$ by $\mathbf{y}:\mathcal{I}_\mathbf{y} \to \mathbb{R}^n$ and denote the solution to the initial value problem $$ \dot{\mathbf{x}} = \mathbf{f}_{\varsigma}(t,\mathbf{x}),\quad \mathbf{x}(s_0) = \boldsymbol{\eta}, $$ by $\mathbf{z}:\mathcal{I}_\mathbf{z}\to \mathbb{R}^n$. Set $\mathcal{J} := \mathcal{I}_\mathbf{y} \cap \mathcal{I}_\mathbf{z}$ and set $\gamma := \|\boldsymbol{\xi} - \boldsymbol{\eta}\|$. Then the inequality \begin{equation} \label{APPLEMMASWIE1} \|\mathbf{y}(t) - \mathbf{z}(t)\| \leq \gamma e^{L|t-s_0|} + \frac{\delta}{L}(e^{L|t-s_0|}-1) \end{equation} holds for all $t\in\mathcal{J}$. \end{theorem} \begin{proof} We prove only inequality (\ref{APPLEMMASWIE1}) for $t\geq s_0$, the case $t 0 \quad \text{for all $x\in \mathcal{I} \setminus \mathcal{C}$}, &&\text{implies that } \text{$g$ is a strictly monotonically }\\ & &&\text{increasing function on $\mathcal{I}$.}\\ &D^*g(x) \leq 0 \quad \text{for all $x\in \mathcal{I} \setminus \mathcal{C}$}, &&\text{implies that } \text{$g$ is a monotonically }\\ & &&\text{decreasing function on $\mathcal{I}$.}\\ &D^*g(x) < 0 \quad \text{for all $x\in \mathcal{I} \setminus \mathcal{C}$}, &&\text{implies that } \text{$g$ is a strictly monotonically }\\ & && \text{decreasing function on $\mathcal{I}$.} \end{align*} \end{corollary} \subsection{Stability of arbitrary switched systems} The concepts equilibrium point and stability are motivated by the desire to keep a dynamical system in, or at least close to, some desirable state. The term {\it equilibrium} or {\it equilibrium point} of a dynamical system, is used for a state of the system that does not change in the course of time, that is, if the system is at an equilibrium at time $t=0$, then it will stay there for all times $t > 0$. \begin{definition}[Equilibrium point] \rm A state $\mathbf{y}$ in the state-space of the Switched System \ref{POLYSYS} is called an equilibrium or an equilibrium point of the system, if and only if $\mathbf{f}_p(t,\mathbf{y})=\boldsymbol{0}$ for all $p\in\mathcal{P}$ and all $t\geq0$. \end{definition} If $\mathbf{y}$ is an equilibrium point of Switched System \ref{POLYSYS}, then obviously the initial value problem $$ \dot{\mathbf{x}} = \mathbf{f}_\sigma(t,\mathbf{x}),\quad \mathbf{x}(0) = \mathbf{y} $$ has the solution $\mathbf{x}(t) = \mathbf{y}$ for all $t\geq 0$ regardless of the switching signal $\sigma \in \mathcal{S}$. The solution with $\mathbf{y}$ as an initial value in the state-space is thus a constant vector and the state does not change in the course of time. By a translation in the state-space one can always reach that $\mathbf{y} = \boldsymbol{0}$ without affecting the dynamics. Hence, there is no loss of generality in assuming that a particular equilibrium point is at the origin. A real-world system is always subject to some fluctuations in the state. There are some external effects that are unpredictable and cannot be modelled, some dynamics that have (hopefully) very little impact on the behavior of the system are neglected in the modelling, etc. Even if the mathematical model of a physical system would be perfect, which hardly seems possible, the system state would still be subject to quantum mechanical fluctuations. The concept of local stability in the theory of dynamical systems is motivated by the desire, that the system state stays at least close to an equilibrium point after small fluctuations in the state. Any system that is expected to do something useful must have a predictable behavior to some degree. This excludes all equilibria that are not locally stable as usable working points for a dynamical system. Local stability is thus a minimum requirement for an equilibrium. It is, however, not a very strong property. It merely states, that there are disturbances that are so small, that they do not have a great effect on the system in the long run. In this monograph we will concentrate on {\it uniform asymptotic stability on a set} containing the equilibrium. This means that we are demanding that the {\it uniform asymptotic stability} property of the equilibrium is not merely valid for some, possibly arbitrary small, neighborhood of the origin, but this property must hold on a a\,priori defined neighborhood of the origin. This is a much more robust and powerful concept. It denotes, that all disturbances up to a certain known degree are ironed out by the dynamics of the system, and, because the domain of the Lyapunov functions is only limited by the size of the equilibriums' region of attraction, that we can get a reasonable lower bound on the region of attraction. The common stability concepts are most practically characterized by the use of so-called $\mathcal{K}$, $\mathcal{L}$, and $\mathcal{K}\mathcal{L}$ functions. \begin{definition}[Comparison functions $\mathcal{K}$, $\mathcal{L}$, and $\mathcal{K}\mathcal{L}$] \rm The function classes $\mathcal{K}$, $\mathcal{L}$, and $\mathcal{K}\mathcal{L}$ of comparison functions are defined as follows: \begin{itemize} \item[(i)] A continuous function $\alpha:\mathbb{R}_{\geq0} \to \mathbb{R}_{\geq0}$ is said to be of class $\mathcal{K}$, if and only if $\alpha(0)=0$, it is strictly monotonically increasing, and $\lim_{r \to +\infty}\alpha(r) = +\infty$. \item[(ii)] A continuous function $\beta:\mathbb{R}_{\geq0} \to \mathbb{R}_{\geq0}$ is said to be of class $\mathcal{L}$, if and only if it is strictly monotonically decreasing and $\lim_{s \to +\infty}\beta(s) = 0$. \item[(iii)] A continuous function $\varsigma:\mathbb{R}_{\geq 0} \times \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}$ is said to be of class $\mathcal{K}\mathcal{L}$, if and only if for every fixed $s\in\mathbb{R}_{\geq0}$ the mapping $r \mapsto \varsigma(r,s)$ is of class $\mathcal{K}$ and for every fixed $r\in\mathbb{R}_{\geq0}$ the mapping $s \mapsto \varsigma(r,s)$ is of class $\mathcal{L}$. \end{itemize} \end{definition} Note that some authors make a difference between strictly monotonically increasing functions that vanish at the origin and strictly monotonically increasing functions that vanish at the origin and additionally asymptotically approach infinity at infinity. They usually denote the functions of the former type as class $\mathcal{K}$ functions and the functions of the latter type as class $\mathcal{K}_\infty$ functions. We are not interested in functions of the former type and in this work $\alpha\in\mathcal{K}$ always implies $\lim_{r \to +\infty} \alpha(r) = +\infty$. We now define various stability concepts for equilibrium points of switched dynamical systems with help of the comparison functions. \begin{definition}[Stability concepts for equilibria] \label{STABDEFS} \rm Assume that the origin is an equilibrium point of the Switched System \ref{POLYSYS}, denote by $\boldsymbol{\phi}$ the solution to the system, and let $\|\cdot\|$ be an arbitrary norm on $\mathbb{R}^n$. \begin{itemize} \item[(i)] The origin is said to be a uniformly stable equilibrium point of the Switched System \ref{POLYSYS} on a neighborhood $\mathcal{N}\subset\mathcal{U}$ of the origin, if and only if there exists an $\alpha\in \mathcal{K}$ such that for every $\sigma\in\mathcal{S}_\mathcal{P}$, every $t\geq t_0\geq0$, and every $\boldsymbol{\xi}\in\mathcal{N}$ the following inequality holds $$ \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \leq \alpha(\|\boldsymbol{\xi}\|). $$ \item[(ii)] The origin is said to be a uniformly asymptotically stable equilibrium point of the Switched System \ref{POLYSYS} on the neighborhood $\mathcal{N}\subset\mathcal{U}$ of the origin, if and only if there exists a $\varsigma\in \mathcal{K}\mathcal{L}$ such that for every $\sigma\in\mathcal{S}_\mathcal{P}$, every $t\geq t_0\geq0$, and every $\boldsymbol{\xi}\in\mathcal{N}$ the following inequality holds \begin{equation} \label{UAS1} \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \leq \varsigma(\|\boldsymbol{\xi}\|,t-t_0). \end{equation} \item[(iii)] The origin is said to be a uniformly exponentially stable equilibrium point of the Switched System \ref{POLYSYS} on the neighborhood $\mathcal{N}\subset\mathcal{U}$ of the origin, if and only if there exist constants $k>0$ and $\gamma > 0$, such that for every $\sigma\in\mathcal{S}_\mathcal{P}$, every $t\geq t_0\geq0$, and every $\boldsymbol{\xi}\in\mathcal{N}$ the following inequality holds \begin{equation*} \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \leq ke^{-\gamma (t-t_0)}\|\boldsymbol{\xi}\|. \end{equation*} \end{itemize} \end{definition} The stability definitions above imply, that if the origin is a uniformly exponentially stable equilibrium of the Switched System \ref{POLYSYS} on the neighborhood $\mathcal{N}$, then the origin is a uniformly asymptotically stable equilibrium on $\mathcal{N}$ as well, and, if the origin is a uniformly asymptotically stable equilibrium of the Switched System \ref{POLYSYS} on the neighborhood $\mathcal{N}$, then the origin is a uniformly stable equilibrium on $\mathcal{N}$. If the Switched System \ref{POLYSYS} is autonomous, then the stability concepts presented above for the systems equilibria are {\it uniform} in a canonical way, that is, independent of $t_0$, and the definitions are somewhat more simple. \begin{definition} \label{STABDEFS2} \rm (Stability concepts for equilibria of autonomous systems)\quad Assume that the origin is an equilibrium point of the Switched System \ref{POLYSYS}, denote by $\boldsymbol{\phi}$ the solution to the system, let $\|\cdot\|$ be an arbitrary norm on $\mathbb{R}^n$, and assume that the system is autonomous. \begin{itemize} \item[(i)] The origin is said to be a stable equilibrium point of the autonomous Switched System \ref{POLYSYS} on a neighborhood $\mathcal{N}\subset\mathcal{U}$ of the origin, if and only if there exists an $\alpha\in \mathcal{K}$ such that for every $\sigma\in\mathcal{S}_\mathcal{P}$, every $t\geq0$, and every $\boldsymbol{\xi}\in\mathcal{N}$ the following inequality holds $$ \|\boldsymbol{\phi}_\sigma(t,\boldsymbol{\xi})\| \leq \alpha(\|\boldsymbol{\xi}\|). $$ \item[(ii)] The origin is said to be an asymptotically stable equilibrium point of the autonomous Switched System \ref{POLYSYS} on the neighborhood $\mathcal{N}\subset\mathcal{U}$ of the origin, if and only if there exists a $\varsigma\in \mathcal{K}\mathcal{L}$ such that for every $\sigma\in\mathcal{S}_\mathcal{P}$, every $t\geq0$, and every $\boldsymbol{\xi}\in\mathcal{N}$ the following inequality holds \begin{equation*} \|\boldsymbol{\phi}_\sigma(t,\boldsymbol{\xi})\| \leq \varsigma(\|\boldsymbol{\xi}\|,t). \end{equation*} \item[(iii)] The origin is said to be an exponentially stable equilibrium point of the Switched System \ref{POLYSYS} on the neighborhood $\mathcal{N}\subset\mathcal{U}$ of the origin, if and only if there exist constants $k>0$ and $\gamma > 0$, such that for every $\sigma\in\mathcal{S}_\mathcal{P}$, every $t\geq0$, and every $\boldsymbol{\xi}\in\mathcal{N}$ the following inequality holds \begin{equation*} \|\boldsymbol{\phi}_\sigma(t,\boldsymbol{\xi})\| \leq ke^{-\gamma t}\|\boldsymbol{\xi}\|. \end{equation*} \end{itemize} \end{definition} The set of those points in the state-space of a dynamical system, that are attracted to an equilibrium point by the dynamics of the system, is of great importance. It is called the {\it region of attraction} of the equilibrium. Some authors prefer {\it domain}, {\it basin}, or even {\it bassin} instead of {\it region}. For nonautonomous systems it might depend on the initial time. \begin{definition}[Region of attraction] \rm Assume that $\mathbf{y}=\boldsymbol{0}$ is an equilibrium point of the Switched System \ref{POLYSYS} and let $\boldsymbol{\phi}$ be the solution to the system. For every $t_0\in\mathbb{R}_{\geq 0}$ the set $$ \mathcal{R}_{\it Att}^{t_0} := \{\boldsymbol{\xi} \in \mathcal{U} : \ \limsup_{t \to +\infty} \boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi}) = \boldsymbol{0}\quad \text{for all $\sigma\in\mathcal{S}_\mathcal{P}$}\} $$ is called the region of attraction with respect to $t_0$ of the equilibrium at the origin. The region of attraction $\mathcal{R}_{\it Att}$ of the equilibrium at the origin is defined by $$ \mathcal{R}_{\it Att} := \bigcap_{t_0 \geq 0}\mathcal{R}_{\it Att}^{t_0}. $$ \end{definition} Thus, for the Switched System \ref{POLYSYS}, $\boldsymbol{\xi} \in \mathcal{R}_{\it Att}$ implies $\lim_{t \to +\infty} \boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi}) = \boldsymbol{0}$ for all $\sigma\in\mathcal{S}_\mathcal{P}$ and all $t_0\geq 0$. \subsection{Three useful lemmas} It is often more convenient to work with smooth rather that merely continuous functions and later on we need estimates by convex $\mathcal{C}^\infty\cap\mathcal{K}$ functions. The two next lemmas state some useful facts in this regard. \begin{lemma}\label{SOBLEMMA} Let $f:\mathbb{R}_{>0} \to \mathbb{R}_{\geq 0}$ be a monotonically decreasing function. Then there exists a function $g:\mathbb{R}_{>0} \to \mathbb{R}_{> 0}$ with the following properties: \begin{enumerate} \item[(i)] $g\in\mathcal{C}^\infty(\mathbb{R}_{>0})$. \item[(ii)] $g(x) > f(x)$ for all $x\in\mathbb{R}_{>0}$. \item[(iii)] $g$ is strictly monotonically decreasing. \item[(iv)] $\lim_{x \to 0+} g(x)= +\infty$ and $\lim_{x \to +\infty} g(x) = \lim_{x \to +\infty} f(x)$. \item[(v)] $g$ is invertible and $g^{-1} \in \mathcal{C}^\infty(g(\mathbb{R}_{>0}))$. \end{enumerate} \end{lemma} \begin{proof} We define the function $\widetilde{h}: \mathbb{R}_{>0} \to \mathbb{R}_{>0}$ by, $$ \widetilde{h}(x) :=\begin{cases} f\big(\frac{1}{n+1}\big)+\frac{1}{x}, &\text{if $x\in[\frac{1}{n+1},\frac{1}{n}[\ $ for some $n\in\mathbb{N}_{>0}$,}\\ f(n)+\frac{1}{x}, &\text{if $x\in [n,n+1[\ $ for some $n\in\mathbb{N}_{>0}$,} \end{cases} $$ and the function $h: \mathbb{R}_{>0} \to \mathbb{R}_{> 0}$ by $$ h(x) := \widetilde{h}(x-\tanh(x)). $$ Then $h$ is a strictly monotonically decreasing measurable function and because $\widetilde{h}$ is, by its definition, strictly monotonically decreasing and larger than $f$, we have $$ h(x+\tanh(x)) =\widetilde{h}(x+\tanh(x) - \tanh(x+\tanh(x))) > \widetilde{h}(x) > f(x) $$ for all $x\in\mathbb{R}_{>0}$. Let $\rho\in\mathcal{C}^\infty(\mathbb{R})$ such that $\rho(x) \geq 0$ for all $x\in\mathbb{R}$, $\operatorname{supp}(\rho) \subset\, ]-1,1[$, and $\int_\mathbb{R}\rho(x)dx=1$. We claim that the function $g:\mathbb{R}_{>0} \to \mathbb{R}_{>0}$, $$ g(x):= \int_{x-\tanh(x)}^{x+\tanh(x)} \rho\big(\frac{x-y}{\tanh(x)}\big) \frac{h(y)}{\tanh(x)}dy = \int_{-1}^1 \rho_1(y)h(x-y\tanh(x))dy, $$ fulfills the properties (i)--(v). Proposition (i) follows from elementary Lebesgue integration theory. Proposition (ii) follows from \begin{align*} g(x) &= \int_{-1}^1 \rho(y)h(x-y\tanh(x))dy\\ & > \int_{-1}^1 \rho(y)h(x+\tanh(x))dy\\ & > \int_{-1}^1 \rho(y)f(x)dy = f(x). \end{align*} To see that $g$ is strictly monotonically decreasing let $t>s>0$ and consider that \begin{equation} \label{HHHHH} t-y\tanh(t) > s-y\tanh(s) \end{equation} for all $y$ in the interval $[-1,1]$. Inequality (\ref{HHHHH}) follows from \begin{align*} t-y\tanh(t) - [s-y\tanh(s)] &= t-s -y[\tanh(t)-\tanh(s)]\\ &= t-s - y(t-s)(1-\tanh^2(s + \vartheta_{t,s}(t-s))) > 0, \end{align*} for some $\vartheta_{t,s} \in [0,1]$, where we used the Mean-value theorem. But then $$ h(t-y\tanh(t)) < h(s-y\tanh(s)) $$ for all $y\in[-1,1]$ and the definition of $g$ implies that $g(t)0}))$, that is, proposition (v). \end{proof} \begin{lemma} \label{CONVLEMMA} Let $\alpha\in\mathcal{K}$. Then, for every $R>0$, there is a function $\beta_R \in \mathcal{K}$, such that: \begin{itemize} \item[(i)] $\beta_R$ is a convex function. \item[(ii)] $\beta_R$ restricted to $\mathbb{R}_{>0}$ is infinitely differentiable. \item[(iii)] For all $0\leq x \leq R$ we have $\beta_R(x) \leq \alpha(x)$. \end{itemize} \end{lemma} \begin{proof} By Lemma \ref{SOBLEMMA} there is a function $g$, such that $g\in\mathcal{C}^\infty(\mathbb{R}_{>0})$, $g(x) > 1/\alpha(x)$ for all $x>0$, $\lim_{t \to 0+} g(x) = +\infty$, and $g$ is strictly monotonically decreasing. Then the function $\beta_R:\mathbb{R}_{\geq0} \to \mathbb{R}_{\geq 0}$, defined through $$ \beta_R(x) := \frac{1}{R}\int_0^x \frac{d\tau}{g(\tau)}, $$ has the desired properties. First, $\beta_R(0)=0$ and for every $0 < x\leq R$ we have $$ \beta_R(x) = \frac{1}{R}\int_0^x\frac{d\tau}{g(\tau)} \leq \frac{1}{g(x)} < \alpha(x). $$ Second, to prove that $\beta_R$ is a convex $\mathcal{K}$ function is suffices to prove that the second derivative of $\beta_R$ is strictly positive. But this follows immediately because for every $x >0$ we have $g'(x) <0$, which implies $$ \frac{d^{\,2}\beta_R}{dx^2}(x) = \frac{-g'(x)}{R[g(x)]^2} > 0. $$ \end{proof} The third existence lemma is the well known and very useful Massera's lemma \cite{massera}. \begin{lemma}[Massera's lemma] \label{MLEMMA} Let $f\in\mathcal{L}$ and $\lambda\in \mathbb{R}_{>0}$. Then there is a function $g\in\mathcal{C}^{1}(\mathbb{R}_{\geq 0})$, such that $g,g'\in\mathcal{K}$, $g$ restricted to $\mathbb{R}_{>0}$ is a $\mathcal{C}^{\infty}(\mathbb{R}_{>0})$ function, $$ \int_0^{+\infty} g(f(t))dt < +\infty,\quad \text{and}\quad \int_0^{+\infty}g'(f(t))e^{\lambda t}dt < +\infty. $$ \end{lemma} Note, that because $g,g'\in\mathcal{K}$ in Massera's lemma above, we have for every measurable function $u:\mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}$, such that $u(t) \leq f(t)$ for all $t\in\mathbb{R}_{\geq 0}$, that $$ \int_0^{+\infty} g(u(t))dt \leq \int_0^{+\infty} g(f(t))dt \quad \text{and}\quad \int_0^{+\infty}g'(u(t))e^{\lambda t}dt \leq \int_0^{+\infty}g'(f(t))e^{\lambda t}dt. $$ It is further worth noting that Massera's lemma can be proved quite simply by using Lemma \ref{SOBLEMMA}, which implies that there is a strictly monotonically decreasing $\mathcal{C}^{\infty}(\mathbb{R}_{>0})$ bijective function $h:\mathbb{R}_{>0}\to\mathbb{R}_{>0}$ such that $h(x) > f(x)$ for all $x >0$ and $h^{-1}\in\mathcal{C}^{\infty}(\mathbb{R}_{>0})$. The function $g:\mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}$, $$ g(t) := \int_0^t e^{-(1+\lambda)h^{-1}(\tau)}d\tau, $$ then fulfills the claimed properties. \subsection{Linear programming} For completeness we spend a few words on linear programming problems. A linear programming problem is a set of linear constraints, under which a linear function is to be minimized. There are several equivalent possibilities to state a linear programming problem, one of them is \begin{equation} \label{DEFLINP} \begin{gathered} \text{minimize}\quad g(\mathbf{x}) := \mathbf{c}\cdot\mathbf{x},\\ \text{given}\quad C\mathbf{x} \leq \mathbf{b},\quad \mathbf{x} \geq \boldsymbol{0}, \end{gathered} \end{equation} where $r,s>0$ are integers, $C \in \mathbb{R}^{s\times r}$ is a matrix, $\mathbf{b} \in \mathbb{R}^s$ and $\mathbf{c} \in \mathbb{R}^r$ are vectors, and $\mathbf{x} \leq \mathbf{y}$ denotes $x_i \leq y_i$ for all $i$. The function $g$ is called the objective of the linear programming problem and the conditions $C\mathbf{x} \leq \mathbf{b}$ and $\mathbf{x} \geq \boldsymbol{0}$ together are called the constraints. A feasible solution to the linear programming problem is a vector $\mathbf{x}' \in \mathbb{R}^r$ that satisfies the constraints, that is, $\mathbf{x}' \geq \boldsymbol{0}$ and $C\mathbf{x}' \leq\mathbf{b}$. There are numerous algorithms known to solve linear programming problems, the most commonly used being the simplex method (see, for example, \cite{TLIP}) or interior point algorithms, for example, the primal-dual logarithmic barrier method (see, for example, \cite{Roos97}). Both need a starting feasible solution for initialization. A feasible solution to (\ref{DEFLINP}) can be found by introducing slack variables $\mathbf{y} \in \mathbb{R}^s$ and solving the linear programming problem: \begin{equation} \label{SLACK} \begin{gathered} \text{minimize}\quad g(\begin{bmatrix}\mathbf{x} \\ \mathbf{y} \end{bmatrix}) := \sum_{i=1}^s y_i ,\\ \text{given }\quad \begin{bmatrix}C & -I_s \end{bmatrix} \begin{bmatrix}\mathbf{x} \\ \mathbf{y} \end{bmatrix} \leq \mathbf{b},\quad \begin{bmatrix}\mathbf{x} \\ \mathbf{y} \end{bmatrix} \geq \boldsymbol{0}, \end{gathered} \end{equation} which has the feasible solution $\mathbf{x}=\boldsymbol{0}$ and $\mathbf{y} = (|b_1|,|b_2|,\dots,|b_s|)$. If the linear programming problem (\ref{SLACK}) has the solution $g([\mathbf{x}'\ \mathbf{y}']) = 0$, then $\mathbf{x}'$ is a feasible solution to (\ref{DEFLINP}), if the minimum of $g$ is strictly larger than zero, then (\ref{DEFLINP}) does not have any feasible solution. \section{Lyapunov's Direct Method for Switched Systems} \label{SECLDM} The Russian mathematician and engineer Alexandr Mikhailovich Lyapunov published a revolutionary work in 1892 on the stability of motion, where he introduced two methods to study the stability of general continuous dynamical systems. An English translation of this work can be found in \cite{lya1}. The more important of these two methods, known as {\it Lyapunov's second method} or {\it Lyapunov's direct method}, enables one to prove the stability of an equilibrium of (\ref{NNSYSTEM}) without integrating the differential equation. It states, that if $\mathbf{y}=\boldsymbol{0}$ is an equilibrium point of the system, $V \in \mathcal{C}^1(\mathbb{R}_{\geq 0}\times\mathcal{U})$ is a {\it positive definite function}, that is, there exist functions $\alpha_1,\alpha_2\in\mathcal{K}$ such that $$ \alpha_1(\|\mathbf{x}\|_2) \leq V(t,\mathbf{x})\leq \alpha_2(\|\mathbf{x}\|_2) $$ for all $\mathbf{x}\in\mathcal{U}$ and all $t\in\mathbb{R}_{\geq 0}$, and $\boldsymbol{\phi}$ is the solution to the ODE (\ref{NNSYSTEM}). Then the equilibrium is uniformly asymptotically stable, if there is an $\omega \in \mathcal{K}$ such that the inequality \begin{equation} \label{UAS2} \begin{aligned} \diff{}{t}V(t,\boldsymbol{\phi}(t,t_0,\boldsymbol{\xi})) & = [\nabla_\mathbf{x} V](t,\boldsymbol{\phi}(t,t_0,\boldsymbol{\xi}))\cdot \mathbf{f}(t,\boldsymbol{\phi}(t,t_0,\boldsymbol{\xi})) + \pdiff{V}{t}(t,\boldsymbol{\phi}(t,t_0,\boldsymbol{\xi})) \\ & \leq -\omega(\|\boldsymbol{\phi}(t,t_0,\boldsymbol{\xi})\|_2) \end{aligned} \end{equation} holds for all $\boldsymbol{\phi}(t,t_0,\boldsymbol{\xi})$ in an open neighborhood $\mathcal{N}\subset \mathcal{U}$ of the equilibrium $\mathbf{y}$. In this case the equilibrium is uniformly asymptotically stable on a neighborhood, which depends on $V$, of the origin. The function $V$ satisfying (\ref{UAS2}) is said to be a {\it Lyapunov function} for (\ref{NNSYSTEM}). The direct method of Lyapunov is covered in practically all modern textbooks on nonlinear systems and control theory. Some good examples are \cite{hahn,hirsch04,NS,NSASAC,vidyasagar,bhatiaszegoe,willems70}. We will prove, that if the time-derivative in the inequalities above is replaced with a Dini derivative with respect to $t$, then the assumption $V\in\mathcal{C}^1(\mathbb{R}_{\geq 0}\times\mathcal{U})$ can be replaced with the less restrictive assumption, that $V$ is merely continuous. The same is done in Theorem 42.5 in \cite{hahn}, but a lot of details are left out. Further, we generalize the results to arbitrary switched systems. Before we state and prove the direct method of Lyapunov for switched systems, we prove a lemma that we use in its proof. \begin{lemma} \label{DMLLEMMA} Assume that the origin is an equilibrium of the Switched System \ref{POLYSYS} and let $\|\cdot\|$ be a norm on $\mathbb{R}^n$. Further, assume that there is a function $\alpha\in \mathcal{K}$, such that for all $\sigma\in\mathcal{S}_\mathcal{P}$ and all $t \geq t_0 \geq0$ the inequality \begin{equation} \label{GBSR} \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \leq \alpha(\|\boldsymbol{\xi}\|) \end{equation} holds for all $\boldsymbol{\xi}$ in some bounded neighborhood $\mathcal{N} \subset \mathcal{U}$ of the origin. Under these assumptions the following two propositions are equivalent: \begin{enumerate} \item[(i)] There exists a function $\beta \in \mathcal{L}$, such that $$ \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \leq \sqrt{\alpha(\|\boldsymbol{\xi}\|)}\beta(t-t_0) $$ for all $\sigma \in \mathcal{S}_\mathcal{P}$, all $t\geq t_0\geq 0$, and all $\boldsymbol{\xi}\in\mathcal{N}$. \item[(ii)] For every $\varepsilon >0$ there exists a $T>0$, such that for every $t_0 \geq 0$, every $\sigma\in\mathcal{S}_\mathcal{P}$, and every $\boldsymbol{\xi}\in \mathcal{N}$ the inequality $$ \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \leq \varepsilon $$ holds for all $t\geq T + t_0$. \end{enumerate} \end{lemma} \begin{proof} Let $R>0$ be so large that $\mathcal{N} \subset \mathcal{B}_{\|\cdot\|,R}$ and set $C:= \max\{1,\alpha(R)\}$. Note that Proposition (i) implies proposition (ii): For every $\varepsilon >0$ we set $T:= \beta^{-1}(\varepsilon/\sqrt{\alpha(R)})$ and proposition (ii) follows immediately. Proposition (ii) implies proposition (i): For every $\varepsilon >0$ define $\widetilde{T}(\varepsilon)$ as the infimum of all $T>0$ with the property, that for every $t_0 \geq 0$, every $\sigma\in\mathcal{S}_\mathcal{P}$, and every $\boldsymbol{\xi}\in \mathcal{N}$ the inequality $$ \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \leq \varepsilon $$ holds for all $t\geq T+t_0$. Then $\widetilde{T}$ is a monotonically decreasing function $\mathbb{R}_{>0} \to \mathbb{R}_{\geq 0}$ and, because of (\ref{GBSR}), $\widetilde{T}(\varepsilon)= 0$ for all $\varepsilon > \alpha(R)$. By Lemma \ref{SOBLEMMA} there exists a strictly monotonically decreasing $\mathcal{C}^{\infty}(\mathbb{R}_{>0})$ bijective function $g:\mathbb{R}_{>0} \to \mathbb{R}_{>0}$, such that $g(\varepsilon) > \widetilde{T}(\varepsilon)$ for all $\varepsilon >0$. Now, for every pair $t>t_0\geq0$ set $\varepsilon' := g^{-1}(t-t_0)$ and note that because $t = g(\varepsilon') + t_0 \geq \widetilde{T}(\varepsilon') + t_0$ we have $$ g^{-1}(t-t_0) = \varepsilon' \geq \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\|. $$ But then $$ \beta(s) := \begin{cases} \sqrt{2C - C/g(1)\cdot s},\quad &\text{if $s\in[0,g(1)]$,} \\ \sqrt{Cg^{-1}(s)}, &\text{if $s> g(1)$,} \end{cases} $$ is an $\mathcal{L}$ function such that $$ \sqrt{\|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\|} \leq \beta(t-t_0), $$ for all $t\geq t_0\geq 0$ and all $\boldsymbol{\xi}\in\mathcal{N}$, and therefore $$ \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \leq \sqrt{\alpha(\|\boldsymbol{\xi}\|)}\beta(t-t_0). $$ \end{proof} We come to the main theorem of this section: The Lyapunov's direct method for arbitrary switched systems. \begin{theorem} \label{TDMOL} Assume that the Switched System \ref{POLYSYS} has an equilibrium at the origin. Let $\|\cdot\|$ be a norm on $\mathbb{R}^n$ and let $R>0$ be a constant such that the closure of the ball $\mathcal{B}_{\|\cdot\|,R}$ is a subset of $\mathcal{U}$. Let $V:\mathbb{R}_{\geq 0}\times\mathcal{B}_{\|\cdot\|,R}\to \mathbb{R}$ be a continuous function and assume that there exist functions $\alpha_1,\alpha_2\in\mathcal{K}$ such that $$ \alpha_1(\|\boldsymbol{\xi}\|)\leq V(t,\boldsymbol{\xi}) \leq \alpha_2(\|\boldsymbol{\xi}\|) $$ for all $t\geq 0$ and all $\boldsymbol{\xi}\in\mathcal{B}_{\|\cdot\|,R}$. Denote the solution to the Switched System \ref{POLYSYS} by $\boldsymbol{\phi}$ and set $d:= \alpha_2^{-1}(\alpha_1(R))$. Finally, let $D^* \in \{D^+,D_+,D^-,D_-\}$ be a Dini derivative with respect to the time $t$, which means, for example with $D^* = D^+$, that $$ D^+[V(t,\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi}))] := \limsup_{h \to 0+}\frac{V(t+h,\boldsymbol{\phi}_\sigma(t+h,t_0,\boldsymbol{\xi})) - V(t,\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi}))}{h}. $$ Then the following propositions are true: \begin{enumerate} \item[(i)] If for every $\sigma\in\mathcal{S}_\mathcal{P}$, every $\boldsymbol{\xi}\in\mathcal{U}$, and every $t\geq t_0 \geq 0$, such that $\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\in \mathcal{B}_{\|\cdot\|,R}$, the inequality \begin{equation} \label{TDMOLIE1} D^*[V(t,\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi}))] \leq 0 \end{equation} holds, then the origin is a uniformly stable equilibrium of the Switched System \ref{POLYSYS} on $\mathcal{B}_{\|\cdot\|,d}$. \item[(ii)] If there exists a function $\psi \in \mathcal{K}$, with the property that for every $\sigma\in\mathcal{S}_\mathcal{P}$, every $\boldsymbol{\xi}\in\mathcal{U}$, and every $t\geq t_0 \geq 0$, such that $\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\in \mathcal{B}_{\|\cdot\|,R}$, the inequality \begin{equation} \label{TDMOLIE2} D^*[V(t,\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi}))] \leq -\psi(\|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\|) \end{equation} holds, then the origin is a uniformly asymptotically stable equilibrium of the Switched System \ref{POLYSYS} on $\mathcal{B}_{\|\cdot\|,d}$. \end{enumerate} \end{theorem} \begin{proof} Proposition (i): Let $t_0\geq0$, $\boldsymbol{\xi}\in \mathcal{B}_{\|\cdot\|,d}$, and $\sigma\in\mathcal{S}_\mathcal{P}$ all be arbitrary but fixed. By the note after the definition of Switched System \ref{POLYSYS} either $\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi}) \in \mathcal{B}_{\|\cdot\|,R}$ for all $t\geq t_0$ or there is a $t^* > t_0$ such that $\boldsymbol{\phi}_\sigma(s,t_0,\boldsymbol{\xi}) \in \mathcal{B}_{\|\cdot\|,R}$ for all $s\in[t_0,t^*[$ and $\boldsymbol{\phi}_\sigma(t^*,t_0,\boldsymbol{\xi}) \in \partial\mathcal{B}_{\|\cdot\|,R}$. Assume that the second possibility applies. Then, by inequality (\ref{TDMOLIE1}) and Corollary \ref{TEMP51} $$ \alpha_1(R) \leq V(t^*,\boldsymbol{\phi}_\sigma(t^*,t_0,\boldsymbol{\xi})) \leq V(t_0,\boldsymbol{\xi}) \leq \alpha_2(\|\boldsymbol{\xi}\|) < \alpha_2(d), $$ which is contradictory to $d = \alpha_2^{-1}(\alpha_1(R))$. Therefore $\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi}) \in \mathcal{B}_{\|\cdot\|,R}$ for all $t\geq t_0$. But then it follows by inequality (\ref{TDMOLIE1}) and Corollary \ref{TEMP51} that $$ \alpha_1(\|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\|) \leq V(t,\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})) \leq V(t_0,\boldsymbol{\xi}) \leq \alpha_2(\|\boldsymbol{\xi}\|), $$ for all $t\geq t_0$, so $$ \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \leq \alpha_1^{-1}(\alpha_2(\|\boldsymbol{\xi}\|)) $$ for all $t \geq t_0$. Because $\alpha_1^{-1}\circ\alpha_2$ is a class $\mathcal{K}$ function, it follows, because $t_0\geq0$, $\boldsymbol{\xi}\in \mathcal{B}_{\|\cdot\|,d}$, and $\sigma\in\mathcal{S}_\mathcal{P}$ were arbitrary, that the equilibrium at the origin is a uniformly stable equilibrium point of the Switched System \ref{POLYSYS} on $\mathcal{B}_{\|\cdot\|,d}$. Proposition (ii): Inequality (\ref{TDMOLIE2}) implies inequality (\ref{TDMOLIE1}) so Lemma \ref{DMLLEMMA} applies and it suffices to show that for every $\varepsilon>0$ there is a finite $T>0$, such that \begin{equation} \label{UATT} t \geq T + t_0 \quad \text{implies} \quad \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \leq \varepsilon \end{equation} for all $t_0 \geq 0$, all $\boldsymbol{\xi} \in \mathcal{B}_{\|\cdot\|,d}$, and all $\sigma\in\mathcal{S}_\mathcal{P}$. To prove this choose an arbitrary $\varepsilon>0$ and set $$ \delta^* := \min\{d,\alpha_2^{-1}(\alpha_1(\varepsilon))\}\quad \text{and}\quad T := \frac{\alpha_2(d)}{\psi(\delta^*)}. $$ We first prove that for every $\sigma\in\mathcal{S}_\mathcal{P}$ the following proposition: \begin{equation} \label{UATT2} \boldsymbol{\xi} \in \mathcal{B}_{\|\cdot\|,d}\quad \text{and}\quad t_0 \geq 0 \quad \text{implies} \quad \|\boldsymbol{\phi}_\sigma(t^*,t_0,\boldsymbol{\xi})\| < \delta^* \end{equation} for some $t^*\in [t_0,T+t_0]$. We prove (\ref{UATT2}) by contradiction. Assume that \begin{equation} \label{ANNAHME1} \|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \geq \delta^* \end{equation} for all $t\in [t_0,T+t_0]$. Then \begin{equation} \label{CONT1} 0 < \alpha_1(\delta^*) \leq \alpha_1(\|\boldsymbol{\phi}_\sigma(T+t_0,t_0,\boldsymbol{\xi})\|) \leq V(T+t_0,\boldsymbol{\phi}_\sigma(T+t_0,t_0,\boldsymbol{\xi})). \end{equation} By Theorem \ref{MEANVT} and the assumption (\ref{ANNAHME1}), there is an $s\in[t_0,T+t_0]$, such that \begin{align*} \frac{V(T+t_0,\boldsymbol{\phi}_\sigma(T+t_0,t_0,\boldsymbol{\xi})) - V(t_0,\boldsymbol{\xi})}{T} &\leq [D^*V](s,\boldsymbol{\phi}(s,t_0,\boldsymbol{\xi}))] \\ &\leq -\psi(\|\boldsymbol{\phi}_\sigma(s,t_0,\boldsymbol{\xi})\|) \\ &\leq -\psi(\delta^*), \end{align*} that is \begin{align*} V(T+t_0,\boldsymbol{\phi}_\sigma(T+t_0,t_0,\boldsymbol{\xi})) &\leq V(t_0,\boldsymbol{\xi})-T\psi(\delta^*) \\ &\leq \alpha_2(\|\boldsymbol{\xi}\|) -T\psi(\delta^*) \\ &< \alpha_2(d) -T\psi(\delta^*) \\ &= \alpha_2(d) - \frac{\alpha_2(d)}{\psi(\delta^*)}\psi(\delta^*) = 0, \end{align*} which is contradictory to (\ref{CONT1}). Therefore proposition (\ref{UATT2}) is true. Now, let $t^*$ be as in (\ref{UATT2}) and let $t>T+t_0$ be arbitrary. Then, because $$ s\mapsto V(s,\boldsymbol{\phi}_\sigma(s,t_0,\boldsymbol{\xi})),\quad s\geq t_0, $$ is strictly monotonically decreasing by inequality (\ref{TDMOLIE2}) and Corollary \ref{TEMP51}, we get by (\ref{UATT2}), that \begin{align*} \alpha_1(\|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\|) &\leq V(t,\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})) \\ & \leq V(t^*,\boldsymbol{\phi}_\sigma(t^*,t_0,\boldsymbol{\xi})) \\ &\leq \alpha_2(\|\boldsymbol{\phi}_\sigma(t^*,t_0,\boldsymbol{\xi})\|) \\ &< \alpha_2(\delta^*) \\ &= \min\{\alpha_2(d),\alpha_1(\varepsilon)\} \\ &\leq \alpha_1(\varepsilon), \end{align*} and we have proved (\ref{UATT}). The proposition (ii) follows.\\ \end{proof} The function $V$ in the last theorem is called a Lyapunov function for the Switched System \ref{POLYSYS}. \begin{definition}[Lyapunov function] \label{DEFLYAFUNC} \rm Assume that the Switched System \ref{POLYSYS} has an equilibrium at the origin. Denote the solution to the Switched System \ref{POLYSYS} by $\boldsymbol{\phi}$ and let $\|\cdot\|$ be a norm on $\mathbb{R}^n$. Let $R>0$ be a constant such that the closure of the ball $\mathcal{B}_{\|\cdot\|,R}$ is a subset of $\mathcal{U}$. A continuous function $V:\mathbb{R}_{\geq 0}\times\mathcal{B}_{\|\cdot\|,R}\to \mathbb{R}$ is called a Lyapunov function for the Switched System \ref{POLYSYS} on $\mathcal{B}_{\|\cdot\|,R}$, if and only if there exists a Dini derivative $D^* \in \{D^+,D_+,D^-,D_-\}$ with respect to the time $t$ and functions $\alpha_1,\alpha_2,\psi\in\mathcal{K}$ with the properties that: \begin{enumerate} \item[{\bf (L1)}] $$ \alpha_1(\|\boldsymbol{\xi}\|)\leq V(t,\boldsymbol{\xi}) \leq \alpha_2(\|\boldsymbol{\xi}\|) $$ for all $t\geq 0$ and all $\boldsymbol{\xi}\in\mathcal{B}_{\|\cdot\|,R}$. \item[{\bf (L2)}] $$ D^*[V(t,\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi}))] \leq -\psi(\|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\|) $$ for every $\sigma\in\mathcal{S}_\mathcal{P}$, every $\boldsymbol{\xi}\in\mathcal{U}$, and every $t\geq t_0 \geq 0$,\\ such that $\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\in \mathcal{B}_{\|\cdot\|,R}$. \end{enumerate} \end{definition} The Direct Method of Lyapunov (Theorem \ref{TDMOL}) can thus, by Definition \ref{DEFLYAFUNC}, be rephrased as follows: \begin{quote} Assume that the Switched System \ref{POLYSYS} has an equilibrium point at the origin and that there exists a Lyapunov function defined on the ball $\mathcal{B}_{\|\cdot\|,R}$, of which the closure is a subset of $\mathcal{U}$, for the system. Then there is a $d$, $00$, and let $\varsigma \in \mathcal{K}\mathcal{L}$ be such that $\|\boldsymbol{\phi}_\sigma(t,t_0,\boldsymbol{\xi})\| \leq \varsigma(\|\boldsymbol{\xi}\|,t-t_0)$ for all $\sigma\in\mathcal{S}_\mathcal{P}$, all $\boldsymbol{\xi} \in \mathcal{B}_{\|\cdot\|,R}$, and all $t\geq t_0 \geq 0$. Assume further, that there exists a constant $L$ for the functions $\mathbf{f}_p$, such that $$ \|\mathbf{f}_p(t,\mathbf{x}) - \mathbf{f}_p(t,\mathbf{y})\| \leq L\|\mathbf{x} - \mathbf{y}\| $$ for all $t\geq 0$, all $\mathbf{x},\mathbf{y} \in \mathcal{B}_{\|\cdot\|,R}$, and all $p\in\mathcal{P}$. By Massera's lemma (Lemma \ref{MLEMMA}) there exists a function $g\in\mathcal{C}^{1}(\mathbb{R}_{\geq 0})$, such that $g,g'\in\mathcal{K}$, $g$ is infinitely differentiable on $\mathbb{R}_{>0}$, $$ \int_0^{+\infty}g(\varsigma(R,\tau))d\tau < +\infty,\quad \text{and}\quad \int_0^{+\infty}g'(\varsigma(R,\tau))e^{L\tau}d\tau < +\infty. $$ \begin{itemize} \item[(i)] For every $\sigma\in\mathcal{S}_\mathcal{P}$ we define the function $W_\sigma$ for all $t\geq 0$ and all $\boldsymbol{\xi} \in\mathcal{B}_{\|\cdot\|,R}$ by $$ W_\sigma(t,\boldsymbol{\xi}):= \int_t^{+\infty} g(\|\boldsymbol{\phi}_\sigma(\tau,t,\boldsymbol{\xi})\|)d\tau. $$ \item[(ii)] We define the function $W$ for all $t\geq 0$ and all $\boldsymbol{\xi} \in\mathcal{B}_{\|\cdot\|,R}$ by $$ W(t,\boldsymbol{\xi}) := \sup_{\sigma \in\mathcal{S}_\mathcal{P}} W_\sigma(t,\boldsymbol{\xi}). $$ Note, that if the Switched System \ref{POLYSYS} is autonomous, then $W$ does not depend on $t$, that is, it is time-invariant. \end{itemize} \end{definition} The function $W$ from the definition above (Definition \ref{WSDEF}) is a Lyapunov function for the Switched System \ref{POLYSYS} used in its construction. This is proved in the next theorem. \begin{theorem}[Converse theorem for switched systems] \label{LL} The function $W$ in Definition \ref{WSDEF} is a Lyapunov function for the Switched System \ref{POLYSYS} used in its construction. Further, there exists a constant $L_W>0$ such that \begin{equation} \label{WLL} |W(t,\boldsymbol{\xi}) - W(t,\boldsymbol{\eta})| \leq L_W\|\boldsymbol{\xi} - \boldsymbol{\eta}\| \end{equation} for all $t\geq 0$ and all $\boldsymbol{\xi},\boldsymbol{\eta} \in \mathcal{B}_{\|\cdot\|,R}$, where the norm $\|\cdot\|$ and the constant $R$ are the same as in Definition \ref{WSDEF}. \end{theorem} \begin{proof} We have to show that the function $W$ complies to the conditions {\bf(L1)} and {\bf(L2)} of Definition \ref{DEFLYAFUNC}. Because $$ \boldsymbol{\phi}_\sigma(u,t,\boldsymbol{\xi}) = \boldsymbol{\xi} +\int_t^u\mathbf{f}_{\sigma(\tau)}(\tau,\boldsymbol{\phi}_\sigma(\tau,t,\boldsymbol{\xi})) d\tau, $$ and $\|\mathbf{f}_{\sigma(s)}(s,\mathbf{y})\| \leq LR$ for all $s\geq0$ and all $\mathbf{y} \in \mathcal{B}_{\|\cdot\|,R}$, we conclude $\|\boldsymbol{\phi}_\sigma(u,t,\boldsymbol{\xi})\| \geq \|\boldsymbol{\xi}\| - (u-t)LR$ for all $u\geq t\geq0$, $\boldsymbol{\xi} \in \mathcal{B}_{\|\cdot\|,R}$, and all $\sigma\in\mathcal{S}_\mathcal{P}$. Therefore, $$ \|\boldsymbol{\phi}_\sigma(u,t,\boldsymbol{\xi})\| \geq \frac{\|\boldsymbol{\xi}\|}{2}\quad \text{whenever}\ t \leq u \leq t+\frac{\|\boldsymbol{\xi}\|}{2LR}, $$ which implies \begin{equation*} W_\sigma(t,\boldsymbol{\xi}) := \int_t^{+\infty} g(\|\boldsymbol{\phi}_\sigma(\tau,t,\boldsymbol{\xi})\|)d\tau \geq \frac{\|\boldsymbol{\xi}\|}{2LR}g(\|\boldsymbol{\xi}\|/2) \end{equation*} and then $\alpha_1(\|\boldsymbol{\xi}\|) \leq W(t,\boldsymbol{\xi})$ for all $t\geq 0$ and all $\boldsymbol{\xi} \in \mathcal{B}_{\|\cdot\|,R}$, where $\alpha_1(x) := x/(2LR)g(x/2)$ is a $\mathcal{K}$ function. By the definition of $W$, $$ W(t,\boldsymbol{\xi}) \geq \int_t^{t+h}g(\|\boldsymbol{\phi}_\sigma(\tau,t,\boldsymbol{\xi})\|)d\tau + W(t+h,\boldsymbol{\phi}_\sigma(t+h,t,\boldsymbol{\xi})) $$ \begin{align*} &\text{(reads: supremum over all trajectories emerging from $\boldsymbol{\xi}$}\\ &\text{at time $t$ is not less than over any particular trajectory}\\ &\text{emerging from $\boldsymbol{\xi}$ at time $t$)} \end{align*} for all $\boldsymbol{\xi}\in \mathcal{B}_{\|\cdot\|,R}$, all $t\geq 0$, all small enough $h>0$, and all $\sigma \in \mathcal{S}_\mathcal{P}$, from which $$ \limsup_{h\to 0+}\frac{W(t+h,\boldsymbol{\phi}_\sigma(t+h,t,\boldsymbol{\xi})) - W(t,\boldsymbol{\xi}) }{h} \leq - g(\|\boldsymbol{\xi}\|) $$ follows. Because $g\in\mathcal{K}$ this implies that the condition {\bf(L2)} from Definition \ref{DEFLYAFUNC} holds for the function $W$. Now, assume that there is an $L_W>0$ such that inequality (\ref{WLL}) holds. Then $W(t,\boldsymbol{\xi}) \leq \alpha_2(\|\boldsymbol{\xi}\|)$ for all $t\geq 0$ and all $\boldsymbol{\xi} \in \mathcal{B}_{\|\cdot\|,R}$, where $\alpha_2(x) := L_Wx$ is a class $\mathcal{K}$ function. Thus, it only remains to prove inequality (\ref{WLL}). However, as this inequality is a byproduct of the next lemma, we spare us the proof here. \end{proof} The results of the next lemma are needed in the proof of our converse theorem on uniform asymptotic stability of a switched system's equilibrium and as a convenient side effect it completes the proof of Theorem \ref{LL}. \begin{lemma} \label{WWLEMMA} The function $W$ in Definition \ref{WSDEF} satisfies for all $t\geq s \geq 0$, all $\boldsymbol{\xi},\boldsymbol{\eta}\in \mathcal{B}_{\|\cdot\|,R}$, and all $\sigma\in\mathcal{S}_\mathcal{P}$ the inequality \begin{equation} \label{WUNGL} W(t,\boldsymbol{\xi}) - W(s,\boldsymbol{\eta}) \leq C\|\boldsymbol{\xi} - \boldsymbol{\phi}_\sigma(t,s,\boldsymbol{\eta})\| - \int_s^tg(\|\boldsymbol{\phi}_\sigma(\tau,s,\boldsymbol{\eta})\|)d\tau, \end{equation} where $$ C:= \int_0^{+\infty} g'(\varsigma(R,\tau))e^{L\tau}d\tau < +\infty. $$ Especially, \begin{equation} \label{WUNGL2} |W(t,\boldsymbol{\xi}) - W(t,\boldsymbol{\eta})| \leq C\|\boldsymbol{\xi} - \boldsymbol{\eta}\| \end{equation} for all $t\geq 0$ and all $\boldsymbol{\xi},\boldsymbol{\eta}\in \mathcal{B}_{\|\cdot\|,R}$. The norm $\|\cdot\|$, the constants $R,L$, and the functions $\varsigma$ and $g$ are, of course, the same as in Definition \ref{WSDEF}. \end{lemma} \begin{proof} By the Mean-value theorem and Theorem \ref{APPLEMMASW} we have \begin{align} \label{WWLEMMAIE1} &W_\sigma(t,\boldsymbol{\xi}) - W_\sigma(s,\boldsymbol{\eta}) \\ &= \int_t^{+\infty} g(\|\boldsymbol{\phi}_\sigma(\tau,t,\boldsymbol{\xi})\|)d\tau - \int_s^{+\infty} g(\|\boldsymbol{\phi}_\sigma(\tau,s,\boldsymbol{\eta})\|)d\tau \nonumber\\ & \leq \int_t^{+\infty} \big{|}g(\|\boldsymbol{\phi}_\sigma(\tau,t,\boldsymbol{\xi})\|) - g(\|\boldsymbol{\phi}_\sigma(\tau,s,\boldsymbol{\eta})\|)\big{|} d\tau - \int_s^tg(\|\boldsymbol{\phi}_\sigma(\tau,s,\boldsymbol{\eta})\|)d\tau \nonumber \\ & = \int_t^{+\infty} \big{|}g(\|\boldsymbol{\phi}_\sigma(\tau,t,\boldsymbol{\xi})\|) - g(\|\boldsymbol{\phi}_\sigma(\tau,t,\boldsymbol{\phi}_\sigma(t,s,\boldsymbol{\eta}))\|)\big{|} d\tau - \int_s^tg(\|\boldsymbol{\phi}_\sigma(\tau,s,\boldsymbol{\eta})\|)d\tau \nonumber \\ & \leq \int_t^{+\infty} g'(\varsigma(R,\tau-t))\|\boldsymbol{\phi}_\sigma(\tau,t,\boldsymbol{\xi}) - \boldsymbol{\phi}_\sigma(\tau,t,\boldsymbol{\phi}_\sigma(t,s,\boldsymbol{\eta}))\| d\tau - \int_s^tg(\|\boldsymbol{\phi}_\sigma(\tau,s,\boldsymbol{\eta})\|)d\tau \nonumber \\ &\leq \int_t^{+\infty} g'(\varsigma(R,\tau-t))e^{L(\tau-t)}\|\boldsymbol{\xi} - \boldsymbol{\phi}_\sigma(t,s,\boldsymbol{\eta})\| d\tau - \int_s^tg(\|\boldsymbol{\phi}_\sigma(\tau,s,\boldsymbol{\eta})\|)d\tau \nonumber \\ & = C\|\boldsymbol{\xi} - \boldsymbol{\phi}_\sigma(t,s,\boldsymbol{\eta})\| - \int_s^tg(\|\boldsymbol{\phi}_\sigma(\tau,s,\boldsymbol{\eta})\|)d\tau. \nonumber \end{align} We now show that we can replace $W_\sigma(t,\boldsymbol{\xi}) - W_\sigma(s,\boldsymbol{\eta})$ by $W(t,\boldsymbol{\xi}) - W(s,\boldsymbol{\eta})$ on the leftmost side of inequality (\ref{WWLEMMAIE1}) without violating the $\leq$ relations. That this is possible might seem a little surprising at first sight. However, a closer look reveals that this is not surprising at all because the rightmost side of inequality (\ref{WWLEMMAIE1}) only depends on the values of $\sigma(z)$ for $s\leq z\leq t$ and because $W_\sigma(t,\boldsymbol{\xi}) - W(s,\boldsymbol{\eta}) \leq W_\sigma(t,\boldsymbol{\xi}) - W_\sigma(s,\boldsymbol{\eta})$, where the left-hand side only depends on the values of $\sigma(z)$ for $z\geq t$, . To rigidly prove the validity of this replacement let $\delta >0 $ be an arbitrary constant and choose a $\gamma \in \mathcal{S}_\mathcal{P}$, such that \begin{equation} \label{SSS1} W(t,\boldsymbol{\xi}) - W_\gamma(t,\boldsymbol{\xi}) < \frac{\delta}{2}, \end{equation} and a $u>0$ so small that \begin{equation} \label{SSS2} ug(\varsigma(\|\boldsymbol{\xi}\|,0)) + 2CR(e^u-1) < \frac{\delta}{2}. \end{equation} We define $\theta\in\mathcal{S}_\mathcal{P}$ by $$ \theta(\tau) := \begin{cases} \sigma(\tau),& \text{if $0 \leq \tau 0$ was arbitrary we have proved inequality (\ref{WUNGL}). Inequality (\ref{WUNGL2}) is a trivial consequence of inequality (\ref{WUNGL}), just set $s=t$ and note that $\boldsymbol{\xi}$ and $\boldsymbol{\eta}$ can be reversed. \end{proof} Finally, we come to the central theorem of this section. It is the promised converse Lyapunov theorem for a uniformly asymptotically stable equilibrium of the Switched System \ref{POLYSYS}. \begin{theorem}[Smooth converse theorem for switched systems] \label{CONVLYA} Assume that the origin is a uniformly asymptotically stable equilibrium point of the Switched System \ref{POLYSYS} on the ball $\mathcal{B}_{\|\cdot\|,R}\subset\mathcal{U}$, $R>0$, where $\|\cdot\|$ is a norm on $\mathbb{R}^n$. Assume further, that the functions $\mathbf{f}_p$, $p\in\mathcal{P}$, satisfy the common Lipschitz condition: there exists a constant $L>0$ such that \begin{equation} \label{CTA2} \|\mathbf{f}_p(s,\mathbf{x}) - \mathbf{f}_p(t,\mathbf{y})\| \leq L(|s-t| + \|\mathbf{x} - \mathbf{y}\|) \end{equation} for all $s,t\geq 0$, all $\mathbf{x},\mathbf{y} \in \mathcal{B}_{\|\cdot\|,R}$, and all $p\in\mathcal{P}$. Then, for every $00$ be constants such that $$ \|\mathbf{x}\|_2 \leq m\|\mathbf{x}\|\quad \text{and}\quad \|\mathbf{x}\| \leq M\|\mathbf{x}\|_2 $$ for all $\mathbf{x}\in \mathbb{R}^n$ and let $a$ be a constant such that $$ a > 2m \quad \text{and set}\quad y^* := \frac{mR}{a}. $$ Define $$ K := \frac{g(y^*)}{a} L\Big(C\big[m(1+M)R + mR\big(\frac{4}{3}LR+M\big) \big] + g(4R/3) mR\Big), $$ and set \begin{equation} \label{EPSMIN} \epsilon := \min\left\{\frac{a}{3g(y^*)},\frac{a(R-R^*)}{R^* g(y^*)},\frac{a}{2mRL g(y^*)},\frac{1}{K}\right\}. \end{equation} Note that $\epsilon$ is a real-valued constant that is strictly larger than zero. We define the function $\varepsilon:\mathbb{R}_{\geq0} \to \mathbb{R}_{\geq 0}$ by \begin{equation} \label{DEFVAREPS} \varepsilon(x) := \epsilon \int_0^{\frac{x}{a}} g(z)dz. \end{equation} The definition of $\varepsilon$ implies \begin{equation} \label{CT1} \varepsilon(x) \leq \epsilon g(x/a)\frac{x}{a} \leq \frac{a}{3g(y^*)}\cdot g(x/a)\frac{x}{a} \leq \frac{x}{3} \end{equation} for all $0\leq x\leq mR$ and \begin{equation} \label{CT2} \varepsilon'(x) = \frac{\epsilon}{a}g(x/a) \end{equation} for all $x\geq 0$. Define the function $\vartheta$ by $\vartheta(x) := g(2x/3) - g(x/2)$ for all $x\geq 0$. Then $\vartheta(0)=0$ and for every $x>0$ we have $$ \vartheta'(x) = \frac{2}{3}g'(2x/3) - \frac{1}{2} g'(x/2) > 0 $$ because $g'\in\mathcal{K}$, that is $\vartheta\in \mathcal{K}$. \smallskip \noindent\textbf{Part II:} Let $\rho\in\mathcal{C}^\infty(\mathbb{R})$ be a nonnegative function with $\operatorname{supp}(\rho) \subset\,]-1,0[$ and $\int_\mathbb{R}\rho(x) =1$ and let $\varrho\in\mathcal{C}^\infty(\mathbb{R}^n)$ be a nonnegative function with $\operatorname{supp}(\varrho) \subset \mathcal{B}_{\|\cdot\|_2,1}$ and $\int_{\mathbb{R}^n}\varrho(\mathbf{x})d^nx = 1$. Extend $W$ on $\mathbb{R}\times\mathbb{R}^n$ by setting it equal to zero outside of $\mathbb{R}_{\geq 0} \times \mathcal{B}_{\|\cdot\|,R}$. We claim that the function $V:\mathbb{R}_{\geq 0} \times \mathcal{B}_{\|\cdot\|,R^*} \to \mathbb{R}_{\geq 0}$, $V(t,\boldsymbol{0}):=0$ for all $t\geq 0$, and \begin{align*} V(t,\boldsymbol{\xi}) &:= \int_\mathbb{R} \int_{\mathbb{R}^n} \rho \Big(\frac{t-\tau}{\varepsilon(\|\boldsymbol{\xi}\|_2)}\Big) \varrho\Big(\frac{\boldsymbol{\xi}-\mathbf{y}}{\varepsilon(\|\boldsymbol{\xi}\|_2)}\Big) \frac{W[\tau,\mathbf{y}]}{\varepsilon^{n+1}(\|\boldsymbol{\xi}\|_2)}d^ny d\tau \\ &= \int_\mathbb{R} \int_{\mathbb{R}^n}\rho(\tau) \varrho(\mathbf{y})W[t - \varepsilon(\|\boldsymbol{\xi}\|_2)\tau ,\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y} ]d^ny d\tau \end{align*} for all $t\geq0$ and all $\boldsymbol{\xi}\in\mathcal{B}_{\|\cdot\|,R^*}\setminus \{\boldsymbol{0}\}$, is a $\mathcal{C}^{\infty}(\mathbb{R}_{\geq 0} \times \left[\mathcal{B}_{\|\cdot\|,R^*}\setminus \{\boldsymbol{0}\}\right])$ Lyapunov function for the switched system. Note, that if the Switched System \ref{POLYSYS} in question is autonomous, then $W$ is time-invariant, which implies that $V$ is time-invariant too. Because, for every $\|\mathbf{y}\|_2 \leq 1$ and every $\|\boldsymbol{\xi}\| < R^*$, we have by (\ref{CT1}) and (\ref{EPSMIN}), that \begin{align*} \|\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y}\| &\leq \Big(1+\frac{\varepsilon(\|\boldsymbol{\xi}\|_2)}{\|\boldsymbol{\xi}\|_2}\Big)\|\boldsymbol{\xi}\| \\ & \leq \Big(1+\frac{\epsilon g(\|\boldsymbol{\xi}\|_2/a)}{\|\boldsymbol{\xi}\|_2} \cdot\frac{\|\boldsymbol{\xi}\|_2}{a}\Big)\|\boldsymbol{\xi}\| \\ & < \Big(1 +\frac{a(R-R^*)g(y^*)}{R^* g(y^*)a} \Big)R^*\\ &= R, \end{align*} so $V$ is properly defined on $\mathbb{R}_{\geq 0}\times \mathcal{B}_{\|\cdot\|,R^*}$. But then, by construction, $V\in\mathcal{C}^{\infty}(\mathbb{R}_{\geq 0} \times \left[\mathcal{B}_{\|\cdot\|,R^*}\setminus \{\boldsymbol{0}\}\right])$. It remains to be shown that $V$ fulfills the conditions {\bf (L1)} and {\bf (L2)} in Definition \ref{DEFLYAFUNC} of a Lyapunov function. By Theorem \ref{LL} and Lemma \ref{WWLEMMA} there is a function $\alpha_1\in\mathcal{K}$ and a constant $L_W>0$, such that $$ \alpha_1(\|\boldsymbol{\xi}\|) \leq W(t,\boldsymbol{\xi}) \leq L_W \|\boldsymbol{\xi}\| $$ for all $t\geq0$ and all $\boldsymbol{\xi} \in \mathcal{B}_{\|\cdot\|,R}$. By inequality (\ref{CT1}) we have for all $\boldsymbol{\xi} \in \mathcal{B}_{\|\cdot\|,R}$ and all $\|\mathbf{y}\|_2 \leq 1$, that \begin{gather} \label{NORMABSX1} \|\boldsymbol{\xi} - \varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y}\| \geq \|\boldsymbol{\xi} - \frac{\|\boldsymbol{\xi}\|_2}{3} \frac{\boldsymbol{\xi}}{\|\boldsymbol{\xi}\|_2}\| = \frac{2}{3}\|\boldsymbol{\xi}\|,\\ \label{NORMABSX2} \|\boldsymbol{\xi} - \varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y}\| \leq \|\boldsymbol{\xi} + \frac{\|\boldsymbol{\xi}\|_2}{3} \frac{\boldsymbol{\xi}}{\|\boldsymbol{\xi}\|_2}\| = \frac{4}{3}\|\boldsymbol{\xi}\|. \end{gather} Hence \begin{equation} \label{ULYA} \begin{aligned} \alpha_1(2\|\boldsymbol{\xi}\|/3) &= \int_\mathbb{R} \int_{\mathbb{R}^n}\rho(\tau) \varrho(\mathbf{y})\alpha_1(2\|\boldsymbol{\xi}\|/3)d^ny d\tau\\ &\leq \int_\mathbb{R} \int_{\mathbb{R}^n}\rho(\tau) \varrho(\mathbf{y})\alpha_1(\|\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2) \mathbf{y}\|)d^ny d\tau \\ &\leq \int_\mathbb{R} \int_{\mathbb{R}^n}\rho(\tau) \varrho(\mathbf{y})W[t - \varepsilon(\|\boldsymbol{\xi}\|_2)\tau ,\boldsymbol{\xi} -\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y} ]d^ny d\tau \\ &= V(t,\boldsymbol{\xi}) \\ &\leq \int_\mathbb{R} \int_{\mathbb{R}^n}\rho(\tau) \varrho(\mathbf{y})L_W\|\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2) \mathbf{y}\|d^ny d\tau \\ &\leq \frac{4L_W}{3}\|\boldsymbol{\xi}\|, \end{aligned} \end{equation} and the function $V$ fulfills the condition {\bf (L1)}. We now prove that $V$ fulfills the condition {\bf (L2)}. To do this let $t\geq 0$, $\boldsymbol{\xi}\in\mathcal{B}_{\|\cdot\|,R^*}$, and $\sigma\in\mathcal{S}_\mathcal{P}$ be arbitrary, but fixed throughout the rest of the proof. Denote by $\mathcal{I}$ the maximum interval in $\mathbb{R}_{\geq 0}$ on which $s \mapsto \boldsymbol{\phi}_\sigma(s,t,\boldsymbol{\xi})$ is defined and set $$ q(s,\tau) := s-\varepsilon(\|\boldsymbol{\phi}_\sigma(s,t,\boldsymbol{\xi})\|_2)\tau $$ for all $s\in\mathcal{I}$ and all $-1\leq \tau \leq 0$ and define \begin{align*} D(h,\mathbf{y},\tau) &:=W[q(t+h,\tau),\boldsymbol{\phi}_\sigma(t+h,t,\boldsymbol{\xi})-\varepsilon(\|\boldsymbol{\phi}_\sigma(t+h,t,\boldsymbol{\xi})\|_2)\mathbf{y}]\\ &\quad \quad \quad \quad \ - W[q(t,\tau),\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y}] \end{align*} for all $h$ such that $t+h\in\mathcal{I}$, all $\|\mathbf{y}\|_2 \leq 1$, and all $-1\leq\tau\leq 0$. Then $$ V(t+h,\boldsymbol{\phi}_\sigma(t+h,t,\boldsymbol{\xi})) - V(t,\boldsymbol{\xi}) = \int_\mathbb{R}\int_{\mathbb{R}^n} \rho(\tau) \varrho(\mathbf{y})D(h,\mathbf{y},\tau)d^ny d\tau $$ for all $h$ such that $t+h \in\mathcal{I}$, especially this equality holds for all $h$ in an interval of the form $[0,h'[$, where $0t$ that is smaller than any switching-time (discontinuity-point) of $\sigma$ larger than $t$, and because of (\ref{EPSMIN}) and (\ref{CTA2}), we have \begin{align*} \frac{dq}{ds}(s,\tau) &= 1 - \frac{\epsilon g(\|\boldsymbol{\phi}_\sigma(s,t,\boldsymbol{\xi})\|_2/a)}{a} \frac{\boldsymbol{\phi}_\sigma(s,t,\boldsymbol{\xi})}{\|\boldsymbol{\phi}_\sigma(s,t,\boldsymbol{\xi})\|_2}\cdot\mathbf{f}_{\sigma(s)}(s,\boldsymbol{\phi}_\sigma(s,t,\boldsymbol{\xi}))\tau\\ &\geq 1 -\epsilon \, \frac{g(y^*)LmR}{a}\\ &\geq \frac{1}{2}, \end{align*} so $q(t+h,\tau) \geq q(t,\tau) \geq 0$ for all small enough $h\geq 0$. Now, denote by $\gamma$ the constant switching signal $\sigma(t)$ in $\mathcal{S}_\mathcal{P}$, that is $\gamma(s) := \sigma(t)$ for all $s\geq 0$, and consider that by Lemma \ref{WWLEMMA} \begin{align*} \frac{D(h,\mathbf{y},\tau)}{h} &\leq \frac{C}{h} \Big{\|}\boldsymbol{\phi}_\sigma(t+h,t,\boldsymbol{\xi})-\varepsilon(\|\boldsymbol{\phi}_\sigma(t+h,t,\boldsymbol{\xi})\|_2)\mathbf{y} \\ &\quad - \boldsymbol{\phi}_\gamma(q(t+h,\tau),q(t,\tau),\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y})\Big{\|} \\ &\quad -\frac{1}{h}\int_{q(t,\tau)}^{q(t+h,\tau)} g(\|\boldsymbol{\phi}_\gamma(s,q(t,\tau),\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y})\|)ds \\ &= C\Big{\|}\frac{\boldsymbol{\phi}_\sigma(t+h,t,\boldsymbol{\xi})-\boldsymbol{\xi}}{h} -\frac{\varepsilon(\|\boldsymbol{\phi}_\sigma(t+h,t,\boldsymbol{\xi})\|_2) - \varepsilon(\|\boldsymbol{\xi}\|_2)}{h}\mathbf{y} \\ &\quad - \frac{\boldsymbol{\phi}_\gamma(q(t+h,\tau),q(t,\tau),\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y}) - [\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y}]}{h} \Big{\|} \\ &\quad -\frac{1}{h}\int_{q(t,\tau)}^{q(t+h,\tau)} g(\|\boldsymbol{\phi}_\gamma(s,q(t,\tau),\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y})\|)ds. \end{align*} For the next calculations we need $s \mapsto q(s,\tau)$ to be differentiable at $t$. If it is not, which might be the case if $t$ is a switching time of $\sigma$, we replace $\sigma$ with $\sigma^*\in\mathcal{S}_\mathcal{P}$ where $$ \sigma^*(s) := \begin{cases} \sigma(t), &\text{if $0\leq s\leq t$},\\ \sigma(s), &\text{if $s\geq t$}. \end{cases} $$ Note that this does not affect the numerical value $$ \limsup_{h\to 0+}\frac{D(h,\mathbf{y},\tau)}{h} $$ because $\sigma^*(t+h) = \sigma(t+h)$ for all $h\geq 0$. Hence, with $p:= \sigma(t)$, and by (\ref{CTA2}), the chain rule, (\ref{NORMABSX1}), and (\ref{NORMABSX2}), \begin{align*} &\limsup_{h\to 0+}\frac{D(h,\mathbf{y},\tau)}{h}\\ &\leq C\Big{\|}\mathbf{f}_p(t,\boldsymbol{\xi}) - \mathbf{f}_p(q(t,\tau),\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y})\cdot\frac{dq}{dt'}(t',\tau)\Big|_{t'=t} \\ &\quad -\varepsilon'(\|\boldsymbol{\xi}\|_2)\cdot\frac{d}{dt'}\|\boldsymbol{\phi}_{\sigma}(t',t,\boldsymbol{\xi})\|_2 \Big|_{t'=t}\mathbf{y}\Big{\|} \\ &\quad - g(\|\boldsymbol{\phi}_\gamma(q(t,\tau),q(t,\tau),\boldsymbol{\xi} -\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y})\|)\cdot\frac{dq}{dt'}(t',\tau)\Big|_{t'=t}\\ & = C\Big{\|}\mathbf{f}_p(t,\boldsymbol{\xi}) - \mathbf{f}_p(q(t,\tau),\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y}) \Big[1-\varepsilon'(\|\boldsymbol{\xi}\|_2)\frac{\boldsymbol{\xi}}{\|\boldsymbol{\xi}\|_2}\cdot \mathbf{f}_p(t,\boldsymbol{\xi})\tau\Big]\\ &\quad -\varepsilon'(\|\boldsymbol{\xi}\|_2)[\frac{\boldsymbol{\xi}}{\|\boldsymbol{\xi}\|_2}\cdot \mathbf{f}_p(t,\boldsymbol{\xi})]\mathbf{y}\Big{\|}\\ &\quad - g(\|\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y}\|)\left[1-\varepsilon'(\|\boldsymbol{\xi}\|_2)\frac{\boldsymbol{\xi}}{\|\boldsymbol{\xi}\|_2}\cdot \mathbf{f}_p(t,\boldsymbol{\xi})\right]\\ & \leq C \big{\|}\mathbf{f}_p(t,\boldsymbol{\xi}) - \mathbf{f}_p(q(t,\tau),\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y})\big{\|} \\ & \quad + C\varepsilon'(\|\boldsymbol{\xi}\|_2)\|\mathbf{f}_p(t,\boldsymbol{\xi})\|_2 \big[\|\mathbf{f}_p(q(t,\tau),\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y})\| + \|\mathbf{y}\|\big]\\ & \quad - g(2\|\boldsymbol{\xi}\|/3 ) + g(4\|\boldsymbol{\xi}\|/3 ) \varepsilon'(\|\boldsymbol{\xi}\|_2)\|\mathbf{f}_p(t,\boldsymbol{\xi})\|_2\\ &\leq C L \big[ |t - q(t,\tau)| + \varepsilon(\|\boldsymbol{\xi}\|_2)\|\mathbf{y}\| ) \big{[]} \\ & \quad +C\varepsilon'(\|\boldsymbol{\xi}\|_2)mLR \big[L\|\boldsymbol{\xi}-\varepsilon(\|\boldsymbol{\xi}\|_2)\mathbf{y})\| + M\|\mathbf{y}\|_2 \big]\\ & \quad - g(2\|\boldsymbol{\xi}\|/3 ) + g(4\|\boldsymbol{\xi}\|/3 ) \varepsilon'(\|\boldsymbol{\xi}\|_2)mLR\\ & \leq C\big[ L (1+M) \varepsilon(\|\boldsymbol{\xi}\|_2)+ \varepsilon'(\|\boldsymbol{\xi}\|_2)mLR \big\{L\frac{4}{3}\|\boldsymbol{\xi}\| + M \big\}\big] \\ & \quad - g(2\|\boldsymbol{\xi}\|/3 ) + g(4\|\boldsymbol{\xi}\|/3 ) \varepsilon'(\|\boldsymbol{\xi}\|_2)mLR. \end{align*} Therefore, by (\ref{CT1}), (\ref{CT2}), and (\ref{EPSMIN}), and with $x:=\|\boldsymbol{\xi}\|$, we can further simplify, \begin{align*} &\limsup_{h\to 0+}\frac{D(h,\mathbf{y},\tau)}{h} \\ &\leq -g(2x/3) +\frac{\epsilon}{a} g(mx/a) L\Big(C\big[m(1+M)x + mR\big(\frac{4}{3}Lx+M\big) \big] + g(4x/3) mR\Big)\\ & \leq - g(2x/3) + K \epsilon g(x/2) \\ & \leq -\vartheta(x), \end{align*} and because $t\geq 0$, $\boldsymbol{\xi}\in\mathcal{B}_{\|\cdot\|,R^*}$, and $\sigma\in\mathcal{S}_\mathcal{P}$ were arbitrary, we have proved that $V$ is a Lyapunov function for the system. \end{proof} Now, we have proved the main theorem of this section, our much wanted converse theorem for the arbitrary Switched System \ref{POLYSYS}. \section{Construction of Lyapunov Functions} \label{SECCLF} In this section we present a procedure to construct Lyapunov functions for the Switched System \ref{POLYSYS}. After a few preliminaries on piecewise affine functions we give an algorithmic description of how to derive a linear programming problem from the Switched System \ref{POLYSYS} (Definition \ref{LP}), and we prove that if the linear programming problem possesses a feasible solution, then it can be used to parameterize a Lyapunov function for the system. Then, in Section \ref{SECALG} and after some preparation in Section \ref{SECCCT}, we present an algorithm that systematically generates linear programming problems for the Switched System \ref{POLYSYS} and we prove, that if the switched system possesses a Lyapunov function at all, then the algorithm generates, in a finite number of steps, a linear programming problem that has a feasible solution. Because there are algorithms that always find a feasible solution to a linear programming problem if one exists, this implies that we have derived an algorithm for constructing Lyapunov functions, whenever one exists. Further, we consider the case when the Switched System \ref{POLYSYS} is autonomous separately, because in this case it is possible to parameterize a time-independent Lyapunov function for the system. Let us be a little more specific on these points before we start to derive the results: To construct a Lyapunov function with a linear programming problem, one needs a class of continuous functions that are easily parameterized. That is, we need a class of functions that is general enough to be used as a search-space for Lyapunov functions, but it has to be a finite-dimensional vector space so that its functions are uniquely characterized by a finite number of real numbers. The class of the continuous piecewise affine functions $\operatorname{CPWA}$ is a well suited candidate. The algorithm for parameterizing a Lyapunov function for the Switched System \ref{POLYSYS} consists roughly of the following steps: \begin{itemize} \item[(i)] Partition a neighborhood of the equilibrium under consideration in a family $\mathfrak{S}$ of simplices. \item[(ii)] Limit the search for a Lyapunov function $V$ for the system to the class of continuous functions that are affine on any $S \in \mathfrak{S}$. \item[(iii)] State linear inequalities for the values of $V$ at the vertices of the simplices in $\mathfrak{S}$, so that if they can be fulfilled, then the function $V$, which is uniquely determined by its values at the vertices, is a Lyapunov function for the system in the whole area. \end{itemize} We first partition $\mathbb{R}^n$ into $n$-simplices and use this partition to define the function spaces $\operatorname{CPWA}$ of continuous piecewise affine functions $\mathbb{R}^n\to\mathbb{R}$. A function in $\operatorname{CPWA}$ is uniquely determined by its values at the vertices of the simplices in $\mathfrak{S}$. Then we present a linear programming problem, algorithmically derived from the Switched System \ref{POLYSYS}, and prove that a $\operatorname{CPWA}$ Lyapunov function for the system can be parameterized from any feasible solution to this linear programming problem. Finally, in Section \ref{SECCCT}, we prove that if the equilibrium of the Switched System \ref{POLYSYS} is uniformly asymptotically stable, then any simplicial partition with small enough simplices leads to a linear programming problem that does have a feasible solution. Because, by Theorem \ref{TDMOL} and Theorem \ref{CONVLYA}, a Lyapunov function exists for the Switched System \ref{POLYSYS} exactly when the equilibrium is uniformly asymptotically stable, and because it is always possible to algorithmically find a feasible solution if at least one exists, this proves that the algorithm we present in Section \ref{SECALG} can parameterize a Lyapunov function for the Switched System \ref{POLYSYS} if the system does possess a Lyapunov functions at all. \subsection{Continuous piecewise affine functions} \label{SUBSECCPWAL} To construct a Lyapunov function by linear programming, one needs a class of continuous functions that are easily parameterized. Our approach is a simplicial partition of $\mathbb{R}^n$, on which we define the finite dimensional $\mathbb{R}$-vector space $\operatorname{CPWA}$ of continuous functions, that are affine on every of the simplices. We first discuss an appropriate simplicial partition of $\mathbb{R}^n$ and then define the function space $\operatorname{CPWA}$. The same is done in considerable more detail in Chapter 4 in \cite{Marinosson:02a}. The simplices $S_\sigma$, where $\sigma\in\operatorname{Perm}[\{1,2,\dots,n\}]$, will serve as the atoms of our partition of $\mathbb{R}^n$. They are defined in the following way: \begin{definition}[The simplices $S_\sigma$] \rm For every $\sigma \in \operatorname{Perm}[\{1,2,\dots,n\}]$ we define the $n$-simplex \begin{equation*} S_\sigma := \{ \mathbf{y} \in \mathbb{R}^n : \ 0 \leq y_{\sigma(1)} \leq y_{\sigma(2)}\leq \dots \leq y_{\sigma(n)} \leq 1 \}, \end{equation*} where $y_{\sigma(i)}$ is the $\sigma(i)$-th component of the vector $\mathbf{y}$. An equivalent definition of the $n$-simplex $S_\sigma$ is \begin{align*} S_\sigma &= \operatorname{con}\Big\{\sum_{j=1}^n \mathbf{e}_{\sigma(j)}, \sum_{j=2}^n \mathbf{e}_{\sigma(j)},\dots,\sum_{j=n+1}^n \mathbf{e}_{\sigma(j)}\Big\} \\ &=\Big\{ \sum_{i=1}^{n+1}\lambda_i \sum_{j=i}^{n+1}\mathbf{e}_{\sigma(j)}: 0\leq \lambda_i\leq 1\quad \text{for $i=1,2,\dots,n+1$ and } \sum_{i=1}^{n+1}\lambda_i=1 \Big\} , \end{align*} where $\mathbf{e}_{\sigma(i)}$ is the $\sigma(i)$-th unit vector in $\mathbb{R}^n$. \end{definition} For every $\sigma \in \operatorname{Perm}[\{1,2,\dots,n\}]$ the set $S_\sigma$ is an $n$-simplex with the volume $1/n!$ and, more importantly, if $\alpha,\beta\in \operatorname{Perm}[\{1,2,\dots,n\}]$, then \begin{equation} \label{SIMSCHNITT} S_\alpha \cap S_\beta = \operatorname{con}\left\{ \mathbf{x} \in\mathbb{R}^n : \text{$\mathbf{x}$ is a vertex of $S_\alpha$ and $\mathbf{x}$ is a vertex of $S_\beta$}\right\}. \end{equation} Thus, we can define a continuous function $p:[0,1]^n\to \mathbb{R}$ that is affine on every $S_\sigma$, $\sigma \in \operatorname{Perm}[\{1,2,\dots,n\}]$, by just specifying it values at the vertices of the hypercube $[0,1]^n$. That is, if $\mathbf{x} \in S_\sigma$, then $$ \mathbf{x} = \sum_{i=1}^{n+1}\lambda_i \sum_{j=i}^{n+1}\mathbf{e}_{\sigma(j)} $$ where $0\leq \lambda_i\leq 1$ for $i=1,2,\dots,n+1$ and $\sum_{i=1}^{n+1}\lambda_i=1$, Then we set $$ p(\mathbf{x}) = p\Big(\sum_{i=1}^{n+1}\lambda_i \sum_{j=i}^{n+1}\mathbf{e}_{\sigma(j)}\Big) = \sum_{i=1}^{n+1}\lambda_i\, p\Big(\sum_{j=i}^{n+1}\mathbf{e}_{\sigma(j)}\Big). $$ The function $p$ is now well defined and continuous because of (\ref{SIMSCHNITT}). We could now proceed by partitioning $\mathbb{R}^n$ into the simplices $(\mathbf{z} + S_\sigma)_{\mathbf{z}\in\mathbb{Z}^n,\sigma\in\operatorname{Perm}[\{1,2,\dots,n\}]}$, but we prefer a simplicial partition of $\mathbb{R}^n$ that is invariable with respect to reflections through the hyperplanes $\mathbf{e}_i \cdot \mathbf{x} = 0$, $i=1,2,\dots,n$, as a domain for the function space $\operatorname{CPWA}$. We construct such a partition by first partitioning $\mathbb{R}^n_{\geq 0}$ into the family $(\mathbf{z}+S_\sigma)_{\mathbf{z}\in\mathbb{Z}^n_{\geq 0},\ \sigma\in\operatorname{Perm}[\{1,2,\dots,n\}]}$ and then we extend this partition on $\mathbb{R}^n$ by use of the reflection functions $\mathbf{R}^\mathcal{J}$, where $\mathcal{J} \in \mathfrak{P}( \{1,2,\dots,n\})$. \begin{definition}[Reflection functions $\mathbf{R}^\mathcal{J}$] \label{Refdef} \rm For every $\mathcal{J} \in \mathfrak{P}( \{1,2,\dots,n\})$, we define the reflection function $\mathbf{R}^\mathcal{J}:\mathbb{R}^n \to \mathbb{R}^n$, \begin{equation*} \mathbf{R}^\mathcal{J} (\mathbf{x}) := \sum_{i=1}^n (-1)^{\chi_{_{\mathcal{J}}}(i)}x_i \mathbf{e}_i \end{equation*} for all $\mathbf{x} \in \mathbb{R}^n$, where $\chi_{_{\mathcal{J}}}:\{1,2,\dots,n\}\to \{0,1\}$ is the characteristic function of the set $\mathcal{J}$. \end{definition} Clearly $\mathbf{R}^\mathcal{J}$, where $\mathcal{J}:=\{j_1,j_2,\dots,j_k\}$, represents reflections through the hyperplanes $\mathbf{e}_{j_1} \cdot \mathbf{x} = 0$, $\mathbf{e}_{j_2} \cdot \mathbf{x} = 0, \dots,\mathbf{e}_{j_k} \cdot \mathbf{x} = 0$ in succession. The simplicial partition of $\mathbb{R}^n$ that we use for the definition of the function spaces $\operatorname{CPWA}$ of continuous piecewise affine functions is $$ (\mathbf{R}^\mathcal{J}(\mathbf{z}+S_\sigma))_{\mathbf{z}\in\mathbb{Z}_{\geq 0}^n,\ \mathcal{J} \in \mathfrak{P} (\{1,2,\dots,n\}),\ \sigma\in\operatorname{Perm}[\{1,2,\dots,n\}]}. $$ Similar to (\ref{SIMSCHNITT}), this partition has the advantageous property, that from $$ S,S^* \in \left\{\mathbf{R}^\mathcal{J}(\mathbf{z}+S_\sigma) : \ \mathbf{z}\in\mathbb{Z}_{\geq 0}^n,\ \mathcal{J} \in \mathfrak{P} (\{1,2,\dot