第五章：邻近算法

5.2.1 Tikhonov 正则化：动机与缺陷#

强凸（strongly convex）是优化中一个非常好的性质——它保证解的唯一性和算法的快速收敛。但实际问题中，目标函数 $f(x)$ 往往只是凸的，并不具备强凸性。一个自然的思路是：能否通过某种变换将凸函数转化为强凸函数？

回忆强凸函数的定义：$f(x)$ 是 $\mu$-强凸的，当且仅当 $f(x) - \frac{\mu}{2}\|x\|^2$ 仍然是凸的。因此，给一个凸函数加上强凸项 $\frac{\mu}{2}\|x\|^2$，整体就变成了强凸函数——凸加强凸等于强凸。

Tikhonov 正则化的做法正是在原始目标函数上添加一个正则项：

其中 $\epsilon_k > 0$ 是正则化参数。添加正则项后整个目标函数变成强凸的，可以利用强凸函数的良好性质进行求解。

然而，为了保证正则化问题的解与原问题的解一致，需要在迭代过程中令正则项趋于零。由于 $x$ 的最优值不一定为零，不能期望 $\|x\|^2 \to 0$，因此需要令系数 $\epsilon_k \to 0$。这里存在一个根本性的矛盾：随着 $\epsilon_k \to 0$，正则项的作用越来越弱，函数的强凸性也随之减弱，条件数变差，算法收敛速度退化。

Tikhonov 正则化的核心矛盾：为了等价性需要 $\epsilon_k \to 0$，但 $\epsilon_k \to 0$ 又会使强凸性消失，导致算法性能退化。

5.2.2 邻近点算法的迭代格式#

为了克服 Tikhonov 正则化的缺陷，引入邻近点算法（Proximal Point Algorithm, PPA）。PPA 的迭代格式为：

其中 $\alpha > 0$ 是步长参数（可以固定，也可以取为 $\alpha_k$）。后面的二次项 $\frac{1}{2\alpha}\|x - x^k\|^2$ 称为邻近项（proximal term）。

与 Tikhonov 正则化的关键区别在于：邻近项是关于 $x - x^k$ 的二次项（以当前迭代点为中心），而不是关于 $x$ 本身的二次项。这意味着邻近项的中心随迭代更新，不需要令系数趋于零就能保持等价性。邻近项本身是强凸的，所以整个目标函数也是强凸的，并且这种强凸性不会随迭代减弱。

回忆梯度下降法的线性化展开形式：$x^{k+1} = \arg\min_x \left\{ f(x^k) + \nabla f(x^k)^\top(x - x^k) + \frac{1}{2\alpha}\|x - x^k\|^2 \right\}$。PPA 中同样出现了邻近项 $\frac{1}{2\alpha}\|x - x^k\|^2$，但 PPA 保留了完整的 $f(x)$ 而非其线性近似。

5.2.3 PPA 与隐式梯度下降#

对 PPA 迭代中的目标函数 $f(x) + \frac{1}{2\alpha}\|x - x^k\|^2$ 关于 $x$ 求次梯度并令其包含零（最优性条件）：

整理可得：

这可以理解为隐式梯度下降（implicit gradient descent）。与显式梯度下降 $x^{k+1} = x^k - \alpha \,\nabla f(x^k)$ 对比，两者的关键区别在于：显式方法在当前点 $x^k$ 处计算梯度，而隐式方法在下一步的点 $x^{k+1}$ 处计算次梯度。隐式方法虽然在形式上更复杂（需要求解一个子问题），但具有更好的稳定性和收敛性。

5.3.1 定义与良定义性#

给定闭凸函数 $h: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$，其邻近算子（proximal operator）定义为：

如果 $h$ 是闭凸（proper closed convex）函数，那么对任意 $x \in \mathbb{R}^n$，邻近算子的值存在且唯一。这意味着邻近算子是一个单值映射（single-valued mapping），不会出现一对多的情况。

