Lyapunov Functions

Lyapunov functions are an extremely convenient device for proving that a dynamical system converges. We cover:

The Lyapunov argument
La Salle’s Invariance Principle
An Alternative argument for Convex Functions
Exponential Convergence Rates

For some continuous function $f:{\mathbb R}^n\rightarrow {\mathbb R}^n$ , we suppose $x(t)$ obeys the differential equation $\label{Lya:x} \frac{\mathrm{d}x }{\mathrm{d}t}=f(x(t)),\qquad t\in{\mathbb R}_+.$
A Lyapunov function is a continuously differentiable function $L:{\mathbb R}^n\rightarrow {\mathbb R}$ with unique minimum at $x^*$ such that

$\label{Lya:Lya} f(x)\cdot \nabla L(x) < 0,\qquad \forall x\neq x^*.$

We add the additional assumption that $\{x: L(x)\leq l\}$ is a compact set for every $l\in{\mathbb R}$ .

Theorem 1. If a Lyapunov exists for differential equation then $L(x(t))\searrow L(x^*)$ as $t\rightarrow\infty$ and

$x(t)\xrightarrow[t\rightarrow\infty]{}x^*.$

Proof. Firstly,

$\frac{d L(x(t))}{dt} = f(x(t))\cdot \nabla L(x(t)) < 0.$

So $L(x(t))$ is decreasing. Suppose it decreases to $\tilde{L}$ . By the Fundamental Theorem of Calculus

$\tilde{L}-L(x(t))=\int_t^\infty \frac{d L(x(s))}{ds} ds \xrightarrow[t\rightarrow\infty]{} 0$

Thus we can take a sequence of times $\{s_k\}_{k=1}^\infty$ such that $\frac{d L(x(s_k))}{dt}\rightarrow 0$ as $s_k\rightarrow\infty$ . As $\{ x : L(x)< L(x(0))\}$ is compact, we can take a subsequence of times $\{t_k\} _{k=1}^\infty\subset \{s_k\}_{k=1}^\infty$ , $t_k\rightarrow\infty$ such that $\{x(t_k)\}_{k=0}^\infty$ converges. Suppose it converges to $\tilde{x}$ . By continuity,

$0 =\lim_{k\rightarrow\infty} \frac{dL(x(t_k))}{d t} = \lim_{k\rightarrow\infty} f(x(t_k))\cdot \nabla L(\tilde{x})= f(\tilde{x})\cdot \nabla L(\tilde{x}).$

Thus by definition $\tilde{x}=x^*$ . Thus $\lim_{t\rightarrow\infty} L(x(t))=L(x^*)$ and thus by continuity of $L$ at $x^*$ we must have $x(t)\rightarrow x^*$ QED.

One can check this proof follows more-or-less unchanged if $x^*$ , the minimum of $L$ , is not unique.

La Salle’s Invariance Principle

We generalize and strengthen the Lyapunov convergence result in Theorem 1. Here we no longer consider convergence to a unique global minimum of $L(x)$ . Instead, we find convergence to points $\mathcal X^\star = \left\{ x : g(x)\cdot \nabla L(x) =0 \right\}$ The set $\mathcal X^\star$ is called the set of invariant points. Notice, under the conditions of Theorem 1, $\mathcal X^\star = \{ x^\star\}$ . In general, $\mathcal X^\star$ contains all local [and global] minima of $L(x)$ . If the dynamics exclude invariant points which are non-local minima [for instance by taking $g(x) = -\eta \nabla L(x)$ ] then $\mathcal X^\star$ is exactly the set of local minima. The result which proves convergence to invariant points is called Salle’s Invariance Prinicple.

We assume the following

The process $x(t)$ , $t\in\mathbb R_+$ obeys the o.d.e.

$\frac{d x}{dt} = g(x(t))$

for $g:\mathbb R^d \rightarrow \mathbb R^d$ a continuous function.

$x(0)\in \mathcal X$ where $\mathcal X$ is a compact set such that if $x(0)\in \mathcal X$ then $x(t) \in \mathcal X$ for all $t$ .
The Lyapunov function $L:\mathbb R^d \rightarrow \mathbb R_+$ is a continuously differentiable function such that

$g(x) \cdot \nabla L(x) \leq 0,\qquad \forall x\in \mathcal X$

