推荐系统之理解凸优化

作者: 文子轩 | 来源:发表于2021-05-04 13:36 被阅读0次

转载 https://blog.csdn.net/SIGAI_CSDN/article/details/80695179

导言

凸优化（convex optimization）是最优化问题中非常重要的一类，也是被研究的很透彻的一类。对于机器学习来说，如果要优化的问题被证明是凸优化问题，则说明此问题可以被比较好的解决。在本文中，SIGAI将为大家深入浅出的介绍凸优化的概念以及在机器学习中的应用。

凸优化简介

在SIGAI之前的公众号文章“理解梯度下降法”中我们介绍了最优化的基本概念以及梯度下降法。如果读者对目标函数，优化变量，可行域，等式约束，不等式约束，局部极小值，全局极小值的概念还不清楚，请先阅读那篇文章。

求解一个一般性的最优化问题的全局极小值是非常困难的，至少要面临的问题是：函数可能有多个局部极值点，另外还有鞍点问题。对于第一个问题，我们找到了一个梯度为0的点，它是极值点，但不是全局极值，如果一个问题有多个局部极值，则我们要把所有局部极值找出来，然后比较，得到全局极值，这非常困难，而且计算成本相当高。第二个问题更严重，我们找到了梯度为0的点，但它连局部极值都不是，典型的是这个函数，在0点处，它的导数等于0，但这根本不是极值点：

image.png

梯度下降法和牛顿法等基于导数作为判据的优化算法，找到的都导数/梯度为0的点，而梯度等于0只是取得极值的必要条件而不是充分条件。如果我们将这个必要条件变成充分条件，即：

image.png

问题将会得到简化。如果对问题加以限定，是可以保证上面这个条件成立的。其中的一种限制方案是：

对于目标函数，我们限定是凸函数；对于优化变量的可行域（注意，还要包括目标函数定义域的约束），我们限定它是凸集。

image.png

同时满足这两个限制条件的最优化问题称为凸优化问题，这类问题有一个非常好性质，那就是局部最优解一定是全局最优解。接下来我们先介绍凸集和凸函数的概念。

凸集 image.png

则称该集合称为凸集。如果把这个集合画出来，其边界是凸的，没有凹进去的地方。直观来看，把该集合中的任意两点用直线连起来，直线上的点都属于该集合。相应的点：

image.png

称为点x和y的凸组合。下图是凸集和非凸集的示意图，左边是一个凸集，右边是一个非凸集：

image.png
下面是实际问题中一些常见的凸集例子，记住它们对理解后面的算法非常有帮助：

image.png

这一结论的意义在于如果一个优化问题是不带约束的优化，则其优化变量的可行域是一个凸集。
仿射子空间。给定m行n列的矩阵A和m维向量b，仿射子空间定义为如下向量的集合：

image.png 回忆一下线性代数中所学的，它就是非齐次线性方程组的解。下面我们给出证明。假设

image

并且：

image.png

这一结论的意义在于，如果一组约束是线性等式约束，则它确定的可行域是一个凸集。

多面体。多面体定义为如下向量的集合：

image.png

这一结论的意义在于，如果一组约束是线性不等式约束，则它定义的可行域是凸集。在实际应用中，我们遇到的等式和不等式约束一般是线性的，因此非常幸运，它们定义的可行域是凸集。

一个重要的结论是：多个凸集的交集还是凸集。证明如下：

image.png

这个结论的实际价值是如果每个等式或者不等式约束条件定义的集合都是凸集，那么这些条件联合起来定义的集合还是凸集，而我们遇到的优化问题中，可能有多个等式和不等式约束，只要每个约束条件定义的可行域是凸集，则同时满足这下约束条件的可行域还是凸集。需要注意的是，凸集的并集并不是凸集。

凸函数

在微积分中我们学习过凸函数的定义，下面来回忆一下。在函数的定义域内，如果对于任意的x和y，以及实数

image

，都满足如下条件

image.png

则函数为凸函数。这个不等式和凸集的定义类似。从图像上看，一个函数如果是凸函数，那么它是向下凸出去的。用直线连接函数上的任何两点A和B，线段AB上的点都在函数的上方，如下图所示

image.png
如果把上面不等式中的等号去掉，即：

