基本原理
近端梯度下降（Proximal Gradient Descent）是梯度下降方法的一种，其适用于目标函数存在不可微部分的凸优化问题。问题描述为
$$ \mathbf x = \arg\min_\mathbf x {g(\mathbf x)+h(\mathbf x)}, $$其中，$g(\mathbf x)$为可微凸函数、$h(\mathbf x)$为不可微凸函数。
求解方法
求解该类型凸优化问题可以通过近端映射（Proximal Mapping）和梯度迭代的手段实现。近端映射函数定义为
$$ \text{prox}_{h,t}(\mathbf x) = \arg\min_\mathbf z{\frac1{2t}\lVert\mathbf x-\mathbf z\rVert^2_2+h(\mathbf z)}, $$梯度迭代方法为
$$ \begin{align*} &\mathbf z^{(k)}=\mathbf x^{(k)}-t_k\nabla g(\mathbf x^{(k)}) \\ &\mathbf x^{(k+1)}=\text{prox}_{h,t_k}(\mathbf z^{(k)}) \end{align*} $$证明
对$g(\mathbf x)$在$\mathbf x^{(k)}$处做二阶泰勒展开，令$L=\nabla^2g(\mathbf x)=\frac1t$
$$ \begin{align*} \arg\min_\mathbf x g(\mathbf x)+h(\mathbf x) &\approx \arg\min_\mathbf x{g(\mathbf x^{(k)})+\nabla g(\mathbf x^{(k)})^\text T (\mathbf x -\mathbf x^{(k)})+\frac12(\mathbf x-\mathbf x^{(k)})^\text T\nabla^2g(\mathbf x^{(k)})(\mathbf x-\mathbf x^{(k)})}+h(\mathbf x) \\ \mathbf{\hat x}&= \arg\min_\mathbf x{\nabla g(\mathbf x^{(k)})^\text T (\mathbf x -\mathbf x^{(k)})+\frac1{2t}(\mathbf x-\mathbf x^{(k)})^\text T(\mathbf x-\mathbf x^{(k)})}+h(\mathbf x) \\ &= \arg\min_\mathbf x\sum_i{[\nabla g(\mathbf x^{(k)})]_i (x_i -x_i^{(k)})+\frac1{2t}(x_i-x_i^{(k)})^2}+h(\mathbf x) \\ &= \arg\min_\mathbf x\frac1{2t}\sum_i{2t[\nabla g(\mathbf x^{(k)})]_i (x_i -x_i^{(k)})+(x_i-x_i^{(k)})^2}+h(\mathbf x) \\ &= \arg\min_\mathbf x\frac1{2t}\sum_i{t^2[\nabla g(\mathbf x^{(k)})]_i^2+2t[\nabla g(\mathbf x^{(k)})]_i (x_i -x_i^{(k)})+(x_i-x_i^{(k)})^2}+h(\mathbf x) \\ &= \arg\min_\mathbf x\frac1{2t}\sum_i{[x_i-x_i^{(k)}+t[\nabla g(\mathbf x^{(k)})]_i]^2}+h(\mathbf x) \\ &= \arg\min_\mathbf x\frac1{2t}{\lVert\mathbf x-[\mathbf x^{(k)}-t\nabla g(\mathbf x^{(k)})]\rVert^2_2}+h(\mathbf x) \\ \end{align*}. $$令$\mathbf z^{(k)}=\mathbf x^{(k)}-t\nabla g(\mathbf x^{(k)})$，原问题即可转换为近端映射
$$ \begin{align*} \mathbf{\hat x} &= \arg\min_\mathbf x\frac1{2t}{\lVert\mathbf x-\mathbf z\rVert^2_2}+h(\mathbf x) \\ &=\text{prox}_{h,t}(\mathbf z) \end{align*}. $$设定合适的参数，即可使用迭代方法求得$\arg\min_\mathbf x g(\mathbf x)+h(\mathbf x)$的结果。
Lipschitz常数
假定目标凸函数满足梯度上的Lipschitz连续。当步长$t\le\frac1L$时，保证多次迭代后能收敛到梯度为0的点。梯度Lipschitz连续表示为
$$ \frac{\lVert\nabla f(a)-\nabla f(b)\rVert_2}{\lVert a-b\rVert_2} \le L(f) \quad \forall a,b\in\text{dom}f, $$函数$\nabla f$的Lipschitz常数为
$$ L = \sup\frac{\lVert\nabla f(a)-\nabla f(b)\rVert_2}{\lVert a-b\rVert_2} $$