Clustering with Semidefinite Programming and Fixed Point Iteration
This work provides an improved clustering algorithm for practitioners and researchers working with partitioning data, offering a more effective way to solve the Max k-Cut problem.
This paper proposes a new clustering method that leverages a semidefinite programming (SDP) relaxation of the Max k-Cut problem. By using iterated linear optimization for rounding the SDP solution, the method achieves significantly better clustering results compared to randomized rounding.
We introduce a novel method for clustering using a semidefinite programming (SDP) relaxation of the Max k-Cut problem. The approach is based on a new methodology for rounding the solution of an SDP relaxation using iterated linear optimization. We show the vertices of the Max k-Cut relaxation correspond to partitions of the data into at most k sets. We also show the vertices are attractive fixed points of iterated linear optimization. Each step of this iterative process solves a relaxation of the closest vertex problem and leads to a new clustering problem where the underlying clusters are more clearly defined. Our experiments show that using fixed point iteration for rounding the Max k-Cut SDP relaxation leads to significantly better results when compared to randomized rounding.