ADMM算法原理详解

FeastSC · 发表于 2022-1-3 11:54

作为统计学专业研究高维统计问题的菜鸟，自从学了ADMM算法，内心极度膨胀（不是）

遇事不决，ADMM；如果一个ADMM不能解决，那就ADMM套ADMM！
（正经）ADMM算法提供了一个求解含线性等式约束优化问题的框架，方便我们将原始的优化问题拆解成几个相对好解决的子优化问题进行迭代求解。这种“拆解”的功能是ADMM算法的核心要义。
去年刚学ADMM的时候写过一个notes，按自己的想法整理了一套理解ADMM算法原理的流程，贴出来和大家交流交流~
0. ADMM是个啥？

ADMM用于求解如下最优化问题：

$\begin{aligned} \min_{\mathbf{x},\mathbf{z}} f(\mathbf{x})+g(\mathbf{z}) \\ s.t. \mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{z}=\mathbf{c} \end{aligned}$

其中： $\mathbf{x}\in \mathbb{R}^{p}$ , $\mathbf{z}\in \mathbb{R}^{q}$ , $\mathbf{A}\in \mathbb{R}^{k\times p}$ , $\mathbf{B}\in \mathbb{R}^{k\times q}$ , $\mathbf{c}\in \mathbb{R}^{k}$ ； $f:\mathbb{R}^p\to \mathbb{R}$ , $g:\mathbb{R}^q\to \mathbb{R}$ 。
简单来讲，这一优化问题的目标函数包含两组可分离自变量（和），且存在线性等式约束。对于这一优化问题，ADMM算法首先对目标函数进行增广，将原始优化问题转化为：

$\begin{array}{c} \min_{\mathbf{x},\mathbf{z}} Q_{\rho}(\mathbf{x},\mathbf{z})=f(\mathbf{x})+g(\mathbf{z})+\frac{\rho}{2}\|\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{z}-\mathbf{c}\|_2^2 \\ s.t. \mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{z}=\mathbf{c} \end{array}$

进一步写出该问题的拉格朗日函数式子：

$\begin{aligned} L_{\rho}(\mathbf{x},\mathbf{z},\boldsymbol{\lambda})&= Q_{\rho}(\mathbf{x},\mathbf{z})+\boldsymbol{\lambda}^{\top}(\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{z}-\mathbf{c})\\ &=f(\mathbf{x})+g(\mathbf{z})+\frac{\rho}{2}\|\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{z}-\mathbf{c}\|_2^2+\boldsymbol{\lambda}^{\top}(\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{z}-\mathbf{c}) \end{aligned}$
其中为拉格朗日乘子（向量）。
接着使用如下更新步骤进行迭代（第 $l$ 步更新）直至收敛：

更新： $\mathbf{x}=\arg\min_{\mathbf{x}} L_{\rho}(\mathbf{x},\mathbf{z}^{(l-1)},\boldsymbol{\lambda}^{(l-1)})$
更新： $\mathbf{z}=\arg\min_{\mathbf{z}} L_{\rho}(\mathbf{x}^{(l)},\mathbf{z},\boldsymbol{\lambda}^{(l-1)})$
更新 $\boldsymbol{\lambda}$ ： $\boldsymbol{\lambda}^{(l)}=\boldsymbol{\lambda}^{(l-1)}+\rho(\mathbf{A}\mathbf{x}^{(l)}+\mathbf{B}\mathbf{z}^{(l)}-\mathbf{c})$

这个更新步骤还是很容易看明白的。但朋友，你懵逼了没有？至少我第一次看这玩意的时候是不知道这三个更新步骤是什么意思的。后来看了CMU那个凸优化的课才慢慢搞清楚这个脑洞是怎么开来的。今天来说道说道......
1. 相关发展脉络

1.1 包络定理 (Envelop Theorem)

简单来讲，包络定理其实研究的是：对于一个带超参数的优化问题而言，这个超参数的变动会对这一优化问题的最优值产生什么样的影响。
在线性规划里头常见的“影子价格”问题其实就是这个研究的一个特例~
具体来讲，考虑一个带超参数的优化问题：

$\begin{aligned} V(\boldsymbol{\alpha}&)=\max_{\mathbf{x}} f(\mathbf{x}; \boldsymbol{\alpha}) \\ &s.t. \quad g(\mathbf{x}; \boldsymbol{\alpha}) \geq \mathbf{0} \end{aligned}$

其中： $\mathbf{x}\in \mathbb{R}^p$ ； $f:\mathbb{R}^{p}\to \mathbb{R}$ ， $g:\mathbb{R}^{p}\to \mathbb{R}^k$ ；是相关的超参数（可以是向量或标量）。
我们可以写出这个优化问题的拉格朗日函数：

$L(\mathbf{x},\boldsymbol{\lambda};\boldsymbol{\alpha})=f(\mathbf{x};\boldsymbol{\alpha})+\boldsymbol{\lambda}^{\top}g(\mathbf{x};\boldsymbol{\alpha}))$

其中：为拉格朗日乘子向量。
假设这个优化问题的最优值点为 $(\mathbf{x}^*(\boldsymbol{\alpha}),\boldsymbol{\lambda}^*(\boldsymbol{\alpha}))$ ，那么包络定理告诉我们：

$\frac{\partial V(\boldsymbol{\alpha})}{\partial \boldsymbol{\alpha}}=\frac{\partial L(\mathbf{x}^*(\boldsymbol{\alpha}),\boldsymbol{\lambda}^*(\boldsymbol{\alpha});\boldsymbol{\alpha})}{\partial \boldsymbol{\alpha}}$

一句话概括下，包络定理其实说的是：优化问题的最优值对超参数的偏导数等于拉格朗日函数函数在最优点处对该超参数的偏导。
有了这个定理，我们下面可以引出来凸优化问题里面的一个概念——共轭函数~
1.2 共轭函数 (Conjugate Function)

(待更）
1.3 对偶梯度下降法 (Dual Subgradient Method)

1.4 增广拉格朗日方法（Augmented Lagrangian Method）

2. 算法有关细节

2.1 Scaled Form——表示形式更简单的ADMM算法等价写法

2.2 终止条件

3. ADMM为什么强大——举个例子（Lasso）

		自动登录	找回密码
密码			立即注册

ADMM算法原理详解

本帖子中包含更多资源