第四章：投影梯度法

4.0.1 定义与基本性质#

设 $\Omega \subseteq \mathbb{R}^n$ 为非空闭凸集。对任意 $x \in \mathbb{R}^n$，$x$ 到 $\Omega$ 上的欧几里得投影定义为

即 $\Omega$ 中距离 $x$ 最近的点。闭凸集上的投影具有两个关键性质，它们贯穿本章所有收敛性证明。

性质一：存在唯一性。 由 $\Omega$ 的非空闭凸性和 $\|\cdot\|^2$ 的严格凸性，投影点 $P_\Omega(x)$ 存在且唯一。

性质二：非扩张性。 对任意 $u, v \in \mathbb{R}^n$，

投影不会拉大两个点之间的距离。更强地，$P_\Omega$ 是稳定非扩张（firmly nonexpansive）的，即

非扩张性是投影梯度法收敛性分析的基石：它允许我们在估计 $\|x^{k+1} - x^*\|$ 时”去掉投影”，将问题简化为分析梯度步的行为。

性质三：变分不等式刻画。 $P_\Omega(x)$ 可以等价地通过如下不等式刻画——对任意 $y \in \Omega$，

几何含义：从 $P_\Omega(x)$ 指向 $x$ 的方向与从 $P_\Omega(x)$ 指向 $\Omega$ 中任意点 $y$ 的方向夹角不小于 $90°$。这一性质在 4.3 节外梯度法的证明中起关键作用。

4.0.2 常见集合上的投影公式#

投影算子的抽象定义需要求解一个约束优化子问题，但在许多常见集合上，投影具有显式的闭式公式。下面逐一推导。

欧几里得球。 设 $\Omega = \{y \in \mathbb{R}^n \mid \|y - c\| \leq r\}$ 为以 $c$ 为中心、$r$ 为半径的球。投影为

推导。 当 $x$ 已在球内时，$x$ 本身就是 $\Omega$ 中距离自己最近的点，投影不变。当 $x$ 在球外时，需要求解 $\min_{y} \|y - x\|^2 \;\text{s.t.}\; \|y - c\| \leq r$。由于目标函数是以 $x$ 为中心的球对称函数，最优解必然在从 $c$ 到 $x$ 的射线上——偏离这条射线只会增大到 $x$ 的距离。因此最优解的形式为 $y^* = c + t(x - c)$，其中 $t > 0$。约束 $\|y^* - c\| = t\|x - c\| \leq r$ 要求 $t \leq r/\|x - c\|$。在这个范围内，$\|y^* - x\|^2 = (1-t)^2\|x - c\|^2$ 关于 $t$ 单调递减，所以取 $t = r/\|x - c\|$，即 $y^* = c + r \cdot \frac{x - c}{\|x - c\|}$。投影的操作是将 $x - c$ 方向上的分量缩放到半径 $r$，保持方向不变。

半空间。 设 $\Omega = \{y \mid a^\top y \leq b\}$，其中 $a \neq 0$。投影为

推导。 当 $x$ 满足约束时投影不变。当 $a^\top x > b$ 时，$x$ 在超平面 $a^\top y = b$ 的外侧。半空间的边界是超平面 $H = \{y \mid a^\top y = b\}$，而 $a$ 是 $H$ 的法向量。从 $x$ 到 $H$ 的最短距离由垂直投影给出：沿法向量 $a$ 的方向移动到超平面上。设 $y^* = x - \lambda a$，要求 $a^\top y^* = b$，即 $a^\top x - \lambda \|a\|^2 = b$，解得 $\lambda = (a^\top x - b)/\|a\|^2$。由于半空间包含整个超平面，而超平面上距 $x$ 最近的点就是垂足，所以垂足也是到半空间的投影。投影的操作是沿法向量方向将违反约束的量”减掉”。

非负正象限。 设 $\Omega = \mathbb{R}^n_+ = \{y \mid y_i \geq 0,\; i = 1, \ldots, n\}$。投影逐分量独立进行：

