近端算子 | Codeboy's Blog

形式陈述

设 $H$ 为实Hilbert 空间， $f:H\to\mathbb R\cup\{+\infty\}$ 是 proper、下半连续凸函数， $\lambda>0$ 。近端算子定义为

\operatorname{prox}_{\lambda f}(x) =\operatorname*{argmin}_{y\in H}\left\{f(y)+\frac{\|y-x\|^2}{2\lambda}\right\}.

在这些假设下极小点存在；二次项使目标 $1/\lambda$ -强凸，故它唯一。由次微分最优性， $y=\operatorname{prox}_{\lambda f}(x)$ 等价于

0\in\partial f(y)+\frac{y-x}{\lambda},\qquad \frac{x-y}{\lambda}\in\partial f(y).

因此 $P=\operatorname{prox}_{\lambda f}=(I+\lambda\partial f)^{-1}$ ，即次微分算子的 resolvent（预解算子）。它属于极大单调算子的预解算子这一更大类别；一般预解算子不一定来自凸函数。对两个输入应用次微分的单调性，得到

\left\langle\frac{x-P(x)}\lambda-\frac{z-P(z)}\lambda,P(x)-P(z)\right\rangle\ge0,

整理即 $\|P(x)-P(z)\|^2\le\langle P(x)-P(z),x-z\rangle$ 。这种牢固非扩张性特别蕴含 $\|P(x)-P(z)\|\le\|x-z\|$ ，所以 prox 连续。

完备性怎样保证极小点存在

固定输入 $x$ ，记 $\Phi_x(y)=f(y)+\|y-x\|^2/(2\lambda)$ 。先取一个 $f(y_0)$ 有限的点。下半连续性给出 $r>0$ ，使 $\|z-y_0\|<r$ 时 $f(z)\ge f(y_0)-1$ 。对远处的 $y$ ，在线段上取 $z=y_0+t(y-y_0)$ ，其中 $t=r/(2\|y-y_0\|)$ ；由凸性将这个局部下界传回 $y$ ，得到全局估计

f(y)\ge f(y_0)-1-\frac2r\|y-y_0\|.

二次项压住右侧的线性下降，所以 $a=\inf_y\Phi_x(y)$ 是有限实数。

选择 $\Phi_x(y_n)\to a$ 。由凸性和平行四边形恒等式，

a\le\Phi_x\!\left(\frac{y_n+y_m}{2}\right) \le\frac{\Phi_x(y_n)+\Phi_x(y_m)}2-\frac{\|y_n-y_m\|^2}{8\lambda}.

因此 $\|y_n-y_m\|^2\le4\lambda[\Phi_x(y_n)+\Phi_x(y_m)-2a]\to0$ 。Hilbert 完备性给出范数极限 $y$ ，下半连续性保证 $\Phi_x(y)=a$ ；同一个严格中点估计给出唯一性。这份存在性证明不依赖极大单调性的反向论证。

最优性关系也可直接验证。若 $y$ 最小化 $\Phi_x$ ，比较 $y+t(z-y)$ 与 $y$ ，用 $f$ 的凸性上界，除以 $t>0$ 后令 $t\downarrow0$ ，便得

f(z)\ge f(y)+\left\langle\frac{x-y}{\lambda},z-y\right\rangle.

反过来，这条次梯度不等式与平方项展开给出 $\Phi_x(z)-\Phi_x(y)\ge\|z-y\|^2/(2\lambda)$ ，所以它确实等价于唯一最小性。

直觉

最小化 $f$ 要求降低函数值，二次项则为离输入过远收取代价。小 $\lambda$ 更强调接近输入，大 $\lambda$ 更愿意为降低 $f$ 走远。它把投影从集合推广到函数：指标函数规定哪些位置允许进入，一般闭凸函数则为位置设置不同代价。

隐式关系在新点 $y$ 处取次梯度，而显式梯度步在旧点 $x$ 处取梯度。即使二者都容易计算，也通常不相同。例如 $f(u)=\mu u^2/2$ 时，prox 给出 $y=x/(1+\lambda\mu)$ ，梯度步却是 $(1-\lambda\mu)x$ 。前者是在稳定子问题中求平衡，后者是按当前斜率外推。

例子与边界

从三个次微分分支推导软阈值

设 $\tau>0$ ，考虑 $\min_u\{\tau|u|+(u-z)^2/2\}$ 。最优性是 $0\in u-z+\tau\partial|u|$ 。应按未知最优点的符号分三种情况，而不是给尖点指定导数。

