# Remarks on input to state stability of perturbed gradient flows,
motivated by model-free feedback control learning

Eduardo D. Sontag
24.08.27:

###### Abstract

Recent work on data-driven control and reinforcement learning has renewed
interest in a relative old field in control theory: model-free optimal control
approaches which work directly with a cost function and do not rely upon
perfect knowledge of a system model. Instead, an “oracle” returns an estimate
of the cost associated to, for example, a proposed linear feedback law to
solve a linear-quadratic regulator problem. This estimate, and an estimate of
the gradient of the cost, might be obtained by performing experiments on the
physical system being controlled. This motivates in turn the analysis of
steepest descent algorithms and their associated gradient differential
equations. This note studies the effect of errors in the estimation of the
gradient, framed in the language of input to state stability, where the input
represents a perturbation from the true gradient. Since one needs to study
systems evolving on proper open subsets of Euclidean space, a self-contained
review of input to state stability definitions and theorems for systems that
evolve on such sets is included. The results are then applied to the study of
noisy gradient systems, as well as the associated steepest descent algorithms.

##  1 Introduction

Suppose that a function $V:\mathbb{X}\rightarrow{\mathbb{R}}$, defined on an
open subset $\mathbb{X}$ of ${\mathbb{R}}^{n}$, has a global minimum at a
point $\bar{x}\in\mathbb{X}$, and that its gradient does not vanish except at
$x=\bar{x}$. Under appropriate technical conditions, the solutions of the
gradient flow $\dot{x}=-\eta\nabla V(x)^{T}$ (where $\eta>0$ is a “learning
rate”) will globally, and even exponentially, converge to $\bar{x}$ as
$t\rightarrow\infty$.

In many data-driven applications, the gradient can be well-estimated
numerically. The combination of direct gradient estimation and gradient
descent has generated strong recent interest in control theory, and
specifically in Reinforcement Learning (RL) model-free control. In order to
theoretically better understand the problem, several authors have studied an
archetypical control problem, the infinite-horizon Linear Quadratic Regulator
(LQR) problem. Since the pioneering work of Kalman in the early 1960s, it has
been known that the solution of the LQR problem can be obtained explicitly via
a Riccati equation, and many computational packages do so very efficiently.
Nonetheless, if the system being controlled is imperfectly known, the function
to be optimized is not known except through “queries” involving sampling and
experimentation, and in that context direct methods might be of interest. In
any event, however, working on a well-understood problem like LQR serves to
understand properties of model-free approaches.

It turns out that when the LQR problem is formulated as an optimization over a
set of stabilizing feedback matrices, the loss function, while not convex,
satisfies strong convergence guarantees [8]. The trick is to employ a
reparametrization for the LQR problem that allows solving an associated
strongly convex problem. We refer the reader to [8] for details. Note that, in
the LQR problem as just described, the open set $\mathbb{X}$ is a set of
matrices. Restricting the optimization dynamics to this open set is essential
for the approach to work.

In this note, we study a perturbed gradient system (superscript $T$ indicates
transpose):

$\dot{x}(t)\;=\;-\eta\,\nabla V(x(t))^{T}\,+\,B(x(t))u(t)\,.$ (1)

The additive term represents disturbances. For example, if $B(x)$ is the
constant matrix with rows $(1,0,\ldots,0)$, $(0,1,\ldots,0)$, …,
$(0,0,\ldots,1)$ then we have independent disturbances $u_{i}$ acting on each
coordinate. Without the additive term, this is a standard gradient descent
flow. For generality, we allow state-dependent perturbations (non-constant
$B$).

The “disturbance” inputs might represent errors when numerically approximating
the gradient from data through two-point estimates as in [8], or due to
measurement noise. The paper [6] interprets the discretization error when
solving ODE’s as a perturbation, and relates asymptotic stability for
dynamical systems to families of approximations, specifically applying this to
numerical one step schemes for ordinary differential equations.

To quantify the effect of disturbances, we will use the notion of input-to-
state stability (ISS), introduced in [27] (see expositions in [29, 28, 16,
11]). We will prove (under technical assumptions on $V$, mainly that $V$ blows
up at the boundary of $\mathbb{X}$, so that trajectories cannot escape the
constraint set; assumptions which hold in the motivating example from [8])
that the disturbed gradient system is ISS. This implies that if the
disturbances or errors are bounded, small, “eventually” small, or convergent,
the solutions of the system will inherit the same properties, with well-
controlled transient behavior.

The natural setting is that of differential equations that evolve in a
nontrivial open subset $\mathbb{X}$ of ${\mathbb{R}}^{n}$. An example is a
gradient system that uses a loss function associated to a feedback matrix $K$
that is required to stabilize a given linear system $\dot{x}=Ax+Bu$, in the
sense that $A-BK$ is a Hurwitz matrix (i.e., it has all its eigenvalues with
negative real parts). We can view matrices of size $p\times q$ as elements of
${\mathbb{R}}^{n}$, $n=pq$. Since eigenvalues depend continuously on matrix
entries (a standard fact, proved for example in the linear algebra appendix in
[28]), the set $\mathbb{X}\subset{\mathbb{R}}^{n}$ of stabilizing matrices
(for a fixed system defined by $A$ and $B$) is open.

The precise statement of the ISS result requires introducing appropriate
notions of stability and “size” of elements in open subsets. We consider such
notions here; that material that we discuss, on ISS on open subsets, should be
of independent interest beyond the study of gradient systems, so we provide
detailed proofs of several facts about them for more general systems with
inputs.

None of the results are surprising; nonetheless, it seems worth codifying the
basic theory with (almost) self-contained proofs. Note that, if
$\bar{x}\in\mathbb{X}$ is a globally asymptotically stable equilibrium, then
the set $\mathbb{X}$ must be diffeomorphic to ${\mathbb{R}}^{n}$ (this fact is
actually used in the proof of the converse ISS-Lyapunov theorem below). So one
could argue that, up to this diffeomorphism, everything in this paper follows
from the already known results for systems in Euclidean space. However, the
diffeomorphism is not _a priori_ known, and in any event, we wish to write
everything in the coordinates natural for the problem being studied.

In addition to studying the gradient system, we study the performance of
steepest descent, the discrete process in which a line search is performed,
iteratively minimizing a cost function in the direction of the gradient. Given
a continuously function $V:\mathbb{X}\rightarrow{\mathbb{R}}$ to be minimized
on an open subset $\mathbb{X}\subseteq{\mathbb{R}}^{n}$, the steepest descent
algorithm consists of the following procedure: given any initial state
$x^{\scriptscriptstyle 0}$, one performs a line search in the negative
gradient direction so as to minimize $V(x^{\scriptscriptstyle 0}-\lambda\nabla
V(x^{\scriptscriptstyle 0})^{T})$ over $\lambda\geq 0$; the minimal point then
defines a new point $x^{1}$, and one then iterates. Observe that this search
only makes sense on a maximal interval such that the line segment
$\\{x^{\scriptscriptstyle 0}-\mu\nabla V(x^{\scriptscriptstyle
0})^{T},\mu\in[0,\lambda]\\}$ is included in $\mathbb{X}$ (so that one may
evaluate $V$ for increasing $\lambda$). when the gradient is imperfectly
evaluated, the picture is further complicated by the fact that one in fact
moves in a direction $x^{\scriptscriptstyle 0}-\lambda[\nabla
V(x^{\scriptscriptstyle 0})^{T})+B(x)u]$, for some unknown additive “noise”
input vector $u$ (we include $B(x)$ to allow a state-dependence of the input).
This gives an iteration that we write as $x^{+}=x-\lambda\left[\nabla
V(x)^{T}+B(x)u\right]$.

It is in principle possible that even for a very small step one cannot
diminish the cost at all, and moreover one might even exit the set $X$
altogether for an input of large magnitude. A trivial example of this is
provided by $\mathbb{X}=(-1,1)$, $B(x)=1$, and $V(x)=x^{2}/2$. The perturbed
steepest descent procedure attempts to move to $x-\lambda(x+u)$. If we take
any $x>0$ and any $u<-x$ then for any step size $\lambda>0$ the cost
increases, which means that the steepest descent procedure will be “stuck” at
$x$. Moreover, for large $\lambda$ the expression $x-\lambda(x+u)$ gives a
result outside $\mathbb{X}$. Of course, this can be fixed if the magnitude of
the input $u$ is “not too large” compared to the state $x$. Indeed, we will
show that, under reasonable technical assumptions, the steepest descent
procedure is input to state stable as a discrete-time system with respect to
disturbances.

##  2 Size functions on open subsets

We start by introducing a notion of “size” that is well-suited to quantifying
global convergence to a given equilibrium, and which in particular acts as a
barrier function preventing escape from $\mathbb{X}$.

###### Definition 2.1

Let $\mathbb{X}$ be an open subset of ${\mathbb{R}}^{n}$ and let
$\bar{x}\in\mathbb{X}$. We will say that

$\omega:\mathbb{X}\rightarrow{\mathbb{R}}$

is a _size function for_ $(\mathbb{X},\bar{x})$ if $\omega$ is:

  1. 1.

continuous,

  2. 2.

positive definite with respect to $\bar{x}$, that is, $\omega(\bar{x})=0$ and
$\omega(x)>0$ for all $x\in\mathbb{X}$, $x\not=\bar{x}$, and

  3. 3.

proper, that is, for every real number $r\geq 0$, the sublevel set
$S_{r}:=\\{x\,|\,\omega(x)\leq r\\}$ is a compact subset of $\mathbb{X}$.

###### Remark 2.2

Observe that, since $\mathbb{X}$ is an open set, asking that $S_{r}$ is
compact in the induced topology of $\mathbb{X}$ is equivalent to asking that
$S_{r}$ is compact as a subset of ${\mathbb{R}}^{n}$. $\Box$

###### Remark 2.3

Let us denote by $\left|x\right|$ the standard Euclidean norm in
${\mathbb{R}}^{n}$ (any other norm could be used as well). When
$\mathbb{X}={\mathbb{R}}^{n}$, a natural choice of size is
$\omega(x)=\left|x-\bar{x}\right|$. The notion that we introduce here is based
on the beautiful paper of Kurzweil [17], which studied Lyapunov stability
theory on open sets, and is a particular case of “measures” in the sense of
Lakshmikantham and coauthors (see e.g. [18]). In [33, 23], the concept is
called a “proper indicator function” (but we prefer not to use that term,
since “indicator function” is typically used for the characteristic function
of a set). We remark that one could equally well define a size with respect to
any closed subset ${\cal A}$ of $\mathbb{X}$, simply asking that $\omega(x)=0$
if and only if $x\in{\cal A}$, which is useful when studying convergence of
solutions of differential equations to non-point attractors. Another point
worth mentioning is that the definition of size function and many of the
results can equally well be formulated on a general differentiable manifold
$\mathbb{X}$; in a Riemannian manifold, one can take $\left|x\right|$ as the
geodesic distance to $\bar{x}$, and all the functions of the form
$\omega(x)=\alpha(\left|x\right|)$ are size functions, when $\alpha$ is a
function of class ${\mathcal{K}_{\infty}}$ (defined below). In that sense, the
setup in this note is closely related to the work in [1], in which a variant
of ISS for systems evolving in manifolds was considered. In that paper, the
authors gave a definition that relaxes the stability requirement for the
unforced system; in this note, instead, we study a notion which reduces to the
usual one for systems in ${\mathbb{R}}^{n}$. $\Box$

The following elementary exercise in real analysis provides an intuitive
characterization of size functions. We denote by $\partial\mathbb{X}$ the
boundary of the set $\mathbb{X}$ (which is empty if and only if
$\mathbb{X}={\mathbb{R}}^{n}$).

###### Lemma 2.4

The following two statements are equivalent for any function
$\omega:\mathbb{X}\rightarrow{\mathbb{R}}$:

  * (a)

$\omega$ is a size function for $(\mathbb{X},\bar{x})$

  * (b)

$\omega$ is continuous, positive definite with respect to $\bar{x}$, and for
every sequence $\\{x_{k}\in\mathbb{X},k\geq 1\\}$,