推导。 非负正象限可以写为 $n$ 个半空间的交集：$\Omega = \bigcap_{i=1}^n \{y \mid -e_i^\top y \leq 0\}$，其中 $e_i$ 是第 $i$ 个标准基向量。由于这些约束作用在不同的分量上，投影问题 $\min_y \|y - x\|^2 = \min_y \sum_i (y_i - x_i)^2 \;\text{s.t.}\; y_i \geq 0$ 可以分解为 $n$ 个独立的一维问题：$\min_{y_i \geq 0} (y_i - x_i)^2$。每个子问题的解为 $y_i^* = \max(x_i, 0)$：若 $x_i \geq 0$ 则 $y_i^* = x_i$（已在可行域内）；若 $x_i < 0$ 则 $y_i^* = 0$（边界上距 $x_i$ 最近的可行点）。投影的操作就是将所有负分量截断为零。这是带非负约束的优化（如非负矩阵分解）中最常用的投影。

概率单纯形。 设 $\Omega = \Delta_n = \{y \in \mathbb{R}^n \mid y_i \geq 0,\; \sum_i y_i = 1\}$。与前面三个集合不同，概率单纯形上的投影没有逐分量独立的闭式解——等式约束 $\sum_i y_i = 1$ 耦合了所有分量。

投影可以通过 $O(n \log n)$ 的排序算法高效计算。其思路来自 KKT 条件的分析。投影问题为 $\min_y \|y - x\|^2 \;\text{s.t.}\; \sum_i y_i = 1,\; y_i \geq 0$。引入等式约束的 Lagrange 乘子 $\tau$ 和不等式约束的乘子 $\lambda_i \geq 0$，KKT 条件给出 $y_i - x_i + \tau - \lambda_i = 0$ 以及互补松弛条件 $\lambda_i y_i = 0$。当 $y_i > 0$ 时 $\lambda_i = 0$，得 $y_i = x_i - \tau$；当 $y_i = 0$ 时 $\lambda_i = \tau - x_i \geq 0$。合并两种情况，最优解为 $y_i = \max(x_i - \tau, 0)$，其中 $\tau$ 由等式约束 $\sum_i \max(x_i - \tau, 0) = 1$ 确定。

具体地，将 $x$ 的分量降序排列为 $x_{(1)} \geq x_{(2)} \geq \cdots \geq x_{(n)}$，令

则阈值 $\tau = \frac{1}{\rho}\left(\sum_{i=1}^{\rho} x_{(i)} - 1\right)$，投影为 $[P_\Omega(x)]_i = \max(x_i - \tau, 0)$。

这个公式的直觉是：先将所有分量平移同一个量 $\tau$（使总和调整为 $1$），然后将变为负数的分量截断为零；$\rho$ 标识了哪些分量在平移后仍为正。排序的作用是从大到小逐步确定哪些分量会被截断。概率单纯形上的投影在强化学习的策略更新、注意力机制的归一化等场景中频繁出现。

4.1.1 迭代格式与不动点#

取固定步长 $\alpha_k \equiv 1$，得到最简单的基本投影梯度法：

步长取 $1$ 的目的是在最简设定下建立收敛性理论，变步长推广留给 4.2 节。完整的算法流程如下。

算法 4.1：基本投影梯度法

输入： 初始点 $x^0 \in \Omega$，最大迭代次数 $K$，收敛阈值 $\varepsilon > 0$

for $k = 0, 1, 2, \ldots, K-1$ do

$\quad$ 1. 计算梯度：$g^k = \nabla f(x^k)$

$\quad$ 2. 梯度步：$z^k = x^k - g^k$

$\quad$ 3. 投影步：$x^{k+1} = P_\Omega(z^k)$

$\quad$ 4. 收敛检查：若 $\|x^{k+1} - x^k\| < \varepsilon$，则终止

end for

输出： $x^{k+1}$

最优解 $x^*$ 是该迭代的不动点：

这一性质是收敛性证明的起点——它把”收敛到最优解”转化为”收敛到不动点”。不动点条件的成立可以从最优性的一阶条件推出：$x^*$ 是约束优化问题的最优解当且仅当对所有 $y \in \Omega$ 成立 $\langle \nabla f(x^*),\; y - x^*\rangle \geq 0$，这恰好等价于 $x^* = P_\Omega(x^* - \nabla f(x^*))$（利用 4.0.1 节的变分不等式刻画）。

