08-ADMM算法

⽬录

ADMM最基本情形的推导还是⽐较经典的。这⾥介绍这份著名讲义⾥的treatment：

Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends® inMachine learning, 2011, 3(1): 1-122.

⼀、ADMM 算法动机

这⾥简单讲个例⼦，在深度学习中，样本的维度 d 是⾮常⼤的，如果我们直接对这种⼤维度的样本构建⽬标函数 f(x)，是不容易求解的。

因此我们可以考虑是否可以把 x 拆分成 x1,x2,⋯,xN，也就是把⽬标函数分割成多个⽬标函数 f（）x),f(x),⋯,f(x)，然后我们先最⼩化 f(x)，之后在最⼩化 f(x)，甚⾄可以对这个多

12N12个⽬标函数进⾏分布式优化。

⼆、对偶问题

原问题：

min

s.t.

拉格朗⽇函数：L(x,y)=f(x)+yT(Ax−b)对偶函数：g(y)=infxL(x,y)≤f(x)对偶问题：maxyg(y)最优解：

argminx∗=xL(x,y∗)

argmaxy∗=yg(y)

f(x)

Ax=b

三、对偶上升法

对偶变量 y 迭代更新：yk+1=yk+αk∇g(yk)，其中

ˆ,yk))∇g(yk)=∇y(L(x

ˆ)+(yk)T(Axˆ−b))=∇y(f(xˆ−b=Ax

argmin

xˆ上述公式中 =xL(x,yk)变量和对偶变量更新的步骤：

$x^{k+1} = \set{x}{argmin} L(x,y^k)\\quad \ext{变量 x的更新}$

$y^{k+1} = y^k + \\alpha^k (Ax^{k+1}-b)\\quad \ext{对偶变量 y 的更新}$

注：如果 f(x) 是线性的，可以看到 L(x,y) 基本⽆下界，也就是说 x 的更新不可以求解，这是未来使⽤增⼴拉格朗⽇函数的原因之⼀

四、对偶分割

对偶分割简单点说，就是假设⽬标函数可分，则对偶函数同样可分，这⾥给出简单的证明。假设 f 可分，也就是说⽬标函数 f(x)=∑Ni=1fi(xi)，约束条件 Ax=[A1,A2,⋯,AN]x=A1x,A2x,⋯,ANx通过上述的假设，则对偶函数 L(x,y) 可以通过下式表达：

L(x,y)=i=1fi(xi)+yT(i=1Aixi−b)

∑∑∑

NN

N

∑

N

=i=1(fi(xi)+yTAixi)−yTb

=i=1Li(x,y)−yTb

从上述推导可以看出，对偶函数 L(x,y) 同样可分。

argmin

Li(xi,yk)

+1=xi也就是说，在对 x 进⾏ argmin 的时候，可以分布式处理 x：xki

五、乘⼦法（增⼴拉格朗⽇函数）Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js

ρ

前⾯讲对偶上升法的时候讲到，f(x) 线性时更新时可能⽆法求解，因此把拉格朗⽇函数变成增⼴拉格朗⽇函数，即在拉格朗⽇函数的基础上加上惩罚因⼦ 2‖，让拉格朗⽇函数更加光滑、稳定，并且解决 f(x) 线性⽆法求解的问题，也就是为了不需要 f(x) ⼀定要是严格凸的。增⼴拉格朗⽇函数：L(x,y) = f(x) + y^T(Ax-b) + \\frac{\\rho}{2}\\|Ax-b\\|_2^2进⽽上述对偶上升法变量的更新将会变成：

x^{k+1} = \set{x}{argmin}\\quad L_\\rho(x,y^k) \\\\ y^{k+1} = y^k + \\rho(Ax^{k+1}-b)

5.1 步长为 \\rho 的好处

这⾥通过简单地公式推导证明下使⽤步长 \\rho 的优点。对于优化问题：

\\begin{align} min & \\quad f(x) \\\\ s.t. & \\quad Ax=b \\end{align}它的 KKT 条件为：

\\begin{align} & Ax^*-b = 0\\\\ & \\nabla f(x^*) + A^Ty=0 \\end{align}

现在我们更新变量 x，即 \set{argmin}{x} L_\\rho (x^{k+1},y^k)，有如下推导：

\\begin{align} 0 & = \\nabla_x L_\\rho (x^{k+1},y^k) \\\\ & = \\nabla_x f(x^{k+1}) + A^Ty^k + \\rho A^T (Ax^{k+1}-b) \\\\ & = \\nabla_x f(x^{k+1}) + A^T[y^k+\\rho (Ax^{k+1}-b)] \\\\ & = \\nabla_xf(x^{k+1}) + A^T y^{k+1} \\end{align}

从上述推导，可以看出步长选择 \\rho ，在找 x^{k+1} 的时候，也就是 (x^{k+1},y^{k+1}) ⾃然⽽然的满⾜了 KKT 条件。

注：使⽤了增⼴拉格朗⽇函数后，虽然求解更加稳定，但是由于惩罚项中有交叉项，如 x_1×x_2，导致拉增⼴格朗⽇函数不可以对偶分割，因此⽆法做到分布式处理。因此有了ADMM 算法，结合了对偶上升法的变量和对偶变量的交叉迭代更新和增⼴拉格朗⽇函数的稳定性

六、ADMM算法

为了整合对偶上升法的可分解性与乘⼦法优秀的收敛性质，⼈们就⼜提出了改进形式的优化 ADMM。⽬的就是想能分解原函数和扩增函数，以便于在对 f 更⼀般的假设条件下并⾏优化。所以 ADMM 是⼜想引⼊新变量，然后⼜想通过交叉更换⽅向进⽽交替优化。

ADMM 算法求解 2-block 的凸优化问题的形式如下（n-block 就是 n 个变量，但是 3-block 以上的问题性质会差很多）：\\begin{align} \\min ~ & f(x)+g(z)\\\\ s.t. ~ & Ax+Bz=C \\end{align}

从上⾯ ADMM 算法的形式可以看出，它的思想就是想把 primal 变量、⽬标函数拆分，但是不再像对偶上升⽅法那样，将拆分开的 x_i 都看做是 x 的⼀部分，后⾯融合的时候还需要融合在⼀起，⽽是最先开始就将变量分别看做是不同的变量 x 和 z，同时约束条件也如此处理，这样的好处就是后⾯不需要⼀起融合 x 和 z ，保证了前⾯优化过程的可分解性（每次只优化不同的变量）。

ADMM 算法的增⼴拉格朗⽇函数：L_{\\rho}(x,z,y)=f(x)+g(z)+y^T(Ax+Bz-c)+(\\rho/2)\\|Ax+Bz-c\\|_2^2ADMM 算法的变量更新：

\\begin{align} x^{k+1}:=~ & \\arg\\min_{x} L_{\\rho}(x,z^k,y^k)\\\\ z^{k+1}:=~ & \\arg\\min_{z} L_{\\rho}(x^{k+1},z,y^k)\\\\ y^{k+1}:= ~ & y^k+\\rho(Ax^{k+1}+Bz^{k+1}-c). \\end{align}

6.1 ADMM 的 scaled form 形式

注：ADMM 的 scaled form 形式本质上就是对对偶变量做了处理，并且定义了残差，通过残差可以更易于判别 ADMM 算法的收敛性假设 r = Ax+Bz-C，\\quad u=\\frac{y}{\\rho}进⽽可以得到新的增⼴拉格朗⽇函数：

\\begin{align} L_\\rho & = f(x)+g(z)+y^(r)+\\frac{\\rho}{2}\\|r\\|_2^2 \\\\ & = f(x) + g(z) + \\frac{\\rho}{2}\\|r+\\frac{y}{\\rho}\\|_2^2 - \\frac{1}{2\\rho}\\|y\\|_2^2 \\\\ & = f(x) + g(z) + \\frac{\\rho}{2}\\|r+u\\|_2^2 -\\frac{\\rho}{2}\\|u\\|_2^2 \\\\ \\end{align}由此 ADMM 算法将被改写成：

\\begin{align} x^{k+1}:=~ & \\arg\\min_{x} \\left\\{ f(x)+\\frac{\\rho}{2}\\|Ax+Bz^k-c+u^k\\|_2^2 \\right\\}\\\\ z^{k+1}:=~ & \\arg\\min_{z} \\left\\{ g(z)+\\frac{\\rho}{2}\\|Ax^{k+1}+Bz-c+u^k\\|_2^2 \\right\\}\\\\u^{k+1}:= ~ & u^k+Ax^{k+1}+Bz^{k+1}-c \\end{align}

上述这个形式就⽐前⾯那个更简洁，我们⼀般叫前⼀种形式为ADMM的unscaled形式，⽽这种则是scaled形式了。并且很多ADMM分析都是基于这个scaled形式的。上述u 为scaled scaled dual variable， r 可以理解为对偶变量 u 的每⼀步迭代的残差，⽽ u^k = u^0 + \\sum_{j=1}^k r^j 定义为残差和。

七、ADMM的收敛性证明思路

在两个不太强的假设前提下，本节给出ADMM基本形式的收敛性证明的思路。假设1： 凸函数f,g 是closed和proper的。

假设2：（⾮增⼴）拉格朗⽇函数 L_0 ⾄少有⼀个鞍点（saddle point）。

假设1等价于epigraph \\{(x,t)\\in \\mathbb{R}^n\imes\\mathbb{R}:f(x)\\leq t\\}, \\{(z,s)\\in \\mathbb{R}^m\imes\\mathbb{R}:g(z)\\leq s\\} 都是⾮空的闭凸集（closed

nonempty convex set），也就是说 \\arg\\min_{x} L_{\\rho}(x,z^k,y^k) ， $ \\arg\\min_{z} L_{\\rho}(x{k+1},z,yk)$ 的解⼀定是存在的。注意，这个假设仍然没有限制 f,g ⼀定要是可微（differentiable）的，如果 f，g不可微，可以考虑使⽤次梯度。

假设2 可以这样解释鞍点的作⽤：假设 (x^*,y^*,z^*) 为鞍点，则会有 L_0(x^*,z^*,y)\\leq L_0(x^*,z^*,y^)* \\leq L_0(x,z,y^*)，毫⽆疑问，这个不等式是⼀定成⽴的，也就是说在(x^*,y^*,z^*) 这个点有⼀个⽅向更⼤，另⼀个⽅向更⼩，满⾜鞍点的性质，进⽽推出 L_0 必有⼀个鞍点。从⽽说明了 ADMM 算法是可解的。基于这两个假设，我们证明如下结果：

⽬标函数值收敛。随着 k\\rightarrow\\infty, ~ f(x^k)+g(z^k)\\rightarrow p^*. 也就是说最终我们的⽬标函数值是最优的。对偶变量收敛。随着 k\\rightarrow\\infty, ~ y^k\\rightarrow y^*. 也就是最终对偶变量的值收敛到某个对偶变量的最优解。残差收敛。随着 k\\rightarrow\\infty, ~ r^k\\rightarrow 0. 也就是说最终我们的解是可⾏（feasible）的。

⼋、写在最后

事实上，实际当中你如果写代码跑ADMM会发现它不像那些梯度下降，⽜顿法，很容易快速收敛到⼀个较⾼的误差精度，ADMM实际的收敛速度往往⽐那些算法慢得多。ADMM的主要应⽤，主要是在解空间规模⾮常⼤的情况下（⽐如 A,B 都是存储空间上GB的矩阵），这个时候很多传统的⽅法不好⽤，强制需要分块求解，⽽且对解的绝对精度往往要求也没那么⾼。当然，然后你还得祈祷在primal space上argmin那个迭代的形式⽐较简单。