python - 最小化与 n 维点集的欧几里得距离

Question

让我们看看 nd 空间中的 m 个点 - （这里是 3-d 空间中 4 个点的解决方案：minimize distance from sets of points）

a= (x1, y1, z1, ..)

b= (x2, y2 ,z2, ..)

c= (x3, y3, z3, ..)
.
.

p= (x , y , z, ..)

Find point q = c1* a + c2* b + c3* c + ..

where c1 + c2 + c3 + .. = 1
and  c1, c2, c3, .. >= 0
s.t.
euclidean distance pq is minimized.

可以使用哪些算法？想法或伪代码就足够了。（优化性能在这里是一个大问题。具有所有顶点和变化系数的蒙特卡罗方法也可以提供解决方案。）

标签： pythongeometryprojectionalgebra

Answer 1

我们可以通过从所有其他点中减去 p 来假设 p = 0。那么问题是最小化有限点集（即多面体）的凸包上的范数。

关于这个问题有几篇论文。看起来像 Kazuyuki Sekitani 和 Yoshitsugu Yamamoto 的“一种用于在多面体中找到最小范数点和两个多面体中的一对最近点的递归算法”是一个很好的算法，并对问题的先前解决方案进行了简短的调查。它位于付费墙后面，但如果您可以访问大学图书馆，您可以下载一份副本。

一旦你通过了符号，他们给出的算法就相当简单了。P 是点的有限集。C(P) 是它的凸包。Nr(C(P)) 是最小范数的唯一点，这是您想要找到的。

步骤 0：从有限点 P 的凸包 C(P) 中选择一个点 x_0。他们建议选择 x_0 作为 P 中具有最小范数的点。令 k=1。

现在循环：

第 1 步：设 a_k = min {x^t_{k-1} p | p 在 P} 中。这里 x^t_{k-1} 是 x_{k-1} 的转置（所以被最小化的函数只是一个点积，因为 p 范围在你的有限集 P 上）。如果|x_{k-1}|^2 <= a_k，那么答案是x_{k-1}，停止。

第 2 步：P_k = {p | p 中的 p 和 x^t_{k-1} = a_k}。P_k 是最小化步骤 1 中表达式的 P 的子集。在此集合 P_k 上递归调用算法，并令结果为 y_k = Nr(C(P_k))。

第 3 步：b_k = min{y^t_k p | p in P\P_k}，y_k 与补集 P\P_k 中的点的点积的最小值。如果 |y_k|^2 <= b_k 那么 y_k 就是答案，停止。

第 4 步：s_k = max{s| [(1-s)x_{k-1} + sy_k]^t y_k <= [(1-s)x_{k-1} + sy_k]^tp 对于 P\P_k} 中的每个 p。令 x_k = (1-s_k) x_{k-1} + s_k y_k，令 k=k+1，返回步骤 1。

步骤 4 中有一个明确的 s_k 公式：

s_k = min{ [x^t_{k-1} (p-y_k)]/[(y_k-x_{k-1})^t (y_k-p)] | p 在 P\P_k 和 (y_k - x_{k-1})^t (y_k-p) > 0 }

论文中有一个证明，s_k 具有必要的属性，算法在有限次数的操作后终止，并且结果确实是最优的。

请注意，您应该在比较中添加一些容差，否则舍入错误可能会导致算法失败。关于数值稳定性有很多讨论，详见论文。

他们没有对算法的计算复杂度给出完整的分析，但他们确实证明了在二维情况下最多为 O(m^2)（m 是 P 中的点数），并且他们已经做到了数值实验给人的印象是它在时间上是亚线性的，是 m 的函数，尺寸固定。我对这种说法持怀疑态度。在没有详细分析的情况下，我建议您尝试使用典型数据进行一些实验，以了解该算法对您的执行情况。