optimizationalternating-direction-method-of-multipliersnon-convexdual-ascentaugmented-lagrangian

ADMM 算法 (Alternating Direction Method of Multipliers)

Definition. 交替方向乘子法 (ADMM) 是一类将难优化问题分解为一系列有闭式解或高效近端算子解的子问题的算法框架,核心是引入辅助变量 + 一致性约束,在增广拉格朗日上交替更新原始与对偶变量。

起源

ADMM 的两个直接祖先:

  • 对偶上升 (Dual Ascent): 在 Lagrangian 对偶上梯度上升,但仅在问题严格凸时收敛。
  • 增广 Lagrangian 方法 (Method of Multipliers): 通过罚项改善数值稳定性,但破坏可分性。

ADMM (Glowinski & Marrocco 1975; Gabay & Mercier 1976; Boyd et al. 2011 综述) 把两者结合:可分性 + 罚项改善的数值稳定性。

标准形式

求解:

\min_{x, z}\; f(x) + g(z) \quad \text{s.t.}\; Ax + Bz = c

缩放形式的 ADMM 迭代:

\begin{aligned} x^{k+1} &:= \arg\min_x \mathcal{L}_\rho(x, z^k, u^k) \\ z^{k+1} &:= \arg\min_z \mathcal{L}_\rho(x^{k+1}, z, u^k) \\ u^{k+1} &:= u^k + \rho (Ax^{k+1} + Bz^{k+1} - c) \end{aligned}

其中 \mathcal{L}_\rho(x, z, u) = f(x) + g(z) + \frac{\rho}{2}|Ax + Bz - c + u/\rho|_2^2 是增广拉格朗日, u 是缩放对偶变量, \rho > 0 是罚参数。

三方分裂 (multi-block)

实际中通常遇到三方或更多块,例如 MINGLE 框架引入三份副本:

  • B 的正交副本
  • W 的稀疏+拓扑副本
  • 度向量 d 的显式变量

三方 ADMM 增加对应的对偶变量,迭代形式类似但每轮更新三个原始块 + 三个对偶步。

收敛性

  • 凸情形: 在温和条件下 (f, g 闭凸 proper, A, B 满秩) 收敛到全局最优。
  • 非凸情形: MINGLE 整体问题非凸 (双线性项 B^\top L_W B), ADMM 不保证收敛到全局最优——这是该框架在理论上诚实的代价。但实证上,好的初始化 (降权收益率的最佳秩-K 近似 + RBF 初始图) 给出稳定结果。

在 MINGLE 中的具体应用

MINGLE 的目标函数混合了可微项、需要近端算子处理的 \ell_1 项、图拓扑约束——直接梯度法不可行。ADMM 的工作流:

  1. 因子块 (B, Z): B 走一步梯度, Z 解 Sylvester 方程 (O(N^3) 每轮,主成本)。
  2. 图块 (W, d): W 用 Sherman–Morrison 闭式, d 闭式解一元二次,近端副本强制稀疏。
  3. 对偶更新: 三个对偶变量梯度上升,累积原始-辅助失配历史,驱动原始与辅助趋于一致。

由于图块在因子块之后更新,图拓扑总是适配最新暴露——"互相纠偏"在算法层面落地。

在量化金融中的其他应用

  • Black-Litterman 缩放: 二次约束下的视图融入。
  • Markowitz with constraints: 卖空约束 + 行业中性 + 跟踪误差约束的等式/不等式处理。
  • LASSO / Elastic Net: f 二次, g \ell_1, 经典 ADMM 用例。
  • Robust 回归: Huber 损失 + 稀疏惩罚。
  • Optimal transport: 熵正则化 OT 流的近端算子。

局限

  • 非凸无全局最优: MINGLE 类双线性目标需要仔细的初始化。
  • 罚参数 \rho 需调: 太小收敛慢,太大数值不稳定;变体 (adaptive \rho) 有帮助。
  • 子问题求解假设闭式或高效近端: 若子问题本身难, ADMM 优势丧失。

与其他优化方法的关系

方法 适用 收敛保证 MINGLE 子问题
梯度下降 可微 凸全局, 非凸局部 不可行 (有 \ell_1 + 拓扑)
近端梯度 f 可微 + g 可近端 凸全局 不可行 (有拓扑约束)
内点法 凸, 严格可行 全局 不可行 (非凸)
ADMM f, g 可分 + 等式约束 凸全局, 非凸局部 主导

See also

Sources