image.png

则称函数是严格凸函数。凸函数的一阶判定规则为：

image.png
其几何解释为函数在任何点处的切线都位于函数的下方。对于一元函数，凸函数的判定规则为其二阶导数大于等于0，即：

image.png
如果去掉上面的等号，则函数是严格凸的。对于多元函数，如果它是凸函数，则其Hessian矩阵为半正定矩阵。如果Hessian矩阵是正定的，则函数是严格凸函数。 Hessian矩阵是由多元函数的二阶偏导数组成的矩阵。如果函数

image

二阶可导，Hessian矩阵定义为

image.png

这是一个n阶矩阵。一般情况下，多元函数的混合二阶偏导数与求导次序无关，即：

image.png
因此Hessian矩阵是一个对称矩阵，它可以看作二阶导数对多元函数的推广。Hessian矩阵简写为

image

。对于如下多元函数：

image.png

它的Hessian矩阵为：

image.png
根据多元函数极值判别法，假设多元函数在点M的梯度为0，即M是函数的驻点，则有：

1.如果Hessian矩阵正定，函数在该点有极小值

2.如果Hessian矩阵负定，函数在该点有极大值

3.如果Hessian矩阵不定，还需要看更高阶的导数

这可以看做是一元函数极值判别法对多元函数对推广，Hessian矩阵正定类似于二阶导数大于0，其他的以此类推。对于n阶矩阵A，对于任意非0的n维向量x都有

image.png

则称矩阵A为正定矩阵。判定矩阵正定的常用方法有以下几种：

1.矩阵的特征值全大于0。

2.矩阵的所有顺序主子式都大于0。

3.矩阵合同于单位阵I。

类似的，如果一个n阶矩阵A，对于任何非0的n维向量x，都有：

image.png

则称矩阵A为负定矩阵。如果满足：

image.png
则称矩阵A为半正定矩阵。

image.png

是凸函数。可以根据凸函数的定义进行证明，非常简单，读者可以自己实现
下水平集

image.png

凸优化

有了凸集和凸函数的定义之后，我们就可以给出凸优化的定义。如果一个最优化问题的可行域是凸集，并且目标函数是凸函数，则该问题为凸优化问题。凸优化问题可以形式化的写成：

image.png

局部最优解与全局最优解

image.png

则称x为全局最优点，全局最优解可能不止一个。凸优化问题有一个重要的特性：所有局部最优解都是全局最优解。这个特性可以保证我们在求解时不会陷入局部最优解，即如果找到了问题的一个局部最优解，则它一定也是全局最优解，这极大的简化了问题的求解。下面证明上面的结论，采用反证法，具体证明如下：

假设x是一个局部最优解但不是全局最优解，即存在一个可行解y，有：

image.png

这与x是局部最优解矛盾。如果一个局部最优解不是全局最优解，在它的任何邻域内还可以找到函数值比该点更小的点，这与该点是局部最优解矛盾。

之所以凸优化问题的定义要求目标函数是凸函数而且优化变量的可行域是凸集，是因为缺其中任何一个条件都不能保证局部最优解是全局最优解。下面来看两个反例。

情况1：可行域是凸集，函数不是凸函数。这样的例子如下图所示：

image.png

上图中优化变量的可行域是整个实数集，显然是凸集，目标函数不是凸函数，有两个局部最小值，这不能保证局部最小值就是全局最小值。

情况2：可行域不是凸集，函数是凸函数。这样的例子如下图所示：

image.png

在上图中可行域不是凸集，中间有断裂，目标函数还是凸函数。在曲线的左边和右边各有一个最小值，不能保证局部最小值就是全局最小值。可以很容易把这个例子推广到3维空间里的2元函数（曲面）。由于凸优化的的目标函数是凸函数，Hessian矩阵半正定，因此不会出现鞍点，所以找到的梯度为0的点一定是极值点。
求解算法
对于凸优化问题，可以使用的求解算法很多，包括最常用的梯度下降法，牛顿法，拟牛顿法等，它们都能保证收敛到全局极小值点。梯度下降法在之前的文章中已经介绍，牛顿法和拟牛顿法在接下来将会介绍，请关注SIGAI的公众号。