知识点：交替方向乘子法 (ADMM)

知识点概述

交替方向乘子法（Alternating Direction Method of Multipliers, ADMM）是一种功能强大且应用广泛的优化算法，特别适用于求解具有可分结构的大规模凸优化问题。它结合了对偶分解的易于分解和乘子法的收敛性优势。

问题形式: ADMM主要用于求解形如 $min f (x) + g (z)$ s.t. $A x + B z = c$ 的问题。
核心思想: ADMM基于增广拉格朗日函数，但它不是同时最小化所有变量，而是将最小化步骤交替地在 $x$ 和 $z$ 上进行，这使得子问题更容易求解。
算法:
1. $x_{k + 1} = ar g min_{x} L_{ρ} (x, z_{k}, y_{k})$ (x-minimization)
2. $z_{k + 1} = ar g min_{z} L_{ρ} (x_{k + 1}, z, y_{k})$ (z-minimization)
3. $y_{k + 1} = y_{k} + ρ (A x_{k + 1} + B z_{k + 1} - c)$ (dual update) 其中 $L_{ρ}$ 是增广拉格朗日函数。
优点:
- 收敛性: ADMM的收敛性条件比对偶分解弱得多，即使在没有强凸性的情况下也能保证收敛。
- 可分解性: 如果 $f$ 和 $g$ 是可分的，那么 $x$ 和 $z$ 的更新步骤通常可以分解为许多并行的简单子问题。