ADMM

ADMM算法理论与应用

前言

交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）是一种解决可分解凸优化问题的简单方法，尤其在解决大规模问题上卓有成效，利用ADMM算法可以将原问题的目标函数等价的分解成若干个可求解的子问题，然后并行求解每一个子问题，最后协调子问题的解得到原问题的全局解。ADMM 最早分别由 Glowinski & Marrocco 及 Gabay & Mercier 于 1975 年和 1976 年提出，并被 Boyd 等人于 2011 年重新综述并证明其适用于大规模分布式优化问题。由于 ADMM 的提出早于大规模分布式计算系统和大规模优化问题的出现，所以在 2011 年以前，这种方法并不广为人知。

对偶上升方法

考虑等式约束的最优化问题如下

min ⁡ x f ( x ) \min_x f(x)

min

f(x)

s t . A x = b st. Ax=b

st.Ax=b

其中x ∈ R n , A ∈ R m × n , f : R n ∈ R x\in\mathbb R^n,A\in\mathbb R^{m\times n},f:\mathbb R^n \in\mathbb Rx∈R

,A∈R

m×n

,f:R

∈R是凸函数

原问题的拉格朗日函数为：

L ( x , y ) = f ( x ) + y T ( A x − b ) L(x,y) = f(x) + y^T(Ax-b)

L(x,y)=f(x)+y

(Ax−b)

那么其对偶函数为:

g ( y ) = i n f x L ( x , y ) = − f ∗ ( − A T y ) − b T y g(y)=inf_xL(x,y)=-f^*(-A^Ty)-b^Ty

g(y)=inf

L(x,y)=−f

∗

(−A

y)−b

其中y yy是拉格朗日乘子，也是对偶变量，f ∗ f^*f

∗

是f ff共轭函数。

假设满足强对偶性，则原问题和对偶问题的最优值相等。我们设原问题最优解为x ∗ x^*x

∗

,对偶问题最优解为y ∗ y^*y

∗

，则

x ∗ = a r g m i n x L ( x , y ∗ ) x^*=argmin_xL(x,y^*)

∗

=argmin

L(x,y

∗

)

在对偶上升方法中，对偶问题是通过梯度上升方法来解，因此对偶上升迭代更新为:

x k + 1 = a r g m i n x L ( x , y k ) x_{k+1}=argmin_xL(x,y^k)

k+1

=argmin

L(x,y

)

y k + 1 = y k + α k ( A x k + 1 − b ) y^{k+1}=y^k+\alpha_k(Ax^k+1-b)

k+1

+α

(Ax

+1−b)

其中α k > 0 \alpha_k>0α

>0,是梯度上升的步长。

对偶分解性

对偶上升方法中在满足强对偶性条件下，通过梯度上升来逐步调整对偶变量，再通过对偶变量来求解原问题最优解，这样的好处是在有些情况下可以使算法可分解，假设目标函数是可分解的，即，

f ( x ) = ∑ i = 1 N f i ( x i ) f(x)=\sum_{i=1}^Nf_i(x_i)

f(x)=

i=1

∑

)

其中x = ( x 1 , x 2 , … , x N ) , x i ∈ R n i x=(x_1,x_2,\dots,x_N),x_i\in\mathbb R^{n_i}x=(x

,…,x

),x

∈R

,划分矩阵A

A = [ A 1 , A 2 , ⋯ , A N ] A=[A_1,A_2,\cdots,A_N]

A=[A

,⋯,A

]

所以A x = ∑ i = 1 N A i x i Ax=\sum_{i=1}^NA_ix_iAx=∑

i=1

,则拉格函数重写成

L ( x , y ) = ∑ i = 1 N L i ( x i , y ) = ∑ i = 1 N ( f i ( x i ) + y T A i x i − ( 1 N ) y T b ) L(x,y)=\sum_{i=1}^NL_i(x_i,y)=\sum_{i=1}^N(f_i(x_i)+y^TA_ix_i-(\frac{1}{ N})y^Tb)

L(x,y)=

i=1

∑

,y)=

i=1

∑

)+y

−(

对偶上升的迭代更新:

x i k + 1 = a r g m i n x i L i ( x i , y k ) x_i^{k+1}=argmin_{x_i}L_i(x_i,y^k)

k+1

=argmin

)

y k + 1 = y k + α k ( A x k + 1 − b ) y^{k+1}=y^k+\alpha^k(Ax^{k+1}-b)

k+1

+α

(Ax

k+1

−b)

增广拉格朗日（乘子法）

