最小化距离：距离公式

Question

我正在用C语言编写程序。我想通过最小化表达式来找到解决方案。

D1+D2+......+Dn

其中Di是通过距离公式计算两点之间的距离。上述表达式中包含x和y变量。

现在我将对这个表达式进行微分并找到解决方案。我的疑问是：

由于在上述表达式中，所有的Di都会出现为平方根，这将很难解决。因此，我们可以解决这个表达式：

D1^2 + D2^2 + ......+ Dn^2

通过上述表达式得到的答案会与解决原问题得到的答案相同吗？

我已经检查了一些简单的测试用例，例如n=2。它得出了正确的答案。这在一般情况下是否正确？

如果不是，该如何解决这个问题？

- nowonder

---

对于n=2，距离平方和最小的点位于它们中间的位置，而距离和在连接它们的线段任何位置都是最小的。我认为你需要测试 n=3。 - Steve Jessop

是的，现在我明白了问题。但正确的方法是什么？ - nowonder

使用其他度量标准怎么样？（而不是欧几里得距离） - Gacek

你能给我一些链接吗？我对其他任何指标都没有任何了解。 - nowonder

为什么需要找到这个质心 - 你确定你实际上需要找到这个确切的质心吗？我的意思是，仅使用平均点（在直线上投影）可能对许多目的来说是一个合理的近似，对吧？ - Eamon Nerbonne

Answer 1

即使对于二维距离，一般来说最小值的位置与 a + b 的最小值的位置不同。当然，在某些非常特定的问题中可能是正确的。如果你想找到一个反例，请注意平方会过度惩罚长距离；如果你构造一个包含至少一个长距离的最小值，那么平方和具有不同的最小值的可能性很大。

您要解决的问题是什么？当然，对于您的问题来说，区别可能并不重要；或者说，平方和的最小值是更便宜的问题，并且是最终解决方案的更容易的第一步近似。

显而易见的是，如果各种距离是无关联的，那么对于每个单独的距离来说，当距离为时平方数最小，因此不相关距离的总和在平方和最小时也是最小的。 编辑帖子更新：你正在寻找一个质心，限制条件是它位于特定的一条直线上。总的来说，你只有一个自由度，可以进行简单的微分。但是，在一般情况下，结果将具有分母中带有sqrt的分数总和；代数上解决这个问题是不可能的（据我所知）。我不是100%确定，但我认为你很幸运，因为你的距离和除了全局最小值以外没有局部最小值；在这种情况下，牛顿法将可靠且快速地收敛。

因此，如果您可以验证只有一个局部最小值的假设，那么您就可以成功了。即使您能够这样做，通过将您的牛顿方法计算的最小值与一些现实检查点（例如每个点在直线上的正交投影）进行比较，您也可以相当可靠地获得相当不错的结果，并检测到 何时 出现问题。

- Eamon Nerbonne

---

我不理解“过度惩罚”这个概念，请详细说明。我的问题是：给定平面上的一组点和一条直线（2-D平面）的方程式。现在，我需要找到直线上的一个点，使得所有给定点到该点的距离之和最小化。 - nowonder

在您提供的例子中，想象一条直线上有三个点。如果两个点在0处，而第三个点在10处（沿着这条直线测量），那么从重心到各点距离之和的最小值是在0处（因为到位于10处的那个点的距离是10，离0最远），但是距离平方和的最小值将在10/3处实现（可以试试）。 - Eamon Nerbonne

我应该尝试使用牛顿法来解决原方程吗？ - nowonder

AFAIK：就我所知。在这种情况下，这意味着我不确定;-)。牛顿法在概念上非常简单；维基百科（像往常一样）有一个公平的解释。无论如何，公式都是微不足道的。（请注意，牛顿法找到零交叉点，因此您需要将其应用于微分而不是原始距离和！）。如果牛顿法发散（我几乎可以肯定它不会对您的问题设置），（随机）梯度下降甚至更容易、更可靠，但速度较慢。 - Eamon Nerbonne

非常感谢您的努力。 - nowonder

Answer 2

你对于D1，D2，... Dn的起源有点不清楚，但我假设你有一组在x-y平面上的点P1，P2，...，Pn，并且你想找到一个点p0=(x0,y0)，使得每个点P1...Pn与p0之间的距离之和最小。因此，你的D1...Dn实际上是：

