  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 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. We interpret the
process of fixed point iteration with linear optimization as repeated
relaxations of the closest vertex problem. 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.
