Convergence analysis of a global optimization algorithm for centroid-based clustering

The clustering problem is to partition a set of points into a number of groups based on a notion of closeness or similarity. It is well known that typical cost functions minimized by clustering algorithms can have many local minima. In this paper, we describe a global optimization algorithm that evaluates the cost function at the central points of a rectangular subdivision of the domain. The algorithm works for cost functions satisfying a smoothness assumption and we prove that it converges to the global minimum in the limit as the number of iterations goes to infinity. Furthermore, we establish the convergence rate. We numerically compare our algorithm with alternatives such as classic K-means and K-means++, and simulated annealing and genetic algorithms.