if either $x_{k}\rightarrow\partial\mathbb{X}$ or
$\left|x\right|\rightarrow\infty$, necessarily
$\omega(x_{k})\rightarrow\infty$. (2)

Proof. We must show that property (2) is equivalent to compactness of every
sublevel set $S_{r}$.

Suppose that property (2) is true, and pick any $r\geq 0$. By Remark 2.2, we
need to prove that $S_{r}$ is closed and bounded as a subset of
${\mathbb{R}}^{n}$.

We first prove that $S_{r}$ is closed. Suppose that a sequence $\\{x_{k}\\}$
in $S_{r}$ is such that $x_{k}\rightarrow x\in{\mathbb{R}}^{n}$ as
$k\rightarrow\infty$. We must show that $x\in S_{r}$. There are two cases to
consider: $x\not\in\mathbb{X}$ and $x\in\mathbb{X}$. In the first case, being
the limit of elements in $\mathbb{X}$, necessarily $x\in\partial\mathbb{X}$.
Thus $x_{k}\rightarrow\partial\mathbb{X}$ and, by the assumed property,
$\omega(x_{k})\rightarrow\infty$, contradicting the fact that the sequence
$\\{\omega(x_{k})\\}$ is bounded (by $r$), So this case cannot hold. Thus
$x\in\mathbb{X}$, so that $x\in S_{r}$ because $S_{r}$ is closed in the
relative topology of $\mathbb{X}$. (More explicitly: by continuity of
$\omega$, we have that $\omega(x_{k})\rightarrow\omega(x)$, and hence
$\omega(x)\leq r$, so $x\in S_{r}$.).

Next we prove that $S_{r}$ is bounded. Suppose by way of contradiction that
there is a sequence $\\{x_{k}\\}$ in $S_{r}$ is such that
$\left|x_{k}\right|\rightarrow\infty$ as $k\rightarrow\infty$. Again using the
assumed property, it follows that $\omega(x_{k})\rightarrow\infty$,
contradicting that all $\omega(x_{k})\leq r$. Thus $S_{r}$ is bounded.

Conversely, suppose that $S_{r}$ is compact for every $r\geq 0$ and consider a
sequence $\\{x_{k}\in\mathbb{X},k\geq 1\\}$. Suppose first that
$\left|x_{k}\right|\rightarrow\infty$. We need to prove that, for every $r>0$,
there is an integer $K$ so that $k>K\Rightarrow w(x_{k})>r$. Suppose that this
is not true, i.e., there is some $r$ and a subsequence
$k_{j}\rightarrow\infty$ so that $x_{k_{j}}\in S_{r}$ for all $k_{j}$.
Replacing $\\{x_{k}\\}$ by this subsequence, we can then assume that $x_{k}\in
S_{r}$ for all $k$, and still $\left|x_{k}\right|\rightarrow\infty$. Since
$S_{r}$ is compact, there is a convergent subsequence with its limit $x\in
S_{r}$. This contradicts that $\left|x_{k}\right|\rightarrow\infty$.
Similarly, suppose that $x_{k}\rightarrow\partial\mathbb{X}$. By
contradiction, assume again that there is some $r$ and a subsequence
$k_{j}\rightarrow\infty$ so that $x_{k_{j}}\in S_{r}$ for all $k_{j}$.
Replacing ${x_{k}}$ by the subsequence, we can then assume that $x_{k}\in
S_{r}$ for all $k$, and still $x_{k}\rightarrow\partial\mathbb{X}$. By
compactness, we can assume, taking a subsequence, that $x_{k}\rightarrow x\in
S_{r}\subseteq\mathbb{X}$ for some $x$. However, since
$x_{k}\rightarrow\partial\mathbb{X}$ (because we have subsequences of a
sequence converging to the boundary), this implies that
$x\in\partial\mathbb{X}$. We have a contradiction, because $\mathbb{X}$ and
$\partial\mathbb{X}$ are disjoint subsets of ${\mathbb{R}}^{n}$. This
completes the proof.

Given any open set $\mathbb{X}\subseteq{\mathbb{R}}^{n}$ and any
$\bar{x}\in\mathbb{X}$, there are many possible size functions for
$(\mathbb{X},\bar{x})$. As we remarked earlier, $\left|x-\bar{x}\right|$ works
when $\mathbb{X}={\mathbb{R}}^{n}$. In general, we may use, for example:

$\omega(x)\;=\;\max\left\\{\left|x-\bar{x}\right|\,,\,\frac{1}{{\rm
dist}(x,\partial\mathbb{X})}-\frac{a}{{\rm
dist}(\bar{x},\partial\mathbb{X})}\right\\}$

for any $a\geq 1$. The case $a=2$ of this formula was given in [17], and with
that choice one has that $\omega(x)=\left|x-\bar{x}\right|$ for all $x$ near
$\bar{x}$.

###  2.1 Comparing size functions

In the same manner that any two norms on a finite dimensional space are
equivalent, there is a notion of equivalence of size functions.

We denote by ${\mathbb{R}}_{\geq 0}$ the set of nonnegative real numbers.

Recall that ${\cal K}$ is the set of functions $\alpha:{\mathbb{R}}_{\geq
0}\rightarrow{\mathbb{R}}_{\geq 0}$ that are continuous, strictly increasing,
and satisfy $\alpha(0)=0$, and ${\cal K}_{\infty}\subset{\cal K}$ is the
subset of unbounded functions, that is, $\alpha(r)\rightarrow\infty$ as
$r\rightarrow\infty$. The set ${\cal K}$ is closed under sums, products, and
compositions, as is the set ${\cal K}_{\infty}$. Moreover, functions in ${\cal
K}$ are invertible, and $\alpha^{-1}\in{\cal K}_{\infty}$, so ${\cal
K}_{\infty}$ is a group under composition (with identity element the map
$\alpha(r)=r$). If $\alpha\in{\cal K}$, one also says that “$\alpha$ is of
class ${\cal K}$” and similarly for ${\cal K}_{\infty}$. These classes of
functions have played a central role in dynamical systems since at least the
textbook by Hahn [7], and were key in the development of input to state
stability notions in [27]. They have many other useful properties, for example
the weak subadditivity property $\alpha(r+s)\leq\alpha(2r)+\alpha(2s)$; see
for instance [28, 29]. They allow us to relate size functions. Observe that if
$\omega$ is a size function and $\alpha\in{\mathcal{K}_{\infty}}$, then
$\alpha\circ\omega$ is also a size function.

###### Lemma 2.5

Suppose that $\omega$ is a size function for $(\mathbb{X},\bar{x})$. Then for
each $\varepsilon>0$ there is a $\delta>0$ such that

$\omega(x)<\delta\;\Rightarrow\;\left|x-\bar{x}\right|<\varepsilon\,.$

Proof. Since $\omega$ is continuous and $\omega(\bar{x})=0$, there exists
$\varepsilon_{0}>0$ such that
$\left|x-\bar{x}\right|<\varepsilon_{0}\Rightarrow\omega(x)<1$ (and the ball
of radius $\varepsilon_{0}$ around $\bar{x}$ is included in $\mathbb{X}$). It
follows that for any $x\in\mathbb{X}$ with
$\left|x-\bar{x}\right|\leq\varepsilon_{0}$, $\omega(x)\leq 1$. Now pick any
$\varepsilon>0$. We let
$\bar{\varepsilon}:=\min\\{\varepsilon,\varepsilon_{0}\\}$. Consider the set

$C\,:=\;\\{x\,|\,\left|x-\bar{x}\right|\geq\bar{\varepsilon}\mbox{ and
}\omega(x)\leq 1\\}\,.$

The set is nonempty: pick any $x\in\mathbb{X}$ with
$\left|x-\bar{x}\right|=\varepsilon_{0}$; then $\omega(x)\leq 1$ and also
$\left|x-\bar{x}\right|=\varepsilon_{0}\geq\bar{\varepsilon}$. The set $C$ is
compact, because it is the intersection of a closed set and a compact set.
Also, $w(x)$ is nonzero in this set, because $w$ is positive definite.
Therefore there is a positive minimum of $w$ on the set $C$; we pick $\delta$
as this minimum, and thus $x\in C\Rightarrow\omega(x)\geq\delta$. Without loss
of generality, we will assume $\delta<1$ (otherwise, make $\delta$ smaller).
Now assume that $\omega(x)<\delta$. This means that $x$ is not in $C$, so
either $\omega(x)>1$ or $\left|\bar{x}\right|<\bar{\varepsilon}$. However,
$w(x)>1$ cannot happen, because $\omega(x)<\delta<1$. Therefore,
$\left|x-\bar{x}\right|<\bar{\varepsilon}\leq\varepsilon$, as wanted.

###### Proposition 2.6

Suppose that $\omega_{1}$ and $\omega_{2}$ are two size functions for
$(\mathbb{X},\bar{x})$. Then, there is some $\alpha\in{\cal K}_{\infty}$ such
that

$\omega_{1}(x)\,\leq\,\alpha(w_{2}(x))\mbox{ for all }x\in\mathbb{X}\,.$ (3)

Proof. Define

$\widetilde{\alpha}(r)\,:=\;\max_{\\{x\,|\,\omega_{2}(x)\leq
r\\}}\omega_{1}(x)\,.$

Since the set $\\{x\,|\,\omega_{2}(x)\leq r\\}$ is compact, this maximum is
well-defined. Note that the inequality (3) holds. Indeed, given any
$x\in\mathbb{X}$, let $r:=\omega_{2}(x)$; then
$\omega_{1}(x)\leq\widetilde{\alpha}(r)=\widetilde{\alpha}(\omega_{2}(x))$,
because $x$ belongs to the set over which we are maximizing. Moreover,
$\widetilde{\alpha}$ is nondecreasing (since as $r$ is larger, one takes a
maximum over a larger set). Also, $\widetilde{\alpha}(0)=0$ by positive
definiteness of $\omega_{1}$ and $\omega_{2}$. We prove next that
$\widetilde{\alpha}$ is continuous at $0$.

Fix any $\varepsilon>0$. We want to find a $\delta>0$ so that
$r<\delta\Rightarrow\widetilde{\alpha}(r)<\varepsilon$. From the definition of
$\widetilde{\alpha}$, it is enough to find a $\delta$ such that, for each
$r<\delta$:

$\omega_{2}(x)\leq r\;\Rightarrow\;\omega_{1}(x)<\varepsilon/2\,.$

Since $\omega_{1}$ is continuous and $\omega_{1}(\bar{x})=0$, there is a
$\delta_{1}>0$ such that

$\left|x-\bar{x}\right|<\delta_{1}\;\Rightarrow\;\omega_{1}(x)<\varepsilon/2\,.$

By Lemma 2.5 applied to $\omega_{2}$ and $\varepsilon=\delta_{1}$, there is a
$\delta>0$ such that

$\omega_{2}(x)<\delta\;\Rightarrow\;\left|x-\bar{x}\right|<\delta_{1}\,.$

We conclude that:

$\omega_{2}(x)<\delta\;\Rightarrow\;\omega_{1}(x)<\varepsilon/2.$

Now assume $r<\delta$. For any $x$ such that $\omega_{2}(x)\leq r$ , also
$\omega_{2}(x)<\delta$, and hence $\omega_{1}(x)<\varepsilon$, as wanted.

So far we have a nondecreasing $\widetilde{\alpha}:{\mathbb{R}}_{\geq
0}\rightarrow{\mathbb{R}}_{\geq 0}$ which satisfies $\widetilde{\alpha}(0)=0$.
Such a function can be majorized by a class ${\cal K}_{\infty}$ function
$\alpha$, i.e. $\widetilde{\alpha}(r)\leq\alpha(r)$ for all $r$, which
together with $\omega_{1}(x)\leq\widetilde{\alpha}(\omega_{2}(x))$ implies the
estimate (3). The construction of $\alpha$ is a standard exercise. First
majorize $\widetilde{\alpha}$ by a nondecreasing continuous function. For
example, pick a doubly infinite sequence of nonnegative numbers $r_{k}$,
$k\in{\mathbb{Z}}$ so that $r_{k}\rightarrow 0$ as $k\rightarrow-\infty$ and
$r_{k}\rightarrow\infty$ as $k\rightarrow+\infty$ and let $\alpha$ interpolate
linearly the values $(r_{k},\widetilde{\alpha}(r_{k+1}))$ (recall that
$\widetilde{\alpha}$ is nondecreasing, so that the interpolation function is
nondecreasing, and it clearly majorizes $\widetilde{\alpha}$). This gives an
$\alpha\in{\cal K}$. Finally, add any ${\cal K}_{\infty}$ function to obtain
an $\alpha$ of class ${\cal K}_{\infty}$.

