11 - 4 - Time to Convergence and Optimality

Lyapunov Functions
"What we learn is that it's at least possible to put a Lyapunov function on a process and have it stop at somewhere less than the optimal point. Doesn't have to stop at the optimal point, it could stop below. That's what we're seeing here. So we've answered two important questions. The first one is: Okay, we know it goes to equilibrium, can we say how fast? And the answer is yes. And the better bound we get on k, and the better bound we get on the max, the more accurately we can put a restriction on how fast, how long it's going take. So, we can put a tighter bound on how long it's going to take, if we can estimate k accurately, and if we can estimate the maximum value accurately. We also learned that it can stop a lot faster than that, because of the fact that the process may not get to that optimum value." - Transcript from Scott Page Coursera
Resource Datasbase
Scott Page Model Thinking MOOC Course