函数的次梯度如何理解？ - @王源

问题描述

非线性规划

次梯度的定义如下：

对于凸函数 $f:D\rightarrow R$ , 其中 $D$ 为定义在 $n$ 维欧式空间上的凸集。若对 $\forall y\in D$ 有如下表达式成立

$f\left( y \right) \ge f\left( x \right) +\left< g,y-x \right>$

则称向量 $g$ 为 $f$ 在 $x$ 处的次梯度。

其实定义都能在教科书上查到，主要是如何理解这个定义。我第一次看到次梯度的定义的时候不是很能理解，因为这个定义的长相是有点奇怪的。当然要想对次梯度有一个基本理解，还需要对凸优化有一个基本了解，否则想要理解次梯度还是比较困难的。

1 次梯度定义初探

$f\left( y \right) \ge f\left( x \right) +\left< g,y-x \right> , \forall y\in D$ 是对所有的 $y$ 都成立，那么对最小值 $y^*$ 也应该成立，由此可得

$f\left( y^* \right)- f\left( x \right) \ge \left< g,y^*-x \right>$

由于 $y^*$ 是最优值，所以上式中不等式左端是小于等于0的，由此进一步可得：

$\left< -g,y^*-x \right>\geq0$

看到这里我们已经有点明朗了,上式表明 $-g$ 与 $y^*-x$ 内积大于等于0，内积反应的是两个向量之间的夹角关系，内积大于等于0表明两个向量夹角小于等于90度。那么我们在点 $x$ 处沿着该点次梯度的负方向 $-g$ 前进，那么在很大可能性上（并不能严格保证）就会靠近最小值 $y^*$ 。

这一点和梯度法的出发点是一样的，负梯度是可导函数局部的最速下降点，那么再每个局部点都沿着负梯度搜索下去就能收敛到全局最优点。由次梯度的定义可知，次梯度也具备着类似的性质，只不过次梯度不依赖于可导的条件罢了。

需要注意的是函数在某点处的次梯度一般来说是一个集合，而并非一个点，这一点和梯度是有很大不同的，梯度一般是唯一的。我们用如下符号表示某点的次梯度

$\partial f =\left\{ g \in E^n : f\left( y \right) \ge f\left( x \right) +\left< g,y-x \right> , \forall y \in E^n \right\}$

只要满足次梯度那个定义的就是次梯度了，所有满足次梯度定义的构成了一个集合。

2 次梯度与梯度的关系

对于凸函数在定义域的内部点上有：

函数在该点处的次梯度存在且唯一 $\Leftrightarrow$ 函数该点是可微的

3 次梯度的几何直观意义

最常见被拿来举例子说明次梯度的就是L1 norm，L1 norm的一维版本就是绝对值函数 $f(x)=\left| x \right|,x \in R$ ,如下图所示是绝对值函数的图像：

红色的线表示函数值，2条虚线表示，绝对值函数在 $x=0$ 处的支撑超平面，其支撑超平面的斜率就是次梯度。熟悉凸优化的童鞋会支撑超平面应该比较熟悉。何谓支撑超平面呢？简单点说就是一个平面会把空间划分为2块，要保证函数图像仅在其中1块就可以。严谨定义参考凸优化的教材[1]，总之就是次梯度就是支撑超平面的斜率。

在绝对值函数这个例子中，我们不难看出在 $x\ne0$ 的地方，其次梯度就是梯度并且唯一，这也刚好验证了我们上面所论述的次梯度和梯度之间的关系。在 $x=0$ 这个地方绝对值函数是不可微的，其支撑超平面的斜率是范围是 $[-1,1]$ ，因此其次梯度也是 $[-1,1]$ 。可以把这个结果带入到次梯度定义中去验证一下：

由次梯度定义有如下不等式

$\left|y \right| \ge \left| 0\right|+\left< g,y-0\right> , \forall y\in D$

进一步整理得

$\left|y \right| \ge g y , \forall y\in D$

由此可得 $g\in [-1,1]$

那么到这里就可以建立起函数的次梯度的一个几何直观感受。若不熟悉支撑超平面则想要理解这块内容有点困难，建议先熟悉凸优化的内容再反过头来看。

4 次梯度与最优性条件

对优化问题而言最优性条件有着举足轻重的地位，肯定要问一下次梯度还有类似导数那样一阶最优性条件吗？答案是有的。这个定理被称为 Fermat's optimal condition [2]

$f$ 是一个凸函数， $x^*$ 为最小值当且仅当 $0 \in \partial f(x^*)$

这个定理和基于导数的一阶最优性条件十分相似，不同点在于函数某点的次梯度是一个集合，所以要只能是 $0 \in \partial f(x^*)$ ，而不是 $0 = \partial f(x^*)$

值得注意的是有些时候我们无法得到 $\partial f(x^*)$ 的closed form的形式，所以也就很难判断这个最优性条件是否成立，这一点在梯度法里则不存在。

5 次梯度的存在性

最后要回答一个问题，次梯度啥时候存在？梯度有不存在的时候，同理次梯度肯定也有其存在的条件。

凸函数是次梯度存在的必要条件，若不是凸函数，则必然会有某些点次梯度是空集（这点从支撑超平面的几何观点就能很好解释）。但是仅仅是凸函数还不够，主要是因为在边界点处会出现凸函数次梯度为空集的情况。

这块想要严谨说明话就比较长了，初学者的话只需知道最起码是凸函数才能保证任意一点的次梯度存在即可。

参考文献：

[1] Boyd S, Boyd S P, Vandenberghe L. Convex optimization[M]. Cambridge university press, 2004.

[2] Beck A. First-order methods in optimization[M]. SIAM, 2017.

[3] Nesterov Y. Introductory lectures on convex programming volume i: Basic course[J]. Lecture notes, 1998, 3(4): 5.