###### Corollary 2.7

Suppose that $\omega_{1}$ is a size function for $(\mathbb{X},\bar{x})$. Let
$\omega_{2}:\mathbb{X}\rightarrow{\mathbb{R}}^{n}$ be a continuous function.
Then the following properties are equivalent:

  * (a)

$\omega_{2}$ is a size function for $(\mathbb{X},\bar{x})$;

  * (b)

there exist functions $\alpha_{1},\alpha_{2}\in{\mathcal{K}_{\infty}}$ such
that

$\alpha_{1}(\omega_{1}(x))\,\leq\,\omega_{2}(x)\,\leq\,\alpha_{2}(w_{1}(x))\;\;\mbox{
for all }x\in\mathbb{X}\,.$ (4)

Proof. Suppose that $\omega_{2}$ is a size function for
$(\mathbb{X},\bar{x})$. By Proposition 2.6, there is an
$\alpha\in{\mathcal{K}_{\infty}}$ such that
$\omega_{1}(x)\leq\alpha(w_{2}(x))$ for all $x$. Thus
$\alpha_{1}(\omega_{1}(x))\leq w_{2}(x)$ where $\alpha_{1}=\alpha^{-1}$.
Applying again Proposition 2.6, but interchanging the $\omega_{i}$’s, we have
an $\alpha_{2}\in{\mathcal{K}_{\infty}}$ such that
$\omega_{2}(x)\leq\alpha_{2}(w_{1}(x))$ for all $x$, so (4) holds.

Conversely, suppose that (4) holds. Since
$\omega_{2}(x)\geq\alpha_{1}(\omega_{1}(x))$ and $\alpha_{1}(\omega(x))>0$ for
$x\not=\bar{x}$, it follows that $\omega_{2}(x)>0$ for $x\not=\bar{x}$. On the
other hand, $\omega_{2}(\bar{x})\leq\alpha_{2}(w_{1}(\bar{x}))=0$, so
$\omega_{2}$ is positive definite with respect to $\bar{x}$. It remains to
show that $\omega_{2}$ is proper. Pick any $r\geq 0$ and consider $S_{r}$.
This set is closed because $\omega_{2}$ is continuous. On the other hand, it
is bounded because
$S_{r}\subseteq\\{x\,|\,\omega_{1}(x)\leq\alpha_{1}^{-1}(r)\\}$ and the latter
set is compact because $\omega_{1}$ is proper.

##  3 Systems with inputs

From now on, assume given an open subset
$\mathbb{X}\subseteq{\mathbb{R}}^{n}$, a point $\bar{x}\in\mathbb{X}$, and a
size function $\omega$ for $(\mathbb{X},\bar{x})$. We consider here systems
with $n$ state variables and $m$-dimensional inputs in the usual sense of
control theory [28]:

$\dot{x}(t)\;=\;f(x(t),u(t))$

(the argument “$t$” is often omitted, and dot indicates derivative with
respect to time). The map

$f:\mathbb{X}\times{\mathbb{R}}^{m}\rightarrow{\mathbb{R}}^{n}$

is assumed to be locally Lipschitz and $\bar{x}$ is an equilibrium when the
input is zero:

$f(\bar{x},0)=0\,.$

States $x(t)$ take values in $\mathbb{X}$, and inputs (also called “controls”
or “disturbances” depending on the context) are Lebesgue measurable
essentially bounded maps

$u\,:\;[0,\infty)\rightarrow{\mathbb{R}}^{m}\,.$

We consider the sup norm of inputs:

$\left\|u\right\|_{\infty}\,:=\;\mbox{ess}\sup_{t\geq 0}\left|u(t)\right|$

where $\left|u\right|$ is the Euclidean norm in ${\mathbb{R}}^{m}$ and “ess
sup” denotes essential supremum.

For each initial state $x^{\scriptscriptstyle 0}$ and each input $u$, the
solution of the initial value problem with initial state
$x(0)=x^{\scriptscriptstyle 0}$ and input $u$ is denoted as

$x(t,x^{\scriptscriptstyle 0},u)\;\in\;\mathbb{X}$

and is defined on some maximal interval

$[0,t_{\max}(x^{\scriptscriptstyle 0},u))\,.$

###### Remark 3.1

For the sake of maximum generality, we allow inputs to be arbitrary (bounded)
measurable functions. A technical issue is that measurable functions are in
reality equivalence classes of functions, equal only up to measure zero
subsets. Solutions of the differential equation are absolutely continuous
functions and estimates over time have to be qualified by the phrase “for
almost all $t$”. We omit this qualification to make reading easier. In any
event, for continuous inputs (which suffice for most applications) solutions
are continuously differentiable and there is no need for the qualifier. $\Box$

###  3.1 Input to state stability

The notion of input-to-state stability (ISS), introduced in [27] (see
expositions in [29, 28, 16, 11]) provides a framework to describe stability
features of the mapping $(x(0),u(\cdot))\mapsto x(\cdot)$ that sends initial
states and input functions into solution trajectories. Prominent among these
features are that inputs that are bounded, small, “eventually” small, or
convergent, should lead to states with the respective property. In addition,
ISS quantifies how initial states affect transient behavior.

The formal definition that we introduce, extended to open subsets, is as
follows. Recall that a function
$\beta:[0,\infty)\times[0,\infty)\rightarrow[0,\infty)$ is said to be of class
${\mathcal{K}}{\mathcal{L}}$ if (1) for each fixed $t$, $\beta(s,t)$ as a
function of $r$ is in class ${\mathcal{K}}$ and (2) for each fixed $r$,
$\beta(r,t)$ decreases to zero as $t\rightarrow\infty$.

###### Definition 3.2

A system is _input to state stable (ISS)_ (on the open set $\mathbb{X}$ and
with respect to $\bar{x}$) if, there exist functions
$\beta\in{\mathcal{K}}{\mathcal{L}}$ and $\gamma\in{\mathcal{K}_{\infty}}$ so
that the following property holds: for all inputs $u(\cdot)$ and all initial
conditions $x^{\scriptscriptstyle 0}\in\mathbb{X}$, the solution is defined
for all $t\geq 0$, that is, $t_{\max}(x^{\scriptscriptstyle 0},u)=+\infty$,
and it satisfies the estimate:

$\quad\quad\quad\omega(x(t,x^{\scriptscriptstyle
0},u))\;\leq\;\beta(\omega(x^{\scriptscriptstyle
0}),t)\,+\,\gamma\left(\left\|u\right\|_{\infty}\right)$ $None$

for all $t\geq 0$.

Note that this definition is independent of the particular size function used
(although with $\beta$ and $\kappa$ functions that may change with $\omega$)
because of Proposition 2.6. When $\mathbb{X}={\mathbb{R}}^{n}$, since
$\left|x\right|$ is a size function, this becomes the usual definition of ISS.

Since, in general, $\max\\{a,b\\}\leq a+b\leq\max\\{2a,2b\\}$, one could
restate the ISS condition in a slightly different manner, namely, asking for
the existence of some $\beta\in{\mathcal{K}}{\mathcal{L}}$ and
$\gamma\in{\mathcal{K}_{\infty}}$ (in general different from the ones in the
ISS definition) such that

$\omega(x(t,x^{\scriptscriptstyle
0},u))\;\leq\;\max\left\\{\beta(\omega(x^{\scriptscriptstyle
0}),t)\,,\,\gamma\left(\left\|u\right\|_{\infty}\right)\right\\}$

holds for all solutions.

Intuitively, the definition of ISS requires that, for $t$ large, the size of
the state must be bounded by some function of the sup norm, that is to say,
the maximum amplitude, of inputs, since $\beta(\omega(x^{\scriptscriptstyle
0}),t)\rightarrow 0$ as $t\rightarrow\infty$. On the other hand, the term
$\beta(\omega(x^{\scriptscriptstyle 0}),0)$ may dominate for small $t$, and
this serves to quantify the magnitude of the transient (overshoot) behavior as
a function of the size of the initial state $x^{\scriptscriptstyle 0}$, see
Figure 1.

$\approx\omega(x^{\scriptscriptstyle
0})$$t$$x$$\approx\left\|u\right\|_{\infty}$ Figure 1: ISS combines overshoot
and asymptotic behavior

For stable ($A$ having all eigenvalues with negative real part) linear systems
$\dot{x}=Ax+Bu$ evolving on $\mathbb{X}={\mathbb{R}}^{n}$, the variation of
parameters formula gives immediately the following inequality:

$\left|x(t)\right|\;\leq\;\beta(t)\left|x^{\scriptscriptstyle
0}\right|\,+\,\gamma\left\|u\right\|_{\infty}\,,$

where

$\beta(t)=\left\|e^{tA}\right\|\;\rightarrow\;0\quad\text{and}\quad\gamma=\left\|B\right\|\int_{0}^{\infty}\left\|e^{sA}\right\|ds\;<\;\infty$

(here $\left\|\cdot\right\|$ is induced operator norm). This is a particular
case of the ISS estimate, $\left|x(t)\right|\leq\beta(|{x^{\scriptscriptstyle
0}}|,t)+\gamma\left(\left\|u\right\|_{\infty}\right)$, with linear comparison
functions. Note that $\beta(t)\leq Ce^{-\lambda t}$ for some $C>0$ and some
$\lambda>0$, so one has exponential convergence when $u\equiv 0$.

###### Remark 3.3

We could think of a particular size function $\omega$ as an _output_ function
or “observable” $y=\omega(x)$ of the system $\dot{x}=f(x,u)$. With this
interpretation, the definition is almost identical with that of “state-
independent input to output stability” (SIIOS) given in [31]. The paper [31]
presents a large number of results relating SIIOS to several other stability
notions with respect to outputs. However, the interest in that paper is on
_non-proper_ $\omega$, and $\mathbb{X}={\mathbb{R}}^{n}$, since for proper
functions and $\mathbb{X}={\mathbb{R}}^{n}$, SIIOS would simply coincide with
ISS. $\Box$

###  3.2 ISS-Lyapunov functions

We now define ISS-Lyapunov functions on open sets. We assume given a system
$\dot{x}=f(x,u)$ as above.

###### Definition 3.4

A continuously differentiable $V:\mathbb{X}\rightarrow{\mathbb{R}}$ is said to
be an _ISS-Lyapunov function_ for $\dot{x}=f(x,u)$ if

  * (a)

$V-V(\bar{x})$ is a size function for $(\mathbb{X},\bar{x})$, and

  * (b)

there exist functions $\alpha,\gamma\in{\mathcal{K}_{\infty}}$ such that

$\dot{V}(x,u)\;\leq\;-\alpha(\omega(x))\,+\,\gamma(\left|u\right|)\quad\forall\,(x,u)\in\mathbb{X}\times{\mathbb{R}}^{m}$
$None$

where $\dot{V}:\mathbb{X}\times{\mathbb{R}}^{m}\rightarrow{\mathbb{R}}$ is the
function:

$\dot{V}(x,u):=\nabla V(x).f(x,u)\,.$

The interpretation of $\dot{V}$ is given by the fact that, for any solution
$x(t)$ of $\dot{x}=f(x,u)$, the derivative $dV(x(t))/dt$ is
$\dot{V}(x(t),u(t))$.

###### Remark 3.5

Property (a) in the definition of ISS-Lyapunov function is equivalent to the
existence of two functions $\alpha_{i}\in{\mathcal{K}_{\infty}}$, $i=1,2$ such
that

$\alpha_{1}(\omega(x))\,\leq\,V(x)-V(\bar{x})\,\leq\,\alpha_{2}(\omega(x))\quad\forall\,x\in\mathbb{X}\,.$
(5)

