ADMM
ADMM简介
- 交替方向乘子法（Alternating Direction Method of Multipliers）通常用于解决存在两个优化变量的只含等式约束的优化类问题，其一般形式为：
min
x
,
z
f
(
x
)
+
g
(
z
)
s
.
t
.
A
x
+
B
z
=
c
\min_{x,z} f(x)+g(z)\\s.t. Ax+Bz=c
minx,zf(x)+g(z)s.t.Ax+Bz=c
- 其中, x ∈ R n , z ∈ R m 是优化变量,等式约束 + 中 A ∈ R p × n , B ∈ R p × m , c ∈ R p 。 f 和 g 都是凸函数 + 。 \begin{aligned}&\text{其中,}x\in R^n,z\in R^m\text{ 是优化变量,等式约束}^+\text{中}A\in R^{p\times n},B\in R^{p\times m},c\in R^p\text{。}f\text{ 和}\\&g\text{ 都是凸函数}^+\text{。}\end{aligned} 其中,x∈Rn,z∈Rm 是优化变量,等式约束+中A∈Rp×n,B∈Rp×m,c∈Rp。f 和g 都是凸函数+。
- ADMM 通过交替求解子问题和更新拉格朗日乘子来
逐步逼近原问题的解。 - 交替方向乘子法被广泛地应用在信号处理、图像处理、机器学习、工程计算等各个领域中，具有收敛速度快，收敛性能好的优势。
增广拉格朗日函数（Augmented Lagrangian）
为解决此类凸优化问题，定义增广拉格朗日函数：
L
ρ
(
x
,
z
,
u
)
=
f
(
x
)
+
g
(
z
)
+
u
T
(
A
x
+
B
z
−
c
)
+
ρ
2
∣
∣
A
x
+
B
z
−
c
∣
∣
2
2
L_\rho(x,z,u)=f(x)+g(z)+u^T(Ax+Bz-c)+\frac\rho2||Ax+Bz-c||_2^2
Lρ(x,z,u)=f(x)+g(z)+uT(Ax+Bz−c)+2ρ∣∣Ax+Bz−c∣∣22
算法流程
每一步只更新一个变量而固定另外两个变量，如此交替重复更新。即，对于 k = 1,2,3,… ，重复如下步骤：
s
t
e
p
1
:
x
(
k
)
=
a
r
g
min
x
L
ρ
(
x
,
z
(
k
−
1
)
,
u
(
k
−
1
)
)
s
t
e
p
2
:
z
(
k
)
=
a
r
g
min
z
L
ρ
(
x
(
k
)
,
z
,
u
(
k
−
1
)
)
s
t
e
p
3
:
u
(
k
)
=
u
(
k
−
1
)
+
ρ
(
A
x
(
k
)
+
B
z
(
k
)
−
c
)
\begin{aligned}&step1:\quad x^{(k)}=arg\min_xL_\rho(x,z^{(k-1)},u^{(k-1)})\\&step2:\quad z^{(k)}=arg\min_zL_\rho(x^{(k)},z,u^{(k-1)})\\&step3:\quad u^{(k)}=u^{(k-1)}+\rho(Ax^{(k)}+Bz^{(k)}-c)\end{aligned}
step1:x(k)=argxminLρ(x,z(k−1),u(k−1))step2:z(k)=argzminLρ(x(k),z,u(k−1))step3:u(k)=u(k−1)+ρ(Ax(k)+Bz(k)−c)
第一步先固定 z 和 u ， L ρ L_\rho Lρ 是只关于 x 的函数，用使得 L ρ L_\rho Lρ 最小的一点来更新 x
第二步固定 u 和更新过的 x， L ρ L_\rho Lρ 是只关于 z 的函数，用使得 L ρ L_\rho Lρ 最小的一点来更新z
第三步用更新过 x 的 z 之来更新 u
不断重复以上三步直到收敛(在不太强的假设前提下，算法可以保证收敛)
为简化形式，如果令 w = u ρ w=\frac u\rho w=ρu,则增广拉格朗日函数可以写成：
L ρ ( x , z , w ) = f ( x ) + g ( z ) + ρ 2 ∣ ∣ A x + B z − c + w ∣ ∣ 2 2 − ρ 2 ∣ ∣ w ∣ ∣ 2 2 L_\rho(x,z,w)=f(x)+g(z)+\frac{\rho}{2}||Ax+Bz-c+w||_2^2-\frac{\rho}{2}||w||_2^2 Lρ(x,z,w)=f(x)+g(z)+2ρ∣∣Ax+Bz−c+w∣∣22−2ρ∣∣w∣∣22
注释：这个等式的成立基于向量的内积和范数的性质。我们可以通过逐步展开和简化来证明这一点。首先，让我们重新审视等式：
ρ w T ( A x + B z − c ) = ρ 2 ( 2 w T ( A x + B z − c ) ) = ρ 2 ( ∣ ∣ A x + B z − c + w ∣ ∣ 2 2 − ∣ ∣ w ∣ ∣ 2 2 − ∣ ∣ A x + B z − c ∣ ∣ 2 2 ) \rho w^T(Ax + Bz - c) = \frac{\rho}{2} (2w^T(Ax + Bz - c)) = \frac{\rho}{2} (||Ax + Bz - c + w||_2^2 - ||w||_2^2 - ||Ax + Bz - c||_2^2) ρwT(Ax+Bz−c)=2ρ(2wT(Ax+Bz−c))=2ρ(∣∣Ax+Bz−c+w∣∣22−∣∣w∣∣22−∣∣Ax+Bz−c∣∣22)
证明步骤
内积与平方差：
我们知道对于任意两个向量 u u u 和 v v v，有以下恒等式：u T v = 1 2 ( ∣ ∣ u + v ∣ ∣ 2 2 − ∣ ∣ u ∣ ∣ 2 2 − ∣ ∣ v ∣ ∣ 2 2 ) u^Tv = \frac{1}{2} (||u + v||_2^2 - ||u||_2^2 - ||v||_2^2) uTv=21(∣∣u+v∣∣22−∣∣u∣∣22−∣∣v∣∣22)
这个恒等式可以通过直接展开 ∣ ∣ u + v ∣ ∣ 2 2 ||u + v||_2^2 ∣∣u+v∣∣22 来验证：
∣ ∣ u + v ∣ ∣ 2 2 = ( u + v ) T ( u + v ) = u T u + 2 u T v + v T v ||u + v||_2^2 = (u + v)^T(u + v) = u^Tu + 2u^Tv + v^Tv ∣∣u+v∣∣22=(u+v)T(u+v)=uTu+2uTv+vTv
= ∣ ∣ u ∣ ∣ 2 2 + 2 u T v + ∣ ∣ v ∣ ∣ 2 2 = ||u||_2^2 + 2u^Tv + ||v||_2^2 =∣∣u∣∣22+2uTv+∣∣v∣∣22因此，
2 u T v = ∣ ∣ u + v ∣ ∣ 2 2 − ∣ ∣ u ∣ ∣ 2 2 − ∣ ∣ v ∣ ∣ 2 2 2u^Tv = ||u + v||_2^2 - ||u||_2^2 - ||v||_2^2 2uTv=∣∣u+v∣∣22−∣∣u∣∣22−∣∣v∣∣22
u T v = 1 2 ( ∣ ∣ u + v ∣ ∣ 2 2 − ∣ ∣ u ∣ ∣ 2 2 − ∣ ∣ v ∣ ∣ 2 2 ) u^Tv = \frac{1}{2} (||u + v||_2^2 - ||u||_2^2 - ||v||_2^2) uTv=21(∣∣u+v∣∣22−∣∣u∣∣22−∣∣v∣∣22)应用到原问题：
在原问题中，令 u = w u = w u=w 和 v = A x + B z − c v = Ax + Bz - c v=Ax+Bz−c，则根据上述恒等式，我们有：w T ( A x + B z − c ) = 1 2 ( ∣ ∣ w + ( A x + B z − c ) ∣ ∣ 2 2 − ∣ ∣ w ∣ ∣ 2 2 − ∣ ∣ A x + B z − c ∣ ∣ 2 2 ) w^T(Ax + Bz - c) = \frac{1}{2} (||w + (Ax + Bz - c)||_2^2 - ||w||_2^2 - ||Ax + Bz - c||_2^2) wT(Ax+Bz−c)=21(∣∣w+(Ax+Bz−c)∣∣22−∣∣w∣∣22−∣∣Ax+Bz−c∣∣22)
乘以 ρ \rho ρ：
将上式两边同时乘以 ρ \rho ρ，得到：ρ w T ( A x + B z − c ) = ρ 2 ( ∣ ∣ w + ( A x + B z − c ) ∣ ∣ 2 2 − ∣ ∣ w ∣ ∣ 2 2 − ∣ ∣ A x + B z − c ∣ ∣ 2 2 ) \rho w^T(Ax + Bz - c) = \frac{\rho}{2} (||w + (Ax + Bz - c)||_2^2 - ||w||_2^2 - ||Ax + Bz - c||_2^2) ρwT(Ax+Bz−c)=2ρ(∣∣w+(Ax+Bz−c)∣∣22−∣∣w∣∣22−∣∣Ax+Bz−c∣∣22)
简化表达式：
注意到 2 w T ( A x + B z − c ) 2w^T(Ax + Bz - c) 2wT(Ax+Bz−c) 只是将 w T ( A x + B z − c ) w^T(Ax + Bz - c) wT(Ax+Bz−c) 乘以 2，因此：ρ w T ( A x + B z − c ) = ρ 2 ( 2 w T ( A x + B z − c ) ) \rho w^T(Ax + Bz - c) = \frac{\rho}{2} (2w^T(Ax + Bz - c)) ρwT(Ax+Bz−c)=2ρ(2wT(Ax+Bz−c))
最终形式：
代入上面的恒等式，我们得到：ρ w T ( A x + B z − c ) = ρ 2 ( ∣ ∣ A x + B z − c + w ∣ ∣ 2 2 − ∣ ∣ w ∣ ∣ 2 2 − ∣ ∣ A x + B z − c ∣ ∣ 2 2 ) \rho w^T(Ax + Bz - c) = \frac{\rho}{2} (||Ax + Bz - c + w||_2^2 - ||w||_2^2 - ||Ax + Bz - c||_2^2) ρwT(Ax+Bz−c)=2ρ(∣∣Ax+Bz−c+w∣∣22−∣∣w∣∣22−∣∣Ax+Bz−c∣∣22)
这样我们就证明了原始等式的正确性。这个转换利用了向量内积与范数之间的关系，使得我们可以将线性项 w T ( A x + B z − c ) w^T(Ax + Bz - c) wT(Ax+Bz−c) 表达为一个关于 w w w 和 A x + B z − c Ax + Bz - c Ax+Bz−c 的二次项的组合。这种形式在优化算法（如ADMM）中非常有用，因为它允许我们将增广拉格朗日函数写成一种更方便的形式。
相应地，更新步骤变为：
s t e p 1 : x ( k ) = a r g min x f ( x ) + ρ 2 ∣ ∣ A x + B z ( k − 1 ) − c + w ( k − 1 ) ∣ ∣ 2 2 s t e p 2 : z ( k ) = a r g min z g ( z ) + ρ 2 ∣ ∣ A x ( k ) + B z − c + w ( k − 1 ) ∣ ∣ 2 2 s t e p 3 : w ( k ) = w ( k − 1 ) + A x ( k ) + B z ( k ) − c \begin{aligned}&step1:\quad x^{(k)}=arg\min_x f(x)+\frac\rho2||Ax+Bz^{(k-1)}-c+w^{(k-1)}||_2^2\\&step2:\quad z^{(k)}=arg\min_z g(z)+\frac\rho2||Ax^{(k)}+Bz-c+w^{(k-1)}||_2^2\\&step3:\quad w^{(k)}=w^{(k-1)}+Ax^{(k)}+Bz^{(k)}-c\end{aligned} step1:x(k)=argxminf(x)+2ρ∣∣Ax+Bz(k−1)−c+w(k−1)∣∣22step2:z(k)=argzming(z)+2ρ∣∣Ax(k)+Bz−c+w(k−1)∣∣22step3:w(k)=w(k−1)+Ax(k)+Bz(k)−c
注释：
在交替方向乘子法（ADMM）中，拉格朗日乘子 u u u 的更新规则u ( k + 1 ) = u ( k ) + ρ ( A x ( k + 1 ) + B z ( k + 1 ) − c ) u^{(k+1)} = u^{(k)} + \rho (Ax^{(k+1)} + Bz^{(k+1)} - c) u(k+1)=u(k)+ρ(Ax(k+1)+Bz(k+1)−c)
是通过增广拉格朗日方法（Augmented Lagrangian Method, ALM）推导出来的。这个更新规则的目的是为了逐步调整拉格朗日乘子，以确保约束条件 A x + B z − c = 0 Ax + Bz - c = 0 Ax+Bz−c=0 在迭代过程中逐渐得到满足。
增广拉格朗日函数
考虑原始优化问题：
min x , z f ( x ) + g ( z ) subject to A x + B z = c \min_{x, z} f(x) + g(z) \quad \text{subject to} \quad Ax + Bz = c minx,zf(x)+g(z)subject toAx+Bz=c
对应的拉格朗日函数为：
L ( x , z , u ) = f ( x ) + g ( z ) + u T ( A x + B z − c ) L(x, z, u) = f(x) + g(z) + u^T (Ax + Bz - c) L(x,z,u)=f(x)+g(z)+uT(Ax+Bz−c)
其中 u u u 是拉格朗日乘子。
为了加速收敛并提高稳定性，我们引入一个惩罚项来增强约束条件，从而得到增广拉格朗日函数：
L ρ ( x , z , u ) = f ( x ) + g ( z ) + u T ( A x + B z − c ) + ρ 2 ∣ ∣ A x + B z − c ∣ ∣ 2 2 L_\rho(x, z, u) = f(x) + g(z) + u^T (Ax + Bz - c) + \frac{\rho}{2} ||Ax + Bz - c||_2^2 Lρ(x,z,u)=f(x)+g(z)+uT(Ax+Bz−c)+2ρ∣∣Ax+Bz−c∣∣22
这里的 ρ > 0 \rho > 0 ρ>0 是一个正则化参数，用于控制惩罚项的强度。
ADMM 迭代步骤（这里w换成了u的符号，含义一样）
ADMM 通过以下三个步骤进行迭代：
- 更新 x x x：固定 z z z 和 u u u，最小化 L ρ ( x , z , u ) L_\rho(x, z, u) Lρ(x,z,u) 关于 x x x。
- 更新 z z z：固定 x x x 和 u u u，最小化 L ρ ( x , z , u ) L_\rho(x, z, u) Lρ(x,z,u) 关于 z z z。
- 更新 u u u：基于当前的 x x x 和 z z z 更新 u u u。
拉格朗日乘子的更新
拉格朗日乘子 u u u 的更新规则是通过对增广拉格朗日函数中的残差项进行累积来实现的。具体来说， u u u 的更新规则可以通过对增广拉格朗日函数关于 u u u 的梯度进行分析得出。
考虑增广拉格朗日函数：
L ρ ( x , z , u ) = f ( x ) + g ( z ) + u T ( A x + B z − c ) + ρ 2 ∣ ∣ A x + B z − c ∣ ∣ 2 2 L_\rho(x, z, u) = f(x) + g(z) + u^T (Ax + Bz - c) + \frac{\rho}{2} ||Ax + Bz - c||_2^2 Lρ(x,z,u)=f(x)+g(z)+uT(Ax+Bz−c)+2ρ∣∣Ax+Bz−c∣∣22
对于固定的 x x x 和 z z z， L ρ L_\rho Lρ 对 u u u 的梯度（
即在拉格朗日函数中对u进行求偏导）为：∇ u L ρ ( x , z , u ) = A x + B z − c \nabla_u L_\rho(x, z, u) = Ax + Bz - c ∇uLρ(x,z,u)=Ax+Bz−c
在每一步迭代中，我们希望使这个梯度逐渐趋近于零，即 A x + B z − c ≈ 0 Ax + Bz - c \approx 0 Ax+Bz−c≈0。为此，我们采用
梯度上升的方法来更新 u u u：u ( k + 1 ) = u ( k ) + α ∇ u L ρ ( x ( k + 1 ) , z ( k + 1 ) , u ( k ) ) u^{(k+1)} = u^{(k)} + \alpha \nabla_u L_\rho(x^{(k+1)}, z^{(k+1)}, u^{(k)}) u(k+1)=u(k)+α∇uLρ(x(k+1),z(k+1),u(k))
这里 α \alpha α 是步长，通常取为 1，因为这可以简化计算并保持算法的稳定性。因此，更新规则变为：
u ( k + 1 ) = u ( k ) + ( A x ( k + 1 ) + B z ( k + 1 ) − c ) u^{(k+1)} = u^{(k)} + (Ax^{(k+1)} + Bz^{(k+1)} - c) u(k+1)=u(k)+(Ax(k+1)+Bz(k+1)−c)
为了进一步加速收敛，我们可以引入一个正则化参数 ρ \rho ρ 来控制更新步长，从而得到最终的更新规则：
u ( k + 1 ) = u ( k ) + ρ ( A x ( k + 1 ) + B z ( k + 1 ) − c ) u^{(k+1)} = u^{(k)} + \rho (Ax^{(k+1)} + Bz^{(k+1)} - c) u(k+1)=u(k)+ρ(Ax(k+1)+Bz(k+1)−c)
这个更新规则确保了随着迭代的进行，拉格朗日乘子 u u u 会逐渐调整，使得约束条件 A x + B z − c = 0 Ax + Bz - c = 0 Ax+Bz−c=0 趋近于满足。每次迭代时， u u u 都会根据当前的残差 A x ( k + 1 ) + B z ( k + 1 ) − c Ax^{(k+1)} + Bz^{(k+1)} - c Ax(k+1)+Bz(k+1)−c 进行更新，从而使下一次迭代更接近最优解。
例
ADMM求解**lasso问题**
考虑 lasso 问题：
min
β
1
2
∣
∣
y
−
X
β
∣
∣
2
2
+
λ
∣
∣
β
∣
∣
1
\min_\beta \frac{1}{2}||y-X\beta||_2^2+\lambda||\beta||_1
βmin21∣∣y−Xβ∣∣22+λ∣∣β∣∣1
重写为：
min
β
,
α
1
2
∣
∣
y
−
X
β
∣
∣
2
2
+
λ
∣
∣
α
∣
∣
1
s
.
t
.
β
−
α
=
0
\begin{aligned}&\min_{\beta,\alpha} \frac{1}{2}||y-X\beta||_{2}^{2}+\lambda||\alpha||_{1}\\&s.t. \beta-\alpha=0\end{aligned}
β,αmin21∣∣y−Xβ∣∣22+λ∣∣α∣∣1s.t.β−α=0
构造增广拉格朗日函数：
L
ρ
(
β
,
α
,
u
)
=
1
2
∣
∣
y
−
X
β
∣
∣
2
2
+
λ
∣
∣
α
∣
∣
1
+
u
T
(
β
−
α
)
+
ρ
2
∣
∣
β
−
α
∣
∣
2
2
L_\rho(\beta,\alpha,u)=\frac{1}{2}||y-X\beta||_2^2+\lambda||\alpha||_1+u^T(\beta-\alpha)+\frac{\rho}{2}||\beta-\alpha||_2^2
Lρ(β,α,u)=21∣∣y−Xβ∣∣22+λ∣∣α∣∣1+uT(β−α)+2ρ∣∣β−α∣∣22
更新步骤：
- 首先求 β 的更新值。由 L ρ 对 β 是可导的,直接令 ∂ L ∂ β = 0 ,有 \text{首先求 }\beta\text{ 的更新值。由 }L_\rho\text{ 对 }\beta\text{ 是可导的,直接令 }\frac{\partial L}{\partial\beta}=0\text{,有} 首先求 β 的更新值。由 Lρ 对 β 是可导的,直接令 ∂β∂L=0,有
∂ L ∂ β = − X T ( y − X β ) + u + ρ ( β − α ) = 0 ⇒ β = ( X T X + ρ I ) − 1 ( X T y + ρ α − u ) ⇒ β = ( X T X + ρ I ) − 1 ( X T y + ρ ( α − w ) ) \begin{aligned} &\frac{\partial L}{\partial\beta}=-X^T(y-X\beta)+u+\rho(\beta-\alpha)=0 \\ &\Rightarrow \beta=(X^TX+\rho I)^{-1}(X^Ty+\rho\alpha-u) \\ &\Rightarrow \beta=(X^TX+\rho I)^{-1}(X^Ty+\rho(\alpha-w)) \end{aligned} ∂β∂L=−XT(y−Xβ)+u+ρ(β−α)=0⇒β=(XTX+ρI)−1(XTy+ρα−u)⇒β=(XTX+ρI)−1(XTy+ρ(α−w))
- 然后求 α 的更新值。 然后求α的更新值。 然后求α的更新值。
a r g min α L ρ ( β , α , u ) = a r g min α { λ ∣ ∣ α ∣ ∣ 1 + u T ( β − α ) + ρ 2 ∣ ∣ β − α ∣ ∣ 2 2 } = a r g min α { λ ∣ ∣ α ∣ ∣ 1 + u T ( β − α ) + ρ 2 ∣ ∣ β − α ∣ ∣ 2 2 } × 2 ρ = a r g min α { 2 λ ρ ∣ ∣ α ∣ ∣ 1 + ∣ ∣ u ρ + ( β − α ) ∣ ∣ 2 2 − ∣ ∣ u ρ ∣ ∣ 2 2 } = a r g min α { 2 λ ρ ∣ ∣ α ∣ ∣ 1 + ∣ ∣ α − ( u ρ + β ) ∣ ∣ 2 2 } = S λ ρ ( u ρ + β ) = S λ ρ ( w + β ) \begin{aligned} arg\min_{\alpha}L_{\rho}(\beta,\alpha,u)& =arg\min_\alpha \{ \lambda||\alpha||_1+u^T(\beta-\alpha)+\frac\rho2||\beta-\alpha||_2^2 \} \\ &=arg\min_{\alpha} \{ \lambda||\alpha||_1+u^T(\beta-\alpha)+\frac{\rho}{2}||\beta-\alpha||_2^2 \}\times\frac{2}{\rho} \\ &=arg\min_\alpha \{ \frac{2\lambda}{\rho}||\alpha||_1+||\frac{u}{\rho}+(\beta-\alpha)||_2^2-||\frac{u}{\rho}||_2^2 \} \\ &=arg\min_\alpha \{ \frac{2\lambda}{\rho}||\alpha||_1+||\alpha-(\frac{u}{\rho}+\beta)||_2^2 \} \\ &=S_{\frac{\lambda}{\rho}}(\frac{u}{\rho}+\beta)=S_{\frac{\lambda}{\rho}}(w+\beta) \end{aligned} argαminLρ(β,α,u)=argαmin{λ∣∣α∣∣1+uT(β−α)+2ρ∣∣β−α∣∣22}=argαmin{λ∣∣α∣∣1+uT(β−α)+2ρ∣∣β−α∣∣22}×ρ2=argαmin{ρ2λ∣∣α∣∣1+∣∣ρu+(β−α)∣∣22−∣∣ρu∣∣22}=argαmin{ρ2λ∣∣α∣∣1+∣∣α−(ρu+β)∣∣22}=Sρλ(ρu+β)=Sρλ(w+β)
- 综上，lasso 问题总的更新策略为：
β ( k ) = ( X T X + ρ I ) − 1 ( X T y + ρ ( α ( k − 1 ) − w ( k − 1 ) ) ) α ( k ) = S λ ρ ( w ( k − 1 ) + β ( k ) ) w ( k ) = w ( k − 1 ) + β ( k ) − α ( k ) \begin{aligned} &\beta^{(k)} =(X^TX+\rho I)^{-1}(X^Ty+\rho(\alpha^{(k-1)}-w^{(k-1)})) \\ &\alpha^{(k)} =S_{\frac{\lambda}{\rho}}(w^{(k-1)}+\beta^{(k)}) \\ &w^{(k)} =w^{(k-1)}+\beta^{(k)}-\alpha^{(k)} \end{aligned} β(k)=(XTX+ρI)−1(XTy+ρ(α(k−1)−w(k−1)))α(k)=Sρλ(w(k−1)+β(k))w(k)=w(k−1)+β(k)−α(k)
标签：Alternating,ADMM,Direction,frac,22,min,rho,Ax,Bz From： https://blog.csdn.net/weixin_50569789/article/details/142564196注意：软阈值算子
令:
h ( x ) = ∣ ∣ x ∣ ∣ 1 h(x)=||x||_1 h(x)=∣∣x∣∣1
近端映射：
p r o x t ( x ) = a r g min z 1 2 t ∣ ∣ x − z ∣ ∣ 2 2 + ∣ ∣ z ∣ ∣ 1 = a r g min z ∣ ∣ x − z ∣ ∣ 2 2 + 2 t ∣ ∣ z ∣ ∣ 1 = S t ( x ) \begin{aligned} prox_{t}(x)& =arg\min_z \frac1{2t}||x-z||_2^2+||z||_1 \\ &=arg\min_z\left.||x-z||_2^2+2t||z|\right|_1 \\ &=S_t(x) \end{aligned} proxt(x)=argzmin2t1∣∣x−z∣∣22+∣∣z∣∣1=argzmin∣∣x−z∣∣22+2t∣∣z∣ 1=St(x)
用 [ S t ( x ) ] i 表示 S t ( x ) 中的第 i 个分量,它们满足 : \text{用}[S_t(x)]_i\text{ 表示 }S_t(x)\text{ 中的第 }i\text{ 个分量,它们满足}: 用[St(x)]i 表示 St(x) 中的第 i 个分量,它们满足:
[ S t ( x ) ] i = { x i − t x i > t 0 ∣ x i ∣ ≤ t x i + t x i < − t [S_t(x)]_i=\begin{cases}x_i-t&x_i>t\\0&|x_i|\leq t\\x_i+t&x_i<-t\end{cases} [St(x)]i=⎩ ⎨ ⎧xi−t0xi+txi>t∣xi∣≤txi<−t
对形如 a r g min x ∣ ∣ x − b ∣ ∣ 2 2 + λ ∣ ∣ x ∣ ∣ 1 这样的目标函数 ∗ ,它的解为 x ∗ ,其第 i 个分量 为: x i ∗ = [ S λ 2 ( b ) ] i = { b i − λ 2 b i > λ 2 0 ∣ b i ∣ ≤ λ 2 b i + λ 2 b i < − λ 2 这个式子称为软阈值公式,其中 b i 为 b 的第 i 个分量, λ 2 为阈值。 \begin{aligned}&\text{对形如 }arg\min_x ||x-b||_2^2+\lambda||x||_1\text{ 这样的目标函数}^*\text{,它的解为 }x^*\text{,其第 }i\text{ 个分量}\\&\text{为:}x_i^*=[S_{\frac{\lambda}{2}}(b)]_i=\begin{cases}b_i-\frac{\lambda}{2}&b_i>\frac{\lambda}{2}\\0&|b_i|\leq\frac{\lambda}{2}\\b_i+\frac{\lambda}{2}&b_i<-\frac{\lambda}{2}\end{cases}\\&\text{这个式子称为软阈值公式,其中 }b_i\text{ 为 }b\text{ 的第 }i\text{ 个分量,}\frac{\lambda}{2}\text{ 为阈值。}\end{aligned} 对形如 argxmin∣∣x−b∣∣22+λ∣∣x∣∣1 这样的目标函数∗,它的解为 x∗,其第 i 个分量为:xi∗=[S2λ(b)]i=⎩ ⎨ ⎧bi−2λ0bi+2λbi>2λ∣bi∣≤2λbi<−2λ这个式子称为软阈值公式,其中 bi 为 b 的第 i 个分量,2λ 为阈值。