为了增加对偶上升方法的鲁棒性和放松目标强凸的要求，引入了增广拉格朗日，增广拉格朗日，形式如下:

L ρ ( x , y ) = f ( x ) + y T ( A x − b ) + ρ 2 ∥ A x − b ∥ 2 2 L_\rho(x,y)=f(x)+y^T(Ax-b)+\frac{\rho}{2}

∥Ax−b∥

‖Ax−b‖

_2^2

(x,y)=f(x)+y

(Ax−b)+

∥

Ax−b

∥

其中ρ > 0 \rho >0ρ>0，是惩罚参数。

增广拉格朗日相当于在拉格朗日加了一个强凸的惩罚项使得原约束问题变成如下形式

min ⁡ x f ( x ) + ρ 2 ∥ A x − b ∥ 2 2 \min_xf(x)+\frac{\rho}{2}

∥Ax−b∥

‖Ax−b‖

_2^2

min

f(x)+

∥

Ax−b

∥

s . t . A x = b s.t. Ax=b

s.t.Ax=b

对偶上升迭代更新:

x k + 1 = a r g m i n x L ρ ( x , y k ) x^{k+1}=argmin_xL_\rho(x,y^k)

k+1

=argmin

(x,y

)

y k + 1 = y k + ρ ( A x k + 1 − b ) y^{k+1}=y^k+\rho(Ax^{k+1}-b)

k+1

+ρ(Ax

k+1

−b)

这就是所谓的乘子法，从迭代形式上看，有两点和对偶上升方法不一样，第一是x k + 1 x^{k+1}x

k+1

更新使用增广拉格朗日，第二是更新的步长用惩罚参数ρ \rhoρ代替了α k \alpha^kα

。乘子法虽然可以比对偶上升方法在更一般的条件下收敛，但是增加了二次惩罚项，使得原问题失去可分解性，因而引入了ADMM算法。

交替方向乘子法（ADMM）

假设有如下优化问题：

min ⁡ x f ( x ) + g ( z ) \min_xf(x)+g(z)

min

f(x)+g(z)

s . t . A x + B z = c s.t. Ax+Bz=c

s.t.Ax+Bz=c

其中x ∈ R n , z ∈ R m , A ∈ R p × n , B ∈ R p × m , c ∈ R p x\in\mathbb R^n,z\in\mathbb R^m,A\in\mathbb R^{p\times n},B\in\mathbb R^{p\times m},c\in\mathbb R^px∈R

,z∈R

,A∈R

p×n

,B∈R

p×m

,c∈R

其增广拉格朗日函数如下：

L ρ ( x , z , y ) = f ( x ) + g ( z ) + y T ( A x + B z − c ) + ρ 2 ∥ A x + B z − c ∥ 2 2 L_\rho(x,z,y)=f(x)+g(z)+y^T(Ax+Bz-c)+\frac{\rho}{2}

∥Ax+Bz−c∥

‖Ax+Bz−c‖

_2^2

(x,z,y)=f(x)+g(z)+y

(Ax+Bz−c)+

∥

Ax+Bz−c

∥

ADMM的更新迭代形式如下:

x k + 1 = a r g m i n x L ρ ( x , y k , z k ) x^{k+1}=argmin_xL_\rho(x,y^k,z^k)

k+1

=argmin

(x,y

)

z k + 1 = a r g m i n z L ρ ( x k + 1 , z , y k ) z^{k+1}=argmin_zL_\rho(x^{k+1},z,y^k)

k+1

=argmin

k+1

,z,y

)

y k + 1 = y k + ρ ( A x k + 1 + B z k + 1 − c ) y^{k+1}=y^k+\rho(Ax^{k+1}+Bz^{k+1}-c)

k+1

+ρ(Ax

k+1

+Bz

k+1

−c)

其中ρ > 0 \rho > 0ρ>0，以上就是最原始的ADMM算法迭代形式

全局变量一致性优化(Global Variable Consensus Optimization)

接下来讨论如何将其应用到机器学习算法分布式计算中，但在这之前我们先讨论一个比较广义的优化问题如下:

min ⁡ x ∑ i = 1 N f i ( x i ) \min_x\sum_{i=1}^Nf_i(x_i)

min

i=1

∑

)

s . t . x i − z = 0 , i = 0 , 1 , … , N s.t.x_i-z=0,i=0,1,\dots,N

s.t.x

−z=0,i=0,1,…,N

以上问题形式就是全局一致性问题，x i x_ix

局部变量，z zz是全局一致变量。从限制约束条件来看，每一个局部变量需要保持一致。

其增广拉格朗日函数为:

L ρ ( x 1 , x 2 , … , x N , z , y ) = ∑ i = 1 N f i ( x i ) + y i T ( x i − z ) + ρ 2 ∥ x i − z ∥ 2 2 L_\rho(x_1,x_2,\dots,x_N,z,y)=\sum_{i=1}^Nf_i(x_i)+y^T_i(x_i-z)+\frac{\rho}{2}

∥xi−z∥

‖xi−z‖

_2^2

,…,x

,z,y)=

i=1

∑

)+y

−z)+

∥

−z

∥

ADMM迭代更新形式:

x i k + 1 = a r g m i n x f i ( x i ) + y i T k ( x i − z k ) + ρ 2 ∥ x i − z k ∥ 2 2 x_i^{k+1}=argmin_xf_i(x_i)+y_i^{T^k}(x_i-z^k)+\frac{\rho}{2}

∥xi−zk∥

‖xi−zk‖

_2^2

k+1

=argmin

)+y

−z

∥

−z

∥

z k + 1 = 1 N ∑ i = 1 N ( x i k + 1 + 1 ρ y i k ) z^{k+1}=\frac{1}{N}\sum_{i=1}^N(x_i^{k+1}+\frac{1}{\rho}y_i^k)

k+1

i=1

∑

k+1

)

y i k + 1 = y i k + ρ ( x i k + 1 − z k + 1 ) y_i^{k+1}=y_i^k+\rho(x_i^{k+1}-z^{k+1})

k+1

+ρ(x

k+1

−z

k+1

)

我们可以更进一步将上述问题推广更广义的优化问题，带正则的全局一致性优化问题，具体问题如下：

min ⁡ x ∑ i = 1 N f i ( x i ) + g ( z ) \min_x\sum_{i=1}^Nf_i(x_i)+g(z)

min

i=1

∑

)+g(z)

s . t . x i − z = 0 , i = 0 , 1 , … , N s.t. x_i-z=0,i=0,1,\dots,N

s.t.x

−z=0,i=0,1,…,N

其ADMM迭代更新形式如下:

x i k + 1 = a r g m i n x ( f i ( x i ) + y i T k ( x i − z k ) + ρ 2 ∥ x i − z k ∥ 2 2 ) x_i^{k+1}=argmin_x(f_i(x_i)+y_i^{T^k}(x_i-z^k)+\frac{\rho}{2}

∥xi−zk∥

‖xi−zk‖

_2^2)

k+1

=argmin

)+y

−z

∥

−z

∥

)

z k + 1 = a r g m i n z ( g ( z ) + ∑ i = 1 N ( − y i T k + ρ 2 ∥ x i k + 1 − z ∥ 2 2 ) ) z^{k+1}=argmin_z(g(z)+\sum_{i=1}^N(-y_i^{T^k}+\frac{\rho}{2}

∥∥xk+1i−z∥∥

‖xik+1−z‖

_2^2))

k+1

=argmin

(g(z)+

i=1

∑

(−y

∥

k+1

−z

∥

))

y i k + 1 = y i k + ρ ( x i k + 1 − z i k + 1 ) y_i^{k+1}=y_i^k+\rho(x_i^{k+1}-z_i^{k+1})

k+1

+ρ(x

k+1

−z

k+1

)

ADMM算法的应用

以上讨论了一些的理论的东西，接下来就尝试一下如何去应用ADMM算法去解决一些机器学习问题。实际上大多数分布式机器学习问题可以表达成全局一致性优化问题：

min ⁡ x ∑ i = 1 N f i ( x i ) + g ( z ) \min_x\sum_{i=1}^Nf_i(x_i)+g(z)

min

i=1

∑

)+g(z)

s . t . x i − z = 0 , i = 0 , 1 , … , N , s.t.x_i-z=0,i=0,1,\dots,N,

s.t.x

−z=0,i=0,1,…,N,

f i ( x i ) f_i(x_i)f

)表示划分到每一个节点上的目函数，x i x_ix

表示局部模型参数，z zz表示全局一致性变量。我们把整个数据集划分到每一节点，各节点独立并行训练，通过迭代更新，最终收敛到一个一致的全局解。

Lasso问题

具体问题形式如下:

min ⁡ x 1 2 ∥ A x − b ∥ 2 2 + λ ∥ x ∥ 1 \min_x\frac{1}{2}

∥Ax−b∥

‖Ax−b‖

_2^2+\lambda

∥x∥

‖x‖

min

∥

Ax−b

∥

+λ

∥

其中,A ∈ R m × n , b ∈ R m A\in\mathbb R^{m\times n},b\in\mathbb R^mA∈R