This is an immediate application of Corollary 2.7. Regarding property (b),
redefining $\alpha:=\alpha\circ\alpha_{2}^{-1}\in{\mathcal{K}_{\infty}}$, one
also has an estimate in which, instead of condition (L-ISS), one has the
differential inequality:

$\dot{V}(x,u)\;\leq\;-\alpha(V(x))-V(\bar{x}))\,+\,\gamma(\left|u\right|)\quad\forall\,(x,u)\in\mathbb{X}\times{\mathbb{R}}^{m}\,.$
$None$

Conversely, suppose that (a) and (L-ISS’) hold. Let $\alpha_{1}$ be as in (5).
Then $\widetilde{\alpha}(\omega(x))\leq\alpha(V(x))-V(\bar{x}))$, where
$\widetilde{\alpha}:=\alpha\circ\alpha_{1}$. This $\widetilde{\alpha}$ gives
an estimate of the form (L-ISS). $\Box$

###### Theorem 1

A system is ISS if and only if it admits an ISS-Lyapunov function.

The sufficiency of the ISS-Lyapunov condition is easy to show, and is entirely
analogous to the proof for $\mathbb{X}={\mathbb{R}}^{n}$ in the original paper
[27]. We sketch the details here, starting from an estimate L-ISS’. Pick any
solution $x(t,x^{\scriptscriptstyle 0},u)$, and define

$v(t)\,:=\;V(x(t,x^{\scriptscriptstyle 0},u)))-V(\bar{x})\,.$

Note that
$\dot{v}(t)=\dot{V}(x(t),u(t))\leq-\alpha(v(t))+\gamma(\left|u(t)\right|)$.
For any $t$, either $\alpha(v(t))\leq 2\gamma(\left|u(t)\right|)$ or
$\dot{v}(t)\leq-\alpha(v(t))/2$. From here, one deduces by a comparison
theorem that

$v(t)\;\leq\;\max\left\\{\beta(v(0),t)\,,\,\alpha^{-1}(2\gamma(\left\|u\right\|_{\infty}))\right\\}\quad\forall\,t\in[0,t_{\max}(x^{\scriptscriptstyle
0},u))\,,$

where the ${\mathcal{K}}{\mathcal{L}}$ function $\beta(s,t)$ is the solution
$y(t)$ of the initial value problem

$\dot{y}=-\frac{1}{2}\alpha(y)\,,\quad y(0)=s\,.$

Using that $v(0)=V(x^{\scriptscriptstyle
0})-V(\bar{x})\leq\alpha_{2}(\omega(x^{\scriptscriptstyle 0}))$ and
$\omega(x(t,x^{\scriptscriptstyle
0},u))\leq\alpha_{1}^{-1}(V(x(t,x^{\scriptscriptstyle
0},u))-V(\bar{x}))=\alpha_{1}^{-1}(v(t))$, we have

$\displaystyle\omega(x(t,x^{\scriptscriptstyle 0},u))$ $\displaystyle\leq$
$\displaystyle\max\left\\{\alpha_{1}^{-1}(\beta(\alpha_{2}(\omega(x^{\scriptscriptstyle
0})),t))\,,\,\alpha_{1}^{-1}(\alpha^{-1}(2\gamma(\left\|u\right\|_{\infty})))\right\\}$
$\displaystyle\leq$
$\displaystyle\max\left\\{\widetilde{\beta}(\omega(x^{\scriptscriptstyle
0}),t)\,,\,\widetilde{\gamma}(\left\|u\right\|_{\infty})\right\\}\quad\forall\,t\in[0,t_{\max}(x^{\scriptscriptstyle
0},u))\,,$

with $~{}\beta\in{\mathcal{K}}{\mathcal{L}}$ and
$\widetilde{\gamma}\in{\mathcal{K}_{\infty}}$. It only remains to prove that
$t_{\max}(x^{\scriptscriptstyle 0},u)=+\infty$. To see this, note that, for
any solution $x(t,x^{\scriptscriptstyle 0},u)$, we have the bound

$\omega(x(t,x^{\scriptscriptstyle
0},u))\;\leq\;r:=\max\left\\{\widetilde{\beta}(\omega(x^{\scriptscriptstyle
0}),0)\,,\,\widetilde{\gamma}(\left\|u\right\|_{\infty})\right\\}\,.$

Therefore, $x(t,x^{\scriptscriptstyle 0},u)\in S_{r}$ for all $t$ on the
maximal interval of definition of the solution. The set $S_{r}$ is compact
(properness of size functions), so the solution is defined for all $t\geq 0$
(see for example the ODE appendix in [28]).

The converse part of the theorem follows by a reduction to the case
$\mathbb{X}={\mathbb{R}}^{n}$, proved in [20, 30], which is basically a
theorem about Lyapunov functions for differential inclusions. Indeed, if a
system is ISS, then the system with zero inputs $\dot{x}=f(x,0)$ has
$x=\bar{x}$ as an asymptotically stable point with domain of attraction all of
$\mathbb{X}$ (this follows from the estimate
$\omega(x)\leq\beta(\omega(0),t)$). This implies that $\mathbb{X}$ is
diffeomorphic to ${\mathbb{R}}^{n}$, see Theorem 2.2 in [35], who obtains this
as a simple corollary of the Brown-Stallings Theorem. (A proof of a simpler
fact, that $\mathbb{X}$ must be contractible, is very easy; see for example
theorem 21 in [28].) This means that under a diffeomorphism, we can apply the
result for $\mathbb{X}={\mathbb{R}}^{n}$, and when transforming back, we
obtain an L-ISS Lyapunov function.

##  4 Application to gradient systems

We assume given a pair $(\mathbb{X},\bar{x})$ and a size function $\omega$ for
$(\mathbb{X},\bar{x})$. We write the gradient of a function
$V:\mathbb{X}\rightarrow{\mathbb{R}}$ as a row (co)vector $\nabla V$, and its
Euclidean norm as $\left|\nabla V\right|$. When $\nabla V$ is locally
Lipschitz, the gradient flow has unique solutions and if $\nabla V$ is
globally Lipschitz, these solutions are automatically defined for all $t\geq
0$. (In the notations of Nesterov’s book [22], the set of functions $V$ for
which $\nabla V$ has a uniform Lipschitz constant $L$ is denoted
$C_{L}^{1,1}(\mathbb{X})$. In our setup, solutions are defined for all $t\geq
0$ even of $\nabla V$ is not assumed to be globally Lipschitz.)

###  4.1 Proper loss functions

###### Definition 4.1

A continuously differentiable $V:\mathbb{X}\rightarrow{\mathbb{R}}$, with
(locally) Lipschitz continuous gradient $\nabla V$, will be said to be a
_proper loss function_ if

  * (a)

$V-V(\bar{x})$ is a size function for $(\mathbb{X},\bar{x})$, and

  * (b)

$\left|\nabla V\right|$ is a size function for $(\mathbb{X},\bar{x})$. $\Box$

###### Lemma 4.2

Suppose given $V:\mathbb{X}\rightarrow{\mathbb{R}}$ continuously
differentiable, with Lipschitz continuous gradient $\nabla V$, such that
$V-V(\bar{x})$ is a size function for $(\mathbb{X},\bar{x})$. Then these two
properties are equivalent:

  * •

$V$ is a proper loss function,

  * •

for some $\alpha\in{\mathcal{K}_{\infty}}$,

$\alpha(\omega(x))\;\leq\;\left|\nabla V(x)\right|\qquad\mbox{for all
}x\in\mathbb{X}\,.$

Proof. Suppose that $V$ is a proper loss function. Since $\left|\nabla
V\right|$ is a size function for $(\mathbb{X},\bar{x})$, there is an
$\alpha\in{\mathcal{K}_{\infty}}$ as claimed, by Corollary 2.7 (take
$\alpha=\alpha_{1}$). Conversely, suppose that
$\alpha(\omega(x))\leq\left|\nabla V(x)\right|$ with
$\alpha\in{\mathcal{K}_{\infty}}$. Then $\nabla V(\bar{x})=0$, because $V$ has
a (local and even global) minimum at $\bar{x}$. For $x\not=\bar{x}$,
$0<\alpha(\omega(x))\leq\left|\nabla V(x)\right|$, so $\left|\nabla
V(x)\right|$ is positive definite. For any $r\geq 0$, the set
$\\{x\,|\,\left|\nabla V(x)\right|\leq r\\}$ is included in
$S_{\alpha^{-1}(r)}$, so this set is bounded, and it is closed because $\nabla
V$ is continuous. Thus $\nabla V$ is proper, and so it is a size function.

Applied with $\omega=V-V(\bar{x})$, Lemma 4.2 together with the definition of
size function says that an equivalent way to define a proper loss function is
to ask:

  * •

$V$ is continuously differentiable, with Lipschitz continuous gradient;

  * •

$V$ has a strict global minimum at $x=\bar{x}$;

  * •

$V$ is proper; and

  * •

there is some $\alpha\in{\mathcal{K}_{\infty}}$ such that

$\alpha(V(x)-V(\bar{x}))\;\leq\;\left|\nabla V(x)\right|^{2}\qquad\mbox{for
all }x\in\mathbb{X}\,.$ (6)

We wrote $\left|\nabla V(x)\right|^{2}$ instead of $\left|\nabla V(x)\right|$
for convenience in what follows; it makes no difference, since
$(\alpha(\cdot))^{2}$ is a ${\mathcal{K}_{\infty}}$ function if and only if
$\alpha$ is.

In many problems one can directly obtain an estimate as in (6), and this is
useful for obtaining explicit ISS stability rates.

###  4.2 Gradient flow is ISS

Fix a proper loss function $V$, a constant $\eta>0$ (the “learning rate”), and
a locally Lipschitz and bounded mapping
$B:\mathbb{X}\rightarrow{\mathbb{R}}^{n\times m}$. We consider the gradient
system in (1), repeated here for convenience:

$\dot{x}(t)\;=\;-\eta\,\nabla V(x(t))^{T}\,+\,B(x(t))u(t)\,.$

###### Theorem 2

If $V$ is a proper loss function, then system (1) is ISS.

Proof. We will prove that $V-V(\bar{x})$ is an ISS-Lyapunov function for (1).
Since $V-V(\bar{x})$ is a size function, we need to show an estimate (L-ISS’).
We have:

