论文标题
通过半决赛编程和固定点迭代聚类
Clustering with Semidefinite Programming and Fixed Point Iteration
论文作者
论文摘要
我们介绍了一种新的方法，该方法使用半finite编程（SDP）放松最大K-CUT问题。该方法基于一种新的方法，用于使用迭代线性优化来整理SDP松弛的解决方案。我们显示了最大K-CUT松弛的顶点，对应于最多K集的数据分区。我们还显示顶点是迭代线性优化的有吸引力的固定点。这个迭代过程的每个步骤都解决了最接近的顶点问题的放松，并导致了一个新的聚类问题，其中更清楚地定义了下面的簇。我们的实验表明，与随机舍入相比，使用固定点迭代来填充最大K-CUT SDP弛豫，从而可以取得明显更好的结果。
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.
