Dear All,
I have the following question.
Suppose we have a system of ODEs dx/dt=f(x) for which V(x) is a Lyapunov function, i.e. dV/dt < 0 and V>=0 with V(x^*)=0, where x^* is a fixed (or equilibrium) point of ODE.
If V(x) is also a convex function of x then the gradient descent equation dx/dt=-dV/dx will gives us a "lower bound on time it takes to converge to equilibrium" for any ODE, i.e. any f(x).
No, since the variational problem isn't well-defined. I'd suggest trying out some specific examples.
What you think may well be true, but what is it? The time to reach equilibrium is infinite, in all reasonable cases. So what is the ``time to converge to equilibrium''? I think you will be able to prove what you want, as soon as you actually know what you mean.
Dear Stam,
Thank your interest.
Could you please explain which part of my question is not well defined. I agree that "time to converge to equilibrium" is a bit vague, but , I guess, what I really mean by this is "how fast it converges to equilibrium", i.e. exponentially, as a power law, etc.
Example: Suppose we want to find a ground state (GS) of the ferromagnetic Ising model using single-flip algorithm, i.e. which flips only one spin at a time, then to get to GS using gradient descent on energy will take at most N (system size) steps and, I guess, it would take longer for any other single-flip algorithm.
Dear Leyvraz,
Thank you for interest in this question. Let me slightly reformulate the question. Suppose we have solutions x(t) and y(t) of two different ODEs with x(0)=y(0) which tend to the same equilibrium point x^* as t goes to infinity. One of these ODEs is a gradient descent on V and for the other V is a Lyapunov function. We want to know how fast is x(t), relative to y(t) ,converges to the equilibrium.
The variational problem in the statement of the question isn't well-defined, among other reasons, because the class of functions f(x) isn't defined, nor are they related to the function V(x). The Ising model isn't an example of the question, in fact, but describes a completely different kind of problem.
I think it is easy to construct counterexamples. For example, take a 1d system, with f(x)=-x, so we have exponential convergence. Of course, I could take a quadratic Lyapunov function, but there is no law against being stupid: I can also choose to take a quartic Lyapunov function. But then, Gradient along the quartic V(x) is much slower than just going along f(x), which is itself the gradient of a quadratic function.
So to make the theorem true, you must find a way to prohibit the kind of foolishness I have been suggesting. That it is foolishness is undeniable. But to find a way of saying exactly what you mean may not be trivial, and it will be an important part of proving what you want.
Dear Leyvraz,
The counterexample you constructed is very nice but, perhaps, it also suggests a solution. Suppose we want to find the minimum of a convex function V(x). Then the gradient descent dynamics is one way of doing this but one could also imagine that there are many ODEs that can take us to the "bottom of the well", V(x), for which V(x) is also a Lyapunov function. So, I guess, not use gradient in this case would be foolish.
If one fixes the well, i.e. the function V(x), then one is looking for the root of V'(x), assuming that V''(x)>0 at the root, of course. The fastest method is Newton-Raphson, i.e. x_(n+1)=x_n - V'(x_n)/V''(x_n), if one starts within the basin of attraction of the root. The reason is that the Lyapunov exponent of the Newton--Raphson recursion relation, *in one dimension*, is minus infinity, which expresses the fact that one gains a finite number of significant digits per iteration.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics