The fact that the update rule keeps the centroid within the convex hull is indeed very important. If you look at Appendix E, the gradient descent methods don't have this property and are less stable than EMA updates.
Regarding simulated annealing, I agree with the parallel. You can see mini-batches as introducing noise in the beginning of the optimization to espace local minima and the step size decreasing through the training acts like a temperature in simulated annealing. Simulated annealing was already used for k-means with theoretical proof that you can reach the global minimum in enough epochs, but in practice, those methods are really slow. A paper that comes to mind is "A simulated annealing algorithm for the clustering problem" (https://www.sciencedirect.com/science/article/pii/0031320391...).
The parallel with expectation maximization is also coherent, though less straightforward to me. K-means can be viewed as a hard-assignment, special case of the Expectation-Maximization algorithm applied to Gaussian Mixture Models (GMMs).
If you have any other questions, I'll be happy to answer.
I agree that simulated annealing is perhaps the closest. The missing link, I suppose, is knowing what distribution you get by running the algorithm for a fixed temperature (alpha). But the method works even if you don't know all that really matters is that it converges to the distribution you want, which is neat! I might use that trick sometime.
The reason simulated annealing sprang to mind is that I've done something similar once where I tuned the temperature curve for a simulated annealing algorithm, but I couldn't find a general enough rule. So seeing someone do something similar is really neat!
There are some theoretical guarantees to be had if the update step can be recast into a MCMC update, or equivalent. And I think there's an expression for the optimal temperature at any point in time (same way you found it for alpha). Any idea if there is a useful description for the steady state distribution at a given alpha?