单值性非常重要：回忆在研究单调包含问题（monotone inclusion）时，预解算子（resolvent operator）也是单值映射，从而可以将"$\in$"关系转换为"$=$"关系。邻近算子同样具备这个性质，因此后续将 PPA 转化为不动点问题时，可以将包含关系转换为等式关系。

5.3.2 直觉理解#

邻近算子的定义虽然以优化问题的形式给出，但其几何含义十分直观。$\mathrm{prox}_h(x)$ 所求解的子问题包含两个相互竞争的目标：

• $h(u)$ 要求 $u$ 使函数值尽可能小——这是”下降”的驱动力；
• $\frac{1}{2}\|u - x\|^2$ 要求 $u$ 不能离 $x$ 太远——这是”保守”的约束。

邻近算子的输出 $\mathrm{prox}_h(x)$ 正是这两个力量达到平衡的点。当 $h$ 本身是光滑函数时，对 $h(u) + \frac{1}{2}\|u-x\|^2$ 求导令其为零：$\nabla h(u) + (u - x) = 0$，即 $u = x - \nabla h(u)$。若 $\nabla h$ 变化缓慢（局部近似为常数），则 $u \approx x - \nabla h(x)$，这正是梯度下降的一步。因此，邻近算子是梯度下降从光滑函数到非光滑函数的自然推广。

5.3.3 邻近算子与次梯度的关系#

设 $h$ 是闭凸函数，则以下等价关系成立：

直观理解：$u$ 是邻近算子在 $x$ 处的值，意味着在 $u$ 处对目标 $h(u) + \frac{1}{2}\|u - x\|^2$ 的最优性条件成立。对 $u$ 求次梯度并令其包含零：$0 \in \partial h(u) + (u - x)$，整理即得 $x - u \in \partial h(u)$。

5.3.4 预解算子形式#

将 PPA 的隐式梯度下降写成算子形式。将含 $x^{k+1}$ 的项移至左边：

两边取逆：

其中 $(I + \alpha\,\partial f)^{-1}$ 即为预解算子（resolvent operator），记为 $J_{\alpha\partial f}$。PPA 的邻近算子形式为：

即邻近算子与预解算子是同一迭代的两种等价表示。

5.3.5 常见函数的邻近算子#

邻近算子的实用性在很大程度上取决于它是否具有解析解。幸运的是，许多在稀疏优化和约束优化中常见的函数都具有闭式的邻近算子。下表给出主要的实例（参数 $\alpha > 0$）：

表中各条目的推导将在 5.6 节给出前两个的完整证明，其余可用类似方法验证。

软阈值算子（soft-thresholding operator）$\mathcal{S}_\alpha$ 是稀疏优化的核心构件：当 $|x_i| > \alpha$ 时，$x_i$ 向零的方向”收缩”$\alpha$；当 $|x_i| \leq \alpha$ 时，$x_i$ 直接被压缩为零。这种”大值收缩、小值归零”的行为正是 $\ell_1$ 正则化产生稀疏解的机制。

投影算子 $P_\Omega$ 是约束优化的基本运算：它将点映射到约束集上距其最近的点。指示函数的邻近算子之所以等于投影，是因为指示函数在集合外取值 $+\infty$，最小化自动要求可行。

块软阈值处理 $\ell_2$ 范数（非平方），其行为类似软阈值但作用于整个向量：当 $\|x\|_2 \leq \alpha$ 时整个向量被置零，否则沿径向收缩。这在 group LASSO 等结构化稀疏问题中出现。

5.4.1 定义与基本性质#

给定闭凸函数 $f$ 和参数 $\alpha > 0$，$f$ 的 Moreau 包络（Moreau envelope，也称 Moreau-Yosida 正则化）定义为：

Moreau 包络与邻近算子的关系是直接的：$M_{\alpha f}(x)$ 是邻近算子定义中那个最小化问题的最优值，而 $\mathrm{prox}_{\alpha f}(x)$ 是取到最优值的点。

