可能您要求证明中位数可以解决问题？好吧，这可以这样做：

目标是分段线性的，因此除了点$m=x_i$之外是可微的。目标的斜率是多少是某个点$m\neq x_i$？好吧，斜率是映射$m\mapsto |m-x_j|$这是$+1$（对于$m>x_j$）或$-1$（对于$m<x_j$）。因此，斜率表示有多少$x_i$小于$m$。如果有同样多的$x_i$小于和大于$m$（对于偶数个$x_i$），您会看到斜率为零。如果有奇数个$x_i$'s 那么斜率是“中间”一个左侧的-1和它右侧的+1，因此中间的一个是最小值。$-1$$+1$

将此问题推广到多维称为几何中值问题。正如大卫指出的那样，中位数是一维情况的解决方案；在那里，您可以使用比排序更有效的中值查找选择算法。排序是而选择算法是；只有在需要多个选择时，排序才会更有效，在这种情况下，您可以（昂贵地）排序一次，然后从排序列表中重复选择。$O(n\log n)$$O(n)$

几何中值问题的链接提到了多维案例的解决方案。

中位数方面的显式解决方案是正确的，但针对 mayenew 的评论，这是另一种方法。

众所周知，最小化问题，特别是后置问题，可以通过线性规划来解决。$\ell^1$

以下 LP 公式将适用于未知数的给定练习：$z_i,m$

显然必须等于至少，因此这要求将误差的绝对值之和最小化。$z_i$$|x_i - m|$

显示这一点的过度凸分析方法只是采用次梯度。事实上，这相当于其他一些涉及斜率的答案中使用的推理。

优化问题是凸的（因为目标是凸的并且没有约束。）另外，是$\left|m-x_i\right|$

-1 如果$m<x_i$

[-1,1] 如果$m=x_i$

+1 如果。$m>x_i$

由于当且仅当凸函数的子梯度包含零时，凸函数才被最小化，并且凸函数和的子梯度是子梯度的（集合）和，因此当且仅当是中位数 x_k 。$m$$x_1,\ldots x_k$