$\displaystyle\dot{V}(x,u)$ $\displaystyle=$ $\displaystyle-\eta\left|\nabla
V(x)\right|^{2}\,+\,\nabla V(x)\,B(x)u$ $\displaystyle=$
$\displaystyle-\eta\left|\nabla V(x)\right|^{2}+(\sqrt{\eta}\nabla
V(x))(\sqrt{1/\eta}B(x)u)$ $\displaystyle\leq$ $\displaystyle-\eta\left|\nabla
V(x)\right|^{2}+\frac{\eta}{2}\left|\nabla
V(x)\right|^{2}+\frac{1}{2\eta}\left|B(x)u)\right|^{2}$ $\displaystyle=$
$\displaystyle-\frac{\eta}{2}\left|\nabla
V(x)\right|^{2}+\frac{1}{2\eta}\left|B(x)u)\right|^{2}$ $\displaystyle\leq$
$\displaystyle-\frac{\eta}{2}\alpha(V(x)-V(\bar{x}))+\frac{C}{2\eta}\left|u\right|^{2}$
$\displaystyle=$
$\displaystyle-\widetilde{\alpha}((V(x)-V(\bar{x}))+\gamma(\left|u\right|)$

where we used that, for row and column vectors in ${\mathbb{R}}^{n}$,
$\left|vw\right|\leq\left|v\right|\left|w\right|\leq(1/2)(\left|v\right|^{2}+\left|w\right|^{2})$
(Cauchy-Schwarz inequality followed by $2ab\leq a^{2}+b^{2}$), and the
inequality $\alpha(V(x)-V(\bar{x}))\leq\left|\nabla V(x)\right|^{2}$, and
where $C$ is an upper bound on $\left|B\right|$, and defined
$\widetilde{\alpha}:=\frac{\eta}{2}\alpha\in{\mathcal{K}_{\infty}}$ and
$\gamma:=\frac{C}{2\eta}r^{2}\in{\mathcal{K}_{\infty}}$. So $V$ is an ISS-
Lyapunov function, and thus the system (1) is ISS.

In the particular case in which the estimate
$\alpha(V(x)-V(\bar{x}))\leq\left|\nabla V(x)\right|^{2}$ holds with a linear
function $\alpha$, the proof of Theorem 1 provides a rate of decrease for
$v(t)=V(x(t))-V(\bar{x})$ which is exponential: the function $\beta(r,t)$ has
the form $e^{-\lambda t}r$ for some positive $\lambda$.

###  4.3 An example: LQR problem

The (infinite-horizon) LQR problem is one of the best-studied optimal control
problems. Consider a time-invariant linear system

$\dot{x}\;=\;Ax+Bu$

and define the cost function:

${\mathcal{J}}(x^{\scriptscriptstyle
0},u)\,:=\;\int_{0}^{\infty}x^{T}(t)Qx(t)\,+\,u^{T}(t)Ru(t)\,dt$

where $x(t)=x(t,x^{\scriptscriptstyle 0},u)$. Here $x(t)\in{\mathbb{R}}^{n}$,
$u(t)\in{\mathbb{R}}^{m}$, $A\in{\mathbb{R}}^{n\times n}$ and
$B\in{\mathbb{R}}^{n\times m}$ are matrices so that the pair $(A,B)$ is
controllable (or even just stabilizable or “asymptotically controllable”),
which guarantees the finiteness of the objective function, and
$Q\in{\mathbb{R}}^{n\times n}$, and $R\in{\mathbb{R}}^{m\times m}$ are
positive definite. The objective is to minimize
${\mathcal{J}}(x^{\scriptscriptstyle 0},u)$ over all measurable essentially
bounded control functions $u:[0,\infty)\rightarrow{\mathbb{R}}^{m}$, for any
given $x^{\scriptscriptstyle 0}$.

The unique optimal control is obtained by using the linear feedback law
$u(t)=-Kx(t)$, where $K=R^{-1}B^{T}\Pi$ and $\Pi$ is the unique positive
definite solution of the algebraic Riccati equation

$\Pi BR^{-1}B^{T}\Pi\,-\,A^{T}\Pi\,-\,\Pi A\,-\,Q\;=\;0$

(that is, $u(t)=-Kx(t)$), where $x$ solves $\dot{x}=(A-BK)x$ with
$x(0)=x^{\scriptscriptstyle 0}$), and at this optimum value,

${\mathcal{J}}(x^{\scriptscriptstyle 0},u)\;=\;(x^{\scriptscriptstyle
0})^{T}\Pi x^{\scriptscriptstyle 0}$

(see, for instance, Theorem 41 in [28]). The optimal feedback matrix
$K=R^{-1}B^{T}\Pi$ stabilizes the system, i.e., $A-BK$ is a Hurwitz matrix
(all eigenvalues have negative part).

Since the optimal control is given by a linear feedback, one may pose the
simpler question of optimizing over all feedback matrices which belong to the
open set $\mathbb{X}:=\\{K\,|\,A-BK\mbox{ is Hurwitz}\\}$. In terms of $K$ and
using $u=-Kx$, one can introduce the loss function

$V_{x^{\scriptscriptstyle
0}}(K)\,:=\;\int_{0}^{\infty}x(t)^{T}Qx(t)\;+\;(-Kx(t))^{T}\,R\,(-Kx(t))\,dt$

where $x(t)$ solves $\dot{x}=(A-BK)x$, i.e.,
$x(t)=e^{(A-BK)t}x^{\scriptscriptstyle 0}$, so that we can also write

$V_{x^{\scriptscriptstyle
0}}(K)\;=\;\int_{0}^{\infty}x(t)^{T}(Q+K^{T}RK)x(t)\,dt\;=\;\mbox{trace}\,\left((Q+K^{T}RK)\int_{0}^{\infty}x(t)\,x(t)^{T}\,dt\right)$

where we have used that for a scalar $a=\mbox{trace}\,(a)$ and that
$\mbox{trace}\,(UV)=\mbox{trace}\,(VU)$. To obtain a simpler problem, we
assume now that the initial state is picked distributed randomly according to
some probability density in ${\mathbb{R}}^{n}$ (for example, Gaussian) with
covariance $\Sigma=\mathbb{E}[x^{\scriptscriptstyle 0}(x^{\scriptscriptstyle
0})^{T}]$ and we wish to minimize

$V(K)\,:=\;\mathbb{E}[V_{x^{\scriptscriptstyle
0}}]\;=\;\mbox{trace}\,((Q+K^{T}RK)P)$

with

$P\;=\;\mathbb{E}\left[\int_{0}^{\infty}e^{tF}x^{\scriptscriptstyle
0}(x^{\scriptscriptstyle
0})^{T}e^{tF^{T}}\,dt\right]\;=\;\int_{0}^{\infty}e^{tF}\,\Sigma\,e^{tF^{T}}\,dt$

where $F=A-BK$. It follows (see for instance Theorem 18 in [28]) that $P$ is
the (unique) solution of the Lyapunov matrix equation

$(A-BK)P+P(A-BK)^{T}+\Sigma\;=\;0$ (7)

In summary, one has to minimize the loss function
$V(K)=\mbox{trace}\,((Q+K^{T}RK)P)$ where the positive definite matrix $P$
satisfies (7) and $K\in\mathbb{X}$. Since the solution $P$ of the linear
system of equations (7) is a rational function of the data (Cramer’s rule), it
follows that $V(K)$ is rational in the entries of the matrix $K$, and hence
$V$ is differentiable. Although it is not generally convex, it has a unique
global minimum at the optimal $K=R^{-1}B^{T}\Pi$. It is also known that it is
a proper function, see [34]. The gradient can be computed as follows (this is
implicit in the computations in [19, 34], but see [25] for a clear
exposition):

$\nabla V(K)\;=\;2(RK-B^{T}L)P$

where $L$ is the unique positive definite matrix that satisfies

$(A-BK)^{T}L+L(A-BK)+Q+K^{T}RK\;=\;0\,.$

For example, suppose that $n=m=1$, $a=q=r=\Sigma=1$. In this case
$\mathbb{X}=\\{k\,|\,bk>1\\}$ and one obtains

$V(k)\;=\;\frac{k^{2}+1}{2(bk-1)}$

and

$V^{\prime}(k)\;=\;\frac{bk^{2}-2k-b}{2(bk-1)^{2}}\,.$

In general, it can be shown, see [8], that $V$ is a proper loss function. In
fact, that reference shows that the Polyak-Łojasiewicz condition [15]

$c_{r}(V(x)-V(\bar{x}))\;\leq\;\left|\nabla V(x)\right|^{2}$

holds on sublevel sets, for constants $c_{r}$, which implies that a lower
bounding $\alpha\in{\mathcal{K}_{\infty}}$ exists.

##  5 ISS and steepest descent

From now on, we fix a pair $(\mathbb{X},\bar{x})$ and a size function $\omega$
for $(\mathbb{X},\bar{x})$.

We recall from the introductory discussion that we are interested in proving
that the steepest descent iteration $x^{+}=x-\lambda[\nabla V(x)^{T}+B(x)u]$,
where $\lambda$ is picked at each step of the iteration so as to minimize the
value $V(x^{+})$, is a discrete-time ISS system.

###  5.1 Gradients of locally Lipschitz functions on $\mathbb{X}$

Suppose given a continuously differentiable function
$V:\mathbb{X}\rightarrow{\mathbb{R}}$ such that these two properties hold:

  * [SV]

$V-V(\bar{x})$ is a size function for $(\mathbb{X},\bar{x})$,

  * [LL]

$\nabla V$ is locally Lipschitz,

We next review a couple of well-known facts about Lipschitz functions.

###### Remark 5.1

For each compact subset $K\subset X$, there some $L\geq 0$ such that the one-
sided Lipschitz estimate

$\left(\nabla V(y)-\nabla V(x)\right)(y-x)\;\leq\;L\left|y-x\right|^{2}$ (8)

holds for all $x,y\in K$. Indeed, the function $\nabla V$ is Lipschitz on $K$,
with some constant $L$ (start locally and take finite subcovers), so

$\left|\left(\nabla V(y)-\nabla V(x)\right)(y-x)\right|\;\leq\;\left|\nabla
V(y)-\nabla
V(x)\right|\left|y-x\right|\;\leq\;(L\left|y-x\right|)\left|y-x\right|\;=\;L\left|y-x\right|^{2}$

by the Cauchy-Schwarz inequality and the Lipschitz property. $\Box$

###### Remark 5.2

Suppose that $x,y\in K$ and that $L$ is a one-sided Lipschitz constant as in
(8) on the segment

$K\;=\;[x,y]\,:=\;\\{z\,|\,z=x+s(y-x),s\in[0,1]\\}$

connecting $x$ and $y$. Then

$V(y)\;\leq\;V(x)+\nabla V(x)(y-x)+\frac{L}{2}\left|y-x\right|^{2}\,.$ (9)

This is a standard fact, see e.g. [22]. The blanket assumption
$\mathbb{X}={\mathbb{R}}^{n}$ made there is not needed; since the proof is so
simple, we write it here. Pick $x,y$, and consider the continuously
differentiable function:

$g\;:\;[0,1]\rightarrow{\mathbb{R}}\;:\;s\mapsto V(x+s(y-x))\,.$

Then

$V(y)-V(x)-\nabla
V(x)(y-x)\,=\,g(1)-g(0)-g^{\prime}(0)\,=\,\int_{0}^{1}g^{\prime}(s)\,ds-g^{\prime}(0)\,=\,\int_{0}^{1}[g^{\prime}(s)-g^{\prime}(0)]\,ds$

where

$\displaystyle g^{\prime}(s)-g^{\prime}(0)$ $\displaystyle=$
$\displaystyle\nabla V(x+s(y-x))(y-x)-\nabla V(x)(y-x)$ $\displaystyle=$
$\displaystyle\frac{1}{s}\left[\nabla V(x+s(y-x))-\nabla
V(x)\right](s(y-x))\;\leq\;sL\left|y-x\right|^{2}$

by (8) when $s\not=0$ (and this is trivial when $s=0$). Therefore

$V(y)-V(x)-\nabla
V(x)(y-x)\;\leq\;\int_{0}^{1}sL\left|y-x\right|^{2}\,ds\;=\;\frac{L}{2}\left|y-x\right|^{2}\,,$

as desired. $\Box$

We wish to study the behavior of steepest descent when the gradient of $V$ is
inaccurately estimated.

From now on we assume that $\nabla V$ is positive definite:

  * [PD]

$\nabla V(x)\not=0$ for all $x\not=\bar{x}$.

in addition to [SV] and [LL].

###### Lemma 5.3

Pick any $x^{\scriptscriptstyle 0}\in\mathbb{X}$, $x^{\scriptscriptstyle
0}\not=\bar{x}$, and let $L$ be a Lipschitz constant for $\nabla V$ on the
compact set

$S\,:=\;\left\\{x\in\mathbb{X}\,|\,V(x)\leq V(x^{\scriptscriptstyle
0})\right\\}$

(without loss of generality, $L>0$). Pick any $q\in{\mathbb{R}}^{n}$ and write
$p:=\nabla V(x^{\scriptscriptstyle 0})^{T}\not=0$. Suppose that $\lambda>0$
has the property that

$x^{\scriptscriptstyle 0}-\mu(p+q)\in S\quad\mbox{for
each}\;0\leq\mu\leq\lambda\,.$

Then

$V(x^{\scriptscriptstyle 0}-\lambda(p+q))-V(x^{\scriptscriptstyle
0})\;\leq\;\left(-\lambda+\frac{\lambda^{2}L}{2}\right)\left|p\right|^{2}\,+\,\frac{\lambda^{2}L}{2}\left|q\right|^{2}\,+\,\left(\lambda+\lambda^{2}L\right)\left|p\right|\left|q\right|\,.$
(10)

Proof. Let $x=x^{\scriptscriptstyle 0}$ and $y=x^{\scriptscriptstyle
0}-\lambda(p+q)$. The segment $[x,y]$ consists of points of the form
$x^{\scriptscriptstyle 0}-\mu(p+q)$, with $0\leq\mu\leq\lambda$. Therefore, we
may apply the Lipschitz estimate (9), to obtain:

