交替方向乘子法(admm)

这篇具有很好参考价值的文章主要介绍了交替方向乘子法(admm)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

统计学、机器学习和科学计算中出现了很多结构复杂且可能非凸、非光滑的优化问题。交替方向乘子法很自然地提供了一种适用范围广泛、容易理解和实现、可靠性不错地解决方案。该方法在20世纪70年代发展起来地,与许多其他算法等价或密切相关,如对偶分解、乘子方法、Douglas-Rachford Splitting方法、Dykstra交替投影方法、Bregman对于带 l 1 l_1 l1范数问题地迭代算法、近似点算法等、本届首先介绍交替方向乘子法地基本算法;在介绍了Douglas-Rachford Splitting方法之后,说明见其应用在对偶问题上与交替方向乘子法应用在原始问题上等价;然后给出交替方向乘子法地一些变形技巧,以及它和其他一些算法地关系;接着给出大量实际问题地例子,并展示如何用交替方向乘子法来求解这些问题

一、交替方向乘子法
本节考虑如下凸问题
min ⁡ x 1 , x 2 f 1 ( x 1 ) + f 2 ( x 2 ) s . t . A 1 x 1 + A 2 x 2 = b , (1) \begin{aligned} &\min_{x_1,x_2}\quad f_1(x_1)+f_2(x_2)\\ & s.t.\quad A_1x_1+A_2x_2=b, \end{aligned}\tag{1} x1,x2minf1(x1)+f2(x2)s.t.A1x1+A2x2=b,(1)
其中 f 1 , f 2 f_1,f_2 f1,f2是适当地闭凸函数,但不要求是光滑的, x 1 ∈ R n , x 2 ∈ R m , A 1 ∈ R p × n , A 2 ∈ R p × m , b ∈ R p x_1\in\mathcal{R^n},x_2\in\mathcal{R^m},A_1\in\mathcal{R^{p\times n}},A_2\in\mathcal{R^{p\times m}},b\in\mathcal{R^p} x1Rn,x2Rm,A1Rp×n,A2Rp×m,bRp.这个问题的特点是目标函数可以分成彼此分离的两块,但是变量被线性约束结合在一起。常见的一些无约束和带约束的优化问题都可以表示成这一形式。下面的一些例子将展示如何把某些一般的优化问题转化为适合交替方向乘子法求解的标准形式。

例1 可以分成两块的无约束优化问题
min ⁡ x f 1 ( x ) + f 2 ( x ) \min_x f_1(x)+f_2(x) xminf1(x)+f2(x)
为了将此问题转化为标准形式(1),需要将目标函数改成可分的形式。我们可以通过引入一个新的变量 z z z并令 x = z x=z x=z,将问题转化为
min ⁡ x , z f 1 ( x ) + f 2 ( z ) , s . t . x − z = 0. \begin{aligned} & \min_{x,z}\quad f_1(x)+f_2(z), \\ & s.t.\quad x-z=0. \end{aligned} x,zminf1(x)+f2(z),s.t.xz=0.

例2 带线性变化的无约束优化问题
min ⁡ x f 1 ( x ) + f 2 ( A x ) . \min_{x} f_1(x)+f_2(Ax). xminf1(x)+f2(Ax).
类似地,我们可以引入一个新的变量 z z z,令 z = A x z=Ax z=Ax,则问题变为
min ⁡ x , z f 1 ( x ) + f 2 ( z ) , s . t . A x − z = 0 \begin{aligned} &\min_{x,z}\quad f_1(x)+f_2(z),\\ &s.t.\quad Ax-z = 0 \end{aligned} x,zminf1(x)+f2(z),s.t.Axz=0
对比问题(1)可知, A 1 = A , A 2 = − I A_1=A,A_2=-I A1=A,A2=I