Moreau 包络的核心意义在于：即使 $f$ 本身不可微，$M_{\alpha f}$ 也是光滑的。具体地，$M_{\alpha f}$ 在全空间可微，且其梯度为：

这个结论的证明可参见教材定理 8.9。其直觉是：$M_{\alpha f}(x)$ 作为以 $u$ 为变量的优化问题的值函数（value function），其关于 $x$ 的变化率由最优解处的边际效应决定。由于邻近项 $\frac{1}{2\alpha}\|u-x\|^2$ 关于 $x$ 的梯度为 $-\frac{1}{\alpha}(u-x)$，而最优解 $u = \mathrm{prox}_{\alpha f}(x)$，代入即得上式。

此外，$\nabla M_{\alpha f}$ 是 Lipschitz 连续的（Lipschitz 常数为 $\frac{1}{\alpha}$），因此 $M_{\alpha f}$ 不仅可微，还具有良好的数值性质。

5.4.2 Moreau 包络的光滑近似性质#

Moreau 包络 $M_{\alpha f}$ 与原函数 $f$ 具有相同的最小值点：$\arg\min_x f(x) = \arg\min_x M_{\alpha f}(x)$。这意味着最小化 $f$ 可以等价地转化为最小化其光滑近似 $M_{\alpha f}$。

以指示函数为例：$f = \iota_C$ 时，$M_{\alpha f}(x) = \frac{1}{2\alpha}\mathrm{dist}^2(x, C)$，即到集合 $C$ 的距离平方（除以 $2\alpha$）。原函数 $\iota_C$ 在边界处跳跃式地从 0 变为 $+\infty$，而 $M_{\alpha f}$ 则用光滑的二次函数过渡。

以 $\ell_1$ 范数为例：$f(x) = \|x\|_1$ 时，$M_{\alpha f}(x)$ 是分量可分的 Huber 损失函数。每个分量上，$|x_i|$ 在零点处的”尖角”被 $M_{\alpha f}$ 替换为二次函数 $\frac{x_i^2}{2\alpha}$（当 $|x_i| \leq \alpha$），而在远离零的区域仍近似为 $|x_i| - \frac{\alpha}{2}$。参数 $\alpha$ 控制光滑化的程度：$\alpha$ 越大，光滑化范围越宽，但对原函数的逼近越粗糙。

5.4.3 PPA 作为 Moreau 包络上的梯度下降#

Moreau 包络提供了理解 PPA 的另一个视角。对 $M_{\alpha f}(x)$ 使用固定步长 $\alpha$ 的梯度下降：

这正是 PPA 的迭代格式。因此，PPA 可以理解为：先将不可微的 $f$ 替换为其光滑近似 $M_{\alpha f}$，再对光滑函数做梯度下降。这一解释揭示了 PPA 为何能同时处理不可微性和保持良好收敛性——它实际上是在一个光滑函数上做梯度下降。

5.5.1 为什么需要极大单调算子#

在 5.4.3 节中，我们从 Moreau 包络的角度直观理解了 PPA 的工作原理。但直觉不能替代严格证明。要证明 PPA 的收敛性，核心问题是：迭代映射 $T = \mathrm{prox}_{\alpha f} = (I + \alpha\,\partial f)^{-1}$ 具有什么性质？

当 $f$ 可微时，$\partial f = \{\nabla f\}$ 是单值映射，$\nabla f$ 的单调性（凸性的直接推论）足以证明 $T$ 是稳定非扩张的（5.7.1 节将给出完整证明）。然而，当 $f$ 不可微时，$\partial f$ 是集值映射——对同一个 $x$，$\partial f(x)$ 可能是一个集合而非单个向量。这时”$\nabla f$ 的单调性”不再适用，我们需要一个能处理集值映射的单调性理论。