$V(x^{\scriptscriptstyle 0}-\lambda(p+q))-V(x^{\scriptscriptstyle
0})\;\leq\;-\lambda
p^{T}(p+q)\,+\,\frac{\lambda^{2}L}{2}\left|p+q\right|^{2}\,.$

Since

$\left|p+q\right|^{2}\;=\;\left|p\right|^{2}+\left|q\right|^{2}+2p^{T}q\;\leq\;\left|p\right|^{2}+\left|q\right|^{2}+2\left|p\right|\left|q\right|$

and similarly
$-p^{T}q\leq\left|p^{T}q\right|\leq\left|p\right|\left|q\right|$, the estimate
(10) follows.

We have this immediate consequence:

###### Corollary 5.4

Suppose that $q\leq c\left|p\right|$ in Lemma 5.3. Then,

$V(x^{\scriptscriptstyle 0}-\lambda(p+q))-V(x^{\scriptscriptstyle
0})\;\leq\;\lambda\left[(c-1)+\frac{\lambda
L}{2}(c+1)^{2}\right]\,\left|p\right|^{2}\,.$

In particular, taking $c=1/2$ and $\lambda\leq\frac{2}{9L}$, then
$V(x^{\scriptscriptstyle 0}-\lambda(p+q))-V(x^{\scriptscriptstyle
0})\leq-\frac{\lambda}{4}\left|p\right|^{2}$. $\Box$

###### Lemma 5.5

Pick $x^{\scriptscriptstyle 0}$, $L$, $q$, and $p$ as in Lemma 5.3. Suppose
that $\left|q\right|\leq\frac{1}{2}\left|p\right|$ and $\lambda=\frac{2}{9L}$.
Then $x^{\scriptscriptstyle 0}-\mu(p+q)\in\mathbb{X}$ for each
$0\leq\mu\leq\lambda$ and

$V(x^{\scriptscriptstyle 0}-\lambda(p+q))-V(x^{\scriptscriptstyle
0})\;\leq\;-\frac{1}{18L}\left|p\right|^{2}\,.$

Proof. Since $\mathbb{X}$ is an open set, $x^{\scriptscriptstyle
0}-\mu(p+q)\in\mathbb{X}$ for all small $\mu>0$. Also, since

$\left.\frac{d}{ds}\right|_{s=0}V(x^{\scriptscriptstyle
0}-s(p+q))\;=\;-p^{T}(p+q)\;=\;-\left|p\right|^{2}+p^{T}q\;\leq\;-\left|p\right|^{2}+\left|p\right|\left|q\right|\;\leq\;-\frac{1}{2}\left|p\right|^{2}\;<\;0\,,$

there is some $\varepsilon>0$ such that

$V(x^{\scriptscriptstyle 0}-\mu(p+q))\;<\;V(x^{\scriptscriptstyle
0})\quad\mbox{for all}\;\mu\in(0,\varepsilon)\,.$

Suppose that there would exist some $\mu\in[0,\lambda]$ such that
$x^{\scriptscriptstyle 0}-\mu(p+q)\not\in S$. Since $S$ is compact and
$\mathbb{X}$ is open, this would mean that there is some
$\mu\in[\varepsilon,\lambda]$ such that $x^{\scriptscriptstyle
0}-\mu(p+q)\in\mathbb{X}$ and $V(x^{\scriptscriptstyle
0}-\mu(p+q))=V(x^{\scriptscriptstyle 0})$. To apply Corollary 5.4, we need to
see that this cannot happen. Let

$\lambda_{0}\,:=\;\min\left\\{\mu\in[\varepsilon,\lambda]\,|\,V(x^{\scriptscriptstyle
0}-\mu(p+q))=V(x^{\scriptscriptstyle 0})\right\\}\;\geq\;\varepsilon\;>\;0\,.$

Since $V(x^{\scriptscriptstyle 0}-\mu(p+q))\leq V(x^{\scriptscriptstyle 0})$
for all $\mu\in[0,\lambda_{0}]$, we may apply Corollary 5.4 to $\lambda_{0}$
to conclude that

$0\;=\;V(x^{\scriptscriptstyle 0}-\lambda(p+q))-V(x^{\scriptscriptstyle
0})\;\leq\;-\frac{\lambda_{0}}{4}\left|p\right|^{2}\,,$

which contradicts $\lambda_{0}>0$ and $p\not=0$. Thus the hypotheses of Lemma
5.3 hold, and applying Corollary 5.4 to $\lambda$ we conclude that

$V(x^{\scriptscriptstyle 0}-\lambda(p+q))-V(x^{\scriptscriptstyle
0})\;\leq\;-\frac{\lambda}{4}\left|p\right|^{2}\;=\;-\frac{1}{18L}\left|p\right|^{2}$

as claimed.

###  5.2 Line search in direction of steepest descent

We continue with the assumptions [PD], [SV], [LL] on $V$. We next define a
function

$F\,:\,\mathbb{X}\times{\mathbb{R}}^{n}\rightarrow\mathbb{X}$

that will represent an individual steepest descent step when starting at a
point $x^{\scriptscriptstyle 0}\in\mathbb{X}$ and the (transpose of the)
gradient is estimated as $p+q$ where $p:=\nabla V(x^{\scriptscriptstyle
0})^{T}$ and $q\in{\mathbb{R}}^{n}$ represents an additive noise. Now take any
$x^{\scriptscriptstyle 0}\in\mathbb{X}$ and any $q\in{\mathbb{R}}^{n}$ such
that $p+q\not=0$. Define

$\Lambda(x^{\scriptscriptstyle 0},q)\,:=\;\left\\{\lambda\geq
0\,|\,V(x^{\scriptscriptstyle 0}-\mu(p+q))\leq V(x^{\scriptscriptstyle
0})\;\mbox{for all}\;\mu\in[0,\lambda]\right\\}\,.$

Note that $0\in\Lambda(x^{\scriptscriptstyle 0},q)$. In the particular case
$x^{\scriptscriptstyle 0}=\bar{x}$, $V(x^{\scriptscriptstyle 0})$ is the
unique minimizer of $V$, so $\Lambda(x^{\scriptscriptstyle 0},q)=\\{0\\}$. We
consider $x^{\scriptscriptstyle 0}\not=\bar{x}$ from now on.

The set $\Lambda(x^{\scriptscriptstyle 0},q)$ is compact. It is bounded above:
otherwise, it would be the case that $x^{\scriptscriptstyle
0}-\lambda(p+q)\in\mathbb{X}$ and $V(x^{\scriptscriptstyle
0}-\lambda(p+q))\leq V(x^{\scriptscriptstyle 0})$ for all $\lambda\geq 0$;
then since $V$ is proper, the set of points $x^{\scriptscriptstyle
0}-\lambda(p+q)$ is bounded, but this contradicts that
$\left|x^{\scriptscriptstyle
0}-\lambda(p+q)\right|\geq\left|\left|x^{\scriptscriptstyle
0}\right|-\lambda\left|p+q\right|\right|\rightarrow\infty$ as
$\lambda\rightarrow\infty$ because $\left|p+q\right|\not=0$. It is also
closed. Indeed, suppose that $\lambda_{k}\rightarrow\lambda$, with
$\lambda_{k}\in\Lambda(x^{\scriptscriptstyle 0},q)$. Then
$V(x^{\scriptscriptstyle 0}-\lambda(p+q))\leq V(x^{\scriptscriptstyle 0})$, by
continuity. In addition, for each $\mu<\lambda$, there is some $k$ so that
$\mu<\lambda_{k}$ so $V(x^{\scriptscriptstyle 0}-\mu(p+q))\leq
V(x^{\scriptscriptstyle 0})$, proving that
$\lambda\in\Lambda(x^{\scriptscriptstyle 0},q)$.

Thus we may define

${\bar{\lambda}}_{x^{\scriptscriptstyle
0},q}\,:=\;\operatorname*{arg\,min}_{\lambda\in\Lambda(x^{\scriptscriptstyle
0},q)}V(x^{\scriptscriptstyle 0}-\lambda(p+q))$

where “arg min” means that we take the smallest $\lambda$ that achieves this
minimum value in the direction of $p+q$ when there is more than one. We then
define

$F(x^{\scriptscriptstyle 0},q)\,:=\;x^{\scriptscriptstyle
0}-{\bar{\lambda}}_{x^{\scriptscriptstyle 0},q}(p+q)\,.$

and $F(x^{\scriptscriptstyle 0},q):=x^{\scriptscriptstyle 0}$ if $p+q=0$. Note
that $V(F(x^{\scriptscriptstyle 0},q))\leq V(x^{\scriptscriptstyle 0})$,
because $0\in\Lambda(x^{\scriptscriptstyle 0},q)$ and we are minimizing. In
other words,

${\widetilde{\Delta}}V(x^{\scriptscriptstyle
0},q)\,:=\;V(F(x^{\scriptscriptstyle 0},q))-V(x^{\scriptscriptstyle
0})\;\leq\;0\quad\forall\,(x^{\scriptscriptstyle 0},q)$

and observe that ${\widetilde{\Delta}}V(x,q)=0$ if $V(x^{\scriptscriptstyle
0}-\varepsilon(p+q))\geq V(x^{\scriptscriptstyle 0})$ for all small
$\varepsilon$. On the other hand, since

$\left.\frac{d}{ds}\right|_{s=0}V(x^{\scriptscriptstyle
0}-sp)\;=\;-\left|\nabla V(x^{\scriptscriptstyle 0})\right|<0$

it follows that ${\widetilde{\Delta}}V(x^{\scriptscriptstyle 0},0)<0$ for all
$x^{\scriptscriptstyle 0}\not=\bar{x}$.

We next estimate ${\widetilde{\Delta}}V(x^{\scriptscriptstyle 0},q)$ for all
$\left|q\right|$ that are not “too large” compared to $\left|p\right|$.

Suppose that $L$ is any Lipschitz constant for $\nabla V$ on the set
$S=\left\\{x\in\mathbb{X}\,|\,V(x)\leq V(x^{\scriptscriptstyle 0})\right\\}$,
$\left|q\right|\leq\frac{1}{2}\left|p\right|$, and $\lambda=\frac{2}{9L}$.
From Lemma 5.5, $\lambda\in\Lambda(x^{\scriptscriptstyle 0},q)$, so
$V(F(x^{\scriptscriptstyle 0},q))\leq V(x^{\scriptscriptstyle
0}-\lambda(p+q))$ by definition of ${\bar{\lambda}}_{x^{\scriptscriptstyle
0},q}$ as a minimizer. Thus, again by the Lemma,

${\widetilde{\Delta}}V(x^{\scriptscriptstyle
0},q)\;=\;V(F(x^{\scriptscriptstyle 0},q))-V(x^{\scriptscriptstyle
0})\;\leq\;V(x^{\scriptscriptstyle 0}-\lambda(p+q))-V(x^{\scriptscriptstyle
0})\;\leq\;-\frac{1}{18L}\left|\nabla V(x^{\scriptscriptstyle 0})\right|^{2}$
(11)

where, recall, $L$ is a Lipschitz constant on $\\{V(x)\leq
V(x^{\scriptscriptstyle 0})\\}$.

###  5.3 Steepest descent with inputs

We now consider a slightly more general setup as follows. Let
$B:\mathbb{X}\rightarrow{\mathbb{R}}^{n\times m}$ be a bounded mapping, and
assume that the gradient error at each iteration step is $q=B(x)u$, where
$u\in{\mathbb{R}}^{m}$, so that $\left|q\right|\leq K\left|u\right|$, where
$K$ is an upper bound on the Euclidean induced norm $\left\|B(x)\right\|$,
over all $x\in\mathbb{X}$.

We define the steepest descent algorithm, with inputs $u$, as the discrete-
time system defined by the following iteration function
$f:\mathbb{X}\times{\mathbb{R}}^{m}\rightarrow\mathbb{X}$:

$x^{+}\;=\;f(x,u):=F(x,B(x)u)\,.$

