近端点方法

形式陈述 ​

考虑在 Hilbert 空间上最小化 proper、下半连续凸函数 $f$，并假设 $\mathrm{argmin}f\ne \varnothing$。给定 $x_0$ 与步长 ${\lambda }_k>0$，经典近端点方法迭代

$$x_{k+1}={\mathrm{prox}}_{{\lambda }_{k}f}(x_k)=\underset{x}{\mathrm{argmin}}\{f(x)+\frac{1}{2{\lambda }_k}\Vert x-x_k{\Vert }^2\}.$$

由近端算子公理库近端算子Proximal operator · Proximity operator在降低凸函数值与保持靠近输入点之间取得精确平衡的单值算子。的最优性条件，

$$\frac{x_k-x_{k+1}}{{\lambda }_k}\in \partial f(x_{k+1}),$$

所以它是隐式次梯度步。任意最小点 $x^{\ast }$ 都是 prox 的固定点；反过来，固定点满足 $0\in \partial f(x^{\ast })$，因而是全局最小点。若步长有统一下界 ${\lambda }_k\ge \underset{―}{\lambda }>0$，则精确迭代在有限维中收敛到某个最小点；一般 Hilbert 空间中标准结论是弱收敛。更一般的误差迭代需要误差可求和等附加条件，本页不把它混入经典精确版本。

直觉 ​

每一步不是沿当前斜率大胆外推，而是重新求解一个“原目标加距离惩罚”的稳定子问题。二次项阻止新点跳得过远，原目标则持续把序列拉向解集。这种隐式更新往往比显式次梯度步稳定，但代价也很清楚：每一轮都要真正计算一次 prox。方法的价值不在于假设 prox 总是便宜，而在于当子问题能利用结构高效求解时，它把非光滑最优性转化成一个非扩张固定点迭代。

例子与边界 ​

对 $f(x)=\frac{\mu }{2}\Vert x{\Vert }^2$（$\mu >0$），近端子问题可直接求导，得到

$$x_{k+1}=\frac{x_k}{1+{\lambda }_k\mu }.$$

固定步长 $\lambda$ 下，$\Vert x_k\Vert =(1+\lambda \mu {)}^{-k}\Vert x_0\Vert$，序列以几何速度收缩到唯一最小点 $0$。这个计算也说明它不同于梯度步 $x_{k+1}=(1-\lambda \mu )x_k$：前者的分母形式对任意正步长都保持收缩，后者则受稳定步长范围限制。

若 $f$ 没有最小点，固定点不存在，不能从标准定理推出迭代收敛。步长趋零过快也可能让总推进量不足，例如一般理论通常至少要求 $\sum _k{\lambda }_k=\mathrm{\infty }$，而统一正下界是更简洁的充分条件。对复合目标 $g+h$ 的 proximal gradient 更新是 ${\mathrm{prox}}_{\lambda h}(x_k-\lambda \mathrm{\nabla }g(x_k))$，只对 $h$ 取 prox；它与本页“对整个 $f$ 做近端点迭代”不是同一个算法。

推论与应用 ​

近端点方法把凸优化公理库凸优化问题Convex optimization problem在凸可行域上最小化凸目标且不等式约束为凸函数的优化模型。转成寻找 firmly nonexpansive 映射固定点的问题，Fejér 单调性由此控制迭代到解集的距离；若 $f$ 强凸，prox 进一步成为收缩映射，可由Banach 不动点定理公理库Banach 不动点定理Banach fixed-point theorem · Contraction mapping theorem完备度量空间上的压缩映射具有唯一不动点，且迭代以几何速度收敛。得到唯一固定点与几何收敛。Rockafellar 将它推广到最大单调算子的 resolvent，从而覆盖变分不等式与鞍点系统。实际算法中的 ADMM、Douglas–Rachford 和 proximal gradient 都与这一框架有亲缘关系，但各自拆分的算子、可计算子问题与收敛条件不同；把它们都叫“近端点方法”会掩盖真正的迭代结构。

参考资料

• R. Tyrrell Rockafellar, “Monotone Operators and the Proximal Point Algorithm,” SIAM Journal on Control and Optimization 14(5), 1976, 877–898。
• Neal Parikh and Stephen Boyd, Proximal Algorithms, Foundations and Trends in Optimization 1(3), 2014，§4.1, proximal minimization。