极大单调算子正是为此而设计的概念。它把单调性从单值函数推广到集值映射，并且保证了一个关键结论：闭凸函数的次微分 $\partial f$ 是极大单调算子，从而其预解算子 $(I + \alpha\,\partial f)^{-1}$ 是稳定非扩张的。有了这个结论，PPA 在不可微情形下的收敛性就可以用与可微情形相同的框架来证明。

5.5.2 从单调性到极大单调性#

回忆第二章中的单调算子定义。对于单值映射 $A: \mathbb{R}^n \to \mathbb{R}^n$，单调性是指：

当 $A = \nabla f$（$f$ 是凸可微函数）时，这个性质由凸性直接保证。

对于集值映射 $\Phi: \mathbb{R}^n \rightrightarrows \mathbb{R}^n$（一个 $x$ 可能对应多个输出值），单调性的定义需要稍作调整：对任意 $x, y$ 以及任意 $u \in \Phi(x)$、$v \in \Phi(y)$，都有

含义是：无论从 $\Phi(x)$ 和 $\Phi(y)$ 中各取哪个元素，输出的增量方向与输入的增量方向之间的夹角都不超过 90 度。当 $\Phi$ 是单值映射时，这就退化为上面的标准定义。

然而，单调性本身还不够。考虑一个一维例子：定义映射 $\Phi(x) = \{1\}$（当 $x > 0$），$\Phi(x) = \{-1\}$（当 $x < 0$），在 $x = 0$ 处 $\Phi(0) = \emptyset$（未定义）。可以验证 $\Phi$ 在其定义域上满足单调性。但这个映射在 $x = 0$ 处有一个”缺口”——我们完全可以补充 $\Phi(0) = [-1, 1]$（零处的所有值），得到一个”更完整”的单调映射 $\Psi$，使得 $\Phi$ 的图（所有输入-输出对的集合）被 $\Psi$ 的图严格包含。

极大单调算子排除了这种”有缺口”的情况。设 $\Phi: \mathbb{R}^n \rightrightarrows \mathbb{R}^n$ 是集值映射，$\Phi$ 称为极大单调算子，如果它满足两个条件：(1) $\Phi$ 是单调的；(2) 不存在单调映射 $\Psi$ 使得 $\Phi$ 的图被 $\Psi$ 的图严格包含。第二个条件的含义是：$\Phi$ 在所有单调映射中已经是”最完整的”，无法再向其中添加任何输入-输出对而保持单调性。

在上面的例子中，$\Phi$（在零处未定义的版本）不是极大单调的，因为可以扩展；但补全后的 $\Psi$（$\Psi(0) = [-1, 1]$）是极大单调的——恰好就是 $|x|$ 的次微分 $\partial|\cdot|$。

5.5.3 闭凸函数的次微分是极大单调算子#

极大单调算子理论中最重要的结论之一是：

设 $f: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ 是闭凸函数，则 $\partial f$ 是极大单调算子。

这个结论（Rockafellar 定理）的证明需要较多凸分析的技术工具，此处不展开。它的意义在于：闭凸函数的次微分不仅是单调的（这由凸性直接得到），而且是”最完整的单调映射”——在保持单调性的前提下，$\partial f$ 已经包含了所有可能的次梯度信息，没有遗漏。

5.5.4 预解算子的稳定非扩张性#

极大单调算子理论的核心应用在于以下结论。设 $\Phi$ 是极大单调算子，则对任意 $c > 0$：

1. 预解算子 $J_{c\Phi} = (I + c\,\Phi)^{-1}$ 的定义域和值域均为 $\mathbb{R}^n$，且 $J_{c\Phi}$ 是单值映射
2. $J_{c\Phi}$ 是稳定非扩张的（firmly nonexpansive）

第一条保证了预解算子在整个空间上都有定义且输出唯一——这是将不动点迭代从”包含”关系（$x \in Tx$）转化为”等式”关系（$x = Tx$）的前提。第二条是收敛性的关键：稳定非扩张映射的不动点迭代是收敛的（第二章定理）。