and we let

$\mathcal X^\star = \{ x\in \mathcal X : g(x) \cdot \nabla L(x) =0\}.$

La Salle’s Invariance Prinicple is as follows¹

Theorem 2. [La Salle’s Invariance Prinicple] As $t\rightarrow \infty$ , $x(t)$ convergences to $\mathcal X^\star$ uniformly over initial conditions $x(0)\in \mathcal X$ . That is: $\forall x(0) \in \mathcal X$ $\forall \epsilon >0$ $\exists\; T>0$ such that

$\min_{x^\star \in \mathcal X^\star} \big| x(T) - x^\star \big| < \epsilon\, .$

Proof. If $x(0)$ belongs to a compact set then $L(x(0)) \leq l$ for some $l\geq 0$ . For $\delta >0$ , we let $\mathcal X^\star(\delta)= \{x\in \mathcal X : -g(x) \cdot \nabla L(x) < \delta \}$ . Since $dL/dt = g(x) \cdot \nabla L(x)$ and $L(x_0)\leq l$ , for time $T > L/\delta$ is must be that $x(t)\in \mathcal X^\star(\delta)$ for all $t\geq T$ . [This is the main part of the argument completed.]

It is reasonable to assume that $x(t)\in \mathcal X^\star(\delta)$ for $\delta$ suitably small then $x(t)$ must be close to $\mathcal X^\star$ . This is true and to show this we prove the following claim: for $\epsilon >0$ $\exists \delta>0$ such that if $x(t) \in \mathcal X^\star (\delta)$ then $|x(T) - x^\star| < \epsilon$ for some $x^\star \in \mathcal X^\star$ . The proof is a fairly standard analysis argument: suppose the claim is not true, then there exists a sequence $x_n$ such that $-g(x_n) \cdot \nabla L(x_n) < 1/n$ and $|x_n - x^\star| \geq \epsilon$ for all $x^\star \in \mathcal X^\star$ . Since $\mathcal X$ is compact $x_{n_k} \rightarrow x_\infty$ over some subsequence $\{n_k\}_{k\in\mathbb N}$ . By continuity $g(x_\infty) \cdot \nabla L(x_\infty) =0$ and $|x_\infty - x^\star |\geq \epsilon$ for all $x^\star \in \mathcal X$ , which is a contradiction since $g(x_\infty) \cdot \nabla L(x_\infty) =0$ means $x_\infty \in \mathcal X^\star$ . This contradiction thus such thata there there exists a value $n^\star$ such that for all $x$ such that $-g(x)\cdot \nabla L(x) < \delta := 1/n^\star$ implies $\min_{x^\star} | x-x^\star| < \epsilon$ . QED.

Remark. We assume $x(t) \in \mathcal X$ for some compact set $\mathcal X$ . Notice a natural condition that implies compactness is that

$\liminf_{|x|\rightarrow\infty} L(x) = \infty\,.$

Specifically this implies that $\mathcal X_l := \{ x : L(x) \leq l\}$ is compact and by assumption that $L(x)$ is decreasing, if $x(0) \in \mathcal X_l$ then $x(t)\in X_l$ for all $t\in \mathbb R_+$ .

Convex Lyapunov Functions

Next if we assume a bit more about $L(x)$ we can ask more about the rate of convergence. We assume that

$L(x)$ is convex, $\min_x L(x)=0$
$\frac{dx}{dt}=-\gamma_t \nabla L(x(t))$
$||x_t||\leq D$ for some $D$

Note, before we proceed recall that $L(x)$ is a convex function iff

$\nabla L(x)(y-x)\leq L(y)-L(x) \leq \nabla L(y)(y-x)\, .$

Theorem 3. Given the assumptions itemized above,

$L(\bar x_T)\leq \frac{D}{T\gamma_T}$

where $\bar x_T = \frac{1}{T}\int_{0}^{T} x_t dt$ .

Proof. By Jensen’s inequality,

$\begin{aligned} L(\bar x_T) \leq \frac{1}{T} \int_0^T L(x(t))dt\, . \end{aligned}$

So we analyse the integral of $L(x(t))$ .

$\begin{aligned} \int_0^T L(x(t))dt = \int_0^T L(x(t))-L(x^\star)dt \leq \int_0^T \nabla L(x(t)) ( x(t)-x^\star ) dt\end{aligned}$