D1 = sqrt((x0-x1)^2 + (y0-y1)^2)
D2 = sqrt((x0-x2)^2 + (y0-y2)^2)
..
Dn = sqrt((x0-xn)^2 + (y0-yn)^2)

其中x1 .. xn和y1 ... yn已知，而x0, y0未知。您想要最小化D0：

D0 = D1+D2+......+Dn

如果这是正确的，那么您想要找到几何中位数。维基百科的文章应该能帮助您得出解决方案。

更新： 您在评论中指出点P0应该在给定的直线上（请将此添加到原始问题陈述中）。这意味着您可以将y0重写为x0的函数：

y0 = a*x0 + b

其中a和b是已知的。 这降低了距离函数的复杂度，并使得推导成为可能。

D1 = sqrt((x0-x1)^2 + (ax0+b-y1)^2)
D2 = sqrt((x0-x2)^2 + (ax0+b-y2)^2)
..
Dn = sqrt((x0-xn)^2 + (ax0+b-yn)^2)

但如果点数n不是非常大，我将在x接近x1 .. xn的平均值的线段区域内进行暴力搜索，以找到最小化D0的点x-，y0。

- jilles de wit

---

有趣。鉴于原帖中设定的特定限制条件以及他（理智地）对数学复杂解决方案的厌恶，我怀疑更简单的牛顿法或更稳健的梯度下降法解决方案更容易证明正确性并且速度也已经足够快 - 值得注意的是，维基百科声称无论如何都没有确切的代数解，你需要进行迭代细化。 - Eamon Nerbonne

那就是我所指的。维基百科页面中给出的迭代解决方案非常简单。由于这个问题的本质只有一个最小值，没有局部最小值，因此收敛是有保障的。顺便提一下，重心不等于几何中位数。 - jilles de wit

感谢您提供“几何中位数”这个确切的术语。我一直在搜索它的名称。 - nowonder

Answer 3

你的测试还不够充分。在一般情况下，将D1 + D2最小化并不等同于将D1^2 + D2^2最小化，尽管对于某些特定的D1和D2可能是相同的。

在你提醒我只关心平面距离之后进行编辑：

当D1和D2是几何平面上的距离时，在平面上使D1^2 + D2^2最小化的点也会使D1 + D2最小化，但是在三个点的情况下，这种情况会发生变化。

请尝试使用三个点(0,0)，(1,0)和(10, 0)： 将|x|+|x-1|+|x-10|最小化并不等同于将x^2+(x-1)^2+(x-10)^2最小化。

- Pascal Cuoq

---

我明白了。但既然这些是距离（均为正数），所以我认为可能是这种情况。但对于n=2，我测试了15-20个案例。它给出了正确的结果。解决上述问题的正确方法是什么？ - nowonder

但是Ewan在他的回答中说这是正确的。请澄清。 - nowonder

我认为伊万没有理解D1，... Dn在他的回答中不是独立变化的，而是作为相同x和y的函数变化。 - Pascal Cuoq

如何将最小化 D1+D2 转换为一条直线？ - nowonder

@nwonder 抱歉，我刚才想错了。请忘记我回答中的那部分内容 :) - Pascal Cuoq

Answer 4

你的问题是最小化一个由距离范数构成的目标函数。这些距离是欧几里得距离，因此表示两个向量之间的欧几里得范数。为了理解最小化sum(ai) over sum(ai^2)之间的差异，我建议你阅读维基百科关于范数的条目；底线是，请注意以下内容：

||x||2       <= ||x||1 <= sqrt(n)||x||2
||x||_\infty <= ||x||2 <= sqrt(n)||x||_\infty
||x||_\infty <= ||x||1 <=       n||x||_\infty

其中||x||2是欧几里得范数，||x||1是sum(abs(x1)+abs(x2)+...+abs(xn))，||x||_\infty是max(abs(x1),abs(x2),...,abs(xn))。在您的情况下，所有数字都是正数（您已经有了欧几里得范数，因此可以看到差异）。

阅读Golub和Van Loan的杰出著作Matrix Computations可能也会有所帮助（尽管更难以完全掌握）。

- Escualo

Answer 5

反例：

d1=1 & d2=10 (和为11 & 平方和为101)

d1=6 & d2=6 (和为12 & 平方和为72)

总和增加了，但平方和却减少了。

- Emilio M Bumachar