将这两条结论与 5.5.3 节的结论结合，就得到了 PPA 在不可微情形下收敛的完整逻辑链：

极大单调算子理论对本章的价值集中在上述逻辑链中。读者不必深入极大单调算子的一般理论细节，只需记住两点：(1) 闭凸函数的次微分是极大单调算子；(2) 极大单调算子的预解算子是稳定非扩张的。这两点足以支撑 PPA 及后续 PGA 的收敛性分析。

5.6.1 指示函数上的 PPA 等价于投影#

设 $f = \iota_\Omega$ 为凸集 $\Omega$ 上的指示函数：

指示函数是凸的（当 $\Omega$ 为凸集时），但不可微（其次微分是法锥）。

对指示函数应用 PPA：

由于 $x \notin \Omega$ 时 $\iota_\Omega(x) = +\infty$，最小化自动要求 $x \in \Omega$。此时 $\iota_\Omega(x) = 0$，问题简化为：

系数 $\frac{1}{2\alpha}$ 不影响最优解，因此这等价于：

即在凸集 $\Omega$ 上对 $x^k$ 做投影（projection）。因此，投影梯度法可以视为 PPA 作用在指示函数上的特例。

算子形式验证：从零包含问题出发，PPA 的最优性条件为：

整理为算子形式：

而此前已证明 $(I + \alpha\,\partial\,\iota_\Omega)^{-1} = P_\Omega$，即预解算子等于投影算子，与上面的结论一致。

5.6.2 $\ell_1$ 范数上的 PPA 得到收缩算子#

设 $f(x) = \|x\|_1 = \sum_{i=1}^n |x_i|$，$x \in \mathbb{R}^n$。对其应用 PPA：

展开为分量形式：

由于各分量之间不存在耦合项（coupling term）——即不存在 $x_ix_j$（$i \neq j$）的交叉项——可以对每个分量独立求解：

情况一：$x_i^{k+1} > 0$。此时 $|x_i| = x_i$，对 $x_i$ 求导令其为零：

此情况要求 $x_i^{k+1} > 0$，即 $x_i^k > \alpha$。

情况二：$x_i^{k+1} < 0$。此时 $|x_i| = -x_i$，对 $x_i$ 求导令其为零：

此情况要求 $x_i^{k+1} < 0$，即 $x_i^k < -\alpha$。

情况三：$x_i^{k+1} = 0$。此时 $|x_i|$ 在零处不可微，需要使用次微分。$|x_i|$ 在零处的次微分为 $\partial|0| = [-1, 1]$。最优性条件变为：

即 $\frac{x_i^k}{\alpha} \in [-1, 1]$，等价于 $x_i^k \in [-\alpha, \alpha]$。

综合三种情况，得到软阈值公式（soft-thresholding）：

这就是收缩算子（shrinkage operator），也写作：

5.7.1 方法一：算子形式证明（可微情形）#

条件：$f$ 凸且可微，步长 $\alpha > 0$ 固定，$\nabla f$ 是单调算子。

目标：证明 $T = (I + \alpha\,\nabla f)^{-1}$ 是稳定非扩张的（firmly nonexpansive）。

证明：令 $u = T(x)$，$v = T(y)$，则：

根据稳定非扩张的定义，需证明：

即证 $\|u - v\|^2 \leq \langle x - y,\; u - v \rangle$。将 $x, y$ 的表达式代入右侧：

由于 $\nabla f$ 是单调算子，有 $\langle \nabla f(u) - \nabla f(v),\; u - v \rangle \geq 0$。又 $\alpha > 0$，故：

这正是稳定非扩张的定义。根据不动点迭代的收敛定理，稳定非扩张映射的不动点迭代是收敛的，从而 PPA 收敛。$\blacksquare$

5.7.2 方法二：算子形式证明（不可微情形）#

当 $f$ 凸但不可微时，方法一的证明思路不再直接适用，因为 $\partial f$ 是集值映射，不能简单地写成 $x = u + \alpha\,\nabla f(u)$ 这样的等式。此时需要调用 5.5 节建立的极大单调算子理论。

