I have an algorithm to optimize a process. It is a discrete time algorithm. Every iteration of this algorithm changes the state of the process. I found a function, say $f(s)$, where $s$ is the state of the process, such that if $s_t,s_{t+1}$ are two consecutive states of the process given by my algorithm, then $f(s_t)>f(s_{t+1})+c$, where $c>0$ is a constant. And I know $f()$ is lower bounded. Thus I can prove that the algorithm halts.

My question is about terminology. Is this function $f()$ a Lyapunov function to the process? If not what is the word I can use to describe this function $f()$?

It is a function I derived by trial and error.


It is not necessarily a discrete-time Lyapunov function. For a function, $V: \mathbb{R}^n\rightarrow \mathbb{R}$, to be a discrete-time Lyapunov function, at least for stability, you must satisfy the following:

  1. Let 0 be the equilibrium point, then V(0)=0,
  2. V(s)>0 for all $s\neq 0$, and
  3. $\Delta V(s_k)=V(s_{k+1})-V(s_{k})\leq0$ for all $k$.

Adding the conditions that

  1. If $\Delta V(s_k)<0$, then you get asymptotic stability.
  2. If $\lim\limits_{||s_k||\rightarrow\infty} V(s_k)=\infty$, then you get global asymptotic stability.

Your $f$ only satisfies the third condition, but does not provide what $V$ is.

As for instability, you may want to look at Chetaev's theorem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.