Clustering with Semidefinite Programming and Fixed Point Iteration. (arXiv:2012.09202v2 [math.OC] UPDATED)

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 SDP 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 procedure solves a …

arxiv clustering math programming