证明的逻辑链条如下：$f$ 是闭凸函数 $\Rightarrow$ $\partial f$ 是极大单调算子（5.5.3 节）$\Rightarrow$ $(I + \alpha\,\partial f)^{-1}$ 是稳定非扩张的（5.5.4 节性质 2）$\Rightarrow$ 不动点迭代收敛（第二章不动点定理）。

这条逻辑链中，每一步都已在前面的章节中建立，此处只需串联即可。方法二的价值在于它表明：可微情形的证明（方法一）可以通过极大单调算子的框架自然地推广到不可微情形，而无需引入任何本质上不同的新技巧。

5.7.3 方法三：利用最优性条件和费杰单调性#

条件：$f$ 凸，步长 $\alpha > 0$ 固定。设 $x^*$ 是最优解。

PPA 迭代：$x^{k+1} = x^k - \alpha\,\nabla f(x^{k+1})$（以可微情形为例）。

步骤 1：分析 $\|x^{k+1} - x^*\|^2$。

在中间加减 $x^k$，展开：

进一步在内积中加减 $x^{k+1}$：

步骤 2：代入 PPA 迭代关系 $x^{k+1} - x^k = -\alpha\,\nabla f(x^{k+1})$：

步骤 3：利用最优性条件。$x^*$ 是最优解，故 $\nabla f(x^*) = 0$。因此：

由 $f$ 凸可知 $\nabla f$ 是单调算子，故上式 $\geq 0$。加上 $-2\alpha$（$\alpha > 0$），得：

步骤 4：综合以上结果：

这是经典的费杰单调性（Fejer monotonicity）不等式。它表明：

• $\|x^k - x^*\|^2$ 是单调递减序列（有下界 0），故收敛
• $\sum_{k=0}^{\infty}\|x^{k+1} - x^k\|^2 < \infty$，故 $\|x^{k+1} - x^k\| \to 0$

后续步骤与不动点迭代收敛性证明完全相同，从而得出 PPA 收敛。$\blacksquare$

5.8.1 动机：标准 PPA 的局限性#

标准 PPA 的迭代 $x^{k+1} = \mathrm{prox}_{\alpha f}(x^k)$ 在理论上具有良好的收敛性，但在实践中存在两个局限。

其一，每步迭代要求精确求解邻近子问题 $\arg\min_x \{f(x) + \frac{1}{2\alpha}\|x-x^k\|^2\}$。对于复杂的 $f$，精确求解代价可能很高，而只需要近似求解就足以保证收敛。松弛参数提供了一种系统化的近似机制：当 $\rho_k < 1$ 时，新的迭代点只向邻近映射的方向走一部分，相当于用一个”保守版”的邻近步替代精确邻近步。

其二，标准 PPA 的每步移动量完全由邻近映射决定，没有利用迭代之间的惯性信息。当 $\rho_k > 1$ 时，算法在邻近映射的基础上进一步外推，类似于 Nesterov 加速中的动量项，在某些问题上可以加速收敛。

松弛 PPA 通过引入一个松弛参数 $\rho_k \in (0, 2)$，将标准 PPA 推广为更灵活的迭代格式。当 $\rho_k = 1$ 时退化为标准 PPA，$\rho_k < 1$ 对应保守的松弛步，$\rho_k > 1$ 对应激进的惯性步。下面给出具体的迭代格式和收敛性分析。

5.8.2 迭代格式#

松弛 PPA 的迭代由两步组成：

其中 $\alpha > 0$ 是邻近参数，$\rho_k \in (0, 2)$ 是松弛参数。第一步与标准 PPA 完全相同，计算邻近映射得到中间点 $\hat{x}^{k+1}$；第二步则对 $x^k$ 和 $\hat{x}^{k+1}$ 做加权组合，得到新的迭代点 $x^{k+1}$。当 $\rho_k = 1$ 时，松弛 PPA 退化为标准 PPA，即 $x^{k+1} = \hat{x}^{k+1}$。