We define $\Delta V(x,u):={\widetilde{\Delta}}V(x,B(x)u)$, that is

$\Delta V(x,u)\,:=\;V(f(x,u))-V(x)\,.$

Since ${\widetilde{\Delta}}V(x,q)\leq 0$ for all $(x,q)$, also $\Delta
V(x,u)\leq 0$ for all $(x,u)$. Obviously, we can also write

$\Delta V(x,u)\;=\;[V(f(x,u))-V(\bar{x})]-[V(x)-V(\bar{x})]\,.$

which exhibits $\Delta V$ as the change, in each steepest descent step, of the
“excess cost” of $V$ compared to its minimum value $V(\bar{x})$.

###  5.4 Discrete-time ISS

We now extend to open subsets the definition of input to state stability for
discrete time systems, which is completely analogous to that for continuous
time, see for instance [12, 13, 14]. We consider discrete-time systems
$x^{+}=f(x,u)$, where
$f:\mathbb{X}\times{\mathbb{R}}^{m}\rightarrow\mathbb{X}$ is a continuous
function and $f(\bar{x},0)=0$.

###### Definition 5.6

The discrete-time system $x^{+}=f(x,u)$ is _input to state stable (ISS)_ (on
the open set $\mathbb{X}$ and with respect to $\bar{x}$) if there exist
functions $\beta\in{\mathcal{K}}{\mathcal{L}}$ and
$\gamma\in{\mathcal{K}_{\infty}}$ so that the following property holds: for
all input sequences $u=(u_{0},u_{1},\ldots)\in\ell^{\infty}_{m}$ and all
initial conditions $x^{\scriptscriptstyle 0}\in\mathbb{X}$, the solution
$x^{\scriptscriptstyle 0}$ satisfies the estimate:

$\quad\quad\quad\omega(x(t,x^{\scriptscriptstyle
0},u))\;\leq\;\beta(\omega(x^{\scriptscriptstyle
0}),t)\,+\,\gamma\left(\left\|u\right\|_{\infty}\right)$ $None$

for all $t=0,1,2,\ldots$.

Here $\left\|u\right\|_{\infty}=\sum_{t=0}^{\infty}\left|u_{t}\right|$ and
$x(t,x^{\scriptscriptstyle 0},u)$ is obtained by solving recursively
$x_{t+1}=f(x_{t},u_{t})$.

There are several equivalent definitions of ISS-Lyapunov function for discrete
time systems. We pick here the most convenient one for the current
application.

For any function $V:\mathbb{X}\rightarrow{\mathbb{R}}$, we denote $\Delta
V(x,u):=V(f(x,u))-V(x)$.

###### Definition 5.7

A continuous $V:\mathbb{X}\rightarrow{\mathbb{R}}$ is said to be an _ISS-
Lyapunov function_ for $x^{+}=f(x,u)$ if

  * (a)

$V-V(\bar{x})$ is a size function for $(\mathbb{X},\bar{x})$, and

  * (b)

there are exist (i) a continuous and positive definite function $\alpha$, and
(ii) a function $\chi\in{\mathcal{K}_{\infty}}$, such that:

$\omega(x)\,\geq\,\chi(\left|u\right|)\quad\Rightarrow\quad\Delta
V(x,u)\;\leq\;-\alpha(V(x)-V(\bar{x}))$ (12)

for all $x\in\mathbb{X}$, $u\in{\mathbb{R}}^{m}$.

Equivalences among alternative ISS-Lyapunov function definitions, including a
condition of the type $\Delta
V(x,u)\leq-\alpha(\omega(x))+\gamma(\left|u\right|)$ for functions of class
${\mathcal{K}_{\infty}}$, are discussed in Remark 3.3 of [13]. As with
continuous-time systems, the existence of ISS-Lyapunov functions is equivalent
to the ISS property, see [12, 14]. For completeness, and because of the
interest in open subsets $\mathbb{X}$, we prove the sufficiency below,
appealing to some key technical lemmas in [14, 13].

Let us write, for simplicity of notation, $W(x)=V(x)-V(\bar{x})$. As $\Delta
V(x,u)=[V(f(x,u))-V(\bar{x})]-[V(x)-V(\bar{x})]=W(f(x,u))-W(x)$, one can write
(12) as:

$\omega(x)\,\geq\,\chi(\left|u\right|)\quad\Rightarrow\quad
W(f(x,u))\;\leq\;W(x)-\alpha(W(x))\,.$

###### Theorem 3

If a discrete-time system admits an ISS-Lyapunov function $V$ then it is ISS.

Proof. We first remark that one may redefine $V$, replacing it by a function
of the form $\rho(V(x))$ with $\rho\in{\mathcal{K}_{\infty}}$, in such a
manner that the estimate (12) holds but now $\alpha\in{\mathcal{K}_{\infty}}$
(and the redefined $V$ is so that $V-V(\bar{x})$ still a size function). The
argument is similar to the one given in [27] for the continuous time case, but
it is more delicate, see the proof of Lemma 2.8 in [14]. Moreover, one may
assume that $r\mapsto r-\alpha(r)$ is of class ${\cal K}$ (see Lemma B.1 in
[13]). So, from now on, and redefining $V$ in this manner if needed, we will
assume that $\alpha$ satisfies these two properties. Since $W$ is a size
function, there is a $\pi\in{\mathcal{K}_{\infty}}$ such that
$\omega(x)\geq\pi(W(x))$, and thus $W(x)\geq\pi^{-1}(\chi(\left|u\right|))$
implies $\omega(x)\geq\chi(\left|u\right|)$, so redefining $\chi$ as
$\pi^{-1}\circ\chi$ we can state the ISS-Lyapunov property as:

$W(x)\,\geq\,\chi(\left|u\right|)\quad\Rightarrow\quad
W(f(x,u))\;\leq\;W(x)-\alpha(W(x))\,.$

Now let $\beta(r,t)$ be the solution of the scalar difference equation

$y_{t+1}\;=\;y_{t}-\alpha(y_{t})\,,\quad y_{0}=r\geq 0\,.$

The property that $r\mapsto r-\alpha(r)$ is of class ${\cal K}$ implies
$y_{t}\geq 0$ for all $t$, and also that $y_{t}<y_{t}^{\prime}$ implies
$y_{t+1}<y_{t+1}^{\prime}$ for any two solutions, in other words, the
iteration is monotone (it preserves order). Thus the function $\beta$ is of
class ${\cal K}$ on $r$. Moreover, since $\alpha(y)\geq 0$, $y_{t+1}\leq
y_{t}$, iterates form a decreasing sequence. Thus all solutions converge to
zero as $t\rightarrow\infty$, since the only equilibrium $y-\alpha(y)=y$ is at
$y=0$. So $\beta\in{\mathcal{K}}{\mathcal{L}}$.

We introduce the following function $\gamma:[0,\infty)\rightarrow[0,\infty)$:

$\gamma(\mu)\,:=\;\max\left\\{W(f(x,u))\,|\,\left|u\right|\leq\mu,W(x)\leq\chi(\mu)\right\\}$

which is well-defined (the set over which we are maximizing is compact, and
$W(f(x,u))$ is continuous on $(x,u)$), nondecreasing (the sets are larger as
$\mu$ increases), and satisfies $\gamma(0)=0$ (since $W(x)=0$ implies
$x=\bar{x}$ and $f(\bar{x},0)=\bar{x}$). Note that this implication holds:

$W(x)\,\leq\,\chi(\left|u\right|)\quad\Rightarrow\quad
W(f(x,u))\;\leq\;\gamma(\left|u\right|)\,.$

Replacing $\gamma$ by a larger function if needed, we may assume that
$\gamma\in{\mathcal{K}_{\infty}}$ and also that $\gamma(\mu)\geq\chi(\mu)$ for
all $\mu$. Consider the following sets:

$P_{\mu}\,:=\;\left\\{x\,|\,W(x)\leq\gamma(\mu)\right\\}\,.$

We claim that this set is forward invariant for inputs with
$\left\|u\right\|_{\infty}\leq\mu$. Indeed, pick any $x\in P_{\mu}$ and any
$u\in{\mathbb{R}}^{m}$ with $\left\|u\right\|_{\infty}\leq\mu$. If
$W(x)\geq\chi(\left|u\right|)$, then $W(f(x,u))\leq W(x)\leq\gamma(\mu)$, so
$f(x,u)\in P_{\mu}$. If instead $W(x)\leq\chi(\left|u\right|)$, then
$W(f(x,u))\leq\gamma(\left|u\right|)\leq\gamma(\mu)$ as well.

Consider now any input $u$, any initial state $x^{\scriptscriptstyle 0}$, and
the corresponding solution $x(t,x^{\scriptscriptstyle 0},u)$ of
$x^{+}=f(x,u)$. Let $a_{t}:=W(x(t,x^{\scriptscriptstyle 0},u))$ for
$t=0,1,\ldots$, and $\mu:=\left\|u\right\|_{\infty}$. We will compare this
sequence to $y_{t}=\beta(W(x^{\scriptscriptstyle 0}),t)=\beta(a_{0},t)$. Note
that by definition $a_{0}=y_{0}$.

Consider first the case that $a_{t}\leq\gamma(\mu)$ for all $t$. Obviously in
that case $a_{t}\leq\max\\{\beta(a_{0},t),\gamma(\mu)\\}$ for all $t$.

Consider next the case that $a_{t}>\gamma(\mu)$ for some $t$. Then either (i)
$a_{t}>\gamma(\mu)$ for all $t$, or (ii) there is a $T\geq 0$ so that
$a_{t}\geq\gamma(\mu)$ for $t=0,\ldots,T$ and $a_{T+1}\leq\gamma(\mu)$.
Suppose that $a_{t}\geq\gamma(\mu)$ for $t=0,\ldots,T$. From the ISS-Lyapunov
property, we know that

$a_{t}\,\geq\,\gamma(\mu)\quad\Rightarrow\quad
a_{t}\,\geq\,\chi(\mu)\,\geq\,\chi(\left|u_{t}\right|)\quad\Rightarrow\quad
a_{t+1}\;\leq\;a_{t}-\alpha(a_{t})\,.$

We claim that $a_{t}\leq y_{t}=\beta(a_{0},t)$ for $t=0,\ldots,T$. This holds
for $t=0$. In general, if $\gamma(\mu)\leq a_{t}\leq y_{t}$ then $a_{t+1}\leq
a_{t}-\alpha(a_{t})\leq y_{t}-\alpha(y_{t})=y_{t+1}$, because $r-\alpha(r)$ is
nondecreasing in $r$. By induction, $a_{t}\leq y_{t}$ for $t=0,\ldots,T$. It
cannot be that (i) holds, since $y_{t}\rightarrow 0$ as $t\rightarrow\infty$.
Thus (ii) holds. Now the condition $a_{T+1}\leq\gamma(\mu)$ together with the
forward invariance of $P_{\mu}$ implies that $a_{t}\leq\gamma(\mu)$ for all
$t>T$.

In summary, $a_{t}\leq\max\\{\beta(a_{0},t),\gamma(\mu)\\}$ for all $t$, or

$W(x(t,x^{\scriptscriptstyle
0},u))\;\leq\;\max\\{\beta(W(x^{\scriptscriptstyle
0}),t),\gamma(\left\|u\right\|_{\infty})\\},\,t=0,1,\ldots\,.$

Let $\theta_{i}\in{\mathcal{K}_{\infty}}$ be such that
$\omega(x)\leq\theta_{1}(W(x))$ and $W(x)\leq\theta_{2}(\omega(x))$. Then