Notice that since $\frac{dx}{dt} = -\eta_t \nabla L(x(t))$ we have

$-\frac{1}{2\eta_t}\frac{d}{dt} ||x(t) - x^\star||^2 = \nabla L(x(t)) (x(t) - x^\star).$

Substituting this into the integral above gives

$\begin{aligned} \int_0^T L(x(t))dt &\leq - \int_0^T \frac{1}{2\eta_t}\frac{d}{dt} ||x(t) - x^\star||^2 dt \\ &= -\left[\frac{1}{2\eta_t}||x(t) - x^\star||^2 \right]_0^T + \int_0^T \frac{1}{2}||x(t) - x^\star||^2\frac{d \eta^{-1}}{dt} dt \\ & \leq \frac{D}{2\eta_T} + \frac{D}{2\eta_T} = \frac{D}{\eta_T}\end{aligned}$ Finally, applying this to our Jensen bound on $L(\bar x_T)$ gives

$L(\bar x_T) \leq \frac{D}{T\eta_T}\, .$

QED.

Exponential Convergence

We now place some assumptions where we can make further comments about rates of convergence.

If we further assume that $f$ and $L$ satisfy the conditions

$f(x)\cdot \nabla L(x) \leq -\gamma L(x)$ for some $\gamma>0$ .
$\exists$ $\alpha , \eta>0$ such that $\alpha || x^*-x||^\eta \leq L(x)-L(x^*)$ .
$L(x^*)=0$ .

Theorem 5. There exists a constants $\kappa,K>0$ such that for all $t\in{\mathbb R}_+$

$||x(t)-x^*|| \leq K e^{-\kappa t}.$

Proof.

$\frac{\mathrm{d} L(x(t)) }{\mathrm{d}t}= f(x(t))\cdot \nabla L(x(t)) \leq -\gamma L(x(t)).$

So long as $x(t) \neq x^*$ , $L(x(t))>0$ , thus dividing by $L(x(t))$ and integrating gives

$\log L(x(t)) - \log L(x(0)) = \int_0^t \frac{1}{L(x(s))}\frac{\mathrm{d} L(x(s)) }{\mathrm{d}t} ds \leq -\gamma t$

Rearrganging gives

$L(x(t)) \leq L(x(0)) e^{-\gamma t}$

This gives exponential convergence in $L(x(t))$ and quick application of the bound in the 2nd assumption gives

$|| x(t) -x^* ||\leq \frac{L(x(0))}{\alpha} e^{-\frac{\gamma}{\eta} t}.$

QED.

We can assume the 2nd assumption only holds on a ball arround $x^*$ . We have convergence from Theorem [Lya:ConvThrm], so when $x(t)$ is such that assumption 2 is satisfied we can then apply the same analysis for an exponential convergence rate. Ensuring the 2nd assumption locally is more easy to check, eg. check $L$ is positive definite at $x^*$ .

References

The Lyapunov method goes back to Lyapunov in (1892). Extensions were considered by La Salle. A widely used textbook treatment is Khalil. Applications to internet congestion control are given by Srikant. Theorem 3 is a differential equation version of the proof of Zinkevich (2003).

H. Khalil. Nonlinear Systems. Pearson Education. Prentice Hall, 2002. ISBN 9780130673893.

J. LaSalle. Some extensions of liapunov’s second method. IRE Transactions on circuit theory, 7(4):520–527, 1960.

A. M. Lyapunov. The general problem of the stability of motion. International journal of control, 55(3):531–534, 1992.

R. Srikant. The mathematics of Internet congestion control. Springer Science & Business Media, 2012.

Zinkevich, M. (2003). Online Convex Programming and Generalized Infinitesimal Gradient Ascent. ICML, 928–936.

The original result of La Salle proves point-wise convergence rather than uniform convergence, other than this the proof closely follows La Salle’s argument.↩

One thought on “Lyapunov Functions”

Pingback: ODE method for Stochastic Approximation – Applied Probability Notes

La Salle’s Invariance Principle

Convex Lyapunov Functions

Exponential Convergence

References

Share this:

Like this:

One thought on “Lyapunov Functions”

Leave a Reply Cancel reply