5.8.3 松弛参数的几何含义#

松弛参数 $\rho_k$ 的取值范围 $(0, 2)$ 可以进一步细分为两个区间，它们具有不同的几何含义。

松弛步（$\rho_k \in (0, 1)$）：此时 $x^{k+1} = (1 - \rho_k) x^k + \rho_k \hat{x}^{k+1}$ 是 $x^k$ 和 $\hat{x}^{k+1}$ 的凸组合。新的迭代点 $x^{k+1}$ 落在 $x^k$ 与 $\hat{x}^{k+1}$ 之间的线段上，相当于只走了”一部分”邻近步（under-relaxation）。

惯性步（$\rho_k \in (1, 2)$）：将迭代式改写为 $x^{k+1} = \hat{x}^{k+1} + (\rho_k - 1)(\hat{x}^{k+1} - x^k)$，此时 $x^{k+1}$ 沿 $\hat{x}^{k+1} - x^k$ 方向”冲出”了 $\hat{x}^{k+1}$，超越了标准 PPA 的中间点。这种行为称为惯性步（over-relaxation），算法沿着当前移动方向进行了外推。

5.8.4 收敛性分析#

下面证明在 $\rho_k \in (0, 2)$ 的条件下，序列 $\{\|x^k - x^*\|^2\}$ 具有非递增单调性。

步骤 1：展开迭代点与最优解的距离。将 $x^{k+1}$ 的表达式代入，展开 $\|x^{k+1} - x^*\|^2$：

步骤 2：处理交叉项。对 $\langle x^k - x^*, \hat{x}^{k+1} - x^k \rangle$ 插入 $\hat{x}^{k+1}$：

代入后得到：

步骤 3：利用最优性条件消去内积项。$\hat{x}^{k+1}$ 是邻近映射的解，满足 $\hat{x}^{k+1} - x^k = -\alpha \,\partial f(\hat{x}^{k+1})$。同时 $x^*$ 是全局最优解，$0 \in \partial f(x^*)$。代入内积项：

步骤 4：利用单调性。当 $f$ 是凸函数时，$\partial f$ 是单调算子，故 $\langle \hat{x}^{k+1} - x^*, \partial f(\hat{x}^{k+1}) - \partial f(x^*) \rangle \geq 0$。因此内积项前带负号 $-\alpha$，使得 $2\rho_k \langle \hat{x}^{k+1} - x^*, \hat{x}^{k+1} - x^k \rangle \leq 0$。

步骤 5：得出收敛条件。将上述不等式代回：

由于 $\|\hat{x}^{k+1} - x^k\|^2 \geq 0$ 且 $\rho_k > 0$，要使右端第二项非正需要 $\rho_k - 2 \leq 0$，即 $\rho_k \leq 2$。因此当 $\rho_k \in (0, 2)$ 时：

这就证明了序列 $\{\|x^k - x^*\|^2\}$ 关于 $k$ 非递增单调，从而保证松弛 PPA 的收敛性。$\blacksquare$

5.9.1 复合优化问题#

邻近梯度算法（Proximal Gradient Algorithm, PGA）用于求解复合优化（composite optimization）问题：

其中 $f(x)$ 是光滑函数（可微，且梯度 Lipschitz 连续），$g(x)$ 是非光滑函数（可能不可微），但通常是凸的。这类问题在机器学习和信号处理中极为常见——$f(x)$ 通常是数据拟合项（如最小二乘损失），$g(x)$ 通常是正则化项（如 $\ell_1$ 范数）。

核心思想是：对光滑部分 $f$ 做梯度下降，对非光滑部分 $g$ 做邻近点算法，将两者结合形成一步迭代。这种”分而治之”的思路也称为前向-后向分裂法（Forward-Backward Splitting Method, FBSM）。

5.9.2 迭代格式推导#

PGA 的迭代格式为：

