交替方向乘子法（ADMM）

拆分的好处是分别利用 $f$ 和 $g$ 的计算结构。平方损失可能适合解线性系统，绝对值惩罚则适合逐坐标软阈值；复制变量后，两种操作可以各做一次，再逐渐让两份答案一致。

更新式可以直接从配方得到。记 $u=y/\rho$，则

固定 $z^k,u^k$ 时，第一份二次中心是 $z^k-u^k$；固定刚得到的 $x^{k+1},u^k$ 时，第二份中心变为 $x^{k+1}+u^k$。第二步必须使用第一步的新结果，所以这是一轮交替最小化，并没有联合求出整个增广子问题的最小点。

乘子记录的是历轮未消除的一致性误差：

当两份变量长期朝同一方向偏离时，这份累积会改变后续子问题的中心。固定的二次惩罚配合乘子更新，就能驱动约束误差趋零，无需仅靠不断增大惩罚系数。

两个残差分别检查什么 ​

定义原始残差、相邻 $z$ 位移和对偶残差

负号对应这里的约束写法 $x-z=0$。从两个子问题分别得到

代入 $y^{k+1}=y^k+\rho r^{k+1}$，便有精确关系

因此 $z$ 的驻点条件在每轮结束时已经满足；$s^{k+1}$ 是集合 $\partial f(x^{k+1})+y^{k+1}$ 中一个明确的元素，衡量 $x$ 驻点条件的偏差；$r^{k+1}$ 则衡量两份变量是否可行地一致。二者同时为零时就得到完整鞍点证书。二者仅仅很小时，首先得到的是近似最优性条件；若要换算成目标值或变量距离的误差，还需要额外的误差界或对偶证书。

同一个耦合 Lasso 的四轮精确计算 ​

沿用Lasso 的最优性与对偶间隙公理库Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标，并用可行对偶值认证剩余优化误差。中的数据：

记 $Q=A^{T}A=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$、$c=A^{T}b=(3,3/2{)}^T$，取 $\rho =1$、$z^0=u^0=0$。第一步的最优性方程和第二步的软阈值为

其中 $S_1$ 对各坐标施加阈值 $1$。逆矩阵的非对角项保留了损失的耦合；可分的是后面的惩罚子问题。

第一轮解线性系统得 $x^1=(15/16,3/16)$，两坐标都落在阈值区间内，于是 $z^1=0$、$u^1=x^1$。第二轮的右端为 $(33/16,21/16)$，故 $x^2=(39/64,15/64)$；加上旧乘子后，阈值输入为 $(99/64,27/64)$，所以 $z^2=(35/64,0)$。继续同样的有理数运算得到：

第一轮已经有 $s^1=0$，但 $r^1\ne 0$，两份变量尚未一致。只看对偶残差就会在这里错误停止。$z^k$ 的第二坐标从一开始就是零，$x^k$ 的第二坐标则逐渐减小；中间变量分别承担各自子问题的结构，无需每轮拥有相同的稀疏模式。

反过来，原始残差为零也未必已经最优。取一维 $f(x)=x^2/2$、$g(z)=0$、$\rho =1$，从 $z^0=1,u^0=0$ 开始，第一轮得到 $x^1=z^1=1/2$、$u^1=0$。此时 $r^1=0$，但 $s^1=1/2$，共同变量还没有到最小点零。

用证书确定极限 ​

四行迭代可以展示算法如何运行，但极限应由最优性条件确定。取

直接计算 $Q{v}^{\ast }-c=(-1,-1/2)=-y^{\ast }$。同时，$v_1^{\ast }>0$ 要求绝对值次梯度的第一坐标为 $1$，$v_2^{\ast }=0$ 允许第二坐标取 $[-1,1]$ 中任意值，所以 $y^{\ast }\in \partial \Vert v^{\ast }{\Vert }_1$。这正是本页的鞍点假设；而 $Q$ 的特征值为 $1,3$，平方损失严格凸，故原变量的最优点唯一。

原回归残差为 $b-A{v}^{\ast }=(1/2,1/2,0)$，目标最优值为

下文的收敛证明于是保证 $x^k,z^k\to (1,0)$。若在有限轮结束时认证目标误差，可以把 $z^k$ 作为原问题候选，计算 $P(z^k)=f(z^k)+g(z^k)$，再使用上述 Lasso 条目的可行对偶间隙。$f(x^k)+g(z^k)$ 使用了两份尚未一致的变量，不能直接当成某个原问题可行点的目标值。

