交替方向乘子法

交替方向乘子法（alternating direction method of multipliers，ADMM）把带线性耦合等式的可分目标分成两个变量块，依次优化两块，再更新乘子。它保留增广拉格朗日法的残差反馈，却用两次分开的最小化代替联合最小化。更新次序和残差含义属于算法本身。

两个变量描述同一个决定

考虑 $min_{x} \frac{1}{2} (x - 3)^{2} + | x |$ 。把绝对值单独放到变量 $z$ 上，可等价写成 $min_{x, z} \frac{1}{2} (x - 3)^{2} + | z |, x - z = 0.$ 两个目标项各自容易求解，但等式要求它们最终表示同一数值。取罚参数 $ρ = 1$ ，用缩放乘子 $u$ ，ADMM 的三步为 $x^{+} = \frac{3 + z - u}{2}, z^{+} = S_{1} (x^{+} + u), u^{+} = u + x^{+} - z^{+} .$ 其中 $S_{1} (v) = sign (v) max (| v | - 1, 0)$ 是软阈值。第一式来自平方项求导，第二式来自绝对值加二次项的近端最小化，第三式累积两个变量尚未一致的部分。

交替更新的两个变量逐渐一致并趋于二 — 第二轮起两变量已相等，但还需沿共同值继续改进。

从 $z_{0} = u_{0} = 0$ 出发，第一轮得 $x_{1} = 1.5, z_{1} = 0.5, u_{1} = 1$ ；第二轮得 $x_{2} = z_{2} = 1.25, u_{2} = 1$ ；第三轮得 $x_{3} = z_{3} = 1.625$ 。第二轮已经满足一致性，却还没达到最优点二。这是同时检查两种残差的直接理由。

两块的一般形式

设 $f : ℝ^{n} \to ℝ \cup {+ \infty}$ 、 $g : ℝ^{m} \to ℝ \cup {+ \infty}$ 为闭正常凸函数， $A \in ℝ^{p \times n}$ 、 $B \in ℝ^{p \times m}$ 、 $c \in ℝ^{p}$ 。目标为 $min f (x) + g (z)$ ，约束 $A x + B z = c$ 。固定 $ρ > 0$ ，缩放形式为 $\begin{matrix} x_{k + 1} & \in \arg min_{x} {f (x) + \frac{ρ}{2} ‖ A x + B z_{k} - c + u_{k} ‖^{2}}, \\ z_{k + 1} & \in \arg min_{z} {g (z) + \frac{ρ}{2} ‖ A x_{k + 1} + B z - c + u_{k} ‖^{2}}, \\ u_{k + 1} & = u_{k} + A x_{k + 1} + B z_{k + 1} - c . \end{matrix}$ 未缩放乘子为 $y_{k} = ρ u_{k}$ 。这里假定两子问题均达到最小值；仅有“闭正常凸”而没有子问题可解性检查时，不能把不存在的最小点当作更新。^[1]

原始残差和对偶残差的来源

原始残差 $r_{k + 1} = A x_{k + 1} + B z_{k + 1} - c$ 直接衡量等式。由第二块最优性及乘子更新，有 $0 \in \partial g (z_{k + 1}) + B^{𝖳} y_{k + 1}$ 。第一块用的是旧 $z_{k}$ ，所以其最优性化为 $s_{k + 1} := ρ A^{𝖳} B (z_{k + 1} - z_{k}) \in \partial f (x_{k + 1}) + A^{𝖳} y_{k + 1} .$ 若 $r = s = 0$ ，两个驻点条件和可行性同时成立。其最优性证明可以直接写出：对任意可行 $(\hat{x}, \hat{z})$ ，两个凸次梯度不等式相加，右侧线性项为 $- y^{𝖳} [A (\hat{x} - x) + B (\hat{z} - z)] = 0$ ，所以当前目标不超过任何可行方案。

ADMM原始与对偶残差的数值区别 — 原始残差先归零；对偶残差仍大，不能只检验一致性。

主例中 $A = 1, B = - 1$ ，故 $r = x - z$ 、 $s = - (z^{+} - z)$ 。第一轮为 $r = 1, s = - 0.5$ ；第二轮为 $r = 0, s = - 0.75$ ，仅查一致性会过早停止。从第二轮起 $u = 1$ ，且 $z_{k + 1} = 1 + z_{k} / 2$ ，误差 $z_{k} - 2$ 每轮缩半，完整证明了本例的收敛。

条件、变式与实现

标准两块凸 ADMM 在存在原拉格朗日鞍点、固定正罚参数、子问题可解并按要求精确求解等条件下，有原始残差趋零、目标趋向最优值和乘子收敛的理论。变量序列本身的收敛还可能需要附加条件；直接推广到三个以上块、非凸目标或任意内层误差并不自动成立。

变式将绝对值系数改为 $λ = 4$ ，第一项仍为 $(x - 3)^{2} / 2$ 。最优解是零，因为在零点 $3 \in 4 [- 1, 1]$ 。ADMM 中相应软阈值变为 $4 / ρ$ ；初期 $z$ 可一直等于零，但 $x$ 与原始残差仍需迭代缩小。若阈值变为零，模型则退化到无惩罚的平方最小化，最优点三。

下例只用标准库，输入惩罚、罚参数、初始 $z, u$ 和轮数，返回更新和两种带符号残差，不改写输入。每轮成本为常数，返回历史占 $O (K)$ 。一般模型的成本取决于两个子问题；若需解固定二次线性系统，可复用分解。目标值在不可行迭代点可能低于原最优值，例如第一轮为 $1.625 < 2.5$ ，不构成可行解的最优性证书。

Python 3

def admm_scalar(lam=1.0, rho=1.0, initial=(0.0,0.0), count=4):
    if lam < 0 or rho <= 0 or len(initial) != 2 or count < 0:
        raise ValueError("invalid ADMM parameters")
    z,u = map(float,initial)
    trace = []
    for k in range(1,count+1):
        old_z = z
        x = (3+rho*(z-u))/(1+rho)
        v,a = x+u,lam/rho
        z = max(v-a,0.0)-max(-v-a,0.0)
        r = x-z
        u += r
        s = -rho*(z-old_z)
        trace.append((k,x,z,u,r,s))
    return trace

for row in admm_scalar():
    print(row)
assert abs(admm_scalar(count=50)[-1][2]-2) < 1e-12
assert abs(admm_scalar(lam=4,count=60)[-1][1]) < 1e-12

参考文献

↑ Boyd et al. (2011), Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers，§3.1—3.3及附录A。

[1] Boyd et al. (2011), Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers，§3.1—3.3及附录A。

[1]