近端算法课程讲解 - 第七部分

课程引入：从固定点定理开始

这门课程从一个经典的数学定理开始——Picard固定点定理（1856-1941年提出）。首先让我们理解什么是希尔伯特空间（Hilbert space）。希尔伯特空间\mathcal{H}是一个完备的内积空间，这意味着它不仅有内积结构可以定义长度和角度，而且其中的柯西序列都会收敛到空间内的点。

固定点定理讨论的核心对象是一个算子T: \mathcal{H} \to \mathcal{H}，也就是将希尔伯特空间映射到自身的函数。这个定理给出了一个充分条件，保证算子T存在唯一的固定点。什么是固定点？固定点\hat{x}就是满足T\hat{x} = \hat{x}的点，也就是经过算子T作用后保持不变的点。

定理的核心条件是T必须是严格收缩映射（strict contraction）。严格收缩意味着存在一个常数\rho \in [0,1[（注意\rho严格小于1），使得对于空间中任意两点x和x'，都有：

这个不等式的几何意义是：算子T将任意两点之间的距离至少缩小到原来的\rho倍。由于\rho < 1，所以T确实在"收缩"空间中点之间的距离。这种收缩性质是保证固定点存在且唯一的关键——直观上说，如果一个映射不断地缩小距离，那么反复应用这个映射，所有点最终都会聚集到一个点上。

在这个条件下，定理保证T有唯一的固定点\hat{x}。更进一步，定理还告诉我们如何找到这个固定点：构造一个迭代序列(x_n)_{n \in \mathbb{N}}，其中每一项通过前一项应用算子T得到：

起始点x_0 \in \mathcal{H}可以任意选择。这个序列会收敛到固定点\hat{x}。这种通过反复应用算子来寻找固定点的方法称为固定点迭代法或Picard迭代。

课程目标：扩展与应用

这门课程的核心目标分为两个主要方向。第一个方向是将Picard固定点定理扩展到更一般的算子类别。原始的Picard定理要求算子必须是严格收缩的，这个条件在实际应用中往往过于严格。因此我们需要研究那些不一定严格收缩的算子。这些算子可能只是非扩张的（non-expansive），即\|Tx - Tx'\| \leq \|x - x'\|（注意这里\rho = 1也被允许）。

另一个扩展方向是考虑依赖于迭代次数n的算子。在原始定理中，算子T是固定的，每次迭代都应用相同的T。但在实际算法中，我们可能需要在不同的迭代步使用不同的算子，即x_{n+1} = T_n x_n，其中T_n可能随n变化。这种变化可能来自于算法参数的自适应调整，或者是为了加速收敛而设计的策略。

特别地，课程会研究如何通过组合简单算子来构建复杂算子。这就是所谓的"splitting techniques"（分裂技术）。在优化问题中，目标函数往往可以分解为几个简单函数的和，每个简单函数对应一个容易处理的算子。分裂技术允许我们分别处理这些简单算子，然后通过某种方式组合它们的结果，而不是直接处理复杂的组合算子。

第二个主要目标是将固定点理论应用于求解最小化问题。这里的关键问题是：如何将算子T与目标函数f联系起来？在优化理论中，我们通常想要最小化某个函数f: \mathcal{H} \to \mathbb{R}。固定点理论看起来与最小化问题没有直接关系，但实际上存在深刻的联系。一个函数的最小值点往往可以表征为某个相关算子的固定点。例如，如果f是可微的，那么f的最小值点x^*满足\nabla f(x^*) = 0，这可以重写为x^* = x^* - \alpha \nabla f(x^*)，其中\alpha > 0是步长参数。这表明x^*是算子T(x) = x - \alpha \nabla f(x)的固定点。

对于不可微的函数，这种联系通过近端算子（proximal operator）建立。近端算子及其相关的固定点算法正是本课程"Proximal algorithms"（近端算法）名称的由来。这些算法通过寻找适当定义的算子的固定点来解决优化问题，将优化问题转化为固定点问题，从而可以利用固定点理论的丰富结果。

固定点算法的收敛性理论

收敛性的两种类型

在希尔伯特空间\mathcal{H}中，对于序列(x_n)_{n\in\mathbb{N}}收敛到点\hat{x} \in \mathcal{H}，我们需要区分两种不同的收敛概念。

**强收敛（Strong Convergence）**的定义是序列与极限点之间的范数距离趋于零：

记作x_n \to \hat{x}。这种收敛方式直观地表示序列中的点在空间中"真实地"越来越接近极限点。强收敛意味着序列元素与极限之间的距离（由范数度量）确实在减小到零。

**弱收敛（Weak Convergence）**则通过内积来定义。序列(x_n)_{n\in\mathbb{N}}弱收敛到\hat{x}是指对于空间中的任意元素y，内积序列收敛：

记作x_n \rightharpoonup \hat{x}。弱收敛不是通过距离来衡量，而是通过与所有方向的投影来衡量。即使x_n与\hat{x}的距离可能不趋于零，但它们在任意方向上的投影差异都趋于零。

为什么需要两种收敛概念？在无穷维空间中，强收敛是一个很强的要求。许多重要的算法产生的序列只能保证弱收敛。强收敛总是蕴含弱收敛（如果\|x_n - \hat{x}\| \to 0，那么对任意y，由Cauchy-Schwarz不等式可得|\langle y \mid x_n - \hat{x}\rangle| \leq \|y\| \cdot \|x_n - \hat{x}\| \to 0），但反之不成立。

备注指出，在有限维希尔伯特空间中，强收敛和弱收敛是等价的。这是因为有限维空间中所有的范数都是等价的，而弱收敛本质上是坐标收敛。但在无穷维空间中，这种等价性不再成立，这是无穷维分析的一个核心难点。

弱收敛的充要条件

序列(x_n)_{n\in\mathbb{N}}弱收敛当且仅当满足两个条件。第一个条件是序列必须有界：

这意味着存在常数M > 0使得对所有n都有\|x_n\| \leq M。有界性是弱收敛的必要条件，因为弱收敛的序列必须在某个球内，不能逃逸到无穷远。

第二个条件涉及**顺序聚点（sequential cluster point）**的概念。序列(x_n)_{n\in\mathbb{N}}必须在弱拓扑下至多拥有一个顺序聚点。什么是顺序聚点？如果存在子序列(x_{n_k})_{k\in\mathbb{N}}弱收敛到\hat{x}，那么点\hat{x}是序列(x_n)_{n\in\mathbb{N}}在弱拓扑下的顺序聚点：

"至多一个"顺序聚点的要求确保了序列不会在多个点之间振荡。如果序列有界且只有一个弱聚点，那么整个序列必然弱收敛到这个唯一的聚点。

反例来说明这两个条件的必要性。考虑序列：

这个序列在1和-1之间振荡。它显然是有界的（|x_n| = 1对所有n成立），满足第一个条件。但它有两个顺序聚点：1和-1。子序列(x_{2k})_{k\in\mathbb{N}} = (1, 1, 1, \ldots)收敛到1，而子序列(x_{2k+1})_{k\in\mathbb{N}} = (-1, -1, -1, \ldots)收敛到-1。由于存在两个不同的聚点，违反了"至多一个聚点"的条件，所以整个序列(x_n)_{n\in\mathbb{N}}不收敛。

Fejér单调序列

Fejér单调性是分析固定点算法收敛性的核心工具。设D是希尔伯特空间\mathcal{H}的非空子集，序列(x_n)_{n\in\mathbb{N}}关于集合D是Fejér单调的，如果对D中的每个点，序列到该点的距离是非递增的：

这个条件的几何意义是：对于目标集合D中的任意点x，序列的每一步都不会使我们远离这个点。注意这不意味着序列必然接近D中的点，只是说不会远离。序列可能保持在某个固定距离上，但绝不会增加与D中任意点的距离。

Fejér单调序列具有两个重要性质。首先，对于D中的每个点x，距离序列(\|x_n - x\|)_{n\in\mathbb{N}}收敛。这是因为该序列是非负且单调递减的，根据实数的完备性，它必然收敛到某个非负实数（可能是零，也可能不是）。其次，序列(x_n)_{n\in\mathbb{N}}本身是有界的。这可以通过固定D中任意一点x_0来看出：由于\|x_n - x_0\| \leq \|x_1 - x_0\|对所有n \geq 1成立，序列被包含在以x_0为中心、半径为\max\{\|x_0 - x_0\|, \|x_1 - x_0\|\}的闭球内。

Fejér单调性在固定点算法中的作用是什么？许多迭代算法，特别是投影算法和近端算法，自然地产生Fejér单调序列。如果算子T的不动点集合是D，而迭代序列关于D是Fejér单调的，那么我们就有了收敛性分析的有力工具。结合前面的弱收敛充要条件，如果能证明序列至多有一个弱聚点，就能得出弱收敛的结论。

Fejér单调收敛定理与非扩张算子

Fejér单调收敛定理

前面我们已经了解了Fejér单调序列的基本性质，现在来看它如何保证弱收敛。这个定理给出了一个充分条件：设D是希尔伯特空间\mathcal{H}的非空子集，序列(x_n)_{n\in\mathbb{N}}弱收敛到D中的点，当且仅当满足两个条件：序列关于D是Fejér单调的，且序列的每个弱顺序聚点都在D中。

这个定理的深刻之处在于它将Fejér单调性与弱收敛联系起来。回顾之前的弱收敛充要条件，序列弱收敛需要有界性和至多一个弱聚点。Fejér单调性自动保证了有界性，而要求所有弱聚点都在D中则进一步约束了序列的行为。如果D是凸集且序列关于D是Fejér单调的，那么序列不能有两个不同的弱聚点都在D中——因为如果有两个聚点x_1, x_2 \in D，由于凸性，它们之间的中点(x_1+x_2)/2也在D中，而Fejér单调性会导致矛盾。

这个定理在固定点算法分析中至关重要，因为许多算法自然产生的序列都是关于固定点集合Fejér单调的。如果我们能证明序列的所有弱聚点都是固定点，那么结合Fejér单调性，就能得出序列弱收敛到某个固定点的结论。

非扩张算子的定义

现在我们从严格收缩算子扩展到更一般的非扩张算子。给定希尔伯特空间\mathcal{H}的非空子集C，算子T: C \to \mathcal{H}的固定点集合定义为：

这是所有在T作用下保持不变的点的集合。注意这里T的定义域是C，但值域是整个空间\mathcal{H}，这种设定在后续讨论中会有技术上的便利。

算子T: C \to \mathcal{H}是非扩张的（nonexpansive），如果对C中任意两点都有：

与严格收缩映射\|Tx - Ty\| \leq \rho\|x - y\|（其中\rho < 1）相比，非扩张算子允许\rho = 1的情况。这意味着算子可能保持某些点对之间的距离不变，而不是严格缩小。几何上，非扩张算子不会增加任意两点间的距离，但也不保证减小距离。

在优化和数值分析中，许多重要的算子都是非扩张但不是严格收缩的。最典型的例子是投影算子：将点投影到闭凸集上的算子是非扩张的。如果投影算子是严格收缩的，那么它只能有一个固定点，这意味着被投影的集合只能包含一个点，这显然过于限制。实际上，投影算子的固定点集正是被投影的集合本身。

半闭性原理（Demiclosedness Principle）

半闭性原理是分析非扩张算子固定点的关键工具。设C是希尔伯特空间\mathcal{H}的非空闭凸子集，T: C \to \mathcal{H}是非扩张算子。如果序列(x_n)_{n\in\mathbb{N}}在C中弱收敛到\hat{x}，且Tx_n - x_n \to 0（强收敛到零），那么\hat{x} \in \text{Fix}T。

这个原理的名称来自于它描述的性质：算子I - T（其中I是恒等算子）在弱-强拓扑下是"半闭"的。具体地说，如果x_n弱收敛到\hat{x}，而(I-T)x_n = x_n - Tx_n强收敛到0，那么(I-T)\hat{x} = 0，即\hat{x} = T\hat{x}。

半闭性原理为什么成立？直观理解是：虽然弱收敛不保证Tx_n弱收敛到T\hat{x}（因为T可能不是弱连续的），但当x_n - Tx_n \to 0时，我们知道x_n和Tx_n越来越接近。由于x_n弱收敛到\hat{x}，在某种意义上Tx_n也应该"接近"\hat{x}。非扩张性和凸性的组合保证了这种直觉是正确的。

非扩张算子的固定点算法

现在我们可以建立非扩张算子的固定点定理。设C是希尔伯特空间的非空闭凸子集，T: C \to C是非扩张算子且\text{Fix}T \neq \varnothing。从任意初始点x_0 \in C开始，构造迭代序列：

如果残差x_n - Tx_n \to 0，那么序列(x_n)_{n\in\mathbb{N}}弱收敛到\text{Fix}T中的某个点。

证明的关键步骤如下：首先，对于任意固定点y \in \text{Fix}T，有：

这表明序列(x_n)_{n\in\mathbb{N}}关于\text{Fix}T是Fejér单调的。由Fejér单调性，序列有界且对每个y \in \text{Fix}T，距离序列(\|x_n - y\|)_{n\in\mathbb{N}}收敛。

设(x_{n_k})_{k\in\mathbb{N}}是弱收敛到某个\hat{x} \in \mathcal{H}的子序列。由于x_{n_k} - Tx_{n_k} \to 0且C是闭凸的，根据半闭性原理，\hat{x} \in \text{Fix}T。这证明了序列的所有弱聚点都在\text{Fix}T中。

结合Fejér单调收敛定理，序列(x_n)_{n\in\mathbb{N}}弱收敛到\text{Fix}T中的某个点。注意这里有一个关键条件：x_n - Tx_n \to 0。对于一般的非扩张算子，简单的固定点迭代可能不满足这个条件。这就是为什么需要开发更复杂的算法，如近端点算法、投影算法等，来保证这个残差条件成立。

非扩张算子固定点算法的深入分析

定理陈述与证明结构

这个定理是非扩张算子理论的核心结果。设定条件包括：C是希尔伯特空间\mathcal{H}的非空闭凸子集，T: C \to C是非扩张算子，且固定点集\text{Fix}T \neq \varnothing（即至少存在一个固定点）。从任意初始点x_0 \in C出发，通过迭代公式x_{n+1} = Tx_n生成序列。如果残差序列x_n - Tx_n \to 0，那么(x_n)_{n\in\mathbb{N}}弱收敛到\text{Fix}T中的某个点。

这个定理与Picard固定点定理有本质区别。Picard定理保证严格收缩映射的固定点迭代强收敛到唯一固定点，而这里我们只有弱收敛，且固定点可能不唯一。条件x_n - Tx_n \to 0是额外要求的——对于一般的非扩张算子，简单迭代可能不满足这个条件。

练习：通过证明(x_n)_{n\in\mathbb{N}}关于\text{Fix}T是Fejér单调的来证明这个结果。

第一步：建立Fejér单调性

对于任意n \in \mathbb{N}和任意固定点y \in \text{Fix}T，我们有：

这里第一个等式使用了迭代定义x_{n+1} = Tx_n和固定点性质Ty = y，不等式则来自T的非扩张性。这个不等式对所有n和所有y \in \text{Fix}T都成立，恰好就是Fejér单调性的定义。

第二步：序列的有界性

由Fejér单调性的一般性质，序列(x_n)_{n\in\mathbb{N}}是有界的。具体地，选定任意一个固定点y^* \in \text{Fix}T（存在性由假设保证），则对所有n都有\|x_n - y^*\| \leq \|x_0 - y^*\|，因此：

序列被包含在一个有界集合中。

第三步：弱聚点的刻画

设(x_{n_k})_{k\in\mathbb{N}}是任意弱收敛子序列，弱收敛到某个\hat{x} \in \mathcal{H}。由于C是弱闭的（闭凸集在希尔伯特空间中是弱闭的），我们有\hat{x} \in C。

现在关键是要证明\hat{x} \in \text{Fix}T。由假设条件x_n - Tx_n \to 0，特别地对子序列有x_{n_k} - Tx_{n_k} \to 0。这意味着：

第四步：应用半闭性原理

这正是半闭性原理的使用场景：我们有x_{n_k} \rightharpoonup \hat{x}（弱收敛）且x_{n_k} - Tx_{n_k} \to 0（强收敛）。根据半闭性原理，必有\hat{x} \in \text{Fix}T。

这证明了序列(x_n)_{n\in\mathbb{N}}的每个弱聚点都在\text{Fix}T中。

第五步：应用Fejér单调收敛定理

现在我们已经验证了Fejér单调收敛定理的所有条件：

• 序列(x_n)_{n\in\mathbb{N}}关于\text{Fix}T是Fejér单调的
• 序列的每个弱顺序聚点都在\text{Fix}T中

因此，根据Fejér单调收敛定理，序列(x_n)_{n\in\mathbb{N}}弱收敛到\text{Fix}T中的某个点。

条件x_n - Tx_n \to 0的必要性

为什么需要条件x_n - Tx_n \to 0？考虑一个反例：设T是\mathbb{R}^2中关于原点的旋转\theta度（0 < \theta < 2\pi且\theta不是2\pi的有理倍数）。T是非扩张的（实际上是等距的），唯一固定点是原点。但从任何非零点x_0开始的迭代序列(x_n)会在一个圆上永远旋转，不会收敛到原点。在这个例子中，\|x_n - Tx_n\| = 2\|x_0\|\sin(\theta/2)对所有n都是常数，不趋于零。

这个例子说明，对于一般的非扩张算子，简单的固定点迭代可能不收敛。这就是为什么需要开发更复杂的算法来保证x_n - Tx_n \to 0。近端点算法、前向-后向分裂算法等方法正是为此目的设计的。

与优化的联系

在优化中，许多问题可以表述为寻找某个算子的固定点。例如，最小化凸函数f等价于找到算子T = \text{prox}_{\gamma f}（近端算子）的固定点，其中\gamma > 0是步长参数。近端算子总是非扩张的，这个定理为分析优化算法的收敛性提供了理论基础。

条件x_n - Tx_n \to 0在优化语境下通常对应于"梯度趋于零"或"最优性条件的残差趋于零"。许多实际算法通过特殊的更新规则或自适应参数调整来确保这个条件成立。

Krasnosel'skii-Mann算法与平均算子理论

Krasnosel'skii-Mann算法

前面我们看到，对于非扩张算子T，简单的固定点迭代x_{n+1} = Tx_n可能不满足条件x_n - Tx_n \to 0，从而无法保证收敛。Krasnosel'skii-Mann算法通过引入松弛参数解决了这个问题。

算法的设置条件包括：C是希尔伯特空间\mathcal{H}的非空闭凸子集，T: C \to C是非扩张算子且\text{Fix}T \neq \varnothing。关键创新在于引入松弛参数序列(\lambda_n)_{n\in\mathbb{N}} \subset [0,1]，满足条件：

这个条件确保了参数序列既不能太接近0也不能太接近1。典型的选择是\lambda_n = \lambda \in ]0,1[（常数），这自动满足上述条件因为\sum_{n\in\mathbb{N}} \lambda(1-\lambda) = +\infty。

算法的迭代公式是：

这可以重写为x_{n+1} = (1-\lambda_n)x_n + \lambda_n Tx_n，是当前点x_n和其映像Tx_n的凸组合。当\lambda_n = 1时，退化为标准固定点迭代；当\lambda_n < 1时，我们只部分地向Tx_n移动，这种"欠松弛"策略有助于稳定算法。

定理保证了三个重要性质：

1. 序列(x_n)_{n\in\mathbb{N}}关于\text{Fix}T是Fejér单调的
2. 残差序列(Tx_n - x_n)_{n\in\mathbb{N}}强收敛到0
3. 序列(x_n)_{n\in\mathbb{N}}弱收敛到\text{Fix}T中的某个点

条件\sum_{n\in\mathbb{N}} \lambda_n(1-\lambda_n) = +\infty的作用是什么？这个条件保证算法既有足够的"探索"（\lambda_n不能太小），又有足够的"稳定性"（\lambda_n不能太大接近1）。数学上，这个条件确保了残差Tx_n - x_n能够收敛到零。如果\lambda_n \to 0太快，算法可能停滞；如果\lambda_n \to 1太快，算法可能失去收敛保证。

α-平均算子的定义

为了更深入理解和推广Krasnosel'skii-Mann算法，我们需要引入α-平均算子的概念。设\mathcal{H}是实希尔伯特空间，C \subset \mathcal{H}是非空子集，A: C \to \mathcal{H}是一个算子，\alpha \in ]0,1]。

算子A称为α-平均的（α-averaged），如果存在非扩张算子R: C \to \mathcal{H}使得：

这里\text{Id}是恒等算子。这个定义表明α-平均算子是恒等映射和某个非扩张算子的凸组合。几何直观是：A将每个点x映射到x和Rx之间的某个位置，比例由\alpha决定。

当\alpha = 1/2时，算子A称为坚定非扩张的（firmly nonexpansive）。这是一个特别重要的类别，因为许多优化算法中的关键算子（如近端算子）都是坚定非扩张的。

为什么要研究α-平均算子？首先，它们形成了一个比非扩张算子更具结构的类别，同时仍然保持了良好的收敛性质。其次，Krasnosel'skii-Mann算法实际上可以理解为对某个α-平均算子的固定点迭代。具体地，定义A_\lambda = (1-\lambda)\text{Id} + \lambda T，则A_\lambda是\lambda-平均的，而Krasnosel'skii-Mann迭代正是x_{n+1} = A_{\lambda_n} x_n。

α-平均算子的等价刻画

α-平均算子有一个重要的等价刻画，通过一个特殊的不等式来表征。算子A: C \to \mathcal{H}是α-平均的当且仅当对所有(x,y) \in C^2，有：

这个不等式的左边有两项：第一项\|Ax - Ay\|^2衡量A作用后的距离，第二项涉及\text{Id}-A（即x - Ax，可理解为"位移"）的变化。不等式表明这两项的加权和不超过原始距离的平方。

证明的关键步骤展示了如何从这个不等式推导出A的分解形式。首先，将不等式展开并整理：

通过代数操作，可以得到：

继续化简后得到：

这意味着算子R = \frac{A - (1-\alpha)\text{Id}}{\alpha}满足\|Rx - Ry\| \leq \|x - y\|，即R是非扩张的。而且A = (1-\alpha)\text{Id} + \alpha R，正好就是α-平均算子的定义。

这个等价刻画的意义在于它提供了验证算子是否α-平均的直接方法。在实际应用中，许多算子可以通过验证这个不等式来证明其α-平均性，而不需要显式地找出分解A = (1-\alpha)\text{Id} + \alpha R中的R。

α-平均算子的性质与固定点算法（修正版）

α-平均算子与非扩张性

从α-平均算子的等价刻画：

由于第二项非负，我们立即得到\|Ax - Ay\|^2 \leq \|x-y\|^2，因此每个α-平均算子都是非扩张的。

坚定非扩张算子

当\alpha = 1/2时，算子A称为坚定非扩张的，满足：

α-平均算子的组合性质

设A_1是\alpha_1-平均的，A_2是\alpha_2-平均的。

凸组合：\lambda A_1 + (1-\lambda)A_2是\alpha-平均的，其中\alpha = \lambda\alpha_1 + (1-\lambda)\alpha_2。

复合：若A_2(C) \subset C，则A_1 \circ A_2是\alpha-平均的，其中：

α-平均算子的固定点算法及完整证明

定理：设T: \mathcal{H} \to \mathcal{H}是\alpha-平均算子，\alpha \in [0,1[，\text{Fix}T \neq \varnothing。设(\lambda_n)_{n\in\mathbb{N}}满足\lambda_n \in [0, 1/\alpha]且：

对任意x_0 \in \mathcal{H}，定义x_{n+1} = x_n + \lambda_n(Tx_n - x_n)，则：

1. (x_n)_{n\in\mathbb{N}}关于\text{Fix}T是Fejér单调的
2. (Tx_n - x_n)_{n\in\mathbb{N}}强收敛到0
3. (x_n)_{n\in\mathbb{N}}弱收敛到\text{Fix}T中的某点

证明：

由于T是\alpha-平均的，存在非扩张算子R使得T = (1-\alpha)\text{Id} + \alpha R。

设\mu_n = \alpha\lambda_n \in [0,1]（因为\lambda_n \in [0, 1/\alpha]）。

条件转化：

迭代重写：

固定点集的等价性：对任意x \in \mathcal{H}，

因此\text{Fix}R = \text{Fix}T \neq \varnothing。

现在迭代x_{n+1} = x_n + \mu_n(Rx_n - x_n)正是对非扩张算子R应用Krasnosel'skii-Mann算法，其中\mu_n \in [0,1]且\sum_{n} \mu_n(1-\mu_n) = +\infty。

根据Krasnosel'skii-Mann定理：

• (x_n)_{n\in\mathbb{N}}关于\text{Fix}R = \text{Fix}T是Fejér单调的
• (Rx_n - x_n)_{n\in\mathbb{N}}强收敛到0
• (x_n)_{n\in\mathbb{N}}弱收敛到\text{Fix}R = \text{Fix}T中的某点

由于Tx_n - x_n = (1-\alpha)x_n + \alpha Rx_n - x_n = \alpha(Rx_n - x_n)，且\alpha > 0，我们有(Tx_n - x_n)_{n\in\mathbb{N}}强收敛到0。

备注：当\alpha < 1时，可以选择\lambda_n = 1对所有n，得到简单迭代：

这时条件\sum_{n} 1 \cdot (1-\alpha) = +\infty自动满足（因为\alpha < 1），所以简单固定点迭代对α-平均算子（\alpha < 1）总是收敛的。

Descent Lemma（下降引理）

这个引理建立了一个函数在两点之间的函数值增量的上界估计。我们先看引理的条件设定：设 \mathcal{H} 是一个实希尔伯特空间，f: \mathcal{H} \to \mathbb{R} 是定义在这个空间上的实值函数，\nu \in ]0, +\infty[ 是一个正常数。引理要求 f 满足两个性质：第一，f 是Fréchet可微的，这意味着 f 在每一点都存在梯度 \nabla f(x)，并且这个梯度能够很好地逼近函数在该点附近的线性增量；第二，f 的梯度是 \nu-Lipschitz连续的，即对任意两点 x_1, x_2 \in \mathcal{H}，有 \|\nabla f(x_1) - \nabla f(x_2)\| \leq \nu \|x_1 - x_2\|。这个Lipschitz常数 \nu 实际上控制了梯度变化的剧烈程度。

在这两个条件下，引理给出的结论是：对于希尔伯特空间中的任意两点 (x, y) \in \mathcal{H}^2，函数值 f(y) 可以被如下不等式约束：

这个不等式的含义是：从 x 移动到 y 时，函数值的增量不会超过三项的和。第一项 f(x) 是起点的函数值，第二项 \langle y - x \mid \nabla f(x) \rangle 是用 x 点的梯度对函数增量做的线性近似（这正是一阶泰勒展开的线性项），第三项 \frac{\nu}{2}\|y - x\|^2 是一个二次修正项，它依赖于两点之间的距离平方和梯度的Lipschitz常数。

证明思路

证明的核心策略是将问题从希尔伯特空间降维到一维实数空间上的积分问题。具体来说，对于固定的 (x, y) \in \mathcal{H}^2 和参数 t \in \mathbb{R}，我们构造辅助函数：

这个函数的几何意义是：\varphi(t) 描述了当我们从点 x 沿着方向 y - x 移动距离 t\|y - x\| 时，函数 f 的取值。特别地，\varphi(0) = f(x) 对应起点，\varphi(1) = f(y) 对应终点。通过这个参数化，我们把原本的多维问题转化为关于标量参数 t 的一维函数研究。

由于 f 是Fréchet可微的，复合函数 \varphi 也是Fréchet可微的（实际上就是普通的可微），并且根据链式法则，\varphi 的导数为：

这里用到了多元函数的链式法则：当我们对 t 求导时，内层 x + t(y - x) 对 t 的导数是 y - x，而外层 f 在点 x + t(y - x) 处的导数是梯度 \nabla f(x + t(y - x))，两者的内积就是 \varphi 对 t 的导数。

接下来应用微积分基本定理。对于可微函数 \varphi，从 t=0 到 t=1 的增量可以表示为导数的积分：

将 \varphi 的定义代入，左边变成 f(y) - f(x)，右边代入 \varphi'(t) 的表达式：

现在我们要处理这个积分。注意到当 t=0 时，被积函数中的梯度恰好是 \nabla f(x)。因此我们可以将右边改写，从积分中分离出 \nabla f(x) 这一项：

这个等式的左边正是函数在 y 点的值减去在 x 点的一阶线性近似，也就是我们需要估计上界的那个量。右边的积分衡量了梯度从 x 变化到沿途各点时产生的累积效应。

现在利用梯度的Lipschitz性质来估计这个积分。对于被积函数中的内积项，应用Cauchy-Schwarz不等式：

Cauchy-Schwarz不等式告诉我们两个向量的内积不超过它们范数的乘积。接下来利用梯度的 \nu-Lipschitz性质。点 x + t(y - x) 与点 x 之间的距离是 \|t(y - x)\| = t\|y - x\|（这里用了 t \in [0,1] 所以 t \geq 0），因此：

将这两个不等式结合起来：

把这个上界代入之前的积分式：

计算右边的积分，\nu\|y - x\|^2 是常数可以提出来：

因此我们得到：

移项即得到下降引理的结论：

整个证明的逻辑链条是：通过参数化将多维问题降为一维，用微积分基本定理将函数增量表示为导数积分，再利用Cauchy-Schwarz不等式和梯度的Lipschitz性质控制积分的上界，最终得到函数值的二次上界估计。这个上界中的二次项系数 \frac{\nu}{2} 直接来源于Lipschitz常数和参数积分 \int_0^1 t dt = \frac{1}{2}。

α-averaged operator 的例子

这一部分要证明一个具体的结论：设 f \in \Gamma_0(\mathcal{H})，即 f 是希尔伯特空间上的proper、lower semicontinuous、凸函数，参数 \nu \in ]0, 2[。如果 f 可微且其梯度是 \nu-Lipschitz连续的，那么算子 \text{Id} - \nabla f 是一个 \frac{\nu}{2}-averaged算子。这里 \text{Id} 表示恒等映射，即 \text{Id}(x) = x。我们要证明的核心是算子 \text{Id} - \nabla f 具有某种收缩性质，这个性质由参数 \frac{\nu}{2} 刻画。

证明的第一步：利用共轭函数的定义

证明从任意三点 (x, y, z) \in \mathcal{H}^3 开始。考虑 f 的Fenchel共轭函数 f^*，它的定义是：

这个共轭函数的含义是：对于给定的 u，我们在所有可能的 v 上最大化线性项 \langle v \mid u \rangle 与函数值 f(v) 之差。现在我们具体考虑 f^*(\nabla f(y))，根据定义，它等于在所有 z' \in \mathcal{H} 上对 \langle z' \mid \nabla f(y) \rangle - f(z') 取上确界。由于是取上确界，对于任何特定的 z，我们有：

这个不等式只是说上确界不小于任何一个具体取值。接下来我们要对右边这个表达式进行精细的处理。

引入下降引理

现在对 \langle z \mid \nabla f(y) \rangle - f(z) 进行改写。我们将内积项拆分成两部分：

这只是简单的线性性质。因此：

对于最后一项 \langle z \mid \nabla f(x) \rangle - f(z)，我们可以应用下降引理。在下降引理中，如果我们交换 y 和 z 的角色（即把原本的 y 看作这里的 z，原本的 x 还是 x），下降引理给出：

移项可得：

注意 \langle z \mid \nabla f(x) \rangle - \langle z - x \mid \nabla f(x) \rangle = \langle x \mid \nabla f(x) \rangle，所以：

把这个结果代回到之前的式子：

应用Fenchel-Young不等式

Fenchel-Young不等式是凸分析中的基本不等式，它指出对于凸函数 f 和它的共轭函数 f^*，对任意 x 和 u，有：

等号成立当且仅当 u \in \partial f(x)，即 u 属于 f 在 x 处的次梯度。对于可微函数，\partial f(x) = \{\nabla f(x)\}，所以当 u = \nabla f(x) 时等号成立：

移项得到：

将这个等式代入前面的不等式：

对内积项进行分解

现在对内积 \langle z \mid \nabla f(y) - \nabla f(x) \rangle 进行另一次分解。注意到：

代入得到：

这个不等式对所有的 z \in \mathcal{H} 都成立。现在我们要对 z 取上确界。右边关于 z 的项是：

令 w = z - x，这个表达式变成：

对 w 取上确界，这个表达式的形式正是某个函数的共轭。具体地，考虑函数 g(w) = \frac{\nu}{2}\|w\|^2，它的共轭函数是：

这个上确界在 w = \frac{v}{\nu} 处达到（对 w 求导并令导数为零），代入得：

因此：

将这个结果代入不等式，得到：

这是一个关键的不等式，它表明共轭函数 f^* 在梯度点 \nabla f(y) 处的值可以被 \nabla f(x) 处的值加上某些修正项来下界估计。

对称性与Baillon-Haddad定理

上面的不等式对任意 (x, y) \in \mathcal{H}^2 成立。由于 x 和 y 的地位是对称的，我们可以交换它们得到对称的不等式：

现在将这两个不等式相加。左边是 f^*(\nabla f(y)) + f^*(\nabla f(x))，右边是：

两边同时减去 f^*(\nabla f(x)) + f^*(\nabla f(y))，得到：

注意到 \langle x \mid \nabla f(y) - \nabla f(x) \rangle + \langle y \mid \nabla f(x) - \nabla f(y) \rangle = -\langle y - x \mid \nabla f(y) - \nabla f(x) \rangle，所以：

移项得到：

这个不等式称为Baillon-Haddad定理，它给出了梯度差向量与位置差向量的内积的下界。

最终的averaged operator性质

现在我们来证明 \text{Id} - \nabla f 是 \frac{\nu}{2}-averaged算子。考虑：

展开这个范数的平方：

利用Baillon-Haddad不等式 \langle y - x \mid \nabla f(y) - \nabla f(x) \rangle \geq \frac{1}{\nu}\|\nabla f(y) - \nabla f(x)\|^2，即 -\langle x - y \mid \nabla f(x) - \nabla f(y) \rangle \geq \frac{1}{\nu}\|\nabla f(x) - \nabla f(y)\|^2，代入得：

移项并整理：

注意到 \frac{2 - \nu}{\nu} = \frac{2}{\nu} - 1。另一方面，我们可以写成：

因此最终的不等式是：

这个不等式正是 \text{Id} - \nabla f 是 \frac{\nu}{2}-averaged算子的定义式。它表明算子 \text{Id} - \nabla f 具有受控的非扩张性：不仅算子作用后两点的距离不会变大，而且还有一个额外的"余量"项，这个余量由梯度差的范数平方给出，系数依赖于参数 \frac{\nu}{2}。

α-averaged operator的推广：带步长的梯度下降算子

前面我们证明了当 f 可微且梯度是 \nu-Lipschitz连续时，算子 \text{Id} - \nabla f 是 \frac{\nu}{2}-averaged的。现在我们考虑一个更一般的情况：在梯度前面乘以一个正的步长参数 \gamma。具体地，设 f \in \Gamma_0(\mathcal{H})，\nu \in ]0, +\infty[，并且额外引入参数 \gamma \in ]0, \frac{2}{\nu}[。在同样的可微性和Lipschitz条件下，算子 \text{Id} - \gamma\nabla f 是一个 \frac{\gamma\nu}{2}-averaged算子。

这个结果与之前的区别在于：当我们用 \gamma\nabla f 替换 \nabla f 时，averaged的参数从 \frac{\nu}{2} 变成了 \frac{\gamma\nu}{2}，即按比例缩放了 \gamma 倍。为了理解为什么会这样，我们需要重新审视之前的推导。在之前的证明中，关键的Baillon-Haddad不等式是：

现在考虑算子 \text{Id} - \gamma\nabla f，其作用下两点的距离平方是：

展开得到：

利用Baillon-Haddad不等式，-\langle x - y \mid \nabla f(x) - \nabla f(y) \rangle \geq \frac{1}{\nu}\|\nabla f(x) - \nabla f(y)\|^2，代入得：

注意到 \gamma(\text{Id} - \gamma\nabla f) = \gamma x - \gamma^2\nabla f(x)，但这不是我们需要的形式。我们需要的是 (\text{Id} - \gamma\nabla f) - \text{Id} = -\gamma\nabla f，因此：

为了写成averaged operator的标准形式，注意到：

因此我们需要将系数 \gamma\left(\frac{2}{\nu} - \gamma\right) 表示成形如 \frac{1 - \alpha}{\alpha} \cdot \gamma^2 的形式。令：

解得：

因此：

这就是为什么 \text{Id} - \gamma\nabla f 是 \frac{\gamma\nu}{2}-averaged算子。注意到条件 \gamma \in ]0, \frac{2}{\nu}[ 保证了 \alpha = \frac{\gamma\nu}{2} \in ]0, 1[，这是averaged operator定义所要求的参数范围。

这里有一个注释说明算子 \text{Id} - \gamma\nabla f 就是梯度下降算子。这是因为在优化问题中，为了最小化函数 f，我们从当前点 x 沿着负梯度方向 -\nabla f(x) 移动一个步长 \gamma，得到新的迭代点 x - \gamma\nabla f(x)，这正是算子 \text{Id} - \gamma\nabla f 作用在 x 上的结果。参数 \gamma 称为步长或学习率。

proximity operator的firmly nonexpansive性质

接下来看另一个例子。设 f \in \Gamma_0(\mathcal{H})，那么proximity operator \text{prox}_f 是firmly nonexpansive的，也就是说它是一个 \frac{1}{2}-averaged算子。这个性质不需要 f 可微，只需要 f 是proper、lower semicontinuous、凸函数。

证明的起点：次梯度的单调性

证明从次梯度的单调性开始。对于凸函数 f，它的次梯度映射 \partial f 是单调的，这意味着：对于任意 x_1, x_2 \in \mathcal{H} 和任意 u_1 \in \partial f(x_1)，u_2 \in \partial f(x_2)，有：

这个单调性反映了凸函数的次梯度随着点的移动而"同向变化"。现在对这个不等式进行改写。将 u_1 - u_2 拆分为 (x_1 - x_2) + (u_1 - u_2) - (x_1 - x_2)，代入内积：

因此单调性 \langle x_1 - x_2 \mid u_1 - u_2 \rangle \geq 0 等价于：

这个改写的关键在于，x_1 + u_1 和 x_2 + u_2 出现在右边的内积中。

引入反向proximity operator关系

现在我们利用 \partial f 与 \text{Id} + \partial f 的关系。如果 u_1 \in \partial f(x_1)，那么根据次梯度的定义和proximity operator的一阶最优性条件，我们知道 x_1 = \text{prox}_f(x_1 + u_1)。换句话说，x_1 + u_1 \in (\text{Id} + \partial f)(x_1) 的逆运算就是 x_1 = \text{prox}_f(x_1 + u_1)。

定义 u'_1 = x_1 + u_1 \in (\text{Id} + \partial f)x_1 和 u'_2 = x_2 + u_2 \in (\text{Id} + \partial f)x_2。那么从反向关系，我们有 x_1 = \text{prox}_f u'_1 和 x_2 = \text{prox}_f u'_2。将这些关系代入之前的不等式，x_1 - x_2 = \text{prox}_f u'_1 - \text{prox}_f u'_2 且 x_1 - x_2 + u_1 - u_2 = u'_1 - u'_2，因此：

即：

这个不等式说明 \text{prox}_f 的增量与输入增量的内积至少是 \text{prox}_f 增量的范数平方。

推导firmly nonexpansive性质

现在我们要证明 \text{prox}_f 是 \frac{1}{2}-averaged的，即需要证明：

我们从恒等式开始。注意到 u'_1 - u'_2 = (\text{prox}_f u'_1 - \text{prox}_f u'_2) + ((\text{Id} - \text{prox}_f)u'_1 - (\text{Id} - \text{prox}_f)u'_2)，因此：

交叉项可以改写。注意到：

利用之前得到的不等式 \langle \text{prox}_f u'_1 - \text{prox}_f u'_2 \mid u'_1 - u'_2 \rangle \geq \|\text{prox}_f u'_1 - \text{prox}_f u'_2\|^2，我们有：

因此交叉项非负。这意味着在展开式中，交叉项不会减小右边的和，从而：

这正是 \frac{1}{2}-averaged算子的定义式（当 \alpha = \frac{1}{2} 时，\frac{1-\alpha}{\alpha} = 1，所以两项的系数相等）。这个性质称为firmly nonexpansive，它表明 \text{prox}_f 不仅是非扩张的（non-expansive），而且满足更强的性质：应用算子后的距离平方加上"残差"（即 (\text{Id} - \text{prox}_f) 的增量）的距离平方不超过原始距离平方。

Forward-Backward优化算法

这一部分介绍一个具体的优化算法，用于求解复合优化问题 \min (f + g)，其中两个函数 f 和 g 具有不同的性质。问题设置如下：f \in \Gamma_0(\mathcal{H}) 是一个proper、lower semicontinuous、凸函数，但不一定可微；g \in \Gamma_0(\mathcal{H}) 也是凸函数，但额外要求它可微且其梯度是 \nu-Lipschitz连续的，其中 \nu \in ]0, +\infty[。这种函数分离的设置在实际应用中很常见：g 通常是一个光滑的数据拟合项（如平方损失），而 f 则是一个可能不光滑的正则化项（如L1范数）。

引入两个关键参数。参数 \gamma \in ]0, \frac{2}{\nu}[ 是梯度下降的步长，它的上界 \frac{2}{\nu} 来自于梯度的Lipschitz常数，确保算法的稳定性。参数 \delta = 2 - \frac{\gamma\nu}{2} \in ]1, 2[ 是一个派生量，它与 \gamma 的关系保证了 \delta > 1（因为 \gamma < \frac{2}{\nu} 意味着 \frac{\gamma\nu}{2} < 1，所以 \delta = 2 - \frac{\gamma\nu}{2} > 1）且 \delta < 2（因为 \gamma > 0 意味着 \frac{\gamma\nu}{2} > 0，所以 \delta < 2）。

接下来定义步长序列 (\lambda_n)_{n \in \mathbb{N}}，它是 [0, \delta] 中的一个序列，满足关键条件：

这个条件称为步长充分性条件。它的含义是：尽管每一步的步长 \lambda_n 可能很小，但整个序列必须"足够大"，使得无穷和发散。注意 \lambda_n(\delta - \lambda_n) 是一个关于 \lambda_n 的二次函数，当 \lambda_n = \frac{\delta}{2} 时达到最大值 \frac{\delta^2}{4}。这个条件排除了步长衰减过快的情况，例如 \lambda_n = O(\frac{1}{n^2}) 就不满足。典型的满足条件的例子是常步长 \lambda_n = \lambda_0 \in (0, \delta)（此时和显然发散）或者 \lambda_n = O(\frac{1}{n})（此时 \lambda_n(\delta - \lambda_n) \sim \frac{c}{n}，调和级数发散）。

我们还假设 \text{Argmin}(f + g) \neq \varnothing，即优化问题有解。给定初始点 x_0 \in \mathcal{H}，算法的迭代格式是：

这个迭代分为两步。第一步 y_n = x_n - \gamma\nabla g(x_n) 是一个前向步（forward step），它对可微部分 g 进行显式梯度下降。第二步 x_{n+1} = x_n + \lambda_n(\text{prox}_{\gamma f} y_n - x_n) 是一个后向步（backward step），它对不可微部分 f 应用proximity operator，并用步长 \lambda_n 进行松弛：如果 \lambda_n = 1，这一步就是直接取 x_{n+1} = \text{prox}_{\gamma f} y_n；如果 \lambda_n < 1，则在当前点 x_n 和 \text{prox}_{\gamma f} y_n 之间进行凸组合，即 x_{n+1} = (1 - \lambda_n)x_n + \lambda_n \text{prox}_{\gamma f} y_n。

在这些条件下，定理断言序列 (x_n)_{n \in \mathbb{N}} 弱收敛到 f + g 的一个最小值点。弱收敛意味着对任意连续线性泛函 \phi，有 \phi(x_n) \to \phi(x^*) 其中 x^* \in \text{Argmin}(f + g)。这比强收敛（范数收敛）要弱，但在无穷维希尔伯特空间中已经是很好的结果。

算法的收敛性证明

证明的核心思想是将迭代格式重写为一个不动点迭代，并利用averaged operator的性质。定义算子：

这个算子的复合结构恰好对应于前向-后向迭代的一次完整步骤（当 \lambda_n = 1 时）。我们首先证明 T 的不动点集合恰好是原优化问题的解集。

对于任意 x \in \mathcal{H}，x 是 T 的不动点意味着：

根据proximity operator的定义，x = \text{prox}_{\gamma f}(x - \gamma\nabla g(x)) 等价于 x 是如下问题的最优解：

这个问题的一阶最优性条件（次梯度条件）是：

移项得到 0 \in \nabla g(x) + \partial f(x)。由于 g 可微，\nabla g(x) 就是 g 的次梯度，因此这等价于 0 \in \partial(g + f)(x)，即 x 是 f + g 的稳定点（对于凸函数，稳定点就是最小值点）。

反过来，这个推导也是可逆的，所以：

这里 \text{zer}(A) 表示多值映射 A 的零点集，即 \{x : 0 \in A(x)\}。因此 T 的不动点集恰好是我们要找的解集，而且这个集合非空。

接下来分析算子 T 的averaged性质。我们已经知道 \text{prox}_{\gamma f} 是 \frac{1}{2}-averaged的，\text{Id} - \gamma\nabla g 是 \frac{\gamma\nu}{2}-averaged的。当两个averaged operator复合时，复合算子仍然是averaged的，其参数可以通过特定公式计算。

具体地，如果 A_1 是 \alpha_1-averaged，A_2 是 \alpha_2-averaged，那么在一定条件下，A_2 \circ A_1 是 \alpha-averaged，其中：

但这里PPT给出的公式更直接。将 \alpha_1 = \frac{1}{2} 和 \alpha_2 = \frac{\gamma\nu}{2} 代入，复合算子的averaged参数是：

因此 \alpha^{-1} = 2 - \frac{\gamma\nu}{2} = \delta，即 T 是 \alpha-averaged的，其中 \alpha = \frac{1}{\delta}。由于 \delta \in ]1, 2[，我们有 \alpha \in ]\frac{1}{2}, 1[，这确保 T 是一个averaged operator（参数必须在 (0, 1) 内）。

现在观察实际的迭代格式。将 x_{n+1} = x_n + \lambda_n(\text{prox}_{\gamma f} y_n - x_n) 改写，注意到 y_n = x_n - \gamma\nabla g(x_n)，所以 \text{prox}_{\gamma f} y_n = T(x_n)。因此：

这正是对算子 T 进行的松弛不动点迭代（Krasnoselskii-Mann迭代）。对于 \alpha-averaged operator和满足条件 \sum_n \lambda_n(\delta - \lambda_n) = +\infty 的步长序列（其中 \delta = \alpha^{-1}），Krasnoselskii-Mann迭代理论保证序列弱收敛到 T 的不动点。由于 \text{Fix } T = \text{Argmin}(f + g)，我们得到 (x_n)_{n \in \mathbb{N}} 弱收敛到 f + g 的最小值点。

Forward-Backward算法的变步长版本

上述算法可以进一步推广，允许梯度下降步长 \gamma 也随迭代变化。新的设置是：(\gamma_n)_{n \in \mathbb{N}} 是一个序列，取值于区间 [\gamma, \overline{\gamma}]，其中 0 < \gamma < \overline{\gamma} < \frac{2}{\nu}。这个区间的选择保证每个 \gamma_n 都满足前面算法所需的上界条件。步长序列 (\lambda_n)_{n \in \mathbb{N}} 取值于 [\underline{\lambda}, 1]，其中 0 < \underline{\lambda} \leq 1。注意这里的步长下界是严格正的，这与前面的条件 \sum_n \lambda_n(\delta - \lambda_n) = +\infty 是一致的：如果 \lambda_n \geq \underline{\lambda} > 0，那么无穷和自动发散。

迭代格式变为：

与之前唯一的区别是 \gamma 被替换为 \gamma_n，proximity operator的参数也相应变化为 \gamma_n f。这个推广在实践中很有用，因为它允许自适应地选择步长，例如通过线搜索来加速收敛。在给定的参数范围下，定理保证 (x_n)_{n \in \mathbb{N}} 仍然弱收敛到 f + g 的最小值点。证明的关键在于每次迭代对应的算子 T_n = \text{prox}_{\gamma_n f} \circ (\text{Id} - \gamma_n\nabla g) 都是averaged的，且averaged参数在某个范围内一致有界，这使得可以应用关于非齐次不动点迭代的收敛定理。

Projected Gradient算法

这是Forward-Backward算法的一个特殊但重要的应用场景。问题设置是：C 是 \mathcal{H} 的一个非空闭凸子集，g \in \Gamma_0(\mathcal{H}) 可微且梯度 \nu-Lipschitz连续，\nu \in ]0, +\infty[。参数设置与之前相同：\gamma \in ]0, \frac{2}{\nu}[，\delta = 2 - \frac{\gamma\nu}{2} \in ]1, 2[，步长序列 (\lambda_n)_{n \in \mathbb{N}} 在 [0, \delta] 中且满足 \sum_{n \in \mathbb{N}} \lambda_n(\delta - \lambda_n) = +\infty。我们假设 g 在 C 上的极小值点存在，即 \text{Argmin}_{x \in C} g(x) \neq \varnothing。

迭代格式是：

这里 P_C 是到凸集 C 的投影算子，定义为 P_C(y) = \arg\min_{z \in C} \|z - y\|。第一步仍然是对 g 进行无约束的梯度下降，第二步将结果投影回可行集 C。

这个算法实际上是Forward-Backward算法的特例。为了看清这一点，定义指示函数 \iota_C : \mathcal{H} \to \mathbb{R} \cup \{+\infty\}：

这个函数属于 \Gamma_0(\mathcal{H})（proper、凸、lower semicontinuous）。对于指示函数，它的proximity operator恰好是投影算子：

因此投影梯度算法的迭代格式可以写成：

这恰好是Forward-Backward算法应用于问题 \min (g + \iota_C) 的形式，而 \min_{x \in \mathcal{H}} (g(x) + \iota_C(x)) = \min_{x \in C} g(x) 正是我们要解决的约束优化问题。因此前面的收敛性分析完全适用，我们得出结论：(x_n)_{n \in \mathbb{N}} 弱收敛到 g 在 C 上的最小值点。

这个算法的几何直观是：先沿着负梯度方向移动（这可能离开可行集），然后投影回可行集。当可行集有简单的几何结构（如球、盒子、单纯形等）时，投影算子通常有闭式解或可以高效计算，这使得投影梯度法成为求解约束优化问题的实用方法。

梯度下降算法

这是Forward-Backward算法的一个特殊情况，当 f = 0 时就退化为纯粹的梯度下降。问题设置是：g \in \Gamma_0(\mathcal{H}) 是可微函数，其梯度是 \nu-Lipschitz连续的，\nu \in ]0, +\infty[。步长序列 (\gamma_n)_{n \in \mathbb{N}} 取值于区间 [\gamma, \overline{\gamma}]，其中 0 < \gamma < \overline{\gamma} < \frac{2}{\nu}。这个上界 \frac{2}{\nu} 是收敛性的必要条件，它来自于梯度Lipschitz常数的倒数的两倍。我们假设 \text{Argmin } g \neq \varnothing，即 g 的最小值点存在。

给定初始点 x_0 \in \mathcal{H}，梯度下降的迭代格式是：

这个迭代非常简单：每一步都沿着当前点梯度的负方向移动，移动的距离由步长 \gamma_n 控制。负梯度方向是函数下降最快的方向（至少在局部线性近似意义下），这就是为什么这个算法能够找到最小值点。

为了理解这个算法与之前框架的关系，注意到当 f = 0 时，\text{prox}_{\gamma f}(x) = \text{prox}_0(x) = x（因为 \arg\min_z \{\frac{1}{2\gamma}\|z - x\|^2\} = x）。因此Forward-Backward迭代变成：

如果取 \lambda_n = 1，就得到 x_{n+1} = y_n = x_n - \gamma_n\nabla g(x_n)，这正是梯度下降的迭代。在前面给定的参数范围下，定理保证序列 (x_n)_{n \in \mathbb{N}} 弱收敛到 g 的最小值点。

这个结果的关键在于步长必须足够小。如果 \gamma_n 太大（超过 \frac{2}{\nu}），梯度下降可能会发散或振荡。直观上，\frac{1}{\nu} 给出了函数曲率的某种度量：\nu 越大意味着梯度变化越剧烈，因此需要更小的步长来保证稳定性。步长上界 \frac{2}{\nu} 是一个理论保证，实践中通常会选择更保守的值如 \frac{1}{\nu}。

近端点算法

这是另一个基本的优化算法，它不需要函数可微，只需要函数是 \Gamma_0(\mathcal{H}) 中的元素。设 f \in \Gamma_0(\mathcal{H})，步长序列 (\gamma_n)_{n \in \mathbb{N}} 是 ]0, +\infty[ 中的序列，满足关键条件：

这个条件要求步长的和发散到无穷。它的作用类似于之前Forward-Backward中的 \sum_n \lambda_n(\delta - \lambda_n) = +\infty，确保算法"走得足够远"。如果步长衰减太快（比如 \gamma_n = O(\frac{1}{n^2})），和会收敛到有限值，这会导致迭代序列过早停滞。典型的满足条件的例子是常步长 \gamma_n = \gamma_0 > 0 或者 \gamma_n = \frac{1}{n}（调和级数发散）。

我们假设 \text{Argmin } f \neq \varnothing。给定初始点 x_0 \in \mathcal{H}，近端点算法的迭代格式极其简单：

每一步就是对当前点应用proximity operator。这个迭代的几何意义是：x_{n+1} 是如下问题的解：

这个问题在原目标函数 f 上添加了一个二次惩罚项 \frac{1}{2\gamma_n}\|z - x_n\|^2，它把解"拉"向当前点 x_n。当 \gamma_n 很小时，惩罚很强，x_{n+1} 会非常接近 x_n（迭代步长小）；当 \gamma_n 较大时，惩罚较弱，算法更多地考虑最小化 f(z) 本身（迭代步长大）。

在给定的条件下（\sum_n \gamma_n = +\infty），定理保证 (x_n)_{n \in \mathbb{N}} 弱收敛到 f 的最小值点。这个算法的优势是不需要 f 可微，甚至不需要 f 光滑。只要 proximity operator 可以计算（对于很多结构化的凸函数这都是可行的），算法就能运行。劣势是每次迭代需要解一个子问题（计算 \text{prox}_{\gamma_n f}），这可能比简单的梯度计算更昂贵。

近端点算法可以看作是梯度下降在不可微情况下的推广。当 f 可微且梯度Lipschitz连续时，对于小的 \gamma_n，可以证明 \text{prox}_{\gamma_n f}(x) \approx x - \gamma_n\nabla f(x)，因此近端点迭代近似于梯度下降。但对于一般的凸函数，proximity operator提供了一种更鲁棒的"下降"机制。

加速版本

这一部分介绍Nesterov加速方法，它可以显著提升收敛速度。问题设置与Forward-Backward相同：f \in \Gamma_0(\mathcal{H})，g \in \Gamma_0(\mathcal{H}) 可微且梯度 \nu-Lipschitz连续，\nu \in ]0, +\infty[。但参数设置有所不同：步长 \gamma \in ]0, \frac{1}{\nu}]（注意上界从 \frac{2}{\nu} 变成了 \frac{1}{\nu}，更加保守），动量参数 \zeta \in [2, +\infty[。我们仍然假设 \text{Argmin}(f + g) \neq \varnothing。

初始化需要两个点：x_0 = z_0 \in \mathcal{H}。迭代格式包含三个方程：

第一个方程与Forward-Backward完全相同：对 z_n 做前向-后向步得到 x_{n+1}。关键的改进在于引入了动量序列 z_n。第三个方程定义了 z_{n+1} 为 x_{n+1} 加上一个"动量项" \lambda_n(x_{n+1} - x_n)。这个动量项的意义是：它考虑了过去两次迭代点的差异 x_{n+1} - x_n，可以看作是迭代的"速度"或"方向"。通过将这个方向的信息注入到下一步的搜索起点 z_{n+1} 中，算法可以加速收敛。

动量系数 \lambda_n = \frac{n}{n + 1 + \zeta} 随着 n 增加而递增。当 n = 0 时，\lambda_0 = 0，所以 z_1 = x_1；当 n \to \infty 时，\lambda_n \to 1，意味着动量的影响逐渐增强。参数 \zeta 控制这个增长的速度：\zeta 越大，\lambda_n 增长越慢，算法更保守；\zeta 越小（但至少是2），\lambda_n 增长越快，动量效果越强。

这个算法有两个重要结果。首先，存在常数 M \in [0, +\infty[ 使得对所有 n \in \mathbb{N} \setminus \{0\}（即 n \geq 1），有：

这是一个收敛速率的估计。它说明函数值与最优值的差距以 O(\frac{1}{n^2}) 的速度衰减。相比之下，不带加速的Forward-Backward或梯度下降通常只有 O(\frac{1}{n}) 的速率，因此加速版本在这个意义下快了一个数量级。这个二次速率是光滑凸优化的最优速率（在一阶方法中）。

其次，如果 \zeta > 2，那么序列 (x_n)_{n \in \mathbb{N}} 还弱收敛到 f + g 的最小值点。注意当 \zeta = 2 时定理只保证函数值收敛（速率 O(\frac{1}{n^2})），不保证点列收敛；只有当 \zeta > 2 时才有弱收敛保证。这是一个微妙的区别：在实际应用中，\zeta = 2 给出最快的函数值下降（因为动量最强），但可能导致点列振荡；选择 \zeta 稍大于2可以同时获得快速收敛和点列收敛性。

优化策略的总结

这一部分对之前介绍的算法进行对比和总结。问题的一般形式是：给定 f \in \Gamma_0(\mathcal{H}) 和 g \in \Gamma_0(\mathcal{H})，我们要求解：

根据 f 和 g 的不同性质，我们有不同的算法选择。第一种情况，如果要用梯度下降算法，那么 f + g 需要是光滑的，即整体可微且梯度Lipschitz连续。这个要求很强，因为很多实际问题中的正则化项（如L1范数、指示函数等）都是不可微的，所以纯梯度下降的适用范围受限。

第二种情况，如果要用近端点算法，那么 f + g 需要是"proximable"的，即它的proximity operator可以高效计算。这个条件也相当强。虽然很多单个函数的proximity operator有闭式解（如范数、指示函数、二次函数等），但两个函数和 f + g 的proximity operator通常没有闭式解。计算 \text{prox}_{\gamma(f+g)} 本身就是一个优化问题，可能和原问题一样难。

第三种情况，Forward-Backward算法要求 g 是光滑的（可微且梯度Lipschitz连续），但对 f 没有光滑性要求，只需要 \text{prox}_{\gamma f} 可计算。这个分工非常实用：在很多应用中，我们可以把问题分解为一个光滑的损失函数 g（如数据拟合项）和一个可能不光滑但proximity operator可算的正则化项 f（如L1范数）。这种分解结合了两个世界的优势：对光滑部分用高效的梯度计算，对非光滑部分用proximity operator。

最后提出一个关键问题：当 f 和 g 都不光滑时，能否找到一个splitting算法？这个问题的答案将引出后续的算法，如ADMM（交替方向乘子法）或Douglas-Rachford splitting，它们可以处理两个都不光滑的函数的和。这些算法通常需要引入对偶变量或者利用算子分裂的技巧，其理论基础是单调算子理论和不动点理论的进一步发展。

Douglas-Rachford算法

Douglas-Rachford算法解决了前面提出的关键问题：当两个函数 f 和 g 都不光滑时如何求解 \min(f + g)。这个算法不要求 f 或 g 中的任何一个可微，只需要它们都属于 \Gamma_0(\mathcal{H}) 并且各自的proximity operator可以计算。

问题设置如下：\mathcal{H} 是希尔伯特空间，f \in \Gamma_0(\mathcal{H}) 和 g \in \Gamma_0(\mathcal{H})。参数 \gamma \in ]0, +\infty[ 是一个正的尺度参数。步长序列 (\lambda_n)_{n \in \mathbb{N}} 取值于 [0, 2]，满足条件：

这个条件的形式与Forward-Backward中的 \sum_n \lambda_n(\delta - \lambda_n) = +\infty 类似，但这里上界是2而不是 \delta。条件保证步长序列"足够大"使得无穷和发散。典型的满足条件的例子包括常步长 \lambda_n = \lambda_0 \in (0, 2) 或缓慢衰减的步长。我们假设 \text{zer}(\partial f + \partial g) \neq \varnothing，即存在点使得 0 \in \partial f(x) + \partial g(x)，这等价于 \text{Argmin}(f + g) \neq \varnothing。

给定初始点 x_0 \in \mathcal{H}，Douglas-Rachford迭代包含三个步骤：

我们逐步分析这个迭代的几何意义。第一步 y_n = \text{prox}_{\gamma g} x_n 是对当前点 x_n 应用 g 的proximity operator，得到一个中间点 y_n。这个点是最小化 g(z) + \frac{1}{2\gamma}\|z - x_n\|^2 的解，它在 g 的梯度方向（或次梯度方向）上对 x_n 进行了调整。

第二步 z_n = \text{prox}_{\gamma f}(2y_n - x_n) 更加微妙。它的输入不是 y_n 而是 2y_n - x_n，这是一个"反射点"：从 x_n 到 y_n 的向量被延长了一倍。然后对这个反射点应用 f 的proximity operator得到 z_n。这个反射操作是Douglas-Rachford算法的核心创新，它使得算法能够同时"感知"两个函数 f 和 g 的结构。

第三步 x_{n+1} = x_n + \lambda_n(z_n - y_n) 是一个松弛步。注意 z_n - y_n 是从 y_n 指向 z_n 的向量，它衡量了两次proximity operator应用之间的"不一致性"。如果 z_n = y_n，说明两个proximity operator给出了相同的结果，这时算法已经找到了不动点。用步长 \lambda_n 对这个方向进行加权，然后更新 x_n。

算法的收敛性结果包含四个部分。首先，序列 (x_n)_{n \in \mathbb{N}} 弱收敛到某个极限点 \hat{x}。其次，定义 \hat{y} = \text{prox}_{\gamma g} \hat{x}，那么 \hat{y} 属于 \text{Argmin}(f + g)，即 \hat{y} 是原优化问题的解。注意最优点不是序列 x_n 的极限，而是这个极限经过一次 g 的proximity operator作用后的结果。这是Douglas-Rachford算法的一个特点：迭代序列本身不收敛到最优点，但可以通过最后一次proximity operator操作得到最优点。

第三，差值序列 z_n - y_n 弱收敛到0。这意味着随着迭代进行，两次proximity operator给出的结果越来越接近，算法逐渐找到了两个proximity operator的"共同点"。最后，序列 y_n 和 z_n 都弱收敛到 \hat{y}，即最优点。这四个性质共同刻画了算法的收敛行为。

为什么这个算法能够处理两个都不光滑的函数？关键在于算法交替使用两个proximity operator，并通过反射操作将它们耦合起来。每个proximity operator单独处理一个函数的非光滑性，而反射和松弛机制保证了整体迭代的收敛性。从算子理论的角度，Douglas-Rachford算法可以理解为对两个reflector算子 R_f = 2\text{prox}_{\gamma f} - \text{Id} 和 R_g = 2\text{prox}_{\gamma g} - \text{Id} 的复合进行不动点迭代。

Douglas-Rachford的并行形式

这一部分介绍Douglas-Rachford算法的一个重要变体，它可以处理带有线性算子的复合优化问题。问题设置更加复杂：\mathcal{H} 和 \mathcal{G} 是两个希尔伯特空间（可能维度不同）。函数 g \in \Gamma_0(\mathcal{H})，线性算子 L \in \mathcal{B}(\mathcal{G}, \mathcal{H}) 是从 \mathcal{G} 到 \mathcal{H} 的有界线性算子。

这里有一个关键的条件：L^*L 是同构（isomorphism）。L^* 是 L 的伴随算子，定义为满足 \langle Lu \mid v \rangle_{\mathcal{H}} = \langle u \mid L^*v \rangle_{\mathcal{G}} 的算子。L^*L : \mathcal{G} \to \mathcal{G} 是一个自伴算子，条件 L^*L 是同构意味着这个算子是双射的，即既是单射又是满射，因此存在逆算子 (L^*L)^{-1}。这个条件保证了算法中涉及的某些运算是良定义的。

参数 \gamma \in ]0, +\infty[ 和步长序列 (\lambda_n)_{n \in \mathbb{N}} \subset [0, 2] 的条件与标准Douglas-Rachford相同。但这里的零点条件变成了 \text{zer}(L^* \circ \partial g \circ L) \neq \varnothing。为了理解这个条件，注意 L^* \circ \partial g \circ L 是一个从 \mathcal{G} 的多值映射：对于 v \in \mathcal{G}，首先计算 Lv \in \mathcal{H}，然后求 \partial g(Lv)（这是 \mathcal{H} 中的集合），最后对这个集合中的每个元素应用 L^* 得到 \mathcal{G} 中的元素。条件 \text{zer}(L^* \circ \partial g \circ L) \neq \varnothing 意味着存在 v 使得 0 \in L^*(\partial g(Lv))，这等价于 \text{Argmin}(g \circ L) \neq \varnothing，即复合函数 g(L(\cdot)) 有最小值点。

初始化需要给定 x_0 \in \mathcal{H} 和相应的 v_0 = (L^*L)^{-1}L^*x_0 \in \mathcal{G}。这个 v_0 的定义来自于 x_0 和 v_0 之间应该满足的某种一致性关系。迭代格式包含四个方程：

第一步 y_n = \text{prox}_{\gamma g} x_n 与标准Douglas-Rachford相同，对 x_n 应用 g 的proximity operator。第二步 c_n = (L^*L)^{-1}L^*y_n 计算一个辅助变量，它在 \mathcal{G} 空间中。这个公式可以理解为对 y_n 进行某种"预像"计算：如果我们想找 v 使得 Lv 接近 y_n（在某种最小二乘意义下），那么 c_n 就是这样的 v。

第三步更新 x_n。表达式 L(2c_n - v_n) - y_n 结合了在 \mathcal{G} 空间中的反射（2c_n - v_n，类似于标准Douglas-Rachford中的 2y_n - x_n）和线性变换 L。这个表达式可以看作是 z_n - y_n 的模拟，其中 z_n 现在被隐式地表示为 L(2c_n - v_n)。第四步 v_{n+1} = v_n + \lambda_n(c_n - v_n) 更新 \mathcal{G} 空间中的变量，这是一个向 c_n 的松弛步。

算法的收敛结果是：v_n 弱收敛到 \hat{v}，其中 \hat{v} \in \text{Argmin}(g \circ L)，即 \hat{v} 是复合函数 g(L(v)) 的最小值点。这个结果表明算法在 \mathcal{G} 空间中找到了最优点。

这个并行形式的应用场景是什么？考虑一个优化问题 \min_v g(Lv)，其中 g 是 \mathcal{H} 空间上的函数，而我们在 \mathcal{G} 空间中寻找最优的 v。这种结构在机器学习和信号处理中很常见，例如压缩感知中的 \min_x \|y - Ax\|^2 + \text{regularization}(x)，其中 L 对应于测量矩阵 A。并行形式允许我们在"原空间" \mathcal{G} 和"像空间" \mathcal{H} 之间分配计算，这在某些情况下可以提高效率或者利用问题的特殊结构。算法名称中的"并行"指的是算法在两个空间中同时维护迭代变量（x_n 在 \mathcal{H} 中，v_n 在 \mathcal{G} 中），并且这两个变量的更新可以部分地并行进行。

增广拉格朗日方法：ADMM算法

ADMM的全称是Alternating-Direction Method of Multipliers，即交替方向乘子法。这个算法解决了一类特殊的优化问题：目标函数由两个函数的和组成，但其中一个函数作用在线性变换之后，即 \min (f(x) + g(Lx))，其中 L 是线性算子。

问题设置如下：\mathcal{H} 和 \mathcal{G} 是两个希尔伯特空间（可以是不同维度的空间）。函数 f \in \Gamma_0(\mathcal{H}) 定义在 \mathcal{H} 上，函数 g \in \Gamma_0(\mathcal{G}) 定义在 \mathcal{G} 上。线性算子 L \in \mathcal{B}(\mathcal{H}, \mathcal{G}) 是从 \mathcal{H} 到 \mathcal{G} 的有界线性算子，并且满足关键条件：L^*L 是同构。这里 L^* 是 L 的伴随算子，L^*L : \mathcal{H} \to \mathcal{H} 是自伴算子。同构条件保证 L^*L 可逆，即 (L^*L)^{-1} 存在。参数 \gamma \in ]0, +\infty[ 是增广拉格朗日函数中的惩罚参数。

ADMM迭代维护两个主要变量序列和一个对偶变量序列。给定初始值后，迭代格式包含四个步骤：

我们逐步分析每一步的含义。第一步求解一个关于 x 的优化子问题。这个子问题的目标函数由两项组成：\frac{1}{2}\|Lx - y_n + z_n\|^2 是一个二次项，它惩罚 Lx 偏离 y_n - z_n 的程度；\frac{1}{\gamma}f(x) 是原始目标函数的 f 部分，被 \frac{1}{\gamma} 缩放。这个子问题的形式表明我们在最小化 f 的同时试图满足某种约束（通过二次惩罚项）。变量 z_n 在这里扮演拉格朗日乘子的角色，y_n 是另一个主变量，它们共同定义了约束的"目标"。

第二步 s_n = Lx_n 是直接计算。它将 x_n 通过线性算子 L 映射到 \mathcal{G} 空间，得到 s_n。这个变量代表了在当前 x_n 下，Lx 的实际取值。

第三步 y_{n+1} = \text{prox}_{\frac{g}{\gamma}}(z_n + s_n) 是对 g 的一次proximity operator操作。注意参数是 \frac{g}{\gamma} 而不是 \gamma g，这意味着实际上是 \text{prox}_{\frac{1}{\gamma}g}。输入是 z_n + s_n，这是对偶变量和新计算的 s_n 的和。这一步可以理解为：在考虑了 g 的结构后，对 z_n + s_n 进行调整得到新的 y_{n+1}。

第四步 z_{n+1} = z_n + s_n - y_{n+1} 是对偶变量的更新。它的形式是 z_{n+1} = z_n + (s_n - y_{n+1})，即用残差 s_n - y_{n+1} 来更新 z_n。这个残差衡量了 s_n = Lx_n 与 y_{n+1} 之间的差异。在理想情况下（即收敛时），我们希望 s_n = y_{n+1}，即 Lx_n = y_{n+1}，这时残差为零，对偶变量不再变化。

为什么叫"交替方向"？这是因为算法交替地在两个"方向"上优化：第一步关于 x 优化（在 \mathcal{H} 空间），第三步关于 y 优化（通过proximity operator，在 \mathcal{G} 空间）。"乘子"指的是拉格朗日乘子 z_n，它在第四步被更新。

ADMM的收敛性

为了保证算法收敛，需要额外的假设条件。首先是相对内部条件：要么 \text{int}(\text{dom } g) \cap L(\text{dom } f) \neq \varnothing，要么 \text{dom } g \cap \text{int}(L(\text{dom } f)) \neq \varnothing。这里 \text{dom} 表示函数的有效定义域（函数取有限值的点集），\text{int} 表示内部。这个条件的含义是：函数 g 和复合函数 g \circ L 的定义域必须有"实质性"的交集，不能只是在边界上相切。第一个条件说 g 的定义域的内部与 L 映射后的 f 的定义域有交集；第二个条件说反过来，f 的定义域映射后的内部与 g 的定义域有交集。这个条件确保了约束集合的相容性，是凸分析中常见的约束规范条件（constraint qualification）。

其次假设 \text{Argmin}(f + g \circ L) \neq \varnothing，即优化问题 \min_{x \in \mathcal{H}} \{f(x) + g(Lx)\} 有解。给定初始值 (y_0, z_0) \in \mathcal{G}^2（注意两个初始值都在 \mathcal{G} 空间中），算法的收敛性有两个方面。

第一个收敛结果是：x_n 弱收敛到 \hat{x}，其中 \hat{x} \in \text{Argmin}(f + g \circ L)。这表明序列 (x_n) 直接收敛到原始优化问题的最优解，这与Douglas-Rachford算法不同（后者的迭代序列不直接收敛到最优点，需要额外的操作）。

第二个收敛结果涉及对偶变量：\gamma z_n 弱收敛到 \hat{v}，其中 \hat{v} \in \text{Argmin}(f^* \circ (-L^*) + g^*)。这里 f^* 和 g^* 分别是 f 和 g 的Fenchel共轭函数，-L^* 是 L^* 的负算子。这个结果表明缩放后的对偶变量 \gamma z_n 收敛到对偶问题的最优解。对偶问题是什么？它是原始问题的Fenchel对偶，其形式为 \min \{f^*(-L^*v) + g^*(v)\}。ADMM同时求解原始问题和对偶问题，并且两个序列分别收敛到各自的最优点，这体现了原始-对偶算法的特性。

与Douglas-Rachford的关系

PPT最后提到一个重要的理论联系：ADMM可以被证明等价于对对偶问题应用Douglas-Rachford算法。具体来说，如果我们对对偶问题 \min \{f^*(-L^*v) + g^*(v)\} 应用Douglas-Rachford splitting，那么得到的迭代序列（适当变换后）恰好就是ADMM的迭代序列。这个等价性揭示了ADMM的算法本质：它本质上是在对偶空间中做Douglas-Rachford splitting，然后通过原始-对偶关系将其翻译回原始空间。

这个联系有深刻的理论意义。Douglas-Rachford算法处理的是两个函数和的问题 \min(h_1 + h_2)，而ADMM处理的是带线性算子的问题 \min(f + g \circ L)。通过Fenchel对偶变换，后者可以转化为前者的形式，从而ADMM继承了Douglas-Rachford的收敛性理论。从实现角度看，ADMM的第一步（关于 x 的优化）和第三步（proximity operator）分别对应于处理对偶问题中的两个函数 f^* \circ (-L^*) 和 g^*。第四步的对偶变量更新则对应于Douglas-Rachford中的松弛步。

ADMM的实际优势在于它的可分离性。在很多应用中（如分布式优化、统计学习中的LASSO等），目标函数自然地分解为 f(x) + g(Lx) 的形式，其中 f 和 g 各自有简单的结构（如可分离、有闭式的proximity operator等），而 L 表示某种线性约束或变换。ADMM允许我们分别处理 f 和 g，每个子问题都相对简单，这使得算法在大规模问题中具有很好的可扩展性。第一步关于 x 的优化虽然看起来复杂，但当 f 有特殊结构时（如可分离或正则），这个子问题往往有闭式解或可以高效求解。

原始-对偶方法

这一部分介绍原始-对偶方法，它是为了克服ADMM的某些局限性而发展的算法。问题设置比之前更一般：\mathcal{H} 和 \mathcal{G} 是两个实希尔伯特空间，我们有三个凸函数：f \in \Gamma_0(\mathcal{H})，h \in \Gamma_0(\mathcal{H})（两者都定义在同一空间 \mathcal{H} 上），以及 g \in \Gamma_0(\mathcal{G})（定义在空间 \mathcal{G} 上）。线性算子 L \in \mathcal{B}(\mathcal{H}, \mathcal{G}) 从 \mathcal{H} 映射到 \mathcal{G}。

这里对函数的性质有不同的要求：h 被假设是可微的，且其梯度是 \beta-Lipschitz连续的，\beta \in ]0, +\infty[。而 f 和 g 不需要可微。我们要求解的优化问题是：

这个问题的结构是：三项的和，其中 f 和 h 直接作用在 x 上，而 g 作用在 Lx 上。与ADMM处理的问题 \min(f + g \circ L) 相比，这里多了一个光滑项 h。这个额外的光滑项在很多应用中自然出现，例如在机器学习中，h 可能是损失函数（如平方损失），f 是正则化项（如L1范数），g 是另一个正则化项或约束。

直接应用ADMM的局限性

如果我们直接将ADMM应用于这个问题，参数 \gamma \in ]0, +\infty[，迭代格式会变成：

注意第一步的优化子问题中，目标函数包含了 f(x) + h(x)。这个直接应用存在三个主要局限性。

第一个局限是计算 x_n 在每次迭代时可能非常复杂。子问题 \arg\min \{\frac{1}{2}\|Lx - y_n + z_n\|^2 + \frac{1}{\gamma}(f(x) + h(x))\} 本身就是一个优化问题，它包含了 f 和 h 两个函数。如果 f 没有特殊结构（如可分离性），这个子问题可能和原问题一样难解。即使 h 是光滑的，由于 f 的存在，子问题仍然是非光滑的，不能用简单的梯度法求解。

第二个局限是收敛性要求 L^*L 可逆。这是ADMM理论的固有要求，但在某些应用中这个条件可能不满足。例如，当 L 是投影算子或者秩亏缺的矩阵时，L^*L 不可逆，标准ADMM的收敛性理论就不适用。

第三个局限，也是最关键的，是 h 的光滑性没有被利用。我们知道 h 是可微的且梯度Lipschitz连续，这意味着 h 有良好的结构。但在上述ADMM迭代中，h 和 f 被放在同一个子问题中一起处理，h 的光滑性优势完全没有发挥出来。理想情况下，我们希望对光滑函数 h 用梯度下降（如Forward-Backward算法中那样），而不是把它塞进一个可能很难解的子问题中。

原始-对偶重构的第一个想法

为了克服这些局限，我们需要重新思考问题的表述。第一个关键想法是利用Fenchel对偶来重构 g(Lx) 这一项。回顾Fenchel-Young不等式和共轭函数的性质，对于凸函数 g 和任意 u，有：

这里 g^* 是 g 的Fenchel共轭。等号成立是因为 g 是凸的且proper、lower semicontinuous（这些都由 g \in \Gamma_0(\mathcal{G}) 保证）。将这个等式应用于 u = Lx：

因此原优化问题可以重写为：

这个重构将 g(Lx) 转化为一个关于对偶变量 v 的上确界问题。g 本身不再出现，取而代之的是它的共轭函数 g^* 和一个内积项 \langle v \mid Lx \rangle。这个内积项是双线性的，它将原始变量 x 和对偶变量 v 耦合起来。

进一步地，由于 \inf 和 \sup 的顺序可以交换（在适当的正则性条件下，如鞍点定理），我们可以写成：

这是一个鞍点问题的形式：我们要找 (x, v) 使得对所有 x' 和 v'，拉格朗日函数 \mathcal{L}(x, v) = f(x) + h(x) + \langle v \mid Lx \rangle - g^*(v) 在 (x, v) 处满足 \mathcal{L}(x^*, v') \leq \mathcal{L}(x^*, v^*) \leq \mathcal{L}(x', v^*)。

这个重构的优势是：现在 g 以其共轭形式 g^* 出现，而 g(Lx) 的非线性复合结构被展开成了线性项 \langle v \mid Lx \rangle 加上单独的 g^*(v)。这为设计算法提供了新的可能性：我们可以分别处理关于 x 的项（f(x) + h(x) + \langle v \mid Lx \rangle）和关于 v 的项（-g^*(v) + \langle v \mid Lx \rangle），而不需要处理复合函数 g(Lx)。

Arrow-Hurwicz方法

基于上述重构，一个自然的算法是Arrow-Hurwicz方法。这是一个经典的鞍点算法，它交替地对原始变量 x 和对偶变量 v 进行更新。算法需要两个步长序列：(\tau_n)_{n \in \mathbb{N}} 和 (\sigma_n)_{n \in \mathbb{N}}，都取值于 ]0, +\infty[。

迭代格式包含四个步骤：

我们逐步分析这个迭代。第一步选择 t_n \in \partial f(x_n)，即从 f 在 x_n 处的次梯度集合中选取一个元素。如果 f 可微，\partial f(x_n) = \{\nabla f(x_n)\} 只有一个元素；如果 f 不可微，我们需要从次梯度中选择（在算法实现中通常有特定的选择规则）。

第二步更新原始变量 x_{n+1} = x_n - \tau_n(t_n + \nabla h(x_n) + L^*v_n)。这一步沿着三项和的负方向移动：t_n 是 f 的次梯度（或梯度），\nabla h(x_n) 是 h 的梯度（我们利用了 h 的光滑性，可以直接计算梯度），L^*v_n 是耦合项 \langle v \mid Lx \rangle 关于 x 的梯度（因为 \frac{\partial}{\partial x}\langle v \mid Lx \rangle = L^*v）。步长 \tau_n 控制这一步的大小。这一步可以理解为对拉格朗日函数 \mathcal{L}(x, v_n) 关于 x 做（次）梯度下降。

第三步选择 s_n \in \partial g^*(v_n)，即 g^* 在 v_n 处的次梯度。注意这里出现的是 g^* 的次梯度，而不是 g 的次梯度。由于 g^* 是 g 的共轭，如果 g 有良好的结构，g^* 的次梯度可能也容易计算。

第四步更新对偶变量 v_{n+1} = v_n - \sigma_n(s_n - Lx_{n+1})。注意这里是减去而不是加上，而且用的是新计算的 x_{n+1} 而不是 x_n。从拉格朗日函数的角度，关于 v 我们要做上升（因为是 \sup 而不是 \inf），所以应该是 v_{n+1} = v_n + \sigma_n \cdot (\text{梯度})。但这里 -g^*(v) 关于 v 的次梯度是 -s_n（如果 s_n \in \partial g^*(v_n)），而 \langle v \mid Lx_{n+1} \rangle 关于 v 的梯度是 Lx_{n+1}，所以总的上升方向应该是 -s_n + Lx_{n+1}，即 v_{n+1} = v_n + \sigma_n(-s_n + Lx_{n+1}) = v_n - \sigma_n(s_n - Lx_{n+1})，这正是迭代公式。

Arrow-Hurwicz方法的一个显著特点是它利用了 h 的光滑性：在第二步中，我们直接使用 \nabla h(x_n) 而不是将 h 包含在一个难解的子问题中。但这个方法也有局限性，如PPT所指出的：它对步长选择有严格的条件要求。具体来说，为了保证收敛，步长序列 (\tau_n) 和 (\sigma_n) 通常需要满足衰减条件，例如 \sum_n \tau_n = \infty 但 \sum_n \tau_n^2 < \infty（类似Robbins-Monro条件）。这意味着步长必须趋向于0，但不能太快，这在实践中可能导致收敛速度很慢。此外，两个步长之间还需要满足某种平衡关系（通常依赖于算子 L 的范数），这增加了算法调参的难度。

原始-对偶方法的改进：隐式更新

Arrow-Hurwicz方法的一个问题是即使步长为常数也不收敛，必须让步长衰减到零。为了克服这个问题，第二个想法是使用隐式更新（implicit updates）。我们观察Arrow-Hurwicz迭代并进行改写。

原始的Arrow-Hurwicz迭代是：

现在我们考虑一个变体，将第一步和第三步中的次梯度选择改为"未来时刻"的次梯度：

注意变化：第一步现在是 t_n \in \partial f(x_{n+1}) 而不是 \partial f(x_n)，第三步是 s_n \in \partial g^*(v_{n+1}) 而不是 \partial g^*(v_n)。这使得更新变成了"隐式"的：为了计算 x_{n+1}，我们需要知道 x_{n+1} 处的次梯度 t_n；为了计算 v_{n+1}，我们需要知道 v_{n+1} 处的次梯度 s_n。

这个隐式形式可以被等价地改写。从第二个方程 x_{n+1} = x_n - \tau_n(t_n + \nabla h(x_n) + L^*v_n) 移项得到：

由于 t_n \in \partial f(x_{n+1})，我们可以写成：

这个包含关系等价于：

根据proximity operator的定义，x_{n+1} 满足上式当且仅当：

这是因为 \text{prox}_{\tau_n f}(y) 的定义就是 \arg\min_x \{f(x) + \frac{1}{2\tau_n}\|x - y\|^2\}，其一阶最优性条件是 0 \in \partial f(x) + \frac{1}{\tau_n}(x - y)，即 0 \in x - y + \tau_n\partial f(x)。这正是我们上面得到的条件（令 y = x_n - \tau_n(\nabla h(x_n) + L^*v_n)）。

同样的推理应用于对偶变量。从 v_{n+1} = v_n - \sigma_n(s_n - Lx_{n+1}) 和 s_n \in \partial g^*(v_{n+1}) 可以得到：

这等价于：

因此隐式的Arrow-Hurwicz迭代可以等价地写成两个proximity operator的形式：

这个形式非常优雅：第一步对 f 做proximity operator操作，输入是当前点 x_n 沿着 h 的梯度和耦合项 L^*v_n 的负方向移动后的点；第二步对 g^* 做proximity operator操作，输入是当前对偶点 v_n 加上新计算的耦合项 Lx_{n+1}。

但即使采用这种隐式更新，算法仍然不能保证在常步长下收敛。这是因为两个proximity operator的顺序和耦合方式还需要进一步优化。特别是，第一步使用 v_n（旧的对偶变量），而第二步使用 x_{n+1}（新的原始变量），这种不对称性可能导致不稳定。

原始-对偶方法的最终形式：外推技巧

为了解决常步长收敛问题，第三个关键想法是使用外推近似。具体地，在对偶变量更新中，我们不直接使用 x_{n+1}，而是使用一个外推值来近似"未来"的迭代点。

这个想法基于观察：如果序列收敛良好，那么 x_{n+1} 应该大致延续从 x_n 到 x_{n+1} 的变化趋势。因此我们可以用线性外推来估计"下一步"的位置：

这个近似的几何意义是：从 x_n 到 x_{n+1} 的向量被延长一倍，即 x_n + 2(x_{n+1} - x_n) = 2x_{n+1} - x_n。这类似于Nesterov加速中的动量项，通过预测未来的位置来加速收敛。

将这个近似应用于隐式迭代中的第二步，我们得到最终的原始-对偶算法：

第一步保持不变：对 x_n - \tau_n(\nabla h(x_n) + L^*v_n) 应用 f 的proximity operator得到 x_{n+1}。第二步的改变是：不是用 Lx_{n+1}，而是用 L(2x_{n+1} - x_n) 来更新对偶变量。这个外推项 2x_{n+1} - x_n 给算法引入了一种"向前看"的能力，使得对偶变量的更新基于对下一步的预测而不仅仅是当前步，这增强了算法的稳定性。

这个最终的迭代格式就是Chambolle-Pock原始-对偶算法，它在图像处理和机器学习中有广泛应用。算法的优势在于：每一步都只需要计算一次 f 和 g^* 的proximity operator以及 h 的梯度，计算复杂度适中；算法可以使用常步长而不需要步长衰减；算法对 L 没有可逆性要求。

原始-对偶算法的收敛性定理

现在给出这个算法的完整收敛性结果。问题设置如前：\mathcal{H} 和 \mathcal{G} 是希尔伯特空间，L \in \mathcal{B}(\mathcal{H}, \mathcal{G}) 是有界线性算子，f \in \Gamma_0(\mathcal{H})，g \in \Gamma_0(\mathcal{G})，h \in \Gamma_0(\mathcal{H}) 可微且梯度 \beta-Lipschitz连续。

算法的迭代格式是：

这里步长 \tau 和 \sigma 是常数（不再是序列），\tau \in ]0, +\infty[，\sigma \in ]0, +\infty[。

收敛性的关键条件是步长必须满足：

这个不等式可以改写为多种等价形式。首先将 \beta/2 移到左边：

乘以 \tau 得到：

这个条件的含义是：步长 \tau 和 \sigma 不能太大。特别地，如果固定 \sigma，那么 \tau 必须满足 \tau < \frac{1}{\sigma\|L\|^2 + \beta/2}。如果 h 的Lipschitz常数 \beta 很大（即 h 变化剧烈），或者算子 L 的范数很大，那么允许的步长就必须更小以保证稳定性。

条件中出现 \|L\|^2 而不是 \|L\| 是因为在算法分析中，L 和 L^* 同时出现，而 \|L^*L\| = \|L\|^2。直观上，\sigma\|L\|^2 项来自于对偶变量更新中的 L(2x_{n+1} - x_n) 与原始变量更新中的 L^*v_n 之间的耦合。\beta/2 项来自于 h 的梯度的Lipschitz性质。条件要求这些项的总效应不能超过 \tau^{-1}，即原始变量更新中的"自身收缩"效应。

在满足这个步长条件以及 \text{zer}(\partial f + \nabla h + L^*\partial gL) \neq \varnothing 的前提下，算法有两个收敛结果。

第一个结果是：x_n 弱收敛到 \hat{x}，其中 \hat{x} \in \text{Argmin}(f + h + g \circ L)。这表明原始变量序列收敛到原始优化问题 \min_{x \in \mathcal{H}} \{f(x) + h(x) + g(Lx)\} 的最优解。注意这里的目标函数形式与我们开始设定的问题完全一致。

第二个结果是：v_n 弱收敛到 \hat{v}，其中 \hat{v} \in \text{Argmin}((f + h)^* \circ (-L^*) + g^*)。这是对偶问题的最优解。对偶问题的形式来自于Fenchel对偶理论：原始问题 \min \{f(x) + h(x) + g(Lx)\} 的对偶问题是 \min \{(f + h)^*(-L^*v) + g^*(v)\}。这里 (f + h)^* 是 f + h 的Fenchel共轭（注意当两个函数的和的共轭一般不等于共轭的和，但在适当条件下有 (f + h)^* = f^* \square h^* 其中 \square 是infimal convolution）。算法同时找到了原始最优解和对偶最优解。

这个收敛性定理的意义是：只要合理选择常步长 \tau 和 \sigma，算法就能稳定收敛到最优点，不需要步长衰减。这使得算法在实践中非常实用。步长的选择通常遵循以下启发式规则：先估计 \|L\|（可以用幂迭代方法），然后选择 \tau\sigma\|L\|^2 \approx 1（接近但小于1），并确保满足与 \beta 相关的条件。在很多应用中，h 是简单的二次函数（如 \|x - x_0\|^2），此时 \beta 是已知的常数，步长调整相对容易。