$\omega(x(t,x^{\scriptscriptstyle
0},u))\;\leq\;\max\\{\theta_{1}(\beta(\theta_{2}(\omega(x^{\scriptscriptstyle
0})),t),\gamma(\left\|u\right\|_{\infty})\\}\;\leq\;\widetilde{\beta}(\omega(x^{\scriptscriptstyle
0}),t)\,+\,\gamma(\left\|u\right\|_{\infty})$

with $\widetilde{\beta}(r,t)=\theta_{1}(\beta(\theta_{2}(r),t))$ is an ISS
estimate.

###  5.5 Application to steepest descent

For each $r\geq 0$, we let

$L(r)\;=\;\mbox{a Lipschitz constant for}\,\nabla V\,\mbox{on the
set}\,\\{x\,|\,V(x)\leq r\\}\,.$

Without loss of generality we may take $L$ as a continuous, nondecreasing, and
everywhere nonzero function. Letting

$\theta(r)\,:=\;\frac{1}{18L(r)}$

we conclude that:

$\left|\nabla V(x)\right|\,\geq\,2K\left|u\right|\quad\Rightarrow\quad\Delta
V(x,u)\;\leq\;-\theta(V(x))\left|\nabla V(x)\right|^{2}\,.$ (13)

For $x=\bar{x}$, this is immediate since both sides vanish; for
$x\not=\bar{x}$ it follows from (11).

From now on, we assume that:

  * [SG]

$\left|\nabla V\right|$ is a size function for $(\mathbb{X},\bar{x})$.

This property implies [PD].

###### Theorem 4

Suppose that [SV], [LL], [SG] hold. The system $x^{+}=f(x,u)$ is ISS, and $V$
is an ISS-Lyapunov function for it.

Proof. We need to obtain an estimate as in (12). Let $\theta$ be as in (13).
Since $\left|\nabla V\right|/(2K)$ is a size function, we may pick $\chi$ as
any ${\mathcal{K}_{\infty}}$ function with the property that
$\chi(\left|\nabla V(x)\right|/(2K))\geq\omega(x)$ for all $x$. Now, if the
pair $(x,u)$ is such that $\omega(x)\geq\chi(\left|u\right|)$, then
$\chi(\left|\nabla V(x)\right|/(2K))\geq\omega(x)\geq\chi(\left|u\right|)$,
and therefore $\left|\nabla V(x)\right|>2K\left|u\right|$. Thus we have the
implication

$\omega(x)\,\geq\,\chi(\left|u\right|)\quad\Rightarrow\quad\Delta
V(x,u)\;\leq\;-\theta(V(x))\left|\nabla V(x)\right|^{2}\,.$

Since both $\left|\nabla V\right|^{2}$ and $V-V(\bar{x})$ are size functions,
there is some $\widetilde{\alpha}\in{\mathcal{K}_{\infty}}$ such that
$\left|\nabla V(x)\right|^{2}\geq\widetilde{\alpha}(V(x)-V(\bar{x}))$, from
which

$-\theta(V(x))\left|\nabla
V(x)\right|^{2}\;\leq\;-\theta(V(x))\,\widetilde{\alpha}(V(x)-V(\bar{x}))$

for all $x\in\mathbb{X}$. Let

$\alpha(r)\;:=\;\theta(r+V(\bar{x}))\,\widetilde{\alpha}(r)\,.$

Since $\theta$ is continuous and everywhere positive, and
$\widetilde{\alpha}\in{\mathcal{K}_{\infty}}$, it follows that $\alpha$ is
continuous and positive definite. We have

$\omega(x)\,\geq\,\chi(\left|u\right|)\quad\Rightarrow\quad\Delta
V(x,u)\;\leq\;-\alpha(V(x)-V(\bar{x}))$

and therefore $V$ is a discrete-time ISS Lyapunov function, as claimed.

We remark that in the special case that $\nabla V$ is globally Lipschitz, one
can take $L$, and hence also $\theta$, as a constant, so that $\alpha$ can be
picked of class ${\mathcal{K}_{\infty}}$.

##  6 Discussion

We have analyzed the ISS properties of continuous-time gradient descent on
open subsets of Euclidean space, as well as the ISS properties of the
associated discrete-time steepest descent algorithm.

The conditions that we impose, which generalize the Polyak-Łojasiewicz
condition, have appeared in the recent literature in similar contexts. For
example, in [32] one finds extremum-seeking controllers based on gradient
flows and an ISS property with respect for disturbances, for an integrator and
a kinematic unicycle; $\mathbb{X}$ is a closed submanifold of
${\mathbb{R}}^{n}$. The paper [24] studies the gradient minimization of a
function $V_{q}(x)$ on $\mathbb{X}={\mathbb{R}}^{n}$, where a parameter $q$
represents time-varying uncertainty and an ISS property is established with
respect to the rate of change of $q$ (which is a notion called “DISS” in [2]).
The work [3] solves an output regulation problem for switched linear dynamical
systems, with $\mathbb{X}={\mathbb{R}}^{n}$, proving an ISS property for
gradient flows with respect to unknown disturbances acting on the plant. In
[4], the authors also study a gradient flow and show ISS with respect to
additive errors, assuming strong convexity of the function to be minimized (in
fact, a more general “convex-concave” property), also with
$\mathbb{X}={\mathbb{R}}^{n}$.

It is worth remembering that ISS theory provides an overall conceptual view,
and is never the whole story. To be useful in specific applications, good
estimates of the various gain functions are required. An analogy is Lyapunov-
function analysis of nonlinear differential equations: while showing stability
is an important first step, in practice one wants quantifications of
overshoots, speed of convergence, and so on. The brief discussion of the LQR
problem emphasizes that most of the actual work goes into establishing such
estimates, as is the case in the various works that we have cited.
Nonetheless, it seems useful to have a conceptual framework and “roadmap” that
helps organize the overall abstract ideas.

Even at the conceptual level, there are many extensions still to be explored.
We mentioned the extension to Riemannian manifolds, which should be quite
straightforward. More interestingly, finite- and fixed-time gradient flows [5,
26] may also be studied on open subsets and, most importantly in the current
context, from the point of view of finite and fixed-time ISS in the sense of
e.g. [10, 21, 9].

##  7 Acknowledgments

The author thanks Yuan Wang and Denis Efimov for a critical reading and
suggestions. This research was supported in part by grants ONR
N00014-21-1-2431 and AFOSR FA9550-21-1-0289.

## References

  * [1] D. Angeli and D. Efimov.  Characterizations of input-to-state stability for systems with multiple invariant sets.  IEEE Transactions on Automatic Control, 60(12):3242–3256, 2015\.
  * [2] D. Angeli, E.D. Sontag, and Y. Wang.  Input-to-state stability with respect to inputs and their derivatives.  Internat. J. Robust Nonlinear Control, 13(11):1035–1056, 2003.
  * [3] G. Bianchin, J.I. Poveda, and E. Dall’Anese.  Online optimization of switched lti systems using continuous-time and hybrid accelerated gradient flows.  arXiv 2008.03903, 2020.
  * [4] A. Cherukuri, E. Mallada, S. Low, and J. Cortés.  The role of convexity in saddle-point dynamics: Lyapunov function and robustness.  IEEE Transactions on Automatic Control, 63(8):2449–2464, 2018.
  * [5] K. Garg and D. Panagou.  Fixed-time stable gradient flows: Applications to continuous-time optimization.  IEEE Transactions on Automatic Control, 66(5):2002–2015, 2021.
  * [6] L Grüne.  Input-to-state stability, numerical dynamics and sampled-data control.  GAMM-Mitteilungen, 31(1):94–114, 2008.
  * [7] W. Hahn.  Stability of Motion.  Springer-Verlag, Berlin, 1967.
  * [8] M. Hesameddin, A. Zare, M. Soltanolkotabi, and M. R. Jovanović.  Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem.  arXiv, 1912.11899, 2021.
  * [9] J. Holloway and M. Krstic.  Prescribed-time output feedback for linear systems in controllable canonical form.  Automatica, 107:77–85, 2019.
  * [10] Y. Hong, Z.-P. Jiang, and G. Feng.  Finite-time input-to-state stability and applications to finite-time control.  IFAC Proceedings Volumes, 41(2):2466–2471, 2008.
  * [11] A. Isidori.  Nonlinear Control Systems II.  Springer-Verlag, London, 1999.
  * [12] Z-P. Jiang, E.D. Sontag, and Y. Wang.  Input-to-state stability for discrete-time nonlinear systems.  In Proc. 14th IFAC World Congress, Vol E (Beijing), pages 277–282, 1999.
  * [13] Z.-P. Jiang and Y. Wang.  Input-to-state stability for discrete-time nonlinear systems.  Automatica, 37(6):857–869, 2001.
  * [14] Z-P. Jiang and Y. Wang.  A converse lyapunov theorem for discrete-time systems with disturbances.  Systems & Control Letters, 45(1):49–58, 2002.
  * [15] H. Karimi, J. Nutini, and M. Schmidt.  Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.  In Paolo Frasconi, N. Landwehr, G. Manco, and J. Vreeken, editors, Machine Learning and Knowledge Discovery in Databases, pages 795–811, Cham, 2016. Springer International Publishing.
  * [16] H. Khalil.  Nonlinear Systems, Third Edition.  Prentice Hall, Upper Saddle River, NJ, 2002.
  * [17] J. Kurzweil.  On the inversion of Ljapunov’s second theorem on stability of motion.  Czechoslovak Mathematical Journal, 6:217–259, 1956.  English translation in American Mathematical Society Translations (2), 24, 19-77.
  * [18] V. Lakshmikantham and S. Leela.  Differential and Integral Inequalities.  Academic Press, 1969.
  * [19] W. Levine and M. Athans.  On the determination of the optimal constant output feedback gains for linear multivariable systems.  IEEE Transactions on Automatic Control, 15(1):44–48, 1970.
  * [20] Y. Lin, E.D. Sontag, and Y. Wang.  A smooth converse Lyapunov theorem for robust stability.  SIAM J. Control Optim., 34(1):124–160, 1996.
  * [21] F. Lopez-Ramirez, D. Efimov, A. Polyakov, and W. Perruquettil.  On implicit finite- time and fixed- time iss lyapunov functions.  In 2018 IEEE Conference on Decision and Control (CDC), pages 706–710, 2018.
  * [22] Iu. E. Nesterov.  Introductory lectures on convex optimization: A basic course.  Mathematics and its Applications; v. 564. Kluwer Academic Publishers, Boston, 2004-2004.
  * [23] N. Noroozi, A Khayatian, and R Geiselhart.  A characterization of integral input-to-state stability for hybrid systems.  Mathematics of Control, Signals, and Systems, 29(3):13, Jun 2017\.
  * [24] J.I. Poveda and M. Krstic.  Fixed-time extremum seeking.  arXiv 1912.06999, 2019.
  * [25] T. Rautert and E. W. Sachs.  Computational design of optimal output feedback controllers.  SIAM Journal on Optimization, 7(3):837–852, 1997.
  * [26] O. Romero and M. Benosman.  Finite-time convergence in continuous-time optimization.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8200–8209. PMLR, 13–18 Jul 2020\.
  * [27] E.D. Sontag.  Smooth stabilization implies coprime factorization.  IEEE Trans. Automat. Control, 34(4):435–443, 1989.
  * [28] E.D. Sontag.  Mathematical Control Theory. Deterministic Finite-Dimensional Systems, volume 6 of Texts in Applied Mathematics.  Springer-Verlag, New York, second edition, 1998.
  * [29] E.D. Sontag.  Input to state stability: Basic concepts and results.  In P. Nistri and G. Stefani, editors, Nonlinear and Optimal Control Theory, pages 163–220. Springer-Verlag, Berlin, 2007.
  * [30] E.D. Sontag and Y. Wang.  On characterizations of the input-to-state stability property.  Systems Control Lett., 24(5):351–359, 1995.
  * [31] E.D. Sontag and Y. Wang.  Notions of input to output stability.  Systems Control Lett., 38(4-5):235–248, 1999.
  * [32] R. Suttner and S. Dashkovskiy.  Robustness properties of a large-amplitude, high-frequency extremum seeking control scheme.  arXiv 2009.14676, 2021.
  * [33] A.R. Teel and L. Praly.  A smooth lyapunov function from a class-$\mathcal{KL}$ estimate involving two positive semidefinite functions.  Control Optimisation and Calculus of Variations, 5:313–367, 2000\.
  * [34] H. T. Toivonen.  A globally convergent algorithm for the optimal constant output feedback problem.  International Journal of Control, 41(6):1589–1599, 1985.
  * [35] F.W. Wilson.  The structure of the level surfaces of a Lyapunov function.  J. Differential Equations, 3:323–329, 1967.