Lyapunov functions

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

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

<img class=” aligncenter” title=”\label{Lya:Lya} f(x)\cdot \nabla L(x)

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

Thrm [Lya:ConvThrm] 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,

<img class=” aligncenter” title=”\frac{d L(x(t))}{dt} = f(x(t))\cdot \nabla L(x(t))

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^*$ .

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

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$ .

then there exists a constants $\kappa,K>0$ such that for all $t\in{\mathbb R}_+$

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

$\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}.$

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^*$ .

Share this:

Leave a comment Cancel reply