A Glimpse at Pointwise Asymptotic Stability for Continuous-Time and Discrete-Time Dynamics

Abstract

Given a dynamical system, pointwise asymptotic stability, also called semistability, of a set requires that every point in the set be a Lyapunov stable equilibrium, and that every solution converge to one of the equilibria in the set. This note provides examples of pointwise asymptotic stability related to optimization and states select results from the literature, focusing on necessary and sufficient Lyapunov and Lyapunov-like conditions for and robustness of this stability property. Background on the classical asymptotic stability is included.

10.1 Introduction

Asymptotic stability is an important concept in dynamical systems and control theory. It is often the goal of control engineering design. Given a dynamical system, asymptotic stability of a set requires that the set be Lyapunov stable, i.e., solutions originating near that set remain near that set, and that the distance of every solution to the set decrease asymptotically to 0. Pointwise asymptotic stability is a related property, which requires that every point in the set be a Lyapunov stable equilibrium, and that every solution converge to one of the equilibria in the set. The property appears naturally in algorithms in convex optimization, when the algorithms are viewed as discrete-time dynamical systems; in continuous-time dynamics generated by monotone operators, including the steepest descent for a convex function and the so-called saddle dynamics; in control algorithms for multi-agent systems when consensus is an objective; and in biological, chemical, physiological, and engineered systems not related to optimization.

This note reviews the notion of asymptotic stability; defines and provides examples of pointwise asymptotic stability; and collects some results characterizing these stability properties, with focus on necessary and sufficient Lyapunov and Lyapunov-like conditions, which feature set-valued Lyapunov mappings for the pointwise property, and on robustness of the properties. Continuous-time and discrete-time dynamics are considered and are modeled, respectively, by differential inclusions and difference inclusions.

10.2 Dynamics

Continuous-time dynamics in this note are modeled by differential inclusions

$$\displaystyle \begin{aligned} \dot{x}\in F(x), \end{aligned} $$

(10.1)

where $F:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ is a set-valued mapping.¹ For a general theory of differential inclusions, see [7] or [60]. A solution to (10.1) is a function $\phi :I\to {\mathbb R}^n$, where I is an interval containing and beginning at 0, such that ϕ is absolutely continuous on every compact subinterval of I and $\dot {\phi }(t)=\frac {d\phi }{dt}(t)\in F(\phi (t))$ for almost all t ∈ I. A solution is maximal if it cannot be extended, and complete if its domain is unbounded.

The differential inclusion (10.1), or the mapping F, is said to satisfy basic assumptions if

• F is locally bounded² and outer semicontinuous (osc)³ and for every $x\in {\mathbb R}^n$, F(x) is nonempty and convex.

The basic assumptions are sufficient for existence of solutions to (10.1), and also ensure some regularity of the space of solutions to (10.1); see [7, Chapter 2]. Further assumptions on F, like linear growth, or the knowledge that all solutions are bounded, may ensure that maximal solutions are complete.

Discrete-time dynamics in this note are modeled by difference inclusions

$$\displaystyle \begin{aligned} x^+\in G(x), \end{aligned} $$

(10.2)

where $G:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ is a set-valued mapping. A solution to (10.2) is a function $\phi :{\mathbb N}_0\to {\mathbb R}^n$ such that ϕ(j + 1) ∈ G(ϕ(j)) for all $j\in {\mathbb N}_0:=\{0,1,2,\dots \}$. The difference inclusion (10.2), or the mapping G, satisfies basic assumptions if

• G is locally bounded and outer semicontinuous and for every $x\in {\mathbb R}^n$, G(x) is nonempty.

Nonemptiness of values of G ensures existence and completeness of maximal solutions for (10.2); further conditions in the basic assumptions ensure that the sets of solutions to (10.2) depend outer semicontinuously on initial conditions.

Several concepts, definitions, and results recalled in this note stated for (10.1) have parallel results for (10.2) and vice versa. In fact, they often extend to the setting where constraints are present, i.e., to

$$\displaystyle \begin{aligned} \dot{x}\in F(x), \qquad x\in C, \end{aligned} $$

(10.3)

where $C\subset {\mathbb R}^n$, and

$$\displaystyle \begin{aligned} x^+\in G(x), \qquad x\in D, \end{aligned} $$

(10.4)

where $D\subset {\mathbb R}^n$. In such cases, basic assumptions require that C, or D, be closed. Furthermore, some results carry over to the so-called hybrid dynamical systems, which combine (10.3) and (10.4); see [33].

To quickly suggest what hybrid systems are and to illustrate some concepts that follow, an example from [31] is recalled. Let $x_1,x_2,\dots ,x_K\in {\mathbb R}^m$ represent the positions of K agents. Agents move towards an agreed-upon target a, according to $\dot {x}_k=a-x_k$, and every T > 0 amount of time update the target a by picking a ∈ Γ(x ₁, x ₂, …, x _K), where Γ is some set-valued mapping. The resulting dynamical system, with τ serving as a timer variable, is

which fits the combination of (10.3) and (10.4) by taking $x=(x_1,\dots ,x_K,a,\tau )\in {\mathbb R}^{(K+1)m+1}$, $C={\mathbb R}^{(K+1)m}\times (0,T]$, $D={\mathbb R}^{(K+1)m}\times \{0\}$, and F and G as determined by the dynamics above. If Γ(x ₁, x ₂, …, x _K) is the convex hull of x _k’s, namely, the smallest convex set containing x ₁, x ₂, …, x _K, then, as time and the number of updates of a and τ go to ∞, x _k’s converge to a common limit. In fact, the set $\{x\in {\mathbb R}^{(K+1)m+1}\, |\, x_1=\dots =x_K=a\}$ has a kind of pointwise asymptotic property. The property can be shown by noting that the convex hull of x _k’s and a (a is included to account for a bad initial condition for a, i.e., when a is initially not in the convex hull of x _k’s) is not increasing along solutions and does not remain constant forever unless it consists of a single point. This approach can be made formal, and generalized, using set-valued Lyapunov functions.

10.2.1 Why Basic Assumptions?

Basic assumptions lead to desirable structure of the set of solutions to (10.1) and (10.2). For (10.1), they also have an interesting control engineering motivation. A control system is, in rough terms, a differential equation where the right-hand side depends not just on the state x of the system but also on the input, or control, u. A control system can be thus represented by $\dot {x}=c(x,u)$. Feedback control of a control system is about letting the control u be a function of the state x, u = k(x). In some cases, control objectives—including asymptotic stability—cannot be achieved through continuous feedback k, even if c is continuous, but can be achieved using discontinuous k. See [4] for an example. Discontinuous k may lead to discontinuous x↦c(x, k(x)), and thus to a differential equation $\dot {x}=f(x)$ with a discontinuous right-hand side. Solutions to such differential equations may be quite sensitive to initial conditions. When such differential equations result from a discontinuous feedback u = k(x) applied to a control system, the sensitivity may be to measurement error as well. That is, small errors represented here by e and the application of u = k(x + e) can result in behaviors quite different from those resulting from u = k(x).

Let $f:{\mathbb R}^n\to {\mathbb R}^n$ be a function. An absolutely continuous $\phi :[0,T]\to {\mathbb R}^n$ is a Hermes solution to the differential equation $\dot {x}=f(x)$ if there exist sequences $\phi _i:[0,T]\to {\mathbb R}^n$ of absolutely continuous functions converging uniformly to ϕ and $e_i:[0,T]\to {\mathbb R}^n$ of measurable functions converging uniformly to the 0 function such that

$$\displaystyle \begin{aligned}\dot{\phi}_i(t)=f\left(\phi_i(t)+e_i(t)\right) \qquad \mbox{for almost all}\ t\in[0,T].\end{aligned}$$

