L1正则化问题：

$$\min_{x} f(x)+\lambda\Vert x\Vert_1$$
若 $f(x)$可导，且 $f(x)$满足 L-Lipschitz条件，即存在常数 $L> 0$使得

$$\Vert\nabla f(x')-\nabla f(x)\Vert_2^2\leq L\Vert x'-x\Vert_2^2(\forall x,x')$$
则在 $x_k$附近可将 $f(x)$二阶taylor展开近似为：
$$\begin{aligned} \hat f(x)&\simeq f(x_0)+\left<\nabla f(x_0),x-x_0\right>+\frac{L}{2}\Vert x-x_0\Vert^2 \\ &=\frac{L}{2}\Vert x-(x_0-\frac{1}{L}\nabla f(x_0))\Vert_2^2+const \end{aligned}$$
上式的最小值为：
$$x = x_0-\frac{1}{L}\nabla f(x_0)$$

若通过梯度下降法对$f(x)$进行最小化，则每一步迭代等价于最小化二次函数$\hat f(x)$.

L1正则化问题的迭代公式为：

$$x_{k+1}=\arg\min_x\frac{L}{2}\Vert x-(x_k-\frac{1}{L}\nabla f(x_k))\Vert_2^2+\lambda\Vert x\Vert_1$$
令 $z=x_k-\frac{1}{L}\nabla f(x_k)$,然后求解：
$$x_{k+1}=\arg\min_x\frac{L}{2}\Vert x-z\Vert_2^2+\lambda\Vert x\Vert_1$$
解得：
$$\begin{aligned} x_{k+1}^i=\begin{cases} z^i-\frac{\lambda}{L},&\frac{\lambda}{L}<z^i\\ 0,&|z^i|\le\frac{\lambda}{L}\\ z^i+\frac{\lambda}{L},&\frac{\lambda}{L}>z^i \end{cases} \end{aligned}$$
其中， $x_{k+1}^i$与 $z^i$分别是 $x_{k+1}$与 $z$的第 i 个分量。