当前位置:   article > 正文

一篇论文复现的整体思路和复现记录(二,算法篇)_复现算例

复现算例

以下内容摘自北京大学文再文老师的《最优化:建模、算法与理论》课件

典型问题形式

考虑以下凸问题:
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)

minx1,x2f1(x1)+f2(x2)s.t.A1x1+A2x2=b
\tag{1} x1,x2mins.t.f1(x1)+f2(x2)A1x1+A2x2=b(1)
要求 f 1 f_1 f1, f 2 f_2 f2是适当的闭凸函数,但不要求是光滑的。 x 1 ∈ R n x_1\in\mathbb{R}^n x1Rn, x 2 ∈ R m x_2\in\mathbb{R}^m x2Rm, A 1 ∈ R p × n A_1\in\mathbb{R}^{p\times n} A1Rp×n, A 2 ∈ R p × m A_2\in\mathbb{R}^{p\times m} A2Rp×m, b ∈ R p b\in\mathbb{R}^{p} bRp
问题的特点在于目标函数可以分为彼此分离的两块。但是变量都被线性约束结合在一起。常见的一些无约束和带约束的问题可以表现为这一形式。

1

可以分为两块的无约束优化问题:
min ⁡ x f 1 ( x ) + f 2 ( x ) \min\limits_x\quad f_1(x)+f_2(x) xminf1(x)+f2(x)
引入新的变量 z z z,令 x = z x=z x=z, 将问题转换为:
min ⁡ x , z f 1 ( x ) + f 2 ( z ) s . t . x − z = 0

minx,zf1(x)+f2(z)s.t.xz=0
x,zmins.t.f1(x)+f2(z)xz=0

2

带线性变换的无约束优化问题:
min ⁡ x f 1 ( x ) + f 2 ( A x ) \min\limits_x\quad 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

minx,zf1(x)+f2(z)s.t.Axz=0
x,zmins.t.f1(x)+f2(z)Axz=0

3

凸集 C ⊂ R n C\subset\mathbb{R}^n CRn上的约束优化问题
min ⁡ x f ( x ) s . t . A x ∈ C

minxf(x)s.t.AxC
xmins.t.f(x)AxC
I C ( z ) I_C(z) IC(z)是集合 C C C的示性函数,引入约束 z = A x z=Ax z=Ax,则问题转化为:
min ⁡ x , z f ( x ) + I C ( z ) s . t . A x − z = 0
minx,zf(x)+IC(z)s.t.Axz=0
x,zmins.t.f(x)+IC(z)Axz=0

(Here is a problem: 示性函数是什么东西)

4

全局一致性问题
min ⁡ x ∑ i = 1 N ϕ i ( x ) \min\limits_x\quad\sum_{i=1}^N\phi_i(x) xmini=1Nϕi(x)
x = z x=z x=z,并将x复制 N N N份,分别为 x i x_i xi, 那么问题转换为:
min ⁡ x , z ∑ i = 1 N ϕ i ( x i ) s . t . x i − z = 0

minx,zi=1Nϕi(xi)s.t.xiz=0
x,zmins.t.i=1Nϕi(xi)xiz=0

这个例4和文章中所显示的形式上比较相似。

增广拉格朗日函数法和交替方向乘子法(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ρ(x1,x2,y)=f1(x1)+f2(x2)+yT(A1x1+A2x2b)+ρ2A1x1+A2x2b22
\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 ) , y k + 1 = y k + τ ρ ( A 1 x 1 k + 1 + A 2 x 2 k + 1 − b )

(3)(x1k+1,x2k+1)=argminx1,x2Lρ(x1,x2,yk),(4)yk+1=yk+τρ(A1x1k+1+A2x2k+1b)
(x1k+1,x2k+1)yk+1=x1,x2argminLρ(x1,x2,yk),=yk+τρ(A1x1k+1+A2x2k+1b)(3)(4)

交替方向乘子法: Alternating direction method of multipliers, ADMM

交替方向乘子法的基本思路:

第一步迭代(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 m i n x 1 L ρ ( x 1 , x 2 k , y k ) x 2 k + 1 = a r g m i n x 1 L ρ ( x 1 k + 1 , x 2 , y k ) y k + 1 = y k + τ ρ ( A 1 x 1 k + 1 + A 2 x 2 k + 1 − b )

(5)x1k+1=argminx1Lρ(x1,x2k,yk)(6)x2k+1=argminx1Lρ(x1k+1,x2,yk)(7)yk+1=yk+τρ(A1x1k+1+A2x2k+1b)
x1k+1x2k+1yk+1=x1argminLρ(x1,x2k,yk)=x1argminLρ(x1k+1,x2,yk)=yk+τρ(A1x1k+1+A2x2k+1b)(5)(6)(7)

其中, τ \tau τ为步长,其取值范围通常为 ( 0 , 1 + 5 2 ] (0,\frac{1+\sqrt{5}}{2}] (0,21+5 ]

原问题最优性条件

因为 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(x1,x2,y)=f1(x1)+f2(x2)+yT(A1x1+A2x2b)
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 ∗ , 0 ∈ ∂ x 2 L ( x 1 ∗ , x 2 ∗ , y ∗ ) = ∂ f 2 ( x 2 ∗ ) + A 2 T y ∗ , A 1 x 1 ∗ + A 2 x 2 ∗ = b
(8a)0x1L(x1,x2,y)=f1(x1)+A1Ty,(8b)0x2L(x1,x2,y)=f2(x2)+A2Ty,(8c)A1x1+A2x2=b
0x1L(x1,x2,y)0x2L(x1,x2,y)A1x1+A2x2=f1(x1)+A1Ty,=f2(x2)+A2Ty,=b(8a)(8b)(8c)

其中,前两者成为原始可行性条件,后两者称为对偶可行性条件。

ADMM单步迭代最优性条件

x 2 x_2 x2的更新步骤:
x 2 k = a r g m i n x f 2 ( x ) + ρ 2 ∥ A 1 x 1 k + A 2 x − b + y k − 1 ρ ∥ 2

x2k=argminxf2(x)+ρ2A1x1k+A2xb+yk1ρ2
x2k=xargminf2(x)+2ρA1x1k+A2xb+ρyk12
根据最优性条件不难推出,
0 ∈ ∂ f 2 ( x 2 k ) + A 2 T [ y k − 1 + ρ ( A 1 x 1 k + A 2 x 2 k − b ) ] (9)
0f2(x2k)+A2T[yk1+ρ(A1x1k+A2x2kb)]
\tag{9}
0f2(x2k)+A2T[yk1+ρ(A1x1k+A2x2kb)](9)

τ = 1 \tau=1 τ=1时候,根据(7)可知上式方括号中的表达式就是 y k y^k yk,最终有:
0 ∈ ∂ f 2 ( x 2 k ) + A 2 T y k
0f2(x2k)+A2Tyk
0f2(x2k)+A2Tyk

x 1 x_1 x1的更新公式
x 1 k = a r g m i n x { f 1 ( x ) + ρ 2 ∥ A 1 x + A 2 x 2 k − 1 − b + y k − 1 ρ ∥ 2 }
x1k=argminx{f1(x)+ρ2A1x+A2x2k1b+yk1ρ2}
x1k=xargmin{f1(x)+2ρA1x+A2x2k1b+ρyk12}

假设子问题能够精确求解,根据最优性条件,
0 ∈ ∂ f 1 ( x 1 k ) + A 1 T [ ρ ( A 1 x 1 k + A 2 x 2 k − 1 − b ) + y k − 1 ]
0f1(x1k)+A1T[ρ(A1x1k+A2x2k1b)+yk1]
0f1(x1k)+A1T[ρ(A1x1k+A2x2k1b)+yk1]

根据ADMM的第三式(7)取 τ = 1 \tau=1 τ=1
0 ∈ ∂ f 1 ( x 1 k ) + A 1 T ( y k + ρ A 2 ( x 2 k − 1 − x 2 k ) ) (10)
0f1(x1k)+A1T(yk+ρA2(x2k1x2k)
\tag{10}
0f1(x1k)+A1T(yk+ρA2(x2k1x2k)(10)

对比(8a)可知多出来的项为 A 1 T A 2 ( x 2 k − 1 − x 2 k ) A_1^TA_2(x_2^{k-1}-x_2^k) A1TA2(x2k1x2k)。因此要检测对偶可行性只需要检测残差
s k = A 1 T A 2 ( x 2 k − 1 − x 2 k ) s^k = A^T_1A_2(x_2^{k-1}-x_2^k) sk=A1TA2(x2k1x2k)
综上,当 x 2 x_2 x2更新取到精确解且 τ = 1 \tau=1 τ=1时候,判断ADMM收敛只需要检测前述两个残差 r k , s k r^k, s^k rk,sk是否充分小:
0 ≈ ∣ ∣ r k ∣ ∣ = ∥ A 1 x 1 k + A 2 x 2 k − b ∥ 原始可行性 0 ≈ ∣ ∣ s k ∣ ∣ = ∥ A 1 T A 2 ( x 2 k − 1 − x 2 k ) ∥ 对偶可行性 (11)
0||rk||=A1x1k+A2x2kb0||sk||=A1TA2(x2k1x2k)
\tag{11}
0∣∣rk∣∣=A1x1k+A2x2kb原始可行性0∣∣sk∣∣=A1TA2(x2k1x2k)对偶可行性(11)

常见问题和技巧

线性化

线性化技巧使用近似点项对子问题目标函数进行二次近似。
不失一般性,我们考虑第一个子问题,即:
min ⁡ x 1 f 1 ( x 1 ) + ρ 2 ∥ A 1 x 1 − v k ∥ 2 (12)

minx1f1(x1)+ρ2A1x1vk2
\tag{12} x1minf1(x1)+2ρA1x1vk2(12)
其中: v k = b − A 2 x 2 k − 1 ρ y k v^k = b-A_2x_2^k-\frac{1}{\rho}y^k vk=bA2x2kρ1yk
当子问题目标函数可微的时候,线性化将问题(12)变为:
x 1 k + 1 = a r g m i n 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 2 2 ∥ 2 2
x1k+1=argminx1(f1(x1k)+ρA1T(A1x1kvk))Tx1+12ηkx1x2222
x1k+1=x1argmin(f1(x1k)+ρA1T(A1x1kvk))Tx1+2ηk1x1x2222

其中, η k \eta_k ηk是步长参数,这等价于做一步梯度下降。
当目标函数不可微的时候,可以考虑只将二次项线性化,即:
x 1 k + 1 = a r g m i n 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 2 2 ∥ 2 2
x1k+1=argminx1(f1(x1k)+ρA1T(A1x1kvk))Tx1+12ηkx1x2222
x1k+1=x1argmin(f1(x1k)+ρA1T(A1x1kvk))Tx1+2ηk1x1x2222

这等价于做一步近似点梯度步。

缓存分解

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

优化转移

有时候为了方便求解子问题,可以用一个性质好的矩阵 D D D近似二次项 A 1 T A 1 A_1^TA_1 A1TA1,此时子问题(12)替换为
x 1 k + 1 = a r g m i n x 1 f 1 ( x 1 ) + ρ 2 ∥ A 1 x 1 − v k ∥ 2 + ρ 2 ( x 1 − x k ) T ( D − A 1 T A 1 ) ( x 1 − x k ) x_1^{k+1} = \mathop{argmin}\limits_{x_1}{f_1(x_1)+\frac{\rho}{2}{\Vert{A_1x_1-v^k}\Vert}^2 +\frac{\rho}{2}(x_1-x^k)^T(D-A_1^TA_1)(x_1-x^k)} x1k+1=x1argminf1(x1)+2ρA1x1vk2+2ρ(x1xk)T(DA1TA1)(x1xk)
这种方法也被称为优化转移。
通过选取合适的 D D D,当计算 a r g m i n x 1 { f 1 ( x 1 ) + ρ 2 x 1 T D x 1 } \mathop{argmin}\limits_{x_1}\{f_1(x_1)+\frac{\rho}{2}x_1^TDx_1\} x1argmin{f1(x1)+2ρx1TDx1}明显比计算 a r g m i n x 1 { f 1 ( x 1 ) + ρ 2 x 1 T A 1 T A 1 x 1 } \mathop{argmin}\limits_{x_1}\{f_1(x_1)+\frac{\rho}{2}x_1^TA_1TA_1x_1\} x1argmin{f1(x1)+2ρx1TA1TA1x1}要容易的时候,优化转移可以极大地简化子问题的计算。特别地,当 D = η k ρ I D=\frac{\eta_k}{\rho}I D=ρηkI时,优化转移等价于做单步的近似点梯度步。

二次罚项系数的动态调节

原始可行性和对偶可行性分别用 ∥ r k ∥ \Vert r^k\Vert rk ∥ s k ∥ \Vert s^k\Vert sk度量。

求解过程中二次罚项系数 ρ \rho ρ太大会导致原始可行性 ∥ r k ∥ \Vert r^k\Vert rk下降很快,但是对偶可行性 ∥ s k ∥ \Vert s^k\Vert sk下降很慢;二次罚项系数太小,则会有相反的效果,这样都会导致收敛比较慢或者得到的解的可行性很差。
一个自然的想法是在每次迭代的时候动态调节惩罚系数 ρ \rho ρ的大小,从而使得原始可行性和对偶可行行能够以比较一致的速度下降到0.一个简单有效的方式是令
ρ k + 1 = { γ p ρ k , ∥ r k ∥ > μ ∥ s k ∥ ρ k γ p , ∥ s k ∥ > μ ∥ r k ∥ ρ k , 其他 \rho^{k+1} =

{γpρk,rk>μskρkγp,sk>μrkρk,
ρk+1= γpρk,γpρk,ρk,rk>μsksk>μrk其他
其中, μ > 1 \mu>1 μ>1, γ p > 1 \gamma_p>1 γp>1, γ d > 1 \gamma_d>1 γd>1是参数,常见的选择
μ = 10 , γ p = γ d = 2 \mu=10, \gamma_p=\gamma_d=2 μ=10,γp=γd=2.在迭代过长中将原始可行性 ∣ ∣ r k ∣ ∣ ||r^k|| ∣∣rk∣∣和对偶可行性 ∣ ∣ s k ∣ ∣ ||s^k|| ∣∣sk∣∣保持在彼此的 μ \mu μ倍内,如果发现 ∣ ∣ r k ∣ ∣ ||r^k|| ∣∣rk∣∣ ∣ ∣ s k ∣ ∣ ||s^k|| ∣∣sk∣∣下降过慢就应该相应增大或者减小二次罚项系数 ρ k \rho^k ρk.

多块问题的ADMM

考虑有多块变量的情形
min ⁡ x 1 , x 2 , … , x N f 1 ( x 1 ) + f 2 ( x 2 ) + ⋯ + f N ( x N ) , s . t . A 1 x 1 + A 2 x 2 + ⋯ + A N x N = b . (13)

minx1,x2,,xNf1(x1)+f2(x2)++fN(xN),s.t.A1x1+A2x2++ANxN=b.
\tag{13} x1,x2,,xNmins.t.f1(x1)+f2(x2)++fN(xN),A1x1+A2x2++ANxN=b.(13)
这里, f i ( x i ) f_i(x_i) fi(xi)是闭函数, x i ∈ R n i x_i\in \mathbb{R}^{n_i} xiRni, A i ∈ R m × n i A_i\in \mathbb{R}^{m\times n_i} AiRm×ni
同样写出增广拉格朗日函数 L ρ ( x 1 , x 2 , … , x N , y ) L_{\rho}(x_1, x_2, \dots, x_N, y) Lρ(x1,x2,,xN,y),相应的多块ADMM迭代格式为
x 1 k + 1 = a r g m i n x 1 L ρ ( x , x 2 k , … , x N k , y k ) x 2 k + 1 = a r g m i n x 1 L ρ ( x 1 k + 1 , x , … , x N k , y k ) … x N k + 1 = a r g m i n x 1 L ρ ( x 1 k + 1 , x 2 k + 1 , … , x N , y k ) y k + 1 = y k + τ ρ ( A 1 x 1 k + 1 + A 2 x 2 k + 1 + ⋯ + A N x N k + 1 − b )
x1k+1=argminx1Lρ(x,x2k,,xNk,yk)x2k+1=argminx1Lρ(x1k+1,x,,xNk,yk)xNk+1=argminx1Lρ(x1k+1,x2k+1,,xN,yk)yk+1=yk+τρ(A1x1k+1+A2x2k+1++ANxNk+1b)
x1k+1x2k+1xNk+1yk+1=x1argminLρ(x,x2k,,xNk,yk)=x1argminLρ(x1k+1,x,,xNk,yk)=x1argminLρ(x1k+1,x2k+1,,xN,yk)=yk+τρ(A1x1k+1+A2x2k+1++ANxNk+1b)

其中, τ ∈ ( 0 , 5 + 1 2 ) \tau\in(0, \frac{\sqrt{5}+1}{2}) τ(0,25 +1)为步长参数。

应用举例

限于篇幅和内容需要,部分应用举例已折叠。

Lasso 问题的Primal形式

Lasso 问题的对偶形式

广义Lasso问题

半定规划问题

ADMM求解半定规划问题

稀疏逆协方差矩阵估计

矩阵分离问题

图像去噪模型

全变差去模糊方法

ADMM 求解图像去模糊问题及实例

全局一致性优化问题

原问题为:
min ⁡ x i , z ∑ i = 1 N ϕ i ( x i ) , s . t . x i − z = 0 , i = 1 , 2 , … , N .

minxi,zi=1Nϕi(xi),s.t.xiz=0,i=1,2,,N.
xi,zmins.t.i=1Nϕi(xi),xiz=0,i=1,2,,N.
增广拉格朗日函数:
L ( x 1 , … , x N , z , y 1 , … , y N ) = ∑ i = 1 N ϕ i ( x i ) + ∑ i = 1 N y i T ( x i − z ) + ρ 2 ∑ i = 1 N ∥ x i − z ∥ 2 L(x_1,\dots, x_N, z, y_1,\dots, y_N) = \sum_{i=1}^N\phi_i(x_i) +\sum_{i=1}^N y_i^T(x_i-z)+\frac{\rho}{2}\sum_{i=1}^N{\Vert x_i-z\Vert}^2 L(x1,,xN,z,y1,,yN)=i=1Nϕi(xi)+i=1NyiT(xiz)+2ρi=1Nxiz2
固定 z k z^k zk, y i k y_i^k yik,更新 x i x_i xi的公式为

x i k + 1 = a r g m i n x { ϕ i ( x ) + ρ 2 ∥ x i − z + y i k ρ ∥ 2 } (21)

xik+1=argminx{ϕi(x)+ρ2xiz+yikρ2}
\tag{21} xik+1=xargmin{ϕi(x)+2ρxiz+ρyik2}(21)

注意:虽然表面上看,增广拉格朗日函数有 ( N + 1 ) (N+1) (N+1)个变量块,但本质上还是两个变量块,这是因为在更新某个 x i x_i xi时候并未利用其他 x i x_i xi,所有 x i x_i xi可以看成一个整体。相应地,所有的乘子 y i y_i yi也可以看成一个整体。
迭代式(21)的具体计算依赖于 ψ i \psi_i ψi的形式,在一般情况下,更新 x i x_i xi的表达式为
x i k + 1 = p r o x ϕ i / ρ ( z k − y i k / ρ ) x_i^{k+1}=prox_{\phi_i/\rho}(z^k-y_i^k/\rho) xik+1=proxϕi/ρ(zkyik/ρ)
固定 x i k + 1 x_{i}^{k+1} xik+1, y i k y_i^k yik,问题关于 z z z时二次函数,因此可以直接写出显式解:
z k + 1 = 1 N ∑ i = 1 N ( x i k + 1 + y i k / ρ ) . z^{k+1} = \frac{1}{N}\sum_{i=1}^N(x_i^{k+1}+y_i^k/\rho). zk+1=N1i=1N(xik+1+yik/ρ).
综上,该问题的交替方向乘子法迭代格式为
x i k + 1 = p r o x ϕ i / ρ ( z k − y i k / ρ ) , , i = 1 , 2 , … , N . z k + 1 = 1 N ∑ i = 1 N ( x i k + 1 + y i k / ρ ) . y i k + 1 = y i k + τ ρ ( x i k + 1 − z k + 1 ) , i = 1 , 2 , … , N .

xik+1=proxϕi/ρ(zkyik/ρ),,i=1,2,,N.zk+1=1Ni=1N(xik+1+yik/ρ).yik+1=yik+τρ(xik+1zk+1),i=1,2,,N.
xik+1zk+1yik+1=proxϕi/ρ(zkyik/ρ),,i=1,2,,N.=N1i=1N(xik+1+yik/ρ).=yik+τρ(xik+1zk+1),i=1,2,,N.

与上一篇的关系

因此,在上一篇文章中所提到的
Minimized { − ∑ j = 0 n L j ( x j ) } subject to y − z j = 0 j = 0 , … , n (23)

Minimized{j=0nLj(xj)}subject toyzj=0j=0,,n
\tag{23} Minimizedsubject to{j=0nLj(xj)}yzj=0j=0,,n(23)

应用ADMM解决这一问题:
y k + 1 : = a r g m i n y { ⟨ ∑ j = 0 n p j k , y ⟩ + ρ 2 ∑ j = 0 n ∥ y − z j k ∥ 2 } z j k + 1 : = a r g m i n z j { − L j ( z j ) − ⟨ p j k , z j ⟩ + ρ 2 ∑ j = 0 n ∥ y k + 1 − z j ∥ 2 } p j k + 1 : = p j k + ρ ( y k + 1 − z j k + 1 )

yk+1:=argminy{j=0npjk,y+ρ2j=0nyzjk2}zjk+1:=argminzj{Lj(zj)pjk,zj+ρ2j=0nyk+1zj2}pjk+1:=pjk+ρ(yk+1zjk+1)
yk+1zjk+1pjk+1:=yargmin{⟨j=0npjk,y+2ρj=0nyzjk2}:=zjargmin{Lj(zj)pjk,zj+2ρj=0nyk+1zj2}:=pjk+ρ(yk+1zjk+1)

迭代过程为:
y k + 1 = 1 n + 1 ∑ n + 1 n z j k + − 1 ( n + 1 ) ρ ∑ j = 0 n p j k y^{k+1} = \frac{1}{n+1}\sum_{n+1}^nz_j^k+-\frac{1}{(n+1)\rho}\sum_{j=0}^np_j^k yk+1=n+11n+1nzjk+(n+1)ρ1j=0npjk
{ x i ∗ , i ∈ A j } : = a r g m i n x i ∈ χ i , i ∈ A j { ∑ i ∈ A j g i ( x i ) + ρ 2 ∥ [ m a x { 0 , λ y k + 1 + 1 ρ ( ∑ i ∈ A j ψ i ( x i ) + λ p j k ) } ν y k + 1 + 1 ρ ( ∑ i ∈ A j A i ( x i ) + λ p j k ) ] ∥ 2 }

{xi,iAj}:=argminxiχi,iAj{iAjgi(xi)+ρ2[max{0,λyk+1+1ρ(iAjψi(xi)+λpjk)}νyk+1+1ρ(iAjAi(xi)+λpjk)]2}
{xi,iAj}:=xiχi,iAjargmin iAjgi(xi)+2ρ [max{0,λyk+1+ρ1(iAjψi(xi)+λpjk)}νyk+1+ρ1(iAjAi(xi)+λpjk)] 2
z j = [ λ z j ν z j ] = [ m a x { 0 , λ y k + 1 + 1 ρ ( ∑ i ∈ A j ψ i ( x i ) + λ p j k ) } ν y k + 1 + 1 ρ ( ∑ i ∈ A j A i ( x i ) + λ p j k ) ] z_j = \left[
λzjνzj
\right] = \left[
max{0,λyk+1+1ρ(iAjψi(xi)+λpjk)}νyk+1+1ρ(iAjAi(xi)+λpjk)
\right]
zj=[λzjνzj]=[max{0,λyk+1+ρ1(iAjψi(xi)+λpjk)}νyk+1+ρ1(iAjAi(xi)+λpjk)]

p j k + 1 : = p j k + ρ ( y k + 1 − z j k + 1 )
pjk+1:=pjk+ρ(yk+1zjk+1)
pjk+1:=pjk+ρ(yk+1zjk+1)

可见,复现论文中提到的是具有两个量的ADMM,因此,具体的编程内容,也需要从具有两个量的ADMM展开,这比前面课件提到的内容更为复杂。

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号