近端梯度法

近端梯度法（proximal gradient method）求解由光滑项和易作近端运算的凸项相加而成的问题。它对光滑项使用梯度信息，对可能不可微的项保留其原形求解小子问题；因此可以处理绝对值惩罚或凸约束，而不必把它们勉强求导。

平方误差加绝对值惩罚

以教学问题 $$\underset{x,y\in ℝ}{min}F(x,y)=\underset{f(x,y)}{\underbrace{\frac{1}{2}[(x-3{)}^2+4(y+1{)}^2]}}+\underset{h(x,y)}{\underbrace{|x|+|y|}}$$ 为例。梯度是 $\mathrm{\nabla }f=(x-3,4(y+1))$，其欧氏 Lipschitz 常数可取 $L=4$。绝对值在零点不可微，但标量子问题 $$\underset{z}{min}\lambda |z|+\frac{1}{2t}(z-v{)}^2,\lambda \ge 0,t>0$$ 可以精确解出。若 $z>0$，导数为 $\lambda +(z-v)/t$，得 $z=v-t\lambda$，要求 $v>t\lambda$；若 $z<0$，得到 $z=v+t\lambda$，要求 $v<-t\lambda$。其余 $|v|\le t\lambda$ 时，零点两侧导数夹住零，最小点为零。所以 $$S_{t\lambda }(v)=\mathrm{sign}(v)max\{|v|-t\lambda ,0\}.$$ 这是软阈值：小量归零，大量向零缩减同样的绝对距离。

虚线是恒等映射；中间水平段将小输入归零，外侧保持斜率一。

从局部上界推出更新

一般设 $f:{ℝ}^n\to ℝ$ 凸且可微，$\mathrm{\nabla }f$ 为 $L$-Lipschitz；$h:{ℝ}^n\to ℝ\cup \{+\mathrm{\infty }\}$ 为闭、正常凸函数。“正常”指有效定义域非空，且不取负无穷。无穷值可用来表示禁止的点。取 $t>0$，用 $$Q_t(z;x)=f(x)+\mathrm{\nabla }f(x{)}^{𝖳}(z-x)+\frac{1}{2t}\Vert z-x{\Vert }^2+h(z)$$ 近似目标。配方后，与 $z$ 有关的部分等于 $h(z)+\Vert z-(x-t\mathrm{\nabla }f(x)){\Vert }^2/(2t)$ 加常数。因此 $$x^{+}={\mathrm{prox}}_{th}(x-t\mathrm{\nabla }f(x)),{\mathrm{prox}}_{th}(v)=\mathrm{\ast }{argmin}_z\{h(z)+\frac{\Vert z-v{\Vert }^2}{2t}\}.$$ 该近端子问题因二次项强凸而有唯一解。若 $h$ 为闭非空凸集的指示函数，近端运算就是欧氏投影。

令 $d=x^{+}-x$。近端最优性条件给出 $-\mathrm{\nabla }f(x)-d/t\in \partial h(x^{+})$，由次梯度不等式 $$h(x)\ge h(x^{+})+\mathrm{\nabla }f(x{)}^{𝖳}d+\Vert d{\Vert }^2/t.$$ 另一方面，将 Lipschitz 梯度沿线段积分可得 $f(x^{+})\le f(x)+\mathrm{\nabla }f(x{)}^{𝖳}d+L\Vert d{\Vert }^2/2$。两式相加便得到完整下降界 $$F(x^{+})\le F(x)-(\frac{1}{t}-\frac{L}{2})\Vert d{\Vert }^2.$$ 例如 $0<t\le 1/L$ 时系数至少为 $1/(2t)>0$。如果迭代点不动，近端条件化为 $0\in \mathrm{\nabla }f(x)+\partial h(x)$，再由凸性证明它全局最优。目标存在最小点及上述标准条件下，固定合适步长的算法有收敛理论；这里的下降推导与固定点证明说明了其核心机制。

与正文相同的数值更新

取 $t=1/4$，初点为 $(0,0)$。先做梯度步得到 $v=(3/4,-1)$，再按阈值 $1/4$ 缩减，得到 $(1/2,-3/4)$。第二步梯度步为 $(9/8,-1)$，阈值后得到 $(7/8,-3/4)$。目标依次从 $6.5$ 降至 $4.5$、$4.0078125$。

虚线先走梯度步，实线再作阈值；两段合成一次更新。

从第一步起 $y=-3/4$ 不再变化，$x_{k+1}=3x_k/4+1/2$，所以趋向 $x=2$。直接在正负两侧求导或检查次梯度，可验证唯一最优解为 $(2,-3/4)$，最优值为 $27/8=3.375$。图中梯度步和阈值步分开标出，二者合起来才是一次近端梯度更新。

参数变式与边界

把惩罚改为 $\lambda (|x|+|y|)$，$\lambda \ge 0$，则坐标可分离地得到 $x^{\ast }=max(3-\lambda ,0)$、$y^{\ast }=-max(1-\lambda /4,0)$。变式取 $\lambda =4$，两个坐标均为零；此时 $-\mathrm{\nabla }f(0)=(3,-4)$ 位于 $4[-1,1{]}^2$ 内，验证了零点最优性。

步长过大可失败。即使 $h=0$、$f(x)=x^2/2$，取 $t=3$ 也会得到 $x_{k+1}=-2x_k$，除初值为零外均发散。不存在最小点、近端子问题算得过粗或采用不同非凸分解时，也不能直接套用上述凸模型结论。若 $L$ 未知，可通过检验光滑项上界来回溯步长。

标准库实现

下例输入初始两坐标、非负惩罚、步长及步数，返回更新轨迹，不改写输入。默认步长满足本例 $t\le 1/4$；每步成本为常数，保存 $K$ 步为 $O(K)$。一般问题还应加上梯度和近端子问题的实际成本；近端映射没有便宜解时，算法未必有优势。

Python 3

def proximal_gradient(start, lam=1.0, step=0.25, count=2):
    if len(start) != 2 or lam < 0 or not 0 < step <= 0.25 or count < 0:
        raise ValueError("invalid data or unsafe step for this quadratic")
    x, y = map(float, start)
    def soft(v, a):
        return max(v-a, 0.0)-max(-v-a, 0.0)
    def value(x,y):
        return ((x-3)**2+4*(y+1)**2)/2+lam*(abs(x)+abs(y))
    trace = [(x,y,value(x,y))]
    for _ in range(count):
        x = soft(x-step*(x-3), step*lam)
        y = soft(y-step*4*(y+1), step*lam)
        trace.append((x,y,value(x,y)))
    return trace

for row in proximal_gradient((0,0)):
    print(row)
assert proximal_gradient((0,0), lam=4, count=1)[-1][:2] == (0.0,0.0)

输出包含正文的前三个目标值。停止时可以检查梯度映射 $G_t(x)=(x-{\mathrm{prox}}_{th}(x-t\mathrm{\nabla }f(x)))/t$；它为零与本模型最优性等价，普通梯度则在非光滑最优点未必为零。