理解凸优化

原创声明：本文为 SIGAI 原创文章，仅供个人学习使用，未经允许，不能用于商业目的。

欢迎搜索关注微信公众号SIGAICN，获取更多原创干货。

理解凸优化

导言

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

凸优化简介

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

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

理解凸优化

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

理解凸优化

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

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

理解凸优化

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

凸集

理解凸优化

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

理解凸优化

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

理解凸优化

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

这一结论的意义在于如果一个优化问题是不带约束的优化，则其优化变量的可行域是一个凸集。

仿射子空间。给定m行n列的矩阵A和m维向量b，仿射子空间定义为如下向量的集合：

理解凸优化

回忆一下线性代数中所学的，它就是非齐次线性方程组的解。下面我们给出证明。假设理解凸优化并且：

理解凸优化

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

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

理解凸优化

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

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

理解凸优化

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

凸函数

在微积分中我们学习过凸函数的定义，下面来回忆一下。在函数的定义域内，如果对于任意的x和y，以及实数理解凸优化，都满足如下条件：

理解凸优化

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

理解凸优化

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

理解凸优化

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

理解凸优化

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

理解凸优化

如果去掉上面的等号，则函数是严格凸的。对于多元函数，如果它是凸函数，则其Hessian矩阵为半正定矩阵。如果Hessian矩阵是正定的，则函数是严格凸函数。

Hessian矩阵是由多元函数的二阶偏导数组成的矩阵。如果函数理解凸优化二阶可导，Hessian矩阵定义为：

理解凸优化

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

理解凸优化

因此Hessian矩阵是一个对称矩阵，它可以看作二阶导数对多元函数的推广。Hessian矩阵简写为理解凸优化。对于如下多元函数：

理解凸优化

它的Hessian矩阵为：

理解凸优化

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

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

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

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

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

理解凸优化

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

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

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

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

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

理解凸优化

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

理解凸优化

则称矩阵A为半正定矩阵。

理解凸优化

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

下水平集

给定一个凸函数以及一个实数理解凸优化，函数的下水平集（sub-level set）定义为函数值小于等于的点构成的集合：

理解凸优化

根据凸函数的定义，很容易证明该集合是一个凸集。这个概念的用途在于我们需要确保优化问题中一些不等式约束条件定义的可行域是凸集，如果是凸函数构成的不等式，则是凸集。

凸优化

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

理解凸优化

其中x为优化变量；f为凸目标函数；C是优化变量的可行域，是一个凸集。这个定义给了我们证明一个问题是凸优化问题的思路，即证明目标函数是凸函数（一般是证明它的Hessian矩阵半正定），可行域是凸集。凸优化问题的另一种通用写法是：

理解凸优化

其中理解凸优化是不等式约束函数，为凸函数；是等式约束函数，为仿射函数。上面的定义中不等式的方向非常重要，因为一个凸函数的0-下水平集是凸集。因此这些不等式共同定义的可行域是一些凸集的交集，仍然为凸集。通过将不等式两边同时乘以-1，可以保证把不等式写成小于号的形式。前面已经证明仿射空间是凸集，因此加上这些等式约束后可行域还是凸集。