我有一个简单的机器学习问题：
我有 n (~110) 个元素，以及一个包含所有成对距离的矩阵。我想选择距离最远的 10 个元素。也就是说，我想
最大化：选择 10 个不同的元素。返回（这 10 个元素中所有配对的）最小距离。我的距离度量是对称的，并满足三角不等式。
我可以使用哪种算法？我的第一反应是这样做：
- 将 n 个元素聚类成 20 个簇。
- 将每个簇替换为该簇中距离原始 n 个元素的均值元素最远的元素。
- 使用暴力法解决剩余 20 个候选元素的问题。幸运的是，20 选 10 只有 184,756 种组合。
编辑：感谢 @人名 的深刻评论，将优化问题陈述中的“返回（距离）之和”更改为“返回最小距离”。
回答：
以下是一种通过采用凸松弛来解决此组合优化问题的方法。
设 D 是一个上三角矩阵，其上三角包含你的距离。即，当 i < j 时，D_i,j 是元素 i 和元素 j 之间的距离。（可以预见，对角线上将有零。）
然后，你的目标是最大化 x’*D*x，其中 x 是二元值的，其中 10 个元素设置为 1，其余设置为 0。（将 x 中的第 i 个条目设置为 1 相当于选择第 i 个元素作为你的 10 个元素之一。）
对于像这样的组合问题，要做的“标准”凸优化事情是放宽约束，使得 x 不需要是离散值。这样做会得到以下问题：
最大化 y’*D*y服从：0 <= y_i <= 1 对于所有 i， 1’*y = 10
这在本质上是一个二次规划。（如果我们用 D + D’ 替换 D，它将变成一个真正的二次规划，并且你得到的 y 应该没有什么不同。）你可以使用现成的 QP 求解器，或者直接将其插入到你选择的凸优化求解器中（例如 cvx）。
你得到的 y 不需要（也可能不会）是一个二元向量，但你可以通过多种方式将标量值转换为离散值。（最简单的方法可能是让 x 在 y_i 最高的 10 个条目中为 1，但你可能需要做一些更复杂的事情。）无论如何，你得到的 y 的 y’*D*y 确实为你提供了 x’*D*x 的最优值的上限，因此如果从 y 构造的 x 的 x’*D*x 非常接近 y’*D*y，你可以对你的近似感到非常满意。
如果这些内容有任何不清楚的地方，无论是符号还是其他方面，请告诉我。
