鞍点

第一部分：什么是鞍点？

1.1 几何直观：马鞍的形状

想象一个马鞍：

• 前后方向（马背的走向）：你坐在鞍上，前后移动会向下滑——这是极小值方向。
• 左右方向（马背的两侧）：你坐在鞍上，左右移动腿会向上翘——这是极大值方向。

这就是鞍点（Saddle Point）的几何原型：一个点，在某些方向是极小值，在另一些方向是极大值。

1.2 数学定义

对于一个函数 $F(x,y)$，点 $(x^{\ast },y^{\ast })$ 是鞍点，如果：

• 对于所有 $x$，$F(x^{\ast },y^{\ast })\le F(x,y^{\ast })$（固定 $y^{\ast }$，$x^{\ast }$ 是极小值）
• 对于所有 $y$，$F(x^{\ast },y^{\ast })\ge F(x^{\ast },y)$（固定 $x^{\ast }$，$y^{\ast }$ 是极大值）

用符号表示：

$$F(x^{\ast },y)\le F(x^{\ast },y^{\ast })\le F(x,y^{\ast })$$

这读作：$x^{\ast }$ 极小化 $F$，$y^{\ast }$ 极大化 $F$。

1.3 简单的函数例子

考虑 $F(x,y)=x^2-y^2$：

• 固定 $y$，只看 $x$：$F=x^2-\text{常数}$。这是一条开口向上的抛物线，$x=0$ 是极小值。
• 固定 $x$，只看 $y$：$F=\text{常数}-y^2$。这是一条开口向下的抛物线，$y=0$ 是极大值。

在 $(0,0)$ 处：

• 沿 $x$ 轴走，函数值上升（极小）
• 沿 $y$ 轴走，函数值下降（极大）

这就是一个标准的鞍点。

---

第二部分：约束优化中的鞍点问题

2.1 拉格朗日函数天然是鞍点

对于约束优化问题：

$$\underset{x}{\min }f(x)\text{s.t.}g(x)=0$$

我们构造拉格朗日函数：

$$\mathcal{L}(x,\lambda )=f(x)+\lambda g(x)$$

这个函数关于 $x$ 和 $\lambda$ 的极值性质是相反的：

• 对 $x$：我们要求极小值（找能量最低的位置）
• 对 $\lambda$：我们要求极大值（找最严苛的惩罚力度）

因此，拉格朗日函数的解 $(x^{\ast },{\lambda }^{\ast })$ 是一个鞍点：

$$\mathcal{L}(x^{\ast },\lambda )\le \mathcal{L}(x^{\ast },{\lambda }^{\ast })\le \mathcal{L}(x,{\lambda }^{\ast })$$

2.2 为什么对 $\lambda$ 是极大值？

直觉：$\lambda$ 是约束违反的惩罚价格。

如果我们对 $\lambda$ 求极小，那么 $\lambda$ 会变成负无穷，完全忽略约束。这显然不对。

如果我们对 $\lambda$ 求极大，$\lambda$ 会”尽力”惩罚约束违反，但又受到 $x$ 的反抗。这个博弈的平衡点，正是原约束优化问题的解。

2.3 一个具体的例子

问题：${\min }_x{x}^2$，约束 $x=3$。

拉格朗日函数：$\mathcal{L}(x,\lambda )=x^2+\lambda (x-3)$。

鞍点条件：

• 对 $x$ 极小：$\frac{\partial \mathcal{L}}{\partial x}=2x+\lambda =0\Rightarrow x=-\lambda /2$
• 对 $\lambda$ 极大：$\frac{\partial \mathcal{L}}{\partial \lambda }=x-3=0\Rightarrow x=3$

联立得：$x=3,\lambda =-6$。

验证鞍点性质：

• 固定 $\lambda =-6$：$\mathcal{L}(x,-6)=x^2-6x+18$，最小值在 $x=3$，值为 $9$。
• 固定 $x=3$：$\mathcal{L}(3,\lambda )=9+\lambda (0)=9$，对 $\lambda$ 是常数（这个例子中退化，但一般情况是极大值）。