例3 凸集上的约束优化问题
min ⁡ x f ( x ) s . t . A x ∈ C . \begin{aligned} &\min_x\quad f(x)\\ &s.t.\quad Ax\in C. \end{aligned} xminf(x)s.t.AxC.
其中 C ⊂ R n C\subset\mathcal{R^n} CRn为凸集。对于集合约束 A x ∈ C Ax\in C AxC,我们可以用实行函数 I C ( ⋅ ) I_C(\cdot) IC()将其添加到目标函数中,那么问题可转化为如下形式:
min ⁡ x f ( x ) + I C ( A x ) , \min_x f(x)+I_C(Ax), xminf(x)+IC(Ax),
其中 I C ( z ) I_C(z) IC(z)是集合C的实行函数,即
I C ( z ) = { 0 , z ∈ C , + ∞ , o t h e r w i s e . I_C(z)=\left\{ \begin{aligned} &0,&z\in C,\\ &+\infty,&otherwise. \end{aligned} \right. IC(z)={0,+,zC,otherwise.
再引入约束 z = A x z=Ax z=Ax,那么问题转化为
min ⁡ x , z f ( x ) + I C ( z ) s . t . A x − z = 0 \begin{aligned} &\min_{x,z} f(x)+I_C(z)\\ &s.t. Ax-z = 0 \end{aligned} x,zminf(x)+IC(z)s.t.Axz=0

例4 全局一致性问题
min ⁡ x ∑ i = 1 N ϕ i ( x ) \min_x\sum_{i=1}^{N}\phi_i(x) xmini=1Nϕi(x)
x = z x=z x=z,将 x x x复制 N N N份,分别为 x i x_i xi,那么问题转化为
min ⁡ x i , z ∑ i = 1 N ϕ i ( x i ) , s . t . x i − z = 0 , i = 1 , 2 , ⋯   , N \begin{aligned} &\min_{x_i,z}\sum_{i=1}^{N}\phi_i(x_i),\\ & s.t. x_i-z=0,i=1,2,\cdots,N \end{aligned} xi,zmini=1Nϕi(xi),s.t.xiz=0,i=1,2,,N
在这里注意,从形式上看全局一致性问题仍然具有问题(1)的结果:如果令 x = ( x 1 T , x 2 T , ⋯   , x N T ) T x=(x_1^T,x_2^T,\cdots,x_N^T)^T x=(x1T,x2T,,xNT)T以及 f x ( x ) = ∑ i = 1 N ϕ i ( x i ) , f 2 ( z ) = 0 f_x(x)=\sum_{i=1}^N\phi_i(x_i),f_2(z)=0 fx(x)=i=1Nϕi(xi),f2(z)=0,则此问题可转化为
min ⁡ x , z f 1 ( x ) + f 2 ( x ) , s . t . A 1 x − A 2 z = 0 , \begin{aligned} &\min_{x,z}f_1(x)+f_2(x),\\ &s.t. A_1x-A_2z=0, \end{aligned} x,zminf1(x)+f2(x),s.t.A1xA2z=0,
其中矩阵 A 1 , A 2 A_1,A_2 A1,A2定义为:
A 1 = [ I I ⋱ I ] , A 2 = [ I I ⋮ I ] . A_1=\begin{bmatrix} &I&&&\\ &&I&&\\ &&&\ddots&\\ &&&&I \end{bmatrix}, A_2=\begin{bmatrix} I\\I\\\vdots\\I \end{bmatrix}. A1= III ,A2= III .
在全局一致性问题的例子中,我们将问题重写为具有两个变量快的形式,而不是简单地将问题(1)推广为多个变量快地形式,这样做的原因是ADMM算法从两个变量块推广到多个变量块的形式并不一定收敛。

例5 共享问题
min ⁡ x i ∑ i = 1 N f i ( x i ) + g ( ∑ i = 1 N x i ) \min_{x_i}\sum_{i=1}^{N}f_i(x_i)+g(\sum_{i=1}^{N}x_i) ximini=1Nfi(xi)+g(i=1Nxi)
为了使目标函数可分,我们将 g g g的变量 x i x_i xi分别复制一份为 z i z_i zi,那么问题转化为
min ⁡ x i , z i ∑ i = 1 N f i ( x i ) + g ( ∑ i = 1 N z i ) , s . t . x i − z i = 0 , i = 1 , 2 , ⋯   , N . \begin{aligned} &\min_{x_i,z_i}\sum_{i=1}^{N}f_i(x_i)+g(\sum_{i=1}^{N}z_i),\\ &s.t. x_i-z_i=0,i=1,2,\cdots,N. \end{aligned} xi,zimini=1Nfi(xi)+g(i=1Nzi),s.t.xizi=0,i=1,2,,N.
容易验证此问题也具有(1)的形式。
下面给出交替方向乘子法(alternating direction method of multipliers, ADMM)的迭代格式,首先写出问题(1)的增广拉格朗日函数:
L ρ ( x 1 , x 2 , y ) = f 1 ( x 1 ) + f 2 ( x 2 ) + y T ( A 1 x 1 + A 2 x 2 − b ) + ρ 2 ∣ ∣ A 1 x 1 + A 2 x 2 − b ∣ ∣ 2 2 , (2) L_{\rho}(x_1,x_2,y)=f_1(x_1)+f_2(x_2)+y^T(A_1x_1+A_2x_2-b)+\frac{\rho}{2}||A_1x_1+A_2x_2-b||_2^2, \tag{2} Lρ(x1,x2,y)=f1(x1)+f2(x2)+yT(A1x1+A2x2b)+2ρ∣∣A1x1+A2x2b22,(2)
其中 ρ > 0 \rho>0 ρ>0是二次惩罚项的稀疏。常见的求解带约束问题的拉格朗日函数法为如下更新:
( x 1 k + 1 , x 2 k + 1 ) = a r g m i n x 1 , x 2 L ρ ( x 1 , x 2 , y k ) (3) \begin{aligned} (x_1^{k+1},x_2^{k+1}) & = argmin_{x_1,x_2}L_{\rho}(x_1,x_2,y^k) \end{aligned} \tag{3} (x1k+1,x2k+1)=argminx1,x2Lρ(x1,x2,yk)(3)
y k + 1 = y k + τ ρ ( A 1 x 1 k + 1 + A 2 k + 1 − b ) (4) y^{k+1}=y^k+\tau\rho(A_1x_1^{k+1}+A_2^{k+1}-b) \tag{4} yk+1=yk+τρ(A1x1k+1+A2k+1b)(4)
其中 τ \tau τ为步长。在实际求解中,第一步迭代(3)同时对 x 1 x_1 x1 x 2 x_2 x2进行优化有时候比较困难,而固定一个变量求解关于另一个变量的极小化问题可能比较简单,因此我们可以考虑对 x 1 x_1 x1 x 2 x_2 x2交替极小化,这就是交替方向乘子法的基本思路。其迭代格式可以总结如下:
x 1 k + 1 = a r g min ⁡ x 1 L ρ ( x 1 , x 2 k , y k ) , (5) x_1^{k+1}=arg\min_{x_1}L_{\rho}(x_1,x_2^k,y^k),\tag{5} x1k+1=argx1minLρ(x1,x2k,yk),(5)
x 2 k + 1 = a r g min ⁡ x 2 L ρ ( x k + 1 , x 2 , y k ) , (6) x_2^{k+1}=arg\min_{x_2}L_{\rho}(x_{k+1},x_2,y^k),\tag{6} x2k+1=argx2minLρ(xk+1,x2,yk),(6)
y k + 1 = y k + τ ρ ( A 1 x 1 k + 1 + A 2 x 2 k + 1 − b ) , (7) y^{k+1}=y^k+\tau\rho(A_1x_1^{k+1}+A_2x_2^{k+1}-b),\tag{7} yk+1=yk+τρ(A1x1k+1+A2x2k+1b),(7)
其中 τ \tau τ为步长,通常取值为 ( 0 , 1 + 5 2 ] (0,\frac{1+\sqrt{5}}{2}] (0,21+5 ].关于选择步长的收敛性。
观察交替方向乘子法的迭代格式,第一步固定 x 2 , y x_2,y x2,y x 1 x_1 x1求绩效;第二步固定 x 1 , y x_1,y x1,y x 2 x_2 x2求极小;第二步更新拉格朗日乘子 y y y。这一迭代格式和之前讨论的交替极小化方法非常类似。它们的区别是交替极小化方法的第一步是针对拉格朗日函数求极小,而ADMM的第一步将其化成了增广拉格朗日函数。虽然从形式上看两个算法只是略有差别,但这种改变会带来截然不同的算法表先。ADMM的一个直接的改善就是去掉了目标函数 f 1 ( x ) f_1(x) f1(x)强凸的要求,其本质还是由于它引入了二次惩罚项。而在交替极小化方法中我们要求 f ( x ) f(x) f(x)为强凸函数。
需要注意的是,虽然交替方向乘子法引入了二次惩罚项,但对一般的闭凸函数 f 1 f_1 f1 f 2 f_2 f2,迭代(5)和迭代(6)在某些特殊情况下仍然不是连定义的。本届假设每个子问题的解均是存在且唯一的,但读者应当注意到这个假设对一般闭凸函数是不成立的。
与无约束优化问题不同,交替方向乘子法针对问题(1)是带约束的优化问题,因此算法的收敛准则应当借助约束优化问题的最优性条件(KKT条件)。因为 f 1 , f 2 f_1,f_2 f1,f2均为闭凸函数,约束为线性约束,所以但Slater条件成立时,可以使用凸优化问题的KKT条件来作为交替方向乘子法的收敛准则。问题(1)的拉格朗日函数为
L ρ ( x 1 , x 2 , y ) = f 1 ( x 1 ) + f 2 ( x 2 ) + y T ( A 1 x 1 + A 2 x 2 − b ) L_{\rho}(x_1,x_2,y)=f_1(x_1)+f_2(x_2)+y^T(A_1x_1+A_2x_2-b) Lρ(x1,x2,y)=f1(x1)+f2(x2)+yT(A1x1+A2x2b)
x 1 ∗ , x 2 ∗ x_1^*,x_2^* x1,x2为问题(1)的最优解, y ∗ y* y为对应的拉格朗日橙子,则以下条件满足:
0 ∈ ∂ x 1 L ( x 1 ∗ , x 2 ∗ , y ∗ ) = ∂ f 1 ( x 1 ∗ ) + A 1 T y ∗ , (8a) 0\in\partial_{x_1}L(x_1^*,x_2^*,y^*)=\partial f_1(x_1^*)+A_1^Ty^*,\tag{8a} 0x1L(x1,x2,y)=f1(x1)+A1Ty,(8a)
0 ∈ ∂ x 2 L ( x 1 ∗ , x 2 ∗ , y ∗ ) = ∂ f 2 ( x 2 ∗ ) + A 2 T y ∗ , (8b) 0\in\partial_{x_2}L(x_1^*,x_2^*,y^*)=\partial f_2(x_2^*)+A_2^Ty^*,\tag{8b} 0x2L(x1,x2,y)=f2(x2)+A2Ty,(8b)
A 1 x 1 ∗ + A 2 x 2 ∗ = b . (8c) A_1x_1^*+A_2x_2^*=b.\tag{8c} A1x1+A2x2=b.(8c)
在这里条件(8c)又称为原始可行条件,条件(8a)和条件(8b)又称为对偶可行性条件。由于问题中只含等式约束,KKT条件中的互补松弛条件可以不考虑。在ADMM迭代中,我们得到的迭代点实际为 ( x 1 k , x 2 k , y k ) (x_1^k,x_2^k,y^k) (x1k,x2k,yk),因此收敛准则应当针对 ( x 1 k , x 2 k , y k ) (x_1^k,x_2^k,y^k) (x1k,x2k,yk)检测条件(8).

二、Douglas-Rachford Splitting算法
Douglas-Rachford Splitting(DRS)算法时一类非常重要的算子分裂算法。它可以用于求解下面的无约束优化问题:
min ⁡ x ψ ( x ) = f ( x ) + h ( x ) (9) \min_x\psi(x)=f(x)+h(x) \tag{9} xminψ(x)=f(x)+h(x)(9)
其中 f f f h h h时闭凸函数。DRS算法的迭代格式为
x k + 1 = p r o x t h ( z k ) , y k + 1 = p r o x t f ( 2 x k + 1 − z k ) , z k + 1 = z k + y k + 1 − x k + 1 \begin{aligned} x^{k+1}&=prox_{th}(z^k),\\ y^{k+1}&=prox_{tf}(2x^{k+1}-z^k),\\ z^{k+1}&=z^k+y^{k+1}-x^{k+1} \end{aligned} xk+1yk+1zk+1=proxth(zk),=proxtf(2xk+1zk),=zk+yk+1xk+1
其中t时一个正的常数,我们还可以通过一系列变形来得到DRS格式的等价迭代。首先在原始DRS格式中按照 y , z , x y,z,x y,z,x的顺序更新,则有
y k + 1 = p r o x t f ( 2 x k − z k ) , z k + 1 = z k + y k + 1 − x k , x k + 1 = p r o x t h ( z k + 1 ) . \begin{aligned} y^{k+1}&=prox_{tf}(2x^{k}-z^k),\\ z^{k+1}&=z^k+y^{k+1}-x^{k},\\ x^{k+1}&=prox_{th}(z^{k+1}).\\ \end{aligned} yk+1zk+1xk+1=proxtf(2xkzk),=zk+yk+1xk,=proxth(zk+1).
引入辅助变量 ω k = z k − x k \omega^k=z^k-x^k ωk=zkxk,并注意到上面迭代中变量 z k , z k + 1 z^k,z^{k+1} zk,zk+1可以小区,则得到DRS算法的等价迭代格式:
y k + 1 = p r o x t f ( x k − ω k ) , x k + 1 = p r o x t h ( ω k + y k + 1 ) , ω k + 1 = ω k + y k + 1 − x k + 1 . \begin{aligned} y^{k+1}&=prox_{tf}(x^{k}-\omega^k),\\ x^{k+1}&=prox_{th}(\omega^k+y^{k+1}),\\ \omega^{k+1}&=\omega^k+y^{k+1}-x^{k+1}.\\ \end{aligned} yk+1xk+1ωk+1=proxtf(xkωk),=proxth(ωk+yk+1),=ωk+yk+1xk+1.

三、常见的变形和技巧
本小节将给出交替方向乘子法的一些变形以及实现交替方向乘子法的一些技巧。

  1. 线性化
    我们构造ADMM的初衷时将自变量拆分,最终使得关于 x 1 x_1 x1 x 2 x_2 x2的子问题有显示解。但是实际应用中,有时子问题并不容易求解,或者没必要精确求解。那么如何寻找子问题的一个近似呢?
    不失一般性,我们考虑第一个子问题,即
    min ⁡ x 1 f 1 ( x 1 ) + ρ 2 ∣ ∣ A 1 x 1 − v k ∣ ∣ 2 , (10) \min_{x_1} f_1(x_1)+\frac{\rho}{2}||A_1x_1-v^k||^2,\tag{10} x1minf1(x1)+2ρ∣∣A1x1vk2,(10)
    其中
    v k = b − A 2 x 2 k − 1 ρ y k . (11) v^k=b-A_2x_2^k-\frac{1}{\rho}y^k.\tag{11} vk=bA2x2kρ1yk.(11)
    当子问题不能显示求解时,可采用线性化的方法近似求解问题(9).线性化技巧实际上时使用近似点项对子问题目标函数吉星二次近似。当子问题目标函数可微时,线性化可见问题(9)变为:
    x 1 k + 1 = a r g min ⁡ x 1 { ( ∇ f 1 ( x 1 k ) ) + ρ ( A 1 T ( A 1 x 1 k − v k ) ) T x 1 + 1 2 η k ∣ ∣ x 1 − x k ∣ ∣ 2 2 } , x_1^{k+1}=arg\min_{x_1}\{(\nabla f_1(x_1^k))+\rho (A_1^T(A_1x_1^k-v^k))^Tx_1+\frac{1}{2\eta_k}||x_1-x^k||_2^2\}, x1k+1=argx1min{(f1(x1k))+ρA1T(A1x1kvk)Tx1+2ηk1∣∣x1xk22},
    其中 η k \eta_k ηk是步长参数,这等价于做一步梯度下降。当目标函数不可微时,可以考虑之间二次项线性化,即
    x 1 k + 1 = a r g min ⁡ x 1 { f ( x 1 ) + ρ ( A 1 T ( A 1 x 1 k − v k ) ) T x 1 + 1 2 η k ∣ ∣ x 1 − x k ∣ ∣ 2 2 } , x_1^{k+1}=arg\min_{x_1}\{f(x_1)+\rho (A_1^T(A_1x_1^k-v^k))^Tx_1+\frac{1}{2\eta_k}||x_1-x^k||_2^2\}, x1k+1=argx1min{f(x1)+ρA1T(A1x1kvk)Tx1+2ηk1∣∣x1xk22},
    这等价于求解子问题(9)时做一步近似点梯度步。当然,若 f 1 ( x 1 ) f_1(x_1) f1(x1)时可微函数与不可微函数的和时,也可将其可微部分线性化。

  2. 缓存分解
    如果目标函数中含二次函数,例如 f 1 ( x 1 ) = 1 2 ∣ ∣ C x 1 − d ∣ ∣ 2 2 f_1(x_1)=\frac{1}{2}||Cx_1-d||_2^2 f1(x1)=21∣∣Cx1d22,那么针对 x 1 x_1 x1的更新等价于求解线性方程组
    ( C T C + ρ A 1 T A 1 ) x 1 = C T d + ρ A 1 T v k , (C^TC+\rho A_1^TA_1)x_1=C^Td+\rho A_1^Tv^k, (CTC+ρA1TA1)x1=CTd+ρA1Tvk,
    其中 v k v^k vk的定义如(11)式。虽然子问题有显示解,但是每部求解的复杂度仍然比较高,这个时候可以考虑用缓存分解的方法。首先对 C T C + ρ A 1 T A 1 C^TC+\rho A_1^TA_1 CTC+ρA1TA1进行Cholesky分解并缓存分解的结果,在每步迭代中只需要求解简单的三角形方程组;当 ρ \rho ρ发生更新时,就要重新进行分解。特别地,当 C T C + ρ A 1 T A 1 C^TC+\rho A_1^TA_1 CTC+ρA1TA1一部分容易求逆,另一部分时低秩的情形,可以用SMW公式来求逆。

  3. 优化转移
    有时候为了方便求解子问题,可以用一个性质郝的矩阵D近似二次项 A 1 T A 1 A_1^TA_1 A1TA1,此时子问题(10)替换为
    x 1 k + 1 = a r g min ⁡ x 1 { f 1 ( x 1 ) + ρ 2 ∣ ∣ A 1 x 1 − v k ∣ ∣ 2 2 + ρ 2 ( x 1 − x k ) T ( D − A 1 T A 1 ) ( x 1 − x k ) } , x_1^{k+1}=arg\min_{x_1}\{f_1(x_1)+\frac{\rho}{2}||A_1x_1-v^k||_2^2+\frac{\rho}{2}(x_1-x^k)^T(D-A_1^TA_1)(x_1-x^k)\}, x1k+1=argx1min{f1(x1)+2ρ∣∣A1x1vk22+2ρ(x1xk)T(DA1TA1)(x1xk)},
    其中 v k v^k vk的定义如(11)式,这种方法也称为优化转移。通过选取合适的D,当计算 a r g min ⁡ x 1 { f 1 ( x 1 ) + 2 ρ x 1 T D x 1 } arg\min_{x_1}\{f_1(x_1)+\frac{2}{\rho}x_1^TDx_1\} argminx1{f1(x1)+ρ2x1TDx1}明显比计算 a r g min ⁡ x 1 { f 1 ( x 1 ) + 2 ρ x 1 T A 1 T A 1 x 1 } arg\min_{x_1}\{f_1(x_1)+\frac{2}{\rho}x_1^TA_1^TA_1x_1\} argminx1{f1(x1)+ρ2x1TA1TA1x1}要容易时,优化转移可以极大地简化子问题地计算。特别地,当 D = η k ρ I D=\frac{\eta_k}{\rho}I D=ρηkI时,优化转移等价于做但不地近似点梯度。

  4. 二次惩罚项系数地动态调节
    动态调节二次惩罚项系数在交替方向乘子法地实际应用中时非常重要地数值技巧。在介绍ADMM时我们引入了原始可行性和对偶可行性。在实际求解过程中,二次惩罚项系数 ρ \rho ρ太大会导致原始可行性下降很快,但是对偶可行性下降很慢;二次惩罚项系数太小,则会有相反地效果。这样都会导致收敛比较慢或得到地解可行性很差。一个自然地想法是在每次迭代时动态调节惩罚系数 ρ \rho ρ地大小,从而使得原始可行性和对偶可行性能够以比较一致地速度下降到零。这种做法通常可以改善算法在实际中地收敛效果,以及使算法表现更少地依赖于惩罚系数地初始选择。一个简单有效地方式是令
    ρ k + 1 = { γ p ρ k , ∣ ∣ r k ∣ ∣ > μ ∣ ∣ s k ∣ ∣ , ρ k γ d , ∣ ∣ s k ∣ ∣ > μ ∣ ∣ r k ∣ ∣ , ρ k , o t h e r w i s e \rho^{k+1}=\left\{ \begin{aligned} &\gamma_p\rho^k,&||r^k||>\mu||s^k||,\\ &\frac{\rho^k}{\gamma^d},&||s^k||>\mu||r^k||,\\ &\rho^k,&otherwise \end{aligned} \right. ρk+1= γpρk,γdρk,ρk,∣∣rk∣∣>μ∣∣sk∣∣,∣∣sk∣∣>μ∣∣rk∣∣,otherwise
    其中 μ > 1 , γ p > 1 , γ d > 1 \mu>1,\gamma_p>1,\gamma_d>1 μ>1,γp>1,γd>1是参数,常见地选择为 μ = 10 , γ p = γ d = 2 \mu=10,\gamma_p=\gamma_d=2 μ=10,γp=γd=2。该惩罚参数更新方式背后地想法是在迭代过程中,将原始可行性和对偶可行性保持在彼此地 μ \mu μ倍以内。如果原始可行性或对偶可行性下降过慢就应该相应增加或减小二次惩罚项系数 ρ k \rho^k ρk。但在改变 ρ k \rho^k ρk地时候需要注意,若之前利用了缓存分解地技巧,此时分解需要重新计算。更一般地,我们可以考虑对每一个约束给一个不同地惩罚系数,审制可以将增广拉格朗日函数中地二次项 ρ 2 ∣ ∣ r ∣ ∣ 2 \frac{\rho}{2}||r||^2 2ρ∣∣r2替换为 ρ 2 r T P r \frac{\rho}{2}r^TPr 2ρrTPr,其中P是一个对称镇定矩阵。如果P在郑哥迭代过程中是不变地,我们可以将这个一般地交替方向乘子法解释为标准地交替方向乘子法应用在修改后地初始问题上-----等式约束 A 1 x 1 + A 2 x 2 − b = 0 A_1x_1+A_2x_2-b=0 A1x1+A2x2b=0替换为 F ( A 1 x 1 + A 2 x 2 − b ) = 0 F(A_1x_1+A_2x_2-b)=0 F(A1x1+A2x2b)=0,其中F为P地Cholesky因子,即 P = F T F P=F^TF P=FTF,且F是对角元为正树地上三角矩阵。

  5. 超松弛
    另外一种想法是用超松弛地技巧,在(6)式与(7)式中, A 1 x 1 k + 1 A_1x_1^{k+1} A1x1k+1可以被替换为
    α k A 1 x 1 k + 1 − ( 1 − α k ) ( A 2 x 2 k − b ) , \alpha_kA_1x_1^{k+1}-(1-\alpha_k)(A_2x_2^k-b), αkA1x1k+1(1αk)(A2x2kb),
    其中 α k ∈ ( 0 , 2 ) \alpha_k\in(0,2) αk(0,2)是一个松弛参数。但 α k > 1 \alpha_k>1 αk>1时,这种技巧称为超松弛;但 α k < 1 \alpha_k<1 αk<1时,这种技巧称为欠松弛。实验表明 α k ∈ [ 1.5 , 1.8 ] \alpha_k\in[1.5,1.8] αk[1.5,1.8]地超松弛可以提高收敛速度。

交替方向乘子法(admm)文章来源地址https://www.toymoban.com/news/detail-403677.html

到了这里,关于交替方向乘子法(admm)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【图像恢复】基于交替乘子方法(ADMM)图像恢复算法研究[固定点收敛和应用](Matlab代码实现)

    💥💥💞💞 欢迎来到本博客 ❤️❤️💥💥 🏆博主优势: 🌞🌞🌞 博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️ 座右铭: 行百里者,半于九十。 📋📋📋 本文目录如下: 🎁🎁🎁 目录 💥1 概述 📚2 运行结果 🎉3 参考文献 🌈4 Matlab代码、数据、文献

    2024年02月13日
    浏览(55)
  • 统计学学习笔记:L1-总体、样本、均值、方差

    目录 一、总体和样本 二、集中趋势分析 2.1 均值 2.1.1 样本均值 2.1.2 总体均值 2.2 众数,中位数 三、离散趋势分析 3.1 总体方差 3.2 样本方差 3.3 标准差 比如要计算全国男性的平均身高,但是全部调查是不现实的,所有要采取抽样调查,随机抽取一部分男性的身高,全国男性身

    2024年02月12日
    浏览(41)
  • 统计学 - 数理统计与应用统计的区别

    目录 1. 概率与统计 2. 数理统计与应用统计 概率论是研究随机现象数量规律的数学分支。随机现象是相对于决定性现象而言的,在一定条件下必然发生某一结果的现象称为决定性现象。例如在标准大气压,纯水加热到100℃时水必然会沸腾等。随机现象则是指在基本条件不变的

    2024年02月13日
    浏览(48)
  • 《SPSS统计学基础与实证研究应用精解》视频讲解:SPSS依托统计学处理数据的应用场景

    《SPSS统计学基础与实证研究应用精解》1.4 视频讲解 视频为 《SPSS统计学基础与实证研究应用精解》张甜 杨维忠著 清华大学出版社 一书的随书赠送视频讲解1.4节内容 。本书已正式出版上市,当当、京东、淘宝等平台热销中,搜索书名即可。本书旨在手把手教会使用SPSS撰写实

    2024年01月23日
    浏览(51)
  • 统计学 一元线性回归

    回归(Regression) :假定因变量与自变量之间有某种关系,并把这种关系用适当的数学模型表达出来,利用该模型根据给定的自变量来预测因变量 线性回归 :因变量和自变量之间是线性关系 非线性回归 :因变量和自变量之间是非线性关系 变量间的关系 :往往分为 函数关系

    2024年02月06日
    浏览(41)
  • 【应用统计学】方差分析

    【例7-1】 三台设备平均灌装时间分别是15.82秒、16.67秒和14.97秒。试用样本数据检验这3台机器灌装过程的时间是否存在显著不同,以便对设备的购买做出决策。( α=0.05 )  如果检验结果 接受原假设 ,则样本数据表明三台设备的平均灌装时间没有显著差异,选择任何一家提供商

    2023年04月16日
    浏览(42)
  • 统计学期末复习整理

    统计学:描述统计学和推断统计学。计量尺度:定类尺度、定序尺度、定距尺度、定比尺度。 描述统计中的测度: 1.数据分布的集中趋势 2.数据分布的离散程度 3.数据分布的形状。 离散系数 也称为标准差系数,通常是用一组数据的标准差与其平均数之比计算 C . V . = s x ‾

    2024年02月07日
    浏览(43)
  • 数据科学、统计学、商业分析

    数据科学、统计学、商业分析是在各方面有着不同的侧重和方向的领域。  1.专业技能 数据科学(Data Science):数据科学涉及从大量数据中提取有价值的信息、模式和洞察力的领域。它使用多种技术和领域知识,如统计学、机器学习、数据库管理、数据可视化等,进行数据清

    2024年02月15日
    浏览(49)
  • SCAU 统计学 实验5

    8.14 总体平均值(μ):7.0 cm 总体方差(σ²):0.03 cm² 样本平均值(x̄):6.97 cm 样本方差(s²):0.0375 cm² 样本大小(n):80 在这个问题中,我们已经知道总体方差(σ²),所以应该使用 z 检验。 将检验以下零假设(H₀): H₀: μ = 7.0 cm 与备择假设(H₁): H₁: μ ≠

    2024年02月01日
    浏览(39)
  • 统计学-R语言-3

    本篇文章是介绍对数据的部分图形可视化的图型展现。 需要注意的是,给直方图拟合正态分布曲线并非总是适用,有时甚至是荒谬的,容易产生误导。合理的做法是为直方图拟合一条核密度估计曲线,它是数据实际分布的一种近似描述。 下面通过一个实际例子说明给直方图

    2024年01月16日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包