An absolutely continuous $\phi :[0,T]\to {\mathbb R}^n$ is a Krasovskii solution to $\dot {x}=f(x)$ if it is a solution to the differential inclusion (10.1) with $F:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ defined by⁴

$$\displaystyle \begin{aligned}F(x)=\bigcap_{\delta>0} \overline{\mathop{\mathrm{con}}} f(x+\delta{\mathbb B}) \qquad \forall x\in{\mathbb R}^n.\end{aligned}$$

The set-valued regularization above, of the possibly discontinuous f, comes from [43] and differs from the one used by Filippov [26] in that the latter excludes from $x+\delta {\mathbb B}$ sets of 0 measure. Both regularizations lead to F that satisfies the basic assumptions. The connection between the two notions of generalized solutions to $\dot {x}=f(x)$, stated below, was observed by [37] and formally proved in [35]; see also an extension to hybrid systems in [58].

Theorem 10.1

If $f:{\mathbb R}^n\to {\mathbb R}^n$ is locally bounded, then $\phi :[0,T]\to {\mathbb R}^n$ is a Hermes solution to $\dot {x}=f(x)$ if and only if it is a Krasovskii solution.

In summary, the effect of small perturbations, including measurement error in a control system, on a differential equation with a discontinuous right-hand side can be studied by passing to a well-behaved differential inclusion.

To illustrate the role of basic assumptions in the study of convergence of solutions to the difference inclusion (10.2), a result of [64] is recalled below. In the nonlinear programming setting of [64], (10.2) was understood as an algorithm with a set of solutions (minimizers), denoted below by A. In that sense, the conclusion of the result is that an algorithm either terminates in finite number of steps at a solution or generates a sequence, the convergent subsequences of which converge to solutions.

Theorem 10.2

Let $G:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ be a set-valued map. Let $A\subset {\mathbb R}^n$ be a set. Suppose that:

• There exists a continuous $V:{\mathbb R}^n\to {\mathbb R}$ such that

  • if x∉A then for every x ⁺ ∈ G(x), V (x ⁺) < V (x);

  • if x ∈ A then for every x ⁺ ∈ G(x), V (x ⁺) ≤ V (x).

• For every x∉A, G(x) is nonempty and G is outer semicontinuous at x.

Let ϕ be a bounded maximal solution to (10.2). Then either the domain of ϕ is bounded, given by {0, 1, …, J}, and x(J) ∈ A; or ϕ is complete and the limit of any convergent subsequence of $\{\phi (j)\}_{j=0}^\infty$ is in A.

The gist of the proof is that if ϕ is a complete solution to (10.2), then a limit of any convergent subsequence, denoted $\overline {x}$, satisfies $\overline {x}\in A$. Indeed, otherwise $G(\overline {x})\neq \emptyset$ and for some $y\in G(\overline {x})$, $V(y)=V(\overline {x})$, which cannot hold if $\overline {x}\not \in A$. The result and the method of proof resemble what in control theory is known as the Invariance Principle [10, 44] where, usually, one of the assumptions requires that level sets of V  that are invariant under the dynamics be in A.

10.3 Asymptotic Stability

A set $A\subset {\mathbb R}^n$ is asymptotically stable for the differential inclusion (10.1) if every maximal solution to (10.1) is complete; if

• A is Lyapunov stable: for every ε > 0 there exists δ > 0 so that, for every complete solution ϕ to (10.1), if d _A(ϕ(0)) < δ then d _A(ϕ(t)) < ε for all t ≥ 0; and if

• A is attractive: for every complete solution ϕ to (10.1), lim_t→∞ d _A(ϕ(t)) = 0.

Above, d _A is the distance to A, i.e., d _A(x) =inf_{a ∈ A}∥x − a∥. The property just defined is usually referred to as global asymptotic stability or asymptotic stability in the large, as opposed to local asymptotic stability that requires Lyapunov stability and local attractivity of A: only solutions from a neighborhood of A are required to satisfy lim_t→∞ d _A(ϕ(t)) = 0. For simplicity of presentation, only the global concept is discussed here and the adjective is skipped.

Well-known sufficient conditions for asymptotic stability, dating back to Lyapunov [46], involve a function that decreases along solutions to (10.1). A variety of conditions involving generalized derivatives of a Lyapunov functions have been used to describe that decrease; see [8]. Roughly, they take the form

$$\displaystyle \begin{aligned} \partial V(x)\cdot f\leq-W(x) \quad \forall f\in F(x), \end{aligned} $$

(10.5)

where V  is a Lyapunov function, ∂V  is an appropriate generalized gradient of V , and the nonnegative W represents the rate of decrease of V  along solutions to (10.1): the inequality (10.5) should ensure that V (ϕ(t)) decreases along a solution ϕ with rate W(ϕ(t)). Here, for simplicity—and also because existence of such functions can be shown if the dynamics or the asymptotic stability is somewhat regular, only smooth Lyapunov functions are precisely defined. A function $V:{\mathbb R}^n\to [0,\infty )$ is a smooth Lyapunov function for (10.1) and a compact set A if it is C ^∞, V (x) = 0 if and only if x ∈ A, lim_|x|→∞ V (x) = ∞, and

$$\displaystyle \begin{aligned} \nabla V(x)\cdot f\leq-V(x) \quad \forall x\in{\mathbb R}^n,\ f\in F(x). \end{aligned} $$

(10.6)

Theorem 10.3

If every maximal solution to (10.1) is complete and there exists a smooth Lyapunov function for (10.1) and a compact set A, then A is asymptotically stable for (10.1).

Less known and usually harder to prove are converse Lyapunov results, guaranteeing the existence of Lyapunov functions for asymptotically stable differential and difference inclusions. For linear dynamics with an asymptotically stable origin, Lyapunov showed that there exist quadratic Lyapunov functions, but for nonlinear dynamics, many converse results produce irregular Lyapunov functions. For a historical accounting, see the survey [40]. A strong converse result, guaranteeing the existence of a smooth Lyapunov function for (10.1), was given by [23, Theorem 1.2] for A = {0} and extended to more general A, and more general stability concepts, in [61]. The result below follows from Theorems 1, 3 and Proposition 3 in [61].

Theorem 10.4

If F satisfies the basic assumptions and a compact set A is asymptotically stable for (10.1), then there exists a smooth Lyapunov function for (10.1) and A.

The approach in [23, 61] to the converse result is to first establish robustness of asymptotic stability and then rely on robustness to smooth out a possibly discontinuous and nonsmooth Lyapunov function candidate. The set A is robustly asymptotically stable for (10.1) if it is asymptotically stable and there exists a continuous function $\rho :{\mathbb R}\to [0,\infty )$, with ρ(x) = 0 if and only if x ∈ A, such that A is asymptotically stable for

$$\displaystyle \begin{aligned} \dot{x}\in F_\rho(x), \end{aligned} $$

(10.7)