4.1.2 Q-线性收敛定理#

定理 4.1. 设以下条件成立：

1. 强单调性. $\nabla f$ 关于 $\Omega$ 强单调，即存在 $\mu > 0$，使得对任意 $x, y \in \Omega$，

2. Lipschitz 连续性. $\nabla f$ Lipschitz 连续，即存在 $L > 0$，使得对任意 $x, y$，

3. 参数关系. $L^2 < 2\mu$，且 $L \neq \mu$。

则基本投影梯度法生成的序列 $\{x^k\}$ Q-线性收敛到 $x^*$，收敛因子为

Q-线性收敛意味着误差以几何级数衰减：$\|x^k - x^*\| \leq c^{k/2}\|x^0 - x^*\|$，是很强的收敛性保证。

条件 $L^2 < 2\mu$ 的含义。 这个条件限制了问题的条件数 $\kappa = L/\mu$ 不能太大。条件数衡量目标函数最陡方向与最平方向之间的曲率差异。从 Hessian 的角度，$f$ 的 Hessian 特征值被夹在 $[\mu, L]$ 之间，$\kappa$ 就是最大与最小特征值之比。

考虑二次函数 $f(x) = \frac{1}{2} x^\top A x$ 在 $\mathbb{R}^2$ 上的情形，$A$ 的特征值为 $\mu$ 和 $L$。当 $\kappa = L/\mu$ 接近 $1$ 时，$A$ 接近数量矩阵，$f$ 的等高线接近正圆——各方向曲率相近，固定步长 $1$ 在所有方向上都是合理的步长选择。当 $\kappa$ 增大时，等高线变为狭长的椭圆——沿长轴方向曲率小（需要大步长），沿短轴方向曲率大（需要小步长），一个固定步长无法兼顾两个方向。由 $L^2 < 2\mu$ 可以推出 $\kappa^2 < 2\kappa$（利用 $L \geq \mu$），即 $\kappa < 2$，等高线的椭圆长短轴之比不能超过 $2$。

举一个具体的例子来感受这个条件有多严格。条件 $L^2 < 2\mu$ 等价于 $L < \sqrt{2\mu}$。对 $\mu = 1$ 而言，要求 $L < \sqrt{2} \approx 1.414$，即条件数 $\kappa = L/\mu < 1.414$。设 $A = \text{diag}(1, 1.4)$（$L = 1.4$，$\kappa = 1.4$），则 $L^2 = 1.96 < 2 = 2\mu$，条件刚好满足，收敛因子 $c = 1 + 1.96 - 2 = 0.96$，收敛较慢。若 $A = \text{diag}(1, 1.5)$（$L = 1.5$，$\kappa = 1.5$），则 $L^2 = 2.25 > 2 = 2\mu$，条件已经不满足——即使条件数只有 $1.5$，固定步长 $1$ 也无法保证收敛。等高线的椭圆形变必须非常小。

实际中大多数优化问题的条件数远大于 $2$（例如线性回归中设计矩阵的条件数可达 $10^3$ 量级），因此基本投影梯度法的适用范围有限。这正是 4.2 节引入变步长的动机：通过可调节的步长 $\alpha_k$ 来适应不同方向的曲率差异，从而摆脱对条件数的苛刻限制。

4.1.3 收敛性证明#

需要证明存在 $c \in (0,1)$，使得 $\|x^{k+1} - x^*\|^2 \leq c\,\|x^k - x^*\|^2$。

第一步：非扩张性去投影. 利用 $x^*$ 的不动点性质，

投影算子 $P_\Omega$ 是非扩张的（4.0.1 节性质二），去掉投影得

第二步：展开平方范数. 将右端展开为

到此只用了非扩张性，尚未用强单调性和 Lipschitz 连续性。

第三步：利用条件估计后两项. 目标是把 $(\star)$ 的后两项归结为 $\|x^k - x^*\|^2$ 的倍数。

由 Lipschitz 连续性（条件 2），第三项满足

由强单调性（条件 1），第二项中的内积满足

注意第二项前有系数 $-2$，内积下界取负后变为上界。代入 $(\star)$ 得

