Is this a discrete time Lyapunov function?

Question

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.

Answer 1

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.