近端梯度法

拆分的依据是计算结构：$g$ 的梯度便宜，$h$ 的 prox 便宜。把更新配方，可见新点精确最小化

当 $\alpha \le 1/L$ 时，光滑凸性公理库光滑凸函数Smooth convex function · L-smooth convex function同时具有凸性与全局 Lipschitz 梯度的函数类，其曲率被零与有限上界夹住。与下降引理公理库下降引理Descent lemma · Quadratic upper-bound lemma以 Lipschitz 梯度常数给出函数相对一阶模型的全局二次上界。保证这是一份接触当前目标值的二次上界。它线性化光滑项，却完整保留惩罚的尖角，所以能产生精确零坐标。

图中选取 $\alpha h(x)=\Vert x{\Vert }_1$，故近端步是阈值为 $1$ 的逐坐标软阈值：$(2.1,-0.3,0.2,1.4)\mapsto (1.1,0,0,0.4)$。

当 $h=0$，prox 是恒等映射；当 $h$ 是集合指标函数，prox 是投影。步长约束来自 $g$ 的曲率，不需要为非光滑的整个 $F$ 编造 Hessian。若每轮改为对整个 $F$ 求 prox，就变成近端点方法公理库近端点方法Proximal point method · Proximal point algorithm反复精确求解带二次稳定项的子问题以逼近闭凸函数最小点的方法。，通常会得到另一个、更难的子问题。

一维收缩与耦合回归 ​

保留最简单的计算作为起点：$F(x)=(x-3{)}^2/2+|x|$，$L=1$。从 $x_0=0$ 取 $\alpha =1/2$，软阈值 $S_{\tau }(z)=\mathrm{sign}(z)(|z|-\tau {)}_{+}$ 给出

目标值依次为 $4.5,3,2.625,2.53125$，趋向 $x^{\ast }=2$ 的 $F^{\ast }=2.5$。若取 $\alpha =1$，梯度候选恒为 $3$，于是一步到解。这里二次项恰好消除了初值影响；一般设计矩阵的列相互耦合时，不会如此。

具体地，令

此时 $A^{T}A=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$ 的最大特征值为 $3$，可以取 $\alpha =1/3$。从零开始，前三个迭代点为 $(2/3,1/6)$、$(5/6,0)$、$(17/18,0)$。第二步恰把处于阈值边界的第二坐标送到零。完整候选计算、零坐标最优性与逐轮误差证书见Lasso 的最优性与对偶间隙公理库Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标，并用可行对偶值认证剩余优化误差。；那里同时说明为何不能先求最小二乘解再一次软阈值。

同一组数据也可用交替方向乘子法（ADMM）公理库交替方向乘子法（ADMM）Alternating direction method of multipliers · ADMM将凸目标拆成两个近端子问题，用乘子累积一致性误差，并以原始与对偶残差检查最优性的算法。求解：它对平方损失精确解一个耦合线性系统，对复制变量做软阈值，再累积两份变量的不一致量。近端梯度在这里使用显式梯度候选，ADMM 则保留完整二次损失；该页给出四轮分数计算，并说明为什么停止时需要同时检查原始残差与对偶残差。

步长与结论的边界 ​

“小于安全上界”不意味着累积推进足够。令 $h=0$、$g(x)=x^2/2$、${\alpha }_k=2^{-k-2}$，则

这些步长均不超过 $1/L=1$，但和有限。因为 $0\le {\alpha }_j\le 1/4$，有 $\log (1-{\alpha }_j)\ge -2{\alpha }_j$，所以无穷乘积严格为正；非零初值不会趋于最优点零。这就是本页明确固定正步长的原因。

过大步长也可能破坏下降。对上面的耦合例取 $\alpha =1$，第一步是 $(2,1/2)$，目标值从 $9/4$ 升到 $13/4$。这展示一个实际失败，不表示每个 $\alpha >1/L$ 都必然失败。若用回溯，应检验光滑二次上界并另行说明步长规则；若 prox 仅近似求解，应控制内层误差；若 $g$ 非凸，固定点一般只认证驻点。

三点不等式如何产生下降与速率 ​

记 $y={\mathrm{prox}}_{\alpha h}(x-\alpha \mathrm{\nabla }g(x))$。最优性条件给出

任取 $z\in \mathrm{dom}h$，次梯度不等式给 $h(y)-h(z)\le ⟨s,y-z⟩$；凸性给 $g(x)-g(z)\le ⟨\mathrm{\nabla }g(x),x-z⟩$；光滑性给 $g(y)-g(x)\le ⟨\mathrm{\nabla }g(x),y-x⟩+L\Vert y-x{\Vert }^2/2$。相加后，梯度内积消去，剩下 $⟨x-y,y-z⟩/\alpha +L\Vert y-x{\Vert }^2/2$。再用三点平方恒等式，得到

先取 $z=x$。前一个分式本身又贡献一份负平方项，所以

即使 $\alpha =1/L$，只要新旧点不同仍有严格下降。再取任一最小点 $z=x^{\ast }$，舍去三点不等式末尾的非正项，从 $j=0$ 到 $k-1$ 求和便有

这一步首先控制的是一串函数值差的和。由于刚刚证明了函数值单调，每个求和项都不小于最后一项 $F(x_k)-F^{\ast }$，故

点收敛需要再走一步。三点不等式与 $F(x_{k+1})\ge F^{\ast }$ 表明，到每个最小点的距离不增，这称为 Fejér 单调性，因而序列有界。下降估计还给 $\sum _k\Vert x_{k+1}-x_k{\Vert }^2<\mathrm{\infty }$，故相邻差趋零。有限维有收敛子列 $x_{k_j}\to \overline{x}$；prox 是连续映射，梯度也连续，固定步长更新与相邻差趋零便推出 $\overline{x}={\mathrm{prox}}_{\alpha h}(\overline{x}-\alpha \mathrm{\nabla }g(\overline{x}))$。所以 $\overline{x}$ 是最小点。最后，到这个 $\overline{x}$ 的距离不增且有子列趋零，整个序列都趋于 $\overline{x}$。这一论证没有假设 $h$ 在定义域边界连续。

计算成本与可以认证的对象 ​

对 $m\times n$ 矩阵的平方损失，梯度通过 $Ax$ 和 $A^T(Ax-b)$ 计算，连同残差与输出向量操作，稠密实数算术成本为 $O(1+mn+m+n)$，在 $m,n\ge 1$ 时可简写为 $O(mn)$；若稀疏表示实际保存 $s$ 个条目（包括显式零和重复坐标），稀疏实现为 $O(1+s+m+n)$，逐坐标软阈值另需 $O(n)$。不必形成可能稠密的 $A^{T}A$。要报告新点处的残差与对偶证书，还需新点的矩阵向量乘法、转置乘法及 $O(1+m+n)$ 的范数和内积检查；可以与下一轮梯度共享这些结果。

FISTA 在相应凸条件下将函数值界改善为 $O(1/k^2)$，但需新的加速权重与势函数，且通常不逐轮下降。函数值收敛、迭代点收敛与有限步识别支持集是不同结论；上述一般 $O(1/k)$ 证明没有提供统计意义的变量恢复保证。Moreau 包络公理库Moreau 包络Moreau envelope · Moreau-Yosida regularization以二次 infimal convolution 将闭凸函数平滑化并保留其极小点的函数。则对整个函数做平滑，虽然也出现 $x-\mathrm{prox}(x)$，仍应与这里的拆分子问题区分。