使到 n 个点的集合的欧氏距离之和最小的点

我有一组点W={(x1, y1), (x2, y2),..., (xn, yn)}在 2D 平面上。你能找到一种算法，将这些点作为输入并返回一个点(x, y)在 2D 平面上，距以下点的距离之和最小W？换句话说，如果

di = Euclidean_distance((x, y), (xi, yi))

我想最小化：

d1 + d2 + ... + dn

问题

您正在寻找几何中位数 https://en.wikipedia.org/wiki/Geometric_median.

一个简单的解决方案

该问题没有封闭式解决方案，因此使用迭代或概率方法。找到这个的最简单的方法可能是使用 Weiszfeld 的算法：

我们可以在 Python 中实现它，如下所示：

import numpy as np
from numpy.linalg import norm as npnorm
c_pt_old = np.random.rand(2)
c_pt_new = np.array([0,0])

while npnorm(c_pt_old-c_pt_new)>1e-6:
    num   = 0
    denom = 0
    for i in range(POINT_NUM):
        dist   = npnorm(c_pt_new-pts[i,:])
        num   += pts[i,:]/dist
        denom += 1/dist
    c_pt_old = c_pt_new
    c_pt_new = num/denom

print(c_pt_new)

Weiszfeld 的算法有可能不会收敛，因此最好从不同的起点运行多次。

通用解决方案

您还可以使用以下命令找到它二阶锥规划 (SOCP) https://en.wikipedia.org/wiki/Second-order_cone_programming。除了解决您的特定问题之外，这个通用公式还允许您轻松添加约束和权重，例如每个数据点位置的可变不确定性。

为此，您需要创建许多指示变量来表示建议的中心点和数据点之间的距离。

然后，您可以最小化指标变量的总和。结果如下

import cvxpy as cp
import numpy as np
import matplotlib.pyplot as plt

#Generate random test data
POINT_NUM = 100
pts       = np.random.rand(POINT_NUM,2)

c_pt      = cp.Variable(2)           #The center point we wish to locate
distances = cp.Variable(POINT_NUM)   #Distance from the center point to each data point

#Generate constraints. These are used to hold distances.
constraints = []                     
for i in range(POINT_NUM):
    constraints.append( cp.norm(c_pt-pts[i,:])<=distances[i] ) 

objective = cp.Minimize(cp.sum(distances))

problem = cp.Problem(objective,constraints)

optimal_value = problem.solve()

print("Optimal value = {0}".format(optimal_value))
print("Optimal location = {0}".format(c_pt.value))

plt.scatter(x=pts[:,0], y=pts[:,1], s=1)
plt.scatter(c_pt.value[0], c_pt.value[1], s=10)
plt.show()

SOCP 可用于求解器数量 https://www.cvxpy.org/tutorial/advanced/index.html#choosing-a-solver包括 CPLEX、Elemental、ECOS、ECOS_BB、GUROBI、MOSEK、CVXOPT 和 SCS。

我已经测试过，这两种方法在容差范围内给出了相同的答案。

魏斯菲尔德，E. (1937)。 “Sur le point pour lequel la somme des distances de n points donnes est minimise”。东北数学杂志。 43：355-386。