学习笔记

Appearance

高维空间中子空间上费马点的推广 ​

问题重述 ​

设 $\lbrace X_1, X_2, \dots, X_n\rbrace \subset \mathbb{R}^d$是给定的$n$ 个点。
$L \subset \mathbb{R}^d$ 是一个仿射子空间（例如直线、平面或超平面）。
求一点 $P^* \in L$，使得距离之和
$$ S(P) = \sum_{i=1}^n \Vert{}P - X_i\Vert $$ 在 $L$ 上达到最小。分析该点的存在性、唯一性及求解方法。

原平面三点到 $x$轴的问题是$d=2$，$n=3$，$L$为$x$ 轴的特例。

1. 存在性 ​

  • $S(P)$ 是 连续函数。
  • 当 $\Vert{}P\Vert \to +\infty$且$P \in L$ 时，$S(P) \to +\infty$（强制函数）。
  • $L$ 是闭集，利用强制性与连续函数性质，最小值必在某个有界闭区域内取得。

结论：对任意 $n$个点、任意仿射子空间$L$，最小值点 $P^*$ 恒存在。

2. 唯一性分析 ​

2.1 凸性 ​

每个函数 $f_i(P) = \Vert{}P - X_i\Vert$是$\mathbb{R}^d$上的凸函数（在$P \neq X_i$处光滑，在$X_i$ 处不可微）。
因此 $S(P)$是凸函数。限制在仿射子空间$L$ 上，$S|_L$ 仍为凸函数。

2.2 严格凸的充要条件 ​

$S|_L$在$L$上严格凸$\iff$ 最小值点唯一。

判定准则：

若存在一个方向 $v \in \operatorname{Dir}(L)$（$v \neq 0$），使得所有点 $X_i$都位于某条平行于$v$的直线$P + \mathbb{R}v$上，且这些点在直线上的投影全在$L$上，则$S|_L$沿$v$ 方向是分段线性的，可能不严格凸；
否则，$S|_L$ 严格凸，最小值点唯一。

等价表述：

  • $L$ 是一条直线（$\dim L = 1$）：
    $S(p)$是单变量函数，严格凸$\iff$ 至少有一个点不在该直线上。
    若所有点均在这条直线上，则问题退化为在一维直线上求若干点的中位数：

    • $n$奇数$\implies$ 最小值点唯一（中间点）。
    • $n$偶数$\implies$ 最小值点组成一个闭区间（中间两点之间），此时有无穷多解。

  • $L$ 是一般仿射子空间：
    若存在非零向量 $v \in \operatorname{Dir}(L)$使得所有$X_i$到$L$的正交投影落在与$v$ 平行的一条直线上，则沿该方向可能失去严格凸性，最小值点集合可能是一条线段（或更高维的凸集）。
    最典型的退化情形：所有点 $X_i$本身都位于一个与$L$平行的低维仿射子空间内，且在该子空间中它们的分布使得限制在$L$ 上的目标函数沿某些方向为线性。

实际应用中绝大多数非退化情形：只要点不是人为地全部落在 $L$或与$L$ 平行的某条直线上，$S|_L$ 即为严格凸，最小值点唯一。

3. 最优性条件（力平衡方程） ​

3.1 可微情况 ​

设 $P^*$不是任何$X_i$点，则$S$在$P^*$ 处可微。最小值点满足：$S$在$P^*$处的梯度向量$\nabla S(P^*)$垂直于$L$的切空间$V$。
即 $$ \operatorname{Proj}_{V}\left( \sum_{i=1}^n \frac{P^* - X_i}{\Vert{}P^* - X_i\Vert} \right) = 0. $$

几何意义：从 $P^*$指向所有给定点的单位向量之和在$L$ 上的投影为零。

3.2 不可微情况（$P^* = X_k$ 某点） ​

此时使用次梯度条件：
存在次梯度向量 $g \in \partial S(P^*)$，满足 $g \perp V$。
次梯度集合为 $$ \partial S(P^*) = \sum_{i \neq k} \frac{P^* - X_i}{\Vert{}P^* - X_i\Vert} + B(0,1), $$ 其中 $B(0,1)$是$\mathbb{R}^d$中的单位闭球。条件等价于：存在一个模长$\le 1$的向量$u$，使得 $$ \sum_{i \neq k} \frac{P^* - X_i}{\Vert{}P^* - X_i\Vert} + u \in V^\perp. $$

这种情形只在某些特殊构型下出现，称为点重合解。

4. 特例与退化情形 ​

4.1 $L$ 为一条直线 ​

设 $L = \lbrace P_0 + t v \mid t \in \mathbb{R}\rbrace $，$\Vert{}v\Vert=1$。目标化为单变量函数 $$ S(t) = \sum_{i=1}^n \sqrt{ \Vert{}P_0 - X_i\Vert^2 - \langle P_0 - X_i, v \rangle^2 + (t - t_i)^2 }, $$ 其中 $t_i = \langle X_i - P_0, v \rangle$。

  • 若存在某个 $i$使得$X_i \notin L$，则 $S(t)$ 严格凸，最小值点唯一，可用二分法或牛顿法求根。
  • 若所有 $X_i \in L$，则 $S(t) = \sum |t - t_i|$，最小值点为 $\lbrace t_i\rbrace $ 的中位数（偶数个时为区间）。

4.2 $L$ 为超平面 ​

高维费马点限制在超平面上。存在唯一解的一般条件是：点集 $\lbrace X_i\rbrace $不全落在与$L$ 平行的某条直线上。最优条件为：所有单位向量之和垂直于该超平面。

4.3 $L$为全空间$\mathbb{R}^d$ （无约束费马点） ​

此时 $\operatorname{Proj}_V$ 变为全空间，条件为 $$ \sum_{i=1}^n \frac{P^* - X_i}{\Vert{}P^* - X_i\Vert} = 0. $$ 这是经典的 Fermat-Weber 问题，解称为几何中位点。当点不共线时解唯一。

5. 数值求解方法 ​

由于一般无解析解，可选用：

  1. Weiszfeld 算法及其变种
    适用于无约束或带子空间约束的情况。对约束在 $L$上的情形，可先投影到$L$ 的坐标系中迭代。

  2. 凸优化方法
    问题为凸且非光滑，可用 次梯度法 或 截断牛顿法 求解。

  3. 一维搜索（$L$ 为直线时）
    直接使用黄金分割、二分法（利用导函数单调性）快速收敛到唯一解。

6. 唯一性结论总结 ​

条件最小值点唯一性
所有点 $\lbrace X_i\rbrace $均位于$L$ 中，且沿某些方向对称分布可能不唯一（退化为中位数区间）
至少有一个点不在 $L$中，或点虽在$L$中但使得$S\Vert_L$ 严格凸唯一
$n$为奇数且所有点在$L$ 的一条直线上唯一（中位数点）
$n$为偶数且所有点在$L$ 的一条直线上无穷多解（中位区间）

原问题 $n=3$，$L$为$x$轴，三点即使全在$x$轴上，三点中位数也唯一，故恒满足“有且仅有一个$P$”。推广后需根据上述条件判断唯一性。

结论：高维多点下，限制在子空间上的距离和最小点始终存在；在非退化条件下唯一，且满足投影单位向量之和为零的最优性条件。

原问题见:平面上任取三点到 x 轴上一点距离之和最小问题

相关笔记 ​

基于 Obsidian 整理 · 由 VitePress 构建

学习笔记