第四步：合并得收敛因子. 合并同类项，

令 $c = 1 + L^2 - 2\mu$。Q-线性收敛要求 $0 < c < 1$。

• $c < 1$：等价于 $L^2 < 2\mu$，即条件 3 的第一部分。
• $c > 0$：注意 $1 + L^2 - 2\mu = (L^2 - \mu^2) + (\mu - 1)^2$。由 $L \neq \mu$ 且 $L \geq \mu$（下文证明），有 $L^2 - \mu^2 > 0$，又 $(\mu - 1)^2 \geq 0$，故 $c > 0$。

若 $L = \mu$，则 $c = (\mu - 1)^2$；再若 $\mu = 1$，则 $c = 0$，收敛因子退化。排除 $L = \mu$ 正是为了避免这种退化。$\blacksquare$

4.1.4 Lipschitz 常数与强单调系数的关系#

从 Hessian 的角度，$f$ 的 Hessian 的所有特征值被夹在 $[\mu, L]$ 之间：

因此 $L \geq \mu$ 天然成立。也可以不依赖二阶信息，直接用 Cauchy-Schwarz 不等式证明。

命题 4.2. 若 $\nabla f$ 同时满足强单调性（参数 $\mu$）和 Lipschitz 连续性（参数 $L$），则 $L \geq \mu$。

证明. 由强单调性，

对左端用 Cauchy-Schwarz 不等式，再用 Lipschitz 连续性：

$x \neq y$ 时两端除以 $\|x - y\|^2$ 得 $L \geq \mu$。$\blacksquare$

$L = \mu$ 对应 Hessian 为常数矩阵 $\mu I$ 的特殊情况，即目标函数为强凸二次函数。

4.2.1 迭代格式与收敛条件#

变步长投影梯度法的迭代格式为

其中 $\alpha_k > 0$ 可以每步不同。完整算法如下。

算法 4.2：变步长投影梯度法

输入： 初始点 $x^0 \in \Omega$，步长序列 $\{\alpha_k\}$，最大迭代次数 $K$，收敛阈值 $\varepsilon > 0$

for $k = 0, 1, 2, \ldots, K-1$ do

$\quad$ 1. 计算梯度：$g^k = \nabla f(x^k)$

$\quad$ 2. 梯度步：$z^k = x^k - \alpha_k g^k$

$\quad$ 3. 投影步：$x^{k+1} = P_\Omega(z^k)$

$\quad$ 4. 收敛检查：若 $\|x^{k+1} - x^k\| < \varepsilon$，则终止

end for

输出： $x^{k+1}$

收敛需要两个条件：

条件一：余强制性（cocoercivity）. $\nabla f$ 满足余强制条件，即存在 $\delta > 0$，使得对任意 $x, y$，

常数 $\delta$ 称为余强制系数。余强制性比单调性更强：内积不仅非负，还以梯度差范数的平方为下界。余强制性蕴含 Lipschitz 连续性，且 Lipschitz 常数 $L = 1/\delta$。

条件二：步长约束.

这个约束并非人为规定，而是在收敛性证明中自然产生的要求。

4.2.2 Fejér 单调性的建立#

证明的核心策略是建立 Fejér 单调性：序列 $\{x^k\}$ 到最优解 $x^*$ 的距离单调递减。

第一步：非扩张性去投影. $x^*$ 满足不动点条件 $x^* = P_\Omega(x^* - \alpha_k \nabla f(x^*))$。利用 $P_\Omega$ 的非扩张性去掉投影，

第二步：展开平方范数.

第三步：用余强制条件处理内积项. 将余强制条件代入最后一项的内积，

注意前面有系数 $-2\alpha_k$，代入后得

第四步：合并梯度差项.

4.2.3 步长条件的推导#

Fejér 单调性要求第二项为非正数，即 $\alpha_k(\alpha_k - 2\delta) \leq 0$。由 $\alpha_k > 0$，这等价于

此即条件二。满足后，

序列 $\{x^k\}$ 关于 $x^*$ Fejér 单调。

4.2.4 从 Fejér 单调到 Q-线性收敛#

