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 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.

翻译：我们引入了使用半无限期程序(SDP)放松最大 K- Cut 问题集成的新方法。 这种方法基于使用迭代线性优化来四舍五入 SDP 放松解决方案的新方法。 我们展示了 Max k- Cut SDP 放松的顶点, 与大多数 k 数据集的数据分隔相对应。 我们还显示 顶点是迭代线性优化的有吸引力的固定点。 这个迭代程序的每一步都解决了最接近的顶点问题的放松,并导致一个新的集群问题, 其基本组群在其中得到更明确的界定。 我们的实验显示, 与随机四舍五入的四舍五入相比, 使用固定点迭代点来四舍五入 将最大 k- Cut SDP 放松带来显著更好的结果 。