从单调性到 Fejér 不等式 ​

证明只需凸次微分的单调性公理库单调算子与极大单调性Monotone operator · Maximal monotone operator · 极大单调算子用图上的内积不等式统一凸次微分与旋转关系，并以极大性保证稳定隐式步对每个输入都有唯一解。：$a\in \partial h(p)$、$b\in \partial h(q)$ 蕴含 $⟨p-q,a-b⟩\ge 0$。固定任意鞍点对 $(v^{\ast },y^{\ast })$，在一轮中简记 $x=x^{k+1}$、$z=z^{k+1}$、$y=y^{k+1}$、$r=r^{k+1}$、$d=d^{k+1}$。对两个精确次梯度关系分别应用单调性，得到

相加并利用 $x-z=r$，得到控制原始与对偶误差的关键式

定义乘积空间中的加权平方距离

因为 $y^k=y-\rho r$、$z^k=z-d$，直接展开平方有

这里尚有一个交叉项。当 $k\ge 1$ 时，上一轮的 $z$ 更新已保证 $y^k\in \partial g(z^k)$，本轮又有 $y\in \partial g(z)$，故单调性给出

于是得到所需的 Fejér 不等式：

任意初值未必满足 $y^0\in \partial g(z^0)$，所以证明从第一轮结束后开始。若初值恰好满足该关系，不等式也适用于 $k=0$；任意初值只多出有限的一轮，不影响以下结论。

为什么整个点序列收敛 ​

从 $k=1$ 到 $N$ 求和，并用 $E_{N+1}\ge 0$，得到

因此 $r^k\to 0$、$d^k\to 0$，从而 $s^k\to 0$。同时 $E_k\le E_1$ 保证 $(z^k,y^k)$ 有界；$x^k=z^k+r^k$ 也有界。在有限维空间中可以取子列 $(z^{k_j},y^{k_j})\to (\overline{v},\overline{y})$，于是 $x^{k_j}\to \overline{v}$。

闭凸函数的次微分图在有限维中闭合。这一点也能从 prox 的连续性看出：$a_j\in \partial h(p_j)$ 等价于 $p_j={\mathrm{prox}}_h(p_j+a_j)$，若 $(p_j,a_j)\to (p,a)$，取极限就有 $p={\mathrm{prox}}_h(p+a)$，即 $a\in \partial h(p)$。现在对迭代中的两个关系

取极限，得到 $-\overline{y}\in \partial f(\overline{v})$、$\overline{y}\in \partial g(\overline{v})$。所以聚点本身就是鞍点，而不只是满足一致性约束的点。

最后，把 Fejér 不等式中的固定鞍点换成刚找到的 $(\overline{v},\overline{y})$。相应的距离

从 $k=1$ 起非增，又沿 $k_j$ 趋于零，因此整个 ${\overline{E}}_k$ 都趋于零。这证明 $z^k\to \overline{v}$、$y^k\to \overline{y}$；再由 $r^k\to 0$ 得 $x^k\to \overline{v}$。这里不需要最优点唯一，也没有用到函数在有效域边界的连续性。

计算结构与适用范围 ​

对一般 Lasso，固定 $\rho$ 时的矩阵 $A^{T}A+\rho I$ 在所有轮次中相同，可以预先分解后重复求解。若直接形成稠密的 $n\times n$ 系统，分解需要 $O(n^3)$，已有分解后的每轮求解为 $O(n^2)$，软阈值和乘子更新为 $O(n)$；形成矩阵与计算 $A^{T}b$ 另有一次成本。与近端梯度法公理库近端梯度法Proximal gradient method · Forward-backward splitting对复合目标的光滑项取显式梯度步、对非光滑凸项取隐式近端步的算法。的矩阵向量乘法相比，是否划算取决于维度、稀疏性和能否复用分解。

本页证明依赖恒等约束 $x-z=0$、固定 $\rho$、精确子问题和鞍点存在。一般形式 $Ax+Bz=c$ 会引入矩阵核与子问题可解性等问题，不能由这里的点收敛论证直接推出所有原变量都收敛。非凸项、近似内层求解或调整惩罚参数也需要各自的假设与分析；对当前模型，两次 prox、两种残差和上述加权距离已经构成一条完整的算法与收敛链条。