where the set-valued mapping $F_\rho :{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ is

$$\displaystyle \begin{aligned} F_\rho(x)=\overline{\mathop{\mathrm{con}}} F\left(x+\rho(x){\mathbb B}\right)+\rho(x){\mathbb B} \quad \forall x\in{\mathbb R}^n. \end{aligned} $$

(10.8)

In common words, robustness of asymptotic stability of A requires that the property remain true if the dynamics are enlarged, or inflated, away from A. The result below follows from Theorem 3 and Proposition 3 in [61].

Theorem 10.5

If F satisfies the basic assumptions and a compact set A is asymptotically stable for (10.1), then A is robustly asymptotically stable for (10.1).

In fact, robust asymptotic stability of a compact set A is, essentially, equivalent to the existence of a smooth Lyapunov function. This is visible in [23, Theorem 1.2, Proposition 3.1] for the case of A = {0}, and explicitly stated in greater generality in [61, Theorem 1]. Subject to adding some conditions on the completeness of maximal solutions, one can conclude that the following are equivalent:

• A is robustly asymptotically stable for (10.1);

• there exists a smooth Lyapunov function for (10.1) and A.

This and the other ideas and results above carry over to discrete dynamics [41, 42] and generalize to hybrid dynamical systems [33]. For completeness, the definition parallel to (10.6) and results parallel to Theorem 10.3 and Theorem 10.4, in the setting of (10.2) are given below, summarizing [41, 42]. Note that only continuity is required below; this property, for difference inclusions, plays the role that smoothness (though continuity of the gradient is what matters the most) plays for differential inclusions. However, converse results in [41, 42] do yield smooth V .

A function $V:{\mathbb R}^n\to [0,\infty )$ is a continuous Lyapunov function for (10.2) and a compact set A if it is continuous, V (x) = 0 if and only if x ∈ A, lim_|x|→∞ V (x) = ∞, and

$$\displaystyle \begin{aligned}V(g)\leq \frac{1}{e}V(x) \quad \forall x\in{\mathbb R}^n,\ g\in G(x). \end{aligned}$$

The constant 1∕e above is picked to mimic the exponential decay of V  in (10.5); any positive constant less than 1 leads to asymptotic stability.

Theorem 10.6

If there exists a continuous Lyapunov function for (10.2) and a compact set A, then A is asymptotically stable for (10.2). If (10.2) satisfies the basic assumptions and a compact set A is asymptotically stable for (10.2), then there exists a continuous Lyapunov function for (10.2).

10.4 Pointwise Asymptotic Stability: Some Examples

A set $A\subset {\mathbb R}^n$ is pointwise asymptotically stable for the differential inclusion (10.1) if every maximal solution to (10.1) is complete; if

• every point a ∈ A is Lyapunov stable: for every ε > 0 there exists δ > 0 so that, for every complete solution ϕ to (10.1), if ∥ϕ(0) − a∥ < δ then ∥ϕ(t) − a∥ < ε for all t ≥ 0; and if

• every complete solution ϕ to (10.1) is convergent and lim_t→∞ ϕ(t) ∈ A.

As it was the case for asymptotic stability, the concept above is global/in the large and the adjective is skipped. If A is a singleton, the pointwise asymptotic stability is the same as asymptotic stability. If A is compact, pointwise asymptotic stability implies asymptotic stability. Indeed, given an ε > 0 and, for each a ∈ A, a δ _a > 0 that verifies Lyapunov stability of a, compactness of A leads to a single δ > 0 verifying Lyapunov stability of A. If A is unbounded, this is no longer the case, and Lyapunov stability of every a ∈ A need not imply Lyapunov stability of A in the sense of Section 10.3. Thus, for unbounded A, asymptotic and pointwise asymptotic stability properties are not comparable. Furthermore, an asymptotically stable compact set A consisting of equilibria of (10.1) only, i.e., points with F(x) = 0, need not be pointwise asymptotically stable, as pointed out in a nice example [12, Example 1.1]: for a system on ${\mathbb R}^2$ given by

$$\displaystyle \begin{aligned} \begin{array}{rcl} \dot{x}=f(x)&\displaystyle :=&\displaystyle \mathop{\mathrm{sign}}(x_1^2+x_2^2-1)\left|x_1^2+x_2^2-1\right|{}^\alpha \left(\begin{matrix} -x_1 \\ -x_2 \\ \end{matrix}\right) \\ &\displaystyle &\displaystyle +\mathop{\mathrm{sign}}(x_1^2+x_2^2-1)\left|x_1^2+x_2^2-1\right|{}^\beta \left(\begin{matrix} x_2 \\ -x_1 \\ \end{matrix}\right), \end{array} \end{aligned} $$

the unit circle consists of equilibria, but depending on the parameters α, β, solutions can converge, in distance, to the unit circle while winding themselves around it infinitely many times, violating Lyapunov stability of each point on the circle; or may have limits in the unit circle, leading to pointwise asymptotic stability.

A linear differential equation $\dot {x}=Mx$ has a pointwise asymptotically stable subspace if and only if M has index 0 or 1 and its nonzero eigenvalues have negative real parts; equivalently, if lim_t→∞ e ^Mt exists. Such matrices are called semistable [19]. The name semistability was adopted to study pointwise asymptotic stability in general nonlinear differential equations and more general settings by [12, 38] and others. Pointwise asymptotic stability is the name adopted by the author, beginning in [27], but it has appeared before, including in [63] in the setting of saddle-point dynamics. The reason for a different name was that while, for a matrix M, semistability is indeed weaker than stability,⁵ for nonlinear dynamics and compact sets A, pointwise asymptotic stability is in fact a stronger property than asymptotic stability.

Examples of pointwise asymptotic stability presented below are related to optimization of convex functions, dynamics are generated by monotone mappings and have a nonexpansive property, and, consequently, the pointwise asymptotic stability is particularly nice: Lyapunov stability of equilibria is verified with δ = ε. The example from [12], recalled above, does not have this feature. Further examples where pointwise asymptotic stability appears include modeling of hysteresis [51], biological and physiological systems [34], and mass-action kinetics in chemistry [21].

10.4.1 Fejér Monotonicity

A sequence $\{x_j\}_{j=0}^\infty$ is Fejér monotone with respect to a set A if, for every $n\in {\mathbb N}_0$,

$$\displaystyle \begin{aligned}\|x_{j+1}-a\|\leq\|x_j-a\| \quad \forall a\in A.\end{aligned}$$

Clearly, if G is nonexpansive, i.e., Lipschitz continuous with constant 1, then solutions to (10.2) are Fejér monotone with respect to the set A of equilibria/fixed points of G, i.e., points a with G(a) = a. Several algorithms in convex optimization, whose purpose is to find a minimum of a function f, generate sequences that are Fejér monotone with respect to the set of minimizers of f; see [25] for an exposition. In the terminology of this note, if every solution to (10.2) is Fejér monotone with respect to the set of equilibria of (10.2), then every equilibrium is Lyapunov stable. If, additionally, every solution to (10.2) converges to an equilibrium, then the set of equilibria is pointwise asymptotically stable.

10.4.2 Steepest Descent for Convex Functions, and Beyond

A prototype for the differential inclusions considered in this section is the steepest descent or gradient flow $\dot {x}=-\nabla f(x)$ for a convex and differentiable function $f:{\mathbb R}^n\to {\mathbb R}$. A natural generalization is to consider convex, but nondifferentiable f, leading to the subdifferential inclusion $\dot {x}\in -\partial f(x)$. A further generalization, motivated by the consideration of constraints, is to consider extended-valued convex functions $f:{\mathbb R}^n\to {\mathbb R}\cup \{\infty \}$. A different extension is to begin with a function convex in one variable, concave in the other variable—for example, the Lagrangian for a convex optimization problem—and consider the steepest descent in the first variable, steepest ascent in the second.

These generalizations fit under the umbrella of differential inclusions defined by maximal monotone mappings, discussed in the next section. The cases of convex and convex-concave functions follow.

To account for constraints and so to only consider solutions to the dynamics (10.1) or (10.2) that remain in a particular subset of the state space, in the remainder of Section 10.4 the following variant of pointwise asymptotic stability is considered: Given a set $C\subset {\mathbb R}^n$, a set $A\subset {\mathbb R}^n$ is pointwise asymptotically stable relative to C for the differential inclusion (10.1) if every maximal solution ϕ to (10.1) with ϕ(0) ∈ C is complete; if every point a ∈ A is Lyapunov stable relative to C: for every ε > 0 there exists δ > 0 so that, for every complete solution ϕ to (10.1) with ϕ(0) ∈ C, if ∥ϕ(0) − a∥ < δ then ∥ϕ(t) − a∥ < ε for all t ≥ 0; and if every complete solution ϕ to (10.1) with ϕ(0) ∈ C is convergent and lim_t→∞ ϕ(t) ∈ A.

10.4.2.1 Differential Inclusions Given by Maximal Monotone Mappings

Let $M:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ be a maximal monotone mapping.⁶ Consider the differential inclusion

$$\displaystyle \begin{aligned} \dot{x}\in-M(x), \end{aligned} $$

(10.9)

i.e., consider (10.1) with F = −M. Then [15], [7, Chapter 3, Section 2]:

• For every $x_0\in { \mathop {\mathrm {dom}} \nolimits } M$ ⁷ there exists a unique maximal solution to (10.9) with ϕ(0) = x ₀ and this solution is complete.

• For any two complete solutions ϕ, ψ to (10.9), t↦∥ϕ(t) − ψ(t)∥ is nonincreasing. Indeed,

  $$\displaystyle \begin{aligned}\frac{d}{dt}\frac{1}{2}\|\phi(t)-\psi(t)\|{}^2 = \left(\phi(t)-\psi(t)\right)\cdot\left(\dot{\phi}(t)-\dot{\psi}(t)\right) \leq 0,\end{aligned}$$

  where the inequality follows directly from monotonicity of M. In particular, the solutions to (10.9) depend continuously on initial conditions.

Furthermore, for every solution ϕ to (10.9), $\|\dot {\phi }(t)\|$ is nonincreasing, and, for almost all t ≥ 0,

$$\displaystyle \begin{aligned}\dot{\phi}(t)=m\left(-M(\phi(t))\right),\end{aligned}$$

where m(S) is the element of the closed set S with minimum norm. In other words, every solution is “slow,” “heavy,” or “lazy.”

Let A be the set of equilibria of (10.9). Clearly, every a ∈ A is Lyapunov stable, and if A ≠ ∅, then every solution to (10.9) is bounded. If, additionally, every solution converges to a point in A, the set A is pointwise asymptotically stable relative to ${ \mathop {\mathrm {dom}} \nolimits } M$. A natural sufficient condition for such convergence, proposed by [17], is demipositivity. Let x be a complete solution to (10.9) and let a be an equilibrium of (10.9), i.e., 0 ∈ M(a). Then

$$\displaystyle \begin{aligned}\frac{d}{dt}\frac{1}{2}\|\phi(t)-a\|{}^2 = (\phi(t)-a)\cdot\dot{\phi}(t)\leq 0,\end{aligned}$$

and there must exist such that $(\phi (t_i)-a)\cdot \dot {\phi }(t_i)\to 0$. Without loss of generality, one can assume that ϕ(t _i) and $\dot {\phi }(t_i)$ converge. If $\overline {x}=\lim _{i\to \infty } \phi (t_i)$ is an equilibrium of (10.9), then it is Lyapunov stable, and consequently, $\lim _{t\to \infty } \phi (t)=\overline {x}$. This leads to the definition: M is demipositive if there exists a ∈ A such that, for every convergent sequence x _i and every bounded sequence v _i ∈ M(x _i), if (x _i − a) ⋅ v _i → 0 then lim_i→∞ x _i ∈ A. The original definition, given in an infinite-dimensional Hilbert space setting, considered weak convergence of x _i. Here, since the graph of a maximally monotone $M:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ is closed, demipositivity furthermore reduces to a property sometimes referred to as firm positivity: there exists a ∈ A such that, if v ⋅ (x − a) = 0 for some v ∈ M(x) then x ∈ A.

Sufficient conditions for demipositivity include strict and strong monotonicity of M,⁸ or the interior of A being nonempty. For more, see [54, Proposition 6.2]. In case of strict monotonicity, A reduces to a singleton {a} and ∥ϕ(t) − ψ(t)∥ is strictly decreasing for any two solutions ϕ, ψ whenever ϕ(t) ≠ ψ(t). In case of strong monotonicity, A is also a singleton, the function V (x) = ∥x − a∥² turns out to be a smooth Lyapunov function, and the convergence is exponential.⁹

10.4.2.2 Steepest Descent for a Convex Function

An important case of a maximal monotone mapping is the subdifferential of a proper, lower semicontinuous (lsc), and convex function $f:{\mathbb R}^n\to {\mathbb R}\cup \{\infty \}$.¹⁰ The subdifferential mapping $\partial f:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ of such a function is defined, at every $x\in \mathbb {R}^n$, where f(x) < ∞, by

$$\displaystyle \begin{aligned} \partial f(x)=\{v\in{\mathbb R}^n\, |\, f(x')\geq f(x)+v\cdot(x'-x)\ \forall x'\in{\mathbb R}^n\}. \end{aligned} $$

(10.10)

The subdifferential mapping is maximal monotone, [56, Theorem 12.17], and when f is a differentiable convex function, ∂f = ∇f. Strong convexity of f is equivalent to strong monotonicity of ∂f, see [56, Exercise 12.59], and thus implies demipositivity of ∂f. A similar equivalence and implication holds for strict convexity, see [56, Theorem 12.17].

To illustrate the reason to consider convex functions that are not necessarily differentiable or even finite-valued, and the utility of the subdifferential, consider the question of minimizing a convex and differentiable function $g:{\mathbb R}^n\to {\mathbb R}$ over a nonempty, closed, and convex $C\subset {\mathbb R}^n$. The question is equivalent to that of minimizing, over ${\mathbb R}^n$, a proper, lsc, and convex $f:{\mathbb R}^n\to {\mathbb R}\cup \{\infty \}$ given by

$$\displaystyle \begin{aligned} f(x)=\left\{\begin{matrix} g(x) & \mbox{if} & x\in C, \\ \infty & \mbox{if} & x\not\in C.\end{matrix}\right. \end{aligned} $$

(10.11)

The subdifferential of this function is given by

$$\displaystyle \begin{aligned}\partial f(x)=\left\{\begin{matrix} \nabla g(x)+N_C(x) & \mbox{if} & x\in C, \\ \emptyset & \mbox{if} & x\not\in C.\end{matrix}\right. \end{aligned}$$

Here, N _C(x) is the normal cone to C at x.¹¹ At points x in the interior of C, ∂f(x) = ∇g(x), while at points on the boundary of C, ∂f(x) is naturally unbounded, and so ∂f does not satisfy the basic assumptions. To ensure that solutions to $\dot {x}=-\nabla g(x)$ remain in the set C, projected dynamics are often considered, i.e., at the boundary points of C, −∇g(x) is projected onto the tangent cone to C at x. It turns out that the projection is the same as the minimum norm element of − ∂f(x), with f given by (10.11), and so solutions to the projected gradient dynamics are the same as those to $\dot {x}\in -\partial f(x)$; see [36] or the recent [16, Corollary 2]. These solutions converge to minimizers, if the minimizers exist.

Indeed, consider any proper, lsc, and convex function $f:{\mathbb R}^n\to {\mathbb R}\cup \{\infty \}$ with a nonempty set of minimizers. Then ∂f is demipositive/firmly positive. To see this, note that $a\in A:=\arg \min f$ if and only if 0 ∈ ∂f(a), which follows from (10.10), and then v ⋅ (x − a) = 0 with v ∈ ∂f(x) ensures, via (10.10), that f(x) = f(a). Additionally, in the case of M being the subdifferential of a proper, lsc, and convex function, the existence of solutions to (10.9) holds not just for $x_0\in { \mathop {\mathrm {dom}} \nolimits }\partial f$ but for every $x_0\in \overline {{ \mathop {\mathrm {dom}} \nolimits } f}$; see [14, Theorem 22].¹²

Theorem 10.7

Let $f:{\mathbb R}^m\to {\mathbb R}\cup \{\infty \}$ be lower semicontinuous and convex and suppose $A:=\arg \min f\neq \emptyset$ . Then A is pointwise asymptotically stable, relative to $\overline {{ \mathop {\mathrm {dom}} \nolimits } f}$ , for

$$\displaystyle \begin{aligned}\dot{x}\in-\partial f(x).\end{aligned}$$

The case of steepest descent/steepest ascent for a convex-concave function is more interesting.

10.4.2.3 Saddle-Point Dynamics for a Convex-Concave Function

Let $H:{\mathbb R}^{n+m}\to {\mathbb R}\cup \{-\infty ,\infty \}$ be a proper and closed, in the sense of [55], convex-concave function. Closedness plays here a role similar to the role lower semicontinuity plays for convex functions, but the definition is more technical. See [55, Chapter 33] for details and Theorem 10.8 below for an example of a proper and closed function with ∞ and −∞ as values. The convex-concave subdifferential of H, namely the mapping

$$\displaystyle \begin{aligned} (x,y)\mapsto\partial_x H(x,y)\times \left(-\tilde{\partial}_y H(x,y)\right), \end{aligned} $$

(10.12)

where ∂ _x H(x, y) is the convex analysis subdifferential of the convex function x↦H(x, y), and $\tilde {\partial }_y H(x,y)$ is the negative of the subdifferential of the convex function y↦ − H(x, y), is maximal monotone; see [55, Corollary 37.5.2]. Consequently, saddle-point dynamics

$$\displaystyle \begin{aligned} \dot{x}\in-\partial_x H(x,y),\quad \dot{y}\in\tilde{\partial}_y H(x,y), \end{aligned} $$

(10.13)

are a special case of (10.9). Equilibria of (10.13) are saddle points of H, namely, points (x ^∗, y ^∗) such that H(x ^∗, y) ≤ H(x ^∗, y ^∗) ≤ H(x, y ^∗) for all $x\in {\mathbb R}^n$ and all $y\in {\mathbb R}^m$, and the set of all saddle points of H is a closed convex product set, denoted X ^∗× Y ^∗. Every saddle point of H is thus Lyapunov stable for (10.13), but convergence of solutions to (10.13) is more delicate than what was the case for steepest descent. In particular, the simple convex-concave $H:{\mathbb R}^2\to {\mathbb R}$ given by H(x, y) = xy has a unique saddle point (0, 0) and every solution to (10.13) is periodic. This example also shows that, in general, (10.12) is not demipositive.

Sufficient conditions for convergence of every solution to (10.13) to a saddle point of H include, of course, strong convexity in x and strong concavity in y, as then the convex-concave subdifferential is strongly monotone; and strict convexity in x and strict concavity in y, as then the subdifferential is strictly monotone. A weaker sufficient condition, leading to demipositivity of the convex-concave subdifferential, is the existence of a saddle point (x ^∗, y ^∗) such that, if (x, y) satisfies H(x ^∗, y) = H(x ^∗, y ^∗) = H(x, y ^∗), then (x, y) is a saddle point too; see [20].

A similar, but weaker sufficient condition, requiring a kind of partial demipositivity was noted in [62] for differentiable H extended to include constraints x ∈ X and y ∈ Y  for closed convex sets X and Y  in [63]; and was recently revisited to allow nondifferentiable H in [29, Theorem 3.3].

Theorem 10.8

Let $h:{\mathbb R}^{n+m}\to {\mathbb R}$ be a convex-concave function, let $X\subset {\mathbb R}^n$ , $Y\subset {\mathbb R}^m$ be nonempty, closed, and convex sets, and let $H:{\mathbb R}^{n+m}\to {\mathbb R}\cup \{-\infty ,\infty \}$ be given by

$$\displaystyle \begin{aligned}H(x,y)= \left\{\begin{matrix} h(x,y) & \mathit{\mbox{if}} & x\in X, y\in Y, \\ \infty & \mathit{\mbox{if}} & x\not\in X, \\ -\infty & \mathit{\mbox{if}} & x\in X, y\not\in Y. \end{matrix}\right.\end{aligned}$$

If the set of saddle points of H, X ^∗× Y ^∗ , is nonempty and either H(x ^∗, y ^∗) < H(x, y ^∗) for all x ^∗∈ X ^∗ , y ^∗∈ Y ^∗ , x∉X ^∗ or H(x ^∗, y) < H(x ^∗, y ^∗) for all x ^∗∈ X ^∗ , y ^∗∈ Y ^∗ , y∉Y ^∗ , then X ^∗× Y ^∗ is pointwise asymptotically stable, relative to X × Y , for (10.13).

An example where the assumptions of the theorem hold but (10.12) is not demipositive is H(x, y) = x ² + xy. For further discussion and a proof of the result above, and several references with applications of saddle-point dynamics to control engineering problems, see [29].

10.4.3 Consensus Algorithms

For $x=(x_1,x_2,\dots ,x_K)\in {\mathbb R}^{Km}$, where $x_k\in {\mathbb R}^m$ and which could model positions of K agents, consider

$$\displaystyle \begin{aligned} \dot{x}_i=\sum_{k=1}^K a_{ik}(x_k-x_i), \quad i=1,2,\dots,K \end{aligned} $$

(10.14)

for some constants $a_{ik}\in {\mathbb R}$, i, k = 1, 2, …, K. If these constants are nonnegative and a _ik = a _ki, then (10.14) is the steepest descent $\dot {x}=-\nabla f(x)$ for the convex function $f:{\mathbb R}^{Km}\to {\mathbb R}$ given by

$$\displaystyle \begin{aligned}f(x)=\frac{1}{4}\sum_{i,k=1}^K a_{ik}(x_i-x_k)^2.\end{aligned}$$

From Theorem 10.7, the set of equilibria in (10.14) is pointwise asymptotically stable. Of particular interest in control literature is the case when the set of equilibria of (10.14) is

$$\displaystyle \begin{aligned} A=\{x\in{\mathbb R}^{mK}\, |\, x_1=x_2=\dots=x_K\}, \end{aligned} $$

(10.15)

in which case convergence to A represents the agents reaching consensus. This occurs in particular when nonnegative a _ik = a _ki’s represent weights in an undirected communication graph between the agents—for example, it may be that a _ik = a _ki = 1 if the agents communicate, 0 otherwise—and the communication graph is connected. See the surveys [52, 53] for a broader exposition, [59] and the literature therein for some generalizations of (10.14) that come from more general convex functions or that allow for rapid changes in the communication graph, and [38] for links between consensus and pointwise asymptotic stability. Many of the mentioned generalizations fit under a broader umbrella of a switching system, as noted in [32], leading to the result below. For a general exposition of switching systems in control, see [45]. In common words, a switching system is a differential (or difference) equation (or inclusion) where the right-hand side switches, according to usually a time-dependent but sometimes a state-dependent rule, between several given mappings.

Consider the switching system

$$\displaystyle \begin{aligned} \dot{x}\in-\partial f_q(x), \end{aligned} $$

(10.16)

where Q is a set and for each q ∈ Q, $f_q:{\mathbb R}^n\to {\mathbb R}\cup \{\infty \}$ is a convex function. A switching signal is a function σ : [0, ∞) → Q such that there exist 0 = t ₀ < t ₁ < t ₂ < … with such that σ is constant on each [t _j, t _j+1). Given a switching signal σ, a solution to (10.16) is a locally absolutely continuous function $\phi :[0,T]\to {\mathbb R}^n$ or $\phi :[0,\infty )\to {\mathbb R}^n$ such that $\dot {\phi }(t)\in -\partial f_{\sigma (t)}(\phi (t))$ for almost every t in the domain of ϕ. The following is shown in [32]. The proof relies on picking a ∈ A _∞ and using ∥x − a∥² as a kind of Lyapunov function, which is nondecreasing. (Below, μ stands for the Lebesgue measure, and reduces to a sum of lengths of intervals.)

Theorem 10.9

Suppose that Q = {1, 2, …, p}; for every q ∈ Q, $f_q:{\mathbb R}^n\to {\mathbb R}\cup \{\infty \}$ is a proper, lsc, and convex function; and that $\bigcap _{q\in Q} \mathop {\mathrm {arg}}\, \mathop {\mathrm {min}} f_q\neq \emptyset$ . Let σ : [0, ∞) → Q be a switching signal and let

$$\displaystyle \begin{aligned}T_q(\sigma):=\mu\left(\{t\geq 0\, |\, \sigma(t)=q\}\right), \quad Q_\infty(\sigma):=\{q\in Q\, |\, T_q(\sigma)=\infty\}. \end{aligned}$$

Then every complete and uniformly continuous solution to (10.16) converges to A _∞ , where

$$\displaystyle \begin{aligned}A_\infty(\sigma):=\bigcap_{q\in Q_\infty(\sigma)} \mathop{\mathrm{arg}}\, \mathop{\mathrm{min}} f_q.\end{aligned}$$

In the setting of Theorem 10.9, the distance of every solution to (10.16) to the set $\bigcap _{q\in Q} \mathop {\mathrm {arg}}\, \mathop {\mathrm {min}} f_q$ and to A _∞(σ) is nondecreasing, and so, subject to further existence and uniform continuity assumptions, pointwise asymptotic stability of A _∞ can be concluded. In this setting, the issue of agents reaching consensus reduces to the question whether A _∞(σ), the set of common minimizers of f _q for q ∈ Q _∞(σ), correspond to points representing consensus (10.15).

The switching system (10.16) is a particular kind of time-varying dynamics generalizing (10.9). Different time dependence is considered in, for example, [9] and [5]. When arbitrarily fast switching in (10.16) is allowed, solutions approximate those to $\dot {x}\in -F(x)$ where F(x) is the convex hull of the union of ∂f _q(x). Arbitrary solutions to this inclusion are not expected to converge to common minimizers. However, slow solutions to the inclusion, i.e., solutions to $\dot {x}=m(-F(x))$, are expected to converge to common minimizers if they exist, and to Pareto optimal points in general; see [6, 48] and earlier works referenced therein. Ideas similar to what is behind Theorem 10.9 are related to the ideas behind the alternating or cyclic projection method and other methods of finding common zeros of monotone mappings; see [11, 57], and the numerous references therein. In the discrete-time consensus algorithm setting, this relationship is discussed in [50].

10.5 Pointwise Asymptotic Stability: Some Results

Pointwise asymptotic stability theory has seen contributions in [12, 13, 19, 38, 39], and more, under the name “semistability,” and in the work by the author [27, 28], and [31]. Selected results are recalled below. Focus is on set-valued Lyapunov functions which enable necessary and sufficient conditions for pointwise asymptotic stability and characterizations of its robustness, inspired by what was previously done for asymptotic stability, as recalled in Section 10.3.

10.5.1 Sufficient Conditions

The usual Lyapunov conditions for asymptotic stability of a set A don’t imply pointwise asymptotic stability, unless A consists of a single point. Additional conditions can be posed ensure pointwise asymptotic stability. For example, [12] considered Lyapunov conditions and appropriately understood nontangent to A behavior of solutions, in the setting of differential equations. A condition of a different nature, which is sufficient for Lyapunov stability and can be combined with other conditions to yield pointwise asymptotic stability, is based on the length of solutions. In the setting of a difference inclusion (10.2), let ${ \mathop {\mathrm {Length}}}:{\mathbb R}^n\to {\mathbb R}\cup \{-\infty ,\infty \}$ be defined by

$$\displaystyle \begin{aligned}{\mathop{\mathrm{Length}}}(x_0)=\sup\left\{{\mathop{\mathrm{length}}}(\phi)\, |\, \phi\ \mbox{is a solution to}\ (10.2),\ \phi(0)=x_0\right\},\end{aligned}$$

where

$$\displaystyle \begin{aligned}{\mathop{\mathrm{length}}}(\phi)=\sum_{j=0}^\infty \|\phi(j+1)-\phi(j)\|.\end{aligned}$$

If ${ \mathop {\mathrm {Length}}}(x)=0$ and the function ${ \mathop {\mathrm {Length}}}$ is upper semicontinuous at x, equivalently, continuous at x, then x is Lyapunov stable. See [47], where the length was considered in a general metric space and for a difference inclusion; [13] for related results for differential equations, where the length of a complete solution $x:[0,\infty )\to {\mathbb R}^n$ is $\int _0^\infty \|\dot {\phi }(t)\|\, dt$; and [31] for hybrid systems.

Consensus issues for multiagent systems modeled by difference equations led [49] to introduce a set-valued Lyapunov function, to its use in a sufficient condition for pointwise asymptotic stability, and to applications of the condition to particular cases where the convex hull of the positions of agents can serve as a set-valued Lyapunov function.

Let $A\subset {\mathbb R}^n$ be a closed set. A set-valued mapping $W:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ is a set-valued Lyapunov function for A and the difference inclusion (10.2) if:

• x ∈ W(x) for every $x\in {\mathbb R}^n$, W(x) = {x} if and only if x ∈ A, W is outer semicontinuous at every x ∈ A, and W is locally bounded;

• there exists a continuous $\alpha :{\mathbb R}^n\to [0,\infty )$ such that α(x) = 0 if and only if x ∈ A and

  $$\displaystyle \begin{aligned} W(G(x))+\alpha(x){\mathbb B} \subset W(x) \quad \forall x\in{\mathbb R}^n. \end{aligned} $$

  (10.17)

In [49], an inequality involving some measure of the size of W was used in place of (10.17); the inclusion (10.17) is from [27], and is meant to resemble a version of a Lyapunov inequality: V (G(x)) ≤ V (x) − α(x), i.e., V (G(x)) + α(x) ≤ V (x). The result below is thus a minor variation of [49, Theorem 4].

Theorem 10.10

If there exists a set-valued Lyapunov function for a closed set $A\subset {\mathbb R}^n$ and the difference inclusion (10.2), then A is pointwise asymptotically stable for (10.2).

The proof relies on the fact that, for every solution ϕ to (10.2),

$$\displaystyle \begin{aligned}\phi(j)+\sum_{i=0}^{j-1}\alpha(\phi(i)){\mathbb B}\subset W(\phi(0)).\end{aligned}$$

Then, boundedness of solutions follows from ϕ(j) ∈ W(ϕ(0)); Lyapunov stability of every a ∈ A follows from ϕ(j) ∈ W(ϕ(0)), W(a) = {a}, and outer semicontinuity of W at a; while convergence, for complete solutions, follows from summability of the series of α(ϕ(i)). Details can be found in [31, Theorem 3.3, Theorem 3.7], in a hybrid system setting. In absence of strict decrease of W, i.e., if (10.17) is replaced by W(G(x)) ⊂ W(x), invariance-based arguments can lead to similar conclusions.

For completeness, a set-valued mapping $W:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ is a set-valued Lyapunov function for A and the constrained differential inclusion (10.3) if:

• x ∈ W(x) for every $x\in \overline {C}$, W(x) = {x} if and only if x ∈ A, W is outer semicontinuous at every x ∈ A, and W is locally bounded;

• there exists a continuous $\alpha :{\mathbb R}^n\to [0,\infty )$ such that α(x) = 0 if and only if x ∈ A and, for every solution $\phi :[0,T]\to \mathbb {R}^n$ to (10.3),

  $$\displaystyle \begin{aligned}W(\phi(t))+\left(\int_0^t \alpha(\phi(s))\, ds\right){\mathbb B} \subset W(\phi(0)) \quad \forall t\in[0,T]. \end{aligned}$$

Existence of such a W is sufficient for pointwise asymptotic stability; see [31, Theorem 3.3, Theorem 3.7].

10.5.2 Reachable Sets and Limits of Solutions

Consider the difference inclusion (10.2). Let $\mathcal {R}_{\leq J}:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ be the finite-horizon reachable set, i.e., the set-valued mapping given by

$$\displaystyle \begin{aligned}\mathcal{R}_{\leq J}(x_0)= \left\{\phi(j)\, |\, \phi\ \mbox{is a solution to}\ (10.2)\ \mbox{with}\ \phi(0)=x_0,\ j=0,1,\dots,J\right\},\end{aligned}$$

let ${\mathcal {R}_\infty }:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ be the infinite-horizon reachable set, given by

$$\displaystyle \begin{aligned}{\mathcal{R}_\infty}(x_0)= \left\{\phi(j)\, |\, \phi\ \mbox{is a solution to}\ (10.2)\ \mbox{with}\ \phi(0)=x_0,\ j\in{\mathbb N}_0\right\},\end{aligned}$$

and let $\overline {\mathcal {R}}_\infty :{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ be its closure, i.e., $\overline {\mathcal {R}}_\infty (x_0)=\overline {{\mathcal {R}_\infty }(x_0)}$. When all complete solutions to (10.2) converge, the limit set-valued mapping $\mathcal {L}:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ can be defined by

$$\displaystyle \begin{aligned}\mathcal{L}(x_0)=\left\{\lim_{j\to\infty} \phi(j)\, |\, \phi\ \mbox{is a complete solution to}\ (10.2)\ \mbox{with}\ \phi(0)=x_0 \right\} .\end{aligned}$$

Parallel definitions can be stated for the differential inclusion (10.1).

Simple examples show that neither the infinite-horizon reachable sets nor limits of solutions, if they exist in the first place, need to depend regularly on initial conditions. The presence of an asymptotically stable compact set does not fix this. For example, for $\dot {x}=x^2(1-x)$, [0, 1] is asymptotically stable (in fact, it is the smallest asymptotically stable set), while the infinite horizon reachable set from x < 0 is ${\mathcal {R}_\infty }(x)=[x,0)$; for x = 0, ${\mathcal {R}_\infty }(x)=\{0\}$; and for 0 < x < 1, ${\mathcal {R}_\infty }(x)=[x,1)$. Both ${\mathcal {R}_\infty }$ and $\overline {\mathcal {R}}_\infty$ fail to be outer semicontinuous at x = 0. Similarly, $\mathcal {L}(x)=\{0\}$ for x ≤ 0 and $\mathcal {L}(x)=\{1\}$ for x > 0, and both inner and outer semicontinuity of $\mathcal {L}$ fail at x = 0. On the other hand, the existence and continuous dependence of limits of solutions on initial conditions does not imply Lyapunov stability of equilibria. For $\dot {r}=0$, $\dot {\theta }=\theta (2\pi -\theta )$ in polar coordinates, where θ ∈ [0, 2π), the limit of a solution from (r, θ) is (r, 0), and each such limit is an equilibrium, but only (0, 0) is Lyapunov stable.

The presence of a closed and pointwise asymptotically stable set does lead to regularity of $\overline {\mathcal {R}}_\infty$ and $\mathcal {L}$.

Theorem 10.11

Suppose that $A\subset {\mathbb R}^n$ is a nonempty, closed, and pointwise asymptotically stable for (10.2) set and that G satisfies the basic assumptions. Then

• (a) the set-valued mappings $\overline {\mathcal {R}}_\infty$ and $\mathcal {L}$ are locally bounded and outer semicontinuous, and for every $x_0\in {\mathbb R}^n$ , $\overline {\mathcal {R}}_\infty (x_0)={\mathcal {R}_\infty }(x_0)\cup \mathcal {L}(x_0)$ ;

• (b) for every ε > 0 there exists $J\in {\mathbb N}_0$ such that $\overline {\mathcal {R}}_\infty (x_0)\subset \mathcal {R}_{\leq J}(x_0)+\varepsilon {\mathbb B}$.

If, additionally, G is continuous, then $\overline {\mathcal {R}}_\infty$ and $\mathcal {L}$ are continuous.

The result (a) is in [27, Proposition 4.1], (b) is in [28, Lemma 2.12], and the conclusion on continuity—which follows from (b) and continuity of the finite-horizon reachable set for continuous dynamics—is in [28, Proposition 2.13]. Parallel results for a differential inclusion (10.1) hold, but for the conclusions about continuity of $\overline {\mathcal {R}}_\infty$ and $\mathcal {L}$, an assumption of local Lipschitz continuity of F is needed.

10.5.3 Converse Set-Valued Lyapunov Results and Robustness

The set-valued Lyapunov function concept allows for converse results and characterization of robustness of pointwise asymptotic stability for the difference inclusion (10.2). A converse of Theorem 10.10, first given in [27], is below.

Theorem 10.12

If the difference inclusion (10.2) satisfies the basic assumptions and a compact set $A\subset {\mathbb R}^n$ is pointwise asymptotically stable for (10.2), then there exists a set-valued Lyapunov function for A and (10.2).

One approach to proving this is as follows. By Theorem 10.11, the closure of the reachable set $\overline {\mathcal {R}}_\infty :{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ is locally bounded and osc. Also, by the definition of the reachable set, for every $x\in {\mathbb R}^n$, $x\in \overline {\mathcal {R}}_\infty (x)$ and $\overline {\mathcal {R}}_\infty (G(x))\subset \overline {\mathcal {R}}_\infty (x)$. By Lyapunov stability of every a ∈ A, for each such a one has $\overline {\mathcal {R}}_\infty (a)=\{a\}$. What is missing is the strict decrease along solutions, as required by (10.17). Since A is asymptotically stable for (10.2), by Theorem 10.6 there exists a continuous Lyapunov function $V:{\mathbb R}^n\to [0,\infty )$, so that $V(g)\leq \frac {1}{e}V(x)$ for every $x\in {\mathbb R}^n$, g ∈ G(x). Then

$$\displaystyle \begin{aligned}W(x)=\overline{\mathcal{R}}_\infty(x)+V(x){\mathbb B}\end{aligned}$$

satisfies (10.17) with α(x) = (1 − 1∕e)V (x) and thus $W:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ as defined above is a set-valued Lyapunov function for A and (10.2).

Under further assumptions on the data in (10.2), $\overline {\mathcal {R}}_\infty$ is a continuous set-valued mapping, and then so is the W constructed above.

Corollary 10.1

If the difference inclusion (10.2) satisfies the basic assumptions, G is continuous, and a compact set $A\subset {\mathbb R}^n$ is pointwise asymptotically stable for (10.2), then there exists a continuous set-valued Lyapunov function for A and (10.2).

Continuity of a set-valued Lyapunov function is important, since it relates to robustness of pointwise asymptotic stability. The set A is robustly pointwise asymptotically stable for (10.2) if it is pointwise asymptotically stable and there exists a continuous function $\rho :{\mathbb R}\to [0,\infty )$, with ρ(x) = 0 if and only if x ∈ A, such that A is pointwise asymptotically stable for x ⁺ ∈ G _ρ(x), where the set-valued mapping $G_\rho :{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ is

$$\displaystyle \begin{aligned} G_\rho(x)=\bigcup_{y\in G(x+\rho(x){\mathbb B})} y+\rho(y){\mathbb B} \quad \forall x\in{\mathbb R}^n. \end{aligned} $$

(10.18)

The result below is [28, Theorem 4.3].

Theorem 10.13

Suppose that $G:{\mathbb R}^n\rightrightarrows {\mathbb R}^n$ is locally bounded. Let the compact set $A\subset {\mathbb R}^n$ be pointwise asymptotically stable for (10.2). Then, the following are equivalent:

• (a) A is robustly pointwise asymptotically stable for (10.2).

• (b) There exists a continuous set-valued Lyapunov function for A and (10.2).

The more involved part of the proof, of the implication (a) ⇒ (b), takes an outer semicontinuous set-valued Lyapunov function W, the existence of which is guaranteed by Theorem 10.12, and using the robustness margin ρ, constructs from W a continuous (in fact locally Lipschitz) set-valued Lyapunov function. The construction uses the technique that was used in [23, Proposition 3.5] to smooth a Lyapunov function candidate when proving Theorem 10.4, but applies it to W and not to the dynamics.

It is not immediate how robustness of pointwise asymptotic stability for discrete dynamics, as defined by the perturbation (10.18) of (10.2), and characterized by Corollary 10.1 and Theorem 10.13, relates to sensitivity of optimization algorithms to computational errors [65] and, in particular, to quasi-Fejér monotonicity [24]. Clearly, robustness considered here deals with stability and convergence, while most considerations in the optimization literature focus on convergence only.

Results for continuous-time dynamics (10.1), parallel to Theorem 10.12, Corollary 10.1, and Theorem 10.13 in particular the robustness of pointwise asymptotic stability for continuous (in the set-valued sense) dynamics are expected to hold but have not been published. What is not clear is whether robustness of pointwise asymptotic stability of a compact set automatically holds for outer semicontinuous dynamics, as it is the case for asymptotic stability (recall Theorem 10.5). Partial results in this direction, in the setting of differential inclusions (10.1), have been shown in [29], for the maximal monotone case, and announced in [30] for constrained dynamics with a local Fejér property. A special case of the latter result is below.

Note that even if the dynamics (10.1) are given by a monotone mapping, which ensures the Fejér property in Theorem 10.14, the inflated dynamics (10.8) in the definition of robustness are different from the enlargements of monotone mappings used in analysis of discrete-time optimization algorithms [18] and (10.8) is not monotone. Similarly, the inflated dynamics (10.8) are not single-valued and so robustness considered below is different from what is considered, for example, in [1, 22]. Relating these approaches to robustness properties to one another may be of interest.

Theorem 10.14

Suppose that (10.1) satisfies the basic assumptions; a nonempty, compact $A\subset {\mathbb R}^n$ is asymptotically stable for (10.1); and (10.1) is locally Fejér monotone with respect to A, in the sense that there exists a neighborhood U of A such that, for every solution ϕ to (10.1) with ϕ(0) ∈ U, ∥ϕ(t) − a∥≤∥ϕ(0) − a∥ for every a ∈ A, every $t\in { \mathop {\mathrm {dom}} \nolimits }\phi$ . Then A is robustly pointwise asymptotically stable for (10.1).

An outline of the proof is given, to illustrate the utility of the asymptotic stability results of Section 10.3. By Theorem 10.5, there exists a continuous $\rho _0:{\mathbb R}^n\to [0,\infty )$, with ρ ₀(x) = 0 if and only if x ∈ A, such that A is asymptotically stable for

$$\displaystyle \begin{aligned}\dot{x}\in F_{\rho_0}(x), \end{aligned}$$

where $F_{\rho _0}$ is given by (10.8). By Theorem 10.4, there exists a smooth Lyapunov function for this inclusion and A. Without loss of generality suppose that $\{x\in {\mathbb R}^n\, |\, V(x)\leq 1\}\subset U$, where U comes from the definition of local Fejér monotonicity of (10.1) with respect to A. Let

$$\displaystyle \begin{aligned}R_i:=\left\{x\in{\mathbb R}^n\, |\, 2^{-i}\leq V(x)\leq 2^{-i+1}\right\}, \quad i=1,2,\dots\end{aligned}$$

which are nonempty compact sets, and let

$$\displaystyle \begin{aligned}c_i:=\min_{x\in R_i} \min_{a\in A} \|x-a\|, \quad d_i=c_i-c_{i+1}, \quad r_i=\min_{x\in R_i}\rho_0(x)\end{aligned}$$

which are positive. Compactness-based arguments show that, for each i = 1, 2, …, there exists a positive ρ _i ≤ r _i such that, for every solution ϕ to (10.8) where ρ is given by ρ(x) = ρ _i for all $x\in {\mathbb R}^n$ and where ϕ(0) ∈ R _i; for every t such that ϕ(t) ∈ R _i; and for every a ∈ A, one has

$$\displaystyle \begin{aligned} \|\phi(t)-a\|\leq\|\phi(0)-a\|+d_i. \end{aligned} $$

(10.19)

Let $\rho :{\mathbb R}^n\to [0,\infty )$ be continuous, with ρ(x) = 0 if and only if x ∈ A, and such that ρ(x) ≤ ρ _i for all x ∈ R _i. Then ρ ≤ ρ ₀ and so A is asymptotically stable for (10.8). It is left to show that every a ∈ A is Lyapunov stable for (10.8). Indeed, for a compact set, this property combined with asymptotic stability implies pointwise asymptotic stability.

Let a ∈ A. Let ϕ be a solution to (10.8) with ϕ(0) ∈ R _i for some i. Let t _j, j = 1, 2, … be such that V (x(t _j)) = 2^−i−j+1. By (10.19), for t ∈ [0, t ₁], ∥x(t) − a∥≤∥x(0) − a∥ + d _i. For t ∈ [t ₁, t ₂], ∥x(t) − a∥≤∥x(t ₁) − a∥ + d _i+1 ≤∥x(0) − a∥ + d _i + d _i+1. In general, for t ∈ [t _j, t _j+1], j = 1, 2, …, $\|x(t)-a\|\leq \|x(0)-a\|+\sum _{k=i}^{i+j} d_k$. Hence, for every t ∈ [0, ∞),

$$\displaystyle \begin{aligned} \begin{array}{rcl} \|x(t){-}a\| &\displaystyle \leq&\displaystyle \|x(0){-}a\|+\sum_{k=i}^\infty d_k=\|x(0)-a\|+c_i \leq \|x(0)-a\|+\|x(0)-a\|. \end{array} \end{aligned} $$

Lyapunov stability of a follows, by taking $\delta =\min \{\varepsilon /2,1\}$ for any given ε > 0.

A minor variation of the proof above shows that, in the setting of Theorem 10.14, given any ε > 0, the robustness margin $\rho :{\mathbb R}\to [0,\infty )$ can be picked so that not only is A pointwise asymptotically stable for (10.7), but also there exists a neighborhood U of A such that, for every solution ϕ to (10.7) with ϕ(0) ∈ U, ∥ϕ(t) − a∥≤ (1 + ε)∥ϕ(0) − a∥ for every a ∈ A, every $t\in { \mathop {\mathrm {dom}} \nolimits }\phi$. That is, Fejér monotonicity is almost preserved locally by the inflated dynamics (10.8).