m×n

,b∈R

更换成全局一致性优化问题：

min ⁡ x i ∑ i = 1 N 1 2 ∥ A x − b ∥ 2 + λ ∥ z ∥ 1 \min_{x_i}\sum_{i=1}^N\frac{1}{2}

∥Ax−b∥

‖Ax−b‖

^2+\lambda

∥z∥

‖z‖

min

i=1

∑

∥

Ax−b

∥

+λ

∥

s . t . x i − z = 0 , i = 0 , 1 , … , N s.t. x_i-z=0,i=0,1,\dots,N

s.t.x

−z=0,i=0,1,…,N

ADMM迭代更新形式如下:

x i k + 1 = a r g m i n x i ( 1 2 ∥ A i x i − b i ∥ 2 + y i T k ( x i − z k ) + ρ 2 ∥ x i − z k ∥ 2 2 ) x_i^{k+1}=argmin_{x_i}(\frac{1}{2}

∥Aixi−bi∥

‖Aixi−bi‖

^2+y_i^{T^k}(x_i-z^k)+\frac{\rho}{2}

∥xi−zk∥

‖xi−zk‖

_2^2)

k+1

=argmin

(

∥

−b

∥

−z

∥

−z

∥

)

z k + 1 = a r g m i n z ( λ ∥ z ∥ 1 + ∑ i = 1 N ( − y i T k z + ρ 2 ∥ x i k + 1 − z ∥ 2 2 ) ) z^{k+1}=argmin_z(\lambda

∥z∥

‖z‖

_1+\sum_{i=1}^N(-y_i^{T^k}z+\frac{\rho}{2}

∥∥xk+1i−z∥∥

‖xik+1−z‖

_2^2))

k+1

=argmin

(λ

∥

i=1

∑

(−y

∥

k+1

−z

∥

))

y i k + 1 = y i k + ρ ( x i k + 1 − z k + 1 ) y_i^{k+1}=y_i^k+\rho(x_i^{k+1}-z^{k+1})

k+1

+ρ(x

k+1

−z

k+1

)

对于x k + 1 x^{k+1}x

k+1

的更新，右边括号内的函数对x xx求可导得(这里可以有更高效的算法求解):

A i T ( A i x i − b i ) + y i k + ρ ( x i − z k ) = 0 A_i^T(A_ix_i-b_i)+y_i^k+\rho(x_i-z^k)=0

−b

)+y

+ρ(x

−z

)=0

即可得:

x i k + 1 = ( A i T A i + ρ I ) − 1 ( A i T b i + ρ z k − y i k ) x_i^{k+1}=(A_i^TA_i+\rho I)^{-1}(A_i^Tb_i+\rho z^k-y_i^k)

k+1

=(A

+ρI)

−1

+ρz

−y

)

对于z zz的更新如下:

z k + 1 = a r g m i n z ( λ ∥ z ∥ 1 + ρ N 2 ∥ z − 1 ρ N ∑ i = 1 N ( ρ x i k + 1 + y i k ) ∥ 2 2 ) z^{k+1}=argmin_z(\lambda

∥z∥

‖z‖

_1+\frac{\rho N}{2}

∥∥z−1ρN∑Ni=1(ρxk+1i+yki)∥∥

‖z−1ρN∑i=1N(ρxik+1+yik)‖

_2^2)

k+1

=argmin

(λ

∥

ρN

∥

z−

ρN

∑

i=1

(ρx

k+1

)

∥

)

因此z zz的更新可以使用softthreshold方法如下所示：

z k + 1 = S λ / ρ N ( 1 ρ N ∑ i = 1 N ( ρ x i k + 1 + y i k ) ) z^{k+1}=\mathcal S_{\lambda/\rho N}(\frac{1}{\rho N}\sum_{i=1}^N(\rho x_i^{k+1}+y_i^k))

k+1

λ/ρN

(

ρN

i=1

∑

(ρx

k+1

))

其中

S κ ( a ) = { a − κ , a > κ 0 , ∣ a ∣ ≤ κ a + κ , a < − κ \mathcal S_{\kappa}(a)=

⎧⎩⎨a−κ,0,a+κ, a>κ ∣a∣≤κa<−κ

{a−κ, a>κ 0, ∣a∣≤κa+κ,a<−κ

(a)=

⎩

⎪

⎨

⎪

⎧

a−κ,

a+κ,

a>κ

∣a∣≤κ

a<−κ

————————————————

原文链接：https://blog.csdn.net/oBanTianYun/article/details/72590188

推荐阅读更多精彩内容