Fejér 单调性只保证距离不增——它说明迭代不会”跑远”，但没有说明迭代会以什么速率”靠近”。要升级到线性收敛，需要一个反方向的估计：梯度差的范数不能比距离差衰减得更快。

余强制性恰好提供了这一估计。由余强制性蕴含的 Lipschitz 连续性 $L = 1/\delta$，梯度差的范数可以用距离来下界：

代入 Fejér 单调不等式，

当 $0 < \alpha_k < 2\delta$ 时，括号内的系数 $q_k \in (0,1)$，这正是 Q-线性收敛 的形式：

从 Fejér 单调到 Q-线性收敛，关键在于余强制性与 Lipschitz 连续性之间的对偶关系（$\delta = 1/L$）：它把”减去正数”升级为”乘以收缩因子”。

4.3.1 动机：为什么普通投影梯度法可能失效#

面对变分不等式，最自然的尝试是直接套用投影梯度法：$x^{k+1} = P_\Omega(x^k - \alpha F(x^k))$。这在 $F$ 满足强单调或余强制条件时是有效的（如 4.1 和 4.2 节所示），但当 $F$ 仅满足较弱的单调性条件时，这一方法可能失效。

一个典型的反例是旋转场。考虑 $\mathbb{R}^2$ 上的映射 $F(x_1, x_2) = (x_2, -x_1)$，可行域 $\Omega$ 为以原点为中心的闭球。这个映射是单调的（$\langle F(x) - F(y), x - y \rangle = 0$ 对所有 $x, y$ 成立），解为 $x^* = (0, 0)$。但 $F$ 在每个点处的方向都与径向垂直——它是一个纯旋转场。在点 $(1, 0)$ 处，$F = (0, -1)$，方向指向下方；沿 $-F = (0, 1)$ 方向移动后到达 $(1, \alpha)$（假设在球内），而新点处 $F = (\alpha, -1)$，方向仍然是”旋转的”。迭代的轨迹绕着原点做圆周运动，永远无法靠近解。

问题的根源在于：普通投影梯度法在 $x^k$ 处计算映射值 $F(x^k)$，然后据此更新到 $x^{k+1}$。但 $F(x^k)$ 的信息仅反映 $x^k$ 处的局部状况。当 $F$ 具有较强的旋转分量时，从 $x^k$ 出发的方向 $-F(x^k)$ 在全局尺度上并不指向解 $x^*$——它指向的是”切线方向”而非”径向方向”。

外梯度法为什么能解决这个问题？试探步先移动到 $\hat{x}^{k+1}$，然后在 $\hat{x}^{k+1}$ 处重新计算映射值。由于映射是旋转的，$F(\hat{x}^{k+1})$ 的方向相对于 $F(x^k)$ 发生了旋转。从 $x^k$ 出发按 $F(\hat{x}^{k+1})$（而非 $F(x^k)$）的方向更新，得到的方向会包含指向原点的分量。换言之，试探步的”往前看一步”自动引入了方向修正，将纯旋转的运动分解出了一个径向收缩分量。

4.3.2 外梯度法的思想与迭代格式#

外梯度投影法（Extragradient Projection Method, Korpelevich 1976）通过在每步迭代中执行两次投影来解决上述问题。

试探步（预测）：

正式更新步（校正）：

第一步是一次”试探”：从 $x^k$ 出发，按当前映射值 $F(x^k)$ 做投影，得到一个试探点 $\hat{x}^{k+1}$。第二步是”校正”：在试探点处重新计算映射值 $F(\hat{x}^{k+1})$，然后从 $x^k$（而非 $\hat{x}^{k+1}$）出发，按校正后的映射值做投影。试探步的作用是”往前看一步”——先探查前方的映射信息，在正式更新之前修正迭代方向。“外梯度”这个名称正是来源于此：利用了迭代点外侧（“extra”）的映射信息来指导更新。

若省略第二步，直接令 $x^{k+1} = \hat{x}^{k+1}$，则退化为普通投影梯度法。完整的算法流程如下。

算法 4.3：外梯度投影法

输入： 初始点 $x^0 \in \Omega$，步长 $\alpha > 0$（需满足 $\alpha < 1/L$），最大迭代次数 $K$，收敛阈值 $\varepsilon > 0$