---

第三部分：鞍点问题的数值求解

3.1 交替方向法

求解鞍点问题的经典方法是交替更新：

1. $x$-更新（极小化）：固定 $\lambda$，更新 $x$ 使 $\mathcal{L}$ 下降
2. $\lambda$-更新（极大化）：固定 $x$，更新 $\lambda$ 使 $\mathcal{L}$ 上升

这正是 XPBD 迭代的核心逻辑。

3.2 为什么叫“鞍点问题”而不是“优化问题”？

• 优化问题：通常指单纯的极小化或极大化。
• 鞍点问题：同时涉及极小化和极大化，不能用普通的梯度下降直接求解（因为在 $\lambda$ 方向上梯度下降会走错方向）。

3.3 梯度方向的决定

在鞍点 $(x^{\ast },{\lambda }^{\ast })$：

• ${\nabla }_x\mathcal{L}=0$
• ${\nabla }_{\lambda }\mathcal{L}=0$

但 Hessian 矩阵不定（有正特征值和负特征值），对应极小和极大方向。

---

第四部分：XPBD 中的鞍点问题

4.1 XPBD 的拉格朗日函数

在 XPBD 中，我们构造了：

$$\mathcal{L}(x,\lambda )=\frac{1}{2\Delta t^2}\Vert x-\tilde{x}{\Vert }_M^2+{\lambda }^{T}C(x)-\frac{\Delta t^2}{2}{\lambda }^T\alpha \lambda$$

这是一个鞍点问题：

• 对 $x$：极小化（找到能量最低的位置）
• 对 $\lambda$：极大化（找到最合适的约束冲量）

4.2 迭代过程对应鞍点下降

XPBD 的每次迭代：

1. 计算 $\Delta \lambda$（沿 $\lambda$ 的上升方向）
2. 更新 $\lambda \leftarrow \lambda +\Delta \lambda$
3. 计算 $\Delta x$（沿 $x$ 的下降方向）
4. 更新 $x\leftarrow x+\Delta x$

这正是在鞍点上的交替方向法。

4.3 为什么 XPBD 能收敛？

因为 XPBD 的迭代等价于在鞍点上执行邻近点算法（Proximal Point Algorithm）：

• $\lambda$ 的更新是增广拉格朗日乘子更新
• $x$ 的更新是带正则化的牛顿步

两者交替，保证收敛到鞍点。

---

第五部分：鞍点 vs 局部极小值

特征	局部极小值	鞍点
梯度	$\nabla F=0$	$\nabla F=0$
Hessian	正定（所有特征值 > 0）	不定（有正有负）
所有方向	都是上升	有上升有下降
优化方法	梯度下降	需要特殊方法（如交替方向）
例子	碗底	马鞍

---

第六部分：更广泛的视角

6.1 博弈论解释

鞍点问题是零和博弈的数学表达：

• 玩家 1（$x$）想最小化代价
• 玩家 2（$\lambda$）想最大化代价

纳什均衡点正是鞍点：任何一方单方面改变策略都不会获得更好的结果。

6.2 物理中的鞍点

• 过渡态理论：化学反应路径上的能量最高点（对反应坐标是极大，对其他振动模式是极小）
• 拉格朗日力学：作用量在真实路径上是鞍点（对位置变分极小，对时间变分极大？这涉及更深的变分原理）

---

总结

问题	答案
什么是鞍点？	在某些方向极小、某些方向极大的临界点
为什么约束优化产生鞍点？	拉格朗日函数对原变量极小、对偶变量极大
如何求解鞍点问题？	交替方向法：对 $x$ 下降，对 $\lambda$ 上升
XPBD 为什么是鞍点问题？	它求解的是惯性与弹性平衡的鞍点

一句话精要：

鞍点问题是同时涉及极小化和极大化的数学问题。在约束优化中，拉格朗日函数天然构成鞍点——我们想找到位置使能量最小，同时找到乘子使惩罚最大。XPBD 的迭代循环，正是在这个鞍点上交替地沿 $x$ 下降、沿 $\lambda$ 上升，直到到达平衡点。