构造逻辑如下：对光滑部分 $f$ 在当前点 $x^k$ 处做一阶 Taylor 展开（线性化近似），对非光滑部分 $g$ 保持不动，同时加入邻近项 $\frac{1}{2\alpha_k}\|x - x^k\|^2$ 控制迭代步长。

对线性项和二次项进行配方：

这正是 $g$ 关于点 $x^k - \alpha_k \nabla f(x^k)$ 的邻近算子。记为：

直觉非常清晰：先对光滑部分 $f$ 做一步梯度下降得到中间点 $x^k - \alpha_k \nabla f(x^k)$，再对非光滑部分 $g$ 施加邻近算子进行修正。

5.9.3 算法伪代码#

将 PGA 的完整算法整理如下。

算法 5.1：邻近梯度算法（PGA / ISTA）

输入：初始点 $x^0 \in \mathbb{R}^n$，步长 $\alpha > 0$（满足 $\alpha < 1/L$，其中 $L$ 是 $\nabla f$ 的 Lipschitz 常数），最大迭代次数 $K$，容差 $\varepsilon > 0$

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

$\quad$ 1. 梯度步：$v^k = x^k - \alpha \,\nabla f(x^k)$

$\quad$ 2. 邻近步：$x^{k+1} = \mathrm{prox}_{\alpha g}(v^k)$

$\quad$ 3. 停机检查：若 $\|x^{k+1} - x^k\| < \varepsilon$，则停止

end for

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

当 $g(x) = \lambda\|x\|_1$ 时，邻近步就是软阈值运算，此时 PGA 也称为迭代收缩阈值算法（Iterative Shrinkage-Thresholding Algorithm, ISTA）。ISTA 和 PGA 实质上是同一个算法在不同文献中的不同称呼——前者在信号处理领域广泛使用，后者在优化理论文献中更常见。其加速版本 FISTA（Fast ISTA）引入 Nesterov 动量项，将收敛速度从 $O(1/k)$ 提升到 $O(1/k^2)$。

步长的选取有两种常见策略：固定步长 $\alpha = 1/L$（需要已知 $L$）和回溯线搜索（Backtracking line search，不需要 $L$ 但每步可能多次计算函数值）。

5.9.4 算子形式与分裂算法#

对 PGA 迭代式求最优性条件。由于 $g$ 非光滑，对其取次梯度：

令 $A = \nabla f$（梯度算子），$B = \partial g$（次梯度算子），$c = \alpha_k$（步长参数），整理得 PGA 的算子迭代形式：

其中 $J_{cB} = (I + cB)^{-1}$ 是 $B$ 的预解算子。

原始优化问题的零包含形式为 $0 \in \nabla f(x) + \partial g(x)$，即 $0 \in Ax + Bx$。这正是经典的分裂算法（splitting method）框架：将零包含问题中的算子拆分为 $A$（易于计算梯度的部分）和 $B$（易于计算预解式的部分），分别处理后组合。

5.9.5 收敛性分析#

设 $g$ 为凸函数，$B = \partial g$ 为极大单调算子，PGA 在以下三个条件下收敛：

• 条件一：$J_{cB}$ 是稳定非扩张映射（已在 PPA 收敛性证明中建立）
• 条件二：$A = \nabla f$ 满足余强制（cocoercive）条件，即存在 $\delta > 0$ 使得 $\langle Ax - Ay,\, x - y \rangle \geq \delta \|Ax - Ay\|^2$
• 条件三：步长参数 $c$ 满足 $c < 2\delta$

证明：设 $x^*$ 是不动点（满足 $x^* = J_{cB}(I - cA)x^*$），计算：

第一步：利用 $J_{cB}$ 的非扩张性：

第二步：展开右端：

第三步：利用 $A$ 的 cocoercive 条件，$\langle x^k - x^*, Ax^k - Ax^* \rangle \geq \delta \|Ax^k - Ax^*\|^2$，代入得：