若 $u>0$ ，次微分为 $\{1\}$ ，方程给 $u=z-\tau$ ；要使这一解确实为正，必须 $z>\tau$ 。若 $u<0$ ，次微分为 $\{-1\}$ ，得到 $u=z+\tau$ ，适用条件是 $z<-\tau$ 。若 $u=0$ ，条件成为 $z\in\tau[-1,1]$ ，恰好是 $|z|\le\tau$ 。这三个输入区间覆盖全直线，严格凸性又排除了其他最优点，所以

\operatorname{prox}_{\tau|\cdot|}(z)=S_\tau(z)= \begin{cases} z-\tau,&z>\tau,\\ 0,&-\tau\le z\le\tau,\\ z+\tau,&z<-\tau. \end{cases}

尤其 $z=\tau$ 和 $z=-\tau$ 都返回零。软阈值不仅把幅度减小，还把一整个闭区间压成精确零；这正是稀疏惩罚的算法作用。精确 ℓ1 罚用同一尖角机制抵消约束法向力：阈值来自约束最优乘子，目的是恢复可行性，参数含义与稀疏建模不同。

向量情形中， $\lambda\|u\|_1+\|u-z\|^2/(2\alpha)$ 是 $n$ 个只含单个 $u_j$ 的项之和，故各坐标可以独立最小化：

\operatorname{prox}_{\alpha\lambda\|\cdot\|_1}(z) =\bigl(S_{\alpha\lambda}(z_1),\ldots,S_{\alpha\lambda}(z_n)\bigr).

这一步依赖惩罚与二次距离在同一坐标下可分，并非所有 prox 都能逐坐标计算。耦合 Lasso 算例中，光滑候选依赖所有坐标，但随后的 $\ell_1$ prox 仍然可分；不能把后半步的可分性误认成整个回归问题可分。

投影与非凸反例

若 $f=\delta_C$ 是非空闭凸集的指标函数，即在 $C$ 上为零、外部为 $+\infty$ ，则 $\operatorname{prox}_{\lambda\delta_C}(x)=P_C(x)$ ，结果与正数 $\lambda$ 无关。删去凸性就不同：取 $f=\delta_{\{-1,1\}}$ ，在输入 $x=0$ 时，两个允许点的目标值都等于 $1/(2\lambda)$ ，argmin 恰为 $\{-1,1\}$ ，所以近端映射多值。

定义良好也不保证闭式解便宜。一般凸函数的 prox 本身可能需要内层优化；它的存在唯一性与计算成本是两件事。

推论与应用

固定点 $x=\operatorname{prox}_{\lambda f}(x)$ 等价于 $0\in\partial f(x)$ ，因此恰是 $f$ 的最小点。反复应用整个目标的 prox 得到近端点方法；对光滑项先取梯度、只对剩下惩罚取 prox，则得到近端梯度法。软阈值在后者中只负责惩罚子问题，完整目标的误差仍需单独核验。

在有限维情形，借助凸共轭的等号条件还可得到 Moreau 分解

\operatorname{prox}_{\lambda f}(x) +\lambda\operatorname{prox}_{f^*/\lambda}(x/\lambda)=x.

具体地，令 $y=\operatorname{prox}_{\lambda f}(x)$ 、 $u=(x-y)/\lambda$ 。关系 $u\in\partial f(y)$ 等价于 $y\in\partial f^*(u)$ ，即 $x/\lambda-u\in\partial(f^*/\lambda)(u)$ ；再次使用近端最优性条件，便得到显示的分解。它把原函数和共轭函数的近端计算联系起来。比如 $\ell_1$ 惩罚的共轭是一个无穷范数球的指标函数，软阈值便可理解为输入减去相应盒子的投影；这一几何解释与上面的三个分支计算一致。

参考资料

Neal Parikh and Stephen Boyd, Proximal Algorithms，作者可获取版本，§§1–2，近端算子、可分性与基本性质；§7.1，软阈值与 Lasso。
Heinz H. Bauschke and Patrick L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., Springer, 2017，Chs. 12 and 23。

形式陈述 ​

完备性怎样保证极小点存在 ​

从三个次微分分支推导软阈值 ​

投影与非凸反例 ​

反向链接

形式陈述

完备性怎样保证极小点存在

从三个次微分分支推导软阈值

投影与非凸反例