数学知识

可导：即设$y=f(x)$是一个单变量函数， 如果$y$在$x=x_0$处左右导数分别存在且相等,则称$y$在$x=x_0$处可导。如果一个函数在$x_0$处可导，那么它一定在$x_0$处是连续函数。

可微：设函数$y=f(x)$，若自变量在点$x$的改变量$\mathrm{\Delta }x$与函数相应的改变量$\mathrm{\Delta }y$有关系$\mathrm{\Delta }y=A\times \mathrm{\Delta }x+O(\mathrm{\Delta }x)$，其中$A$与$\mathrm{\Delta }x$无关，则称函数$f(x)$在点$x$可微，并称$A\times \mathrm{\Delta }x$为函数$f(x)$在点$x$的微分，记作$dy$，即$dy=A\times \mathrm{\Delta }x$，当$x=x_0$时，则记作$dy\mid x=x_0$。

与经典的梯度下降法和随机梯度下降法相比，近端梯度下降法的适用范围相对狭窄。对于凸优化问题，当其目标函数存在不可微部分（例如目标函数中有$l_1$​ 范数或迹范数)时，近端梯度下降法才会派上用场。假设目标函数:

$$f(x)=g(x)+h(x)$$

其中，限定$g(x)$ 是可微的凸函数、 $h(x)$​是不可微 (或局部不可微) 的凸函数。

Paper:

$$Pro{x}_{\lambda }^f(x)=arg\underset{y}{min}f(y)+\frac{\lambda }{2}\parallel y-x{\parallel }^2$$

Theory:

$$Pro{x}_{\lambda }^f(x)=arg\underset{y}{min}(f(y)+\frac{1}{2\lambda }\parallel y-x{\parallel }^2)$$

从上面这个式子可以看出，上式是在寻找一个距离$x$点不要太远的一个$y$，使得$f(x)$尽可能小，显然$f(y)<=f(x)$。最小化$f(x)$且要求新求得的$y$点不能和上一轮迭代得到的$x$点距离太远(泰勒公式通常只展开到一阶或二阶，高阶项被丢弃，要使得被丢弃的高阶项不至于对优化造成太大影响，下一个坐标点必须不能离原坐标点距离太大)。$Pro{x}_{\lambda }^f(x)$的点是最小化函数$f$和临近$x$的折中。

这张图形象的表示了上面式子的几何意义，其中加粗的黑线表示作用域，浅色的黑线表示函数$f$的等高线，蓝色的点对应上面式子的$x$点，红色点表示最终求得的$y$点。在蓝色的点处计算$Pro{x}^f$，则为相应的红色点(在蓝色的点处估计其得到红色的点)。函数定义域中的三个点仍然在定义域中，并且移动到函数的最小值，同时，另外两个点移动到定义域的边界并且朝向函数的最小值。参数$\lambda$控制近端操作将点映射到函数$f$的最小值的程度，$\lambda$值越大，则映射后的点更接近最小值，$\lambda$值越小，则向最小值移动的步长越小。

References

Proximal Algorithms_机器学习的小学生-CSDN博客 (opens new window)

www.luolei.info/2016/09/27/proximalAlgo/ (opens new window)