for $k = 0, 1, 2, \ldots, K-1$ do

$\quad$ 1. 计算映射值：$F^k = F(x^k)$

$\quad$ 2. 试探步：$\hat{x}^{k+1} = P_\Omega(x^k - \alpha F^k)$

$\quad$ 3. 计算试探点处映射值：$\hat{F}^{k+1} = F(\hat{x}^{k+1})$

$\quad$ 4. 正式更新步：$x^{k+1} = P_\Omega(x^k - \alpha \hat{F}^{k+1})$

$\quad$ 5. 收敛检查：若 $\|x^{k+1} - x^k\| < \varepsilon$，则终止

end for

输出： $x^{k+1}$

注意每步迭代需要计算两次映射值（$F(x^k)$ 和 $F(\hat{x}^{k+1})$）和两次投影，计算量约为普通投影梯度法的两倍。

4.3.3 收敛条件与伪单调性#

外梯度投影法的收敛需要三个条件。

条件一：伪单调性（pseudomonotonicity）. $F$ 关于解 $x^*$ 伪单调，即对任意 $x \in \Omega$，

为什么可以从单调性放松到伪单调性？回顾单调性条件之间的层级：

强单调性要求 $\langle F(x) - F(y),\; x - y\rangle \geq \mu\|x - y\|^2$ 对所有点对 $(x, y)$ 成立——映射在全空间上都有很强的”正向对齐”性质。单调性将右端的 $\mu\|x-y\|^2$ 放松为 $0$，但仍然要求对所有点对成立。伪单调性则是一个更本质的放松：它不要求映射在任意两点之间表现良好，只要求从可行域中任何一点 $x$ 看，映射 $F(x)$ 所指的方向不会”反对”走向解 $x^*$——即 $F(x)$ 与 $x - x^*$ 的夹角不超过 $90°$。

从收敛性证明的角度看，伪单调性恰好提供了证明所需的最小信息量。在 4.3.5 节的引理 4.4 中，证明仅需要 $\langle F(\hat{x}^{k+1}),\; \hat{x}^{k+1} - x^*\rangle \geq 0$，这正是伪单调条件在 $x = \hat{x}^{k+1}$ 处的实例。更强的条件（如强单调性）当然也满足这一要求，但并非必要。条件越弱，适用范围越广：伪单调性涵盖了鞍点问题、某些非合作博弈、以及映射具有旋转分量的情形。代价是可证明的收敛速率较慢——不再是线性收敛，而是全序列收敛但没有显式的收敛速率。

上面提到的旋转场 $F(x_1, x_2) = (x_2, -x_1)$ 是一个好的检验例。它满足单调性（进而伪单调性）和 Lipschitz 连续性，但不满足强单调性或余强制性。外梯度法可以处理这类映射，而 4.1 和 4.2 节的方法做不到。

条件二：Lipschitz 连续性. $F$ Lipschitz 连续，即存在 $L > 0$，使得

条件三：步长限制.

此条件在证明过程中自然推导出来（见 4.3.5 节末尾）。

4.3.4 投影算子的变分不等式性质#

收敛性证明需要投影算子的一个基本性质，这里先单独陈述。此性质已在 4.0.1 节给出（性质三），这里以引理形式重述以方便后续引用。

引理 4.3（变分不等式刻画）. 对任意 $x \in \mathbb{R}^n$ 和 $y \in \Omega$，

等价地，

证明. $P_\Omega(x)$ 是 $\Omega$ 中距 $x$ 最近的点。从 $P_\Omega(x)$ 指向 $x$ 的方向与从 $P_\Omega(x)$ 指向 $\Omega$ 中任意点 $y$ 的方向夹角不小于 $90°$，这是凸集投影的标准几何性质。$\blacksquare$

4.3.5 收敛性证明#

证明按五步框架展开：Fejér 单调性 $\to$ 趋零性 $\to$ 有界性 $\to$ 聚点是不动点 $\to$ 全序列收敛。核心难度集中在第一步——建立 Fejér 单调性需要三个引理层层推进。后续四步是通用的收敛性论证模式，与具体算法无关。