博客 | 机器学习中的数学基础（凸优化）

2018 年 12 月 16 日 AI研习社

本文原载于知乎专栏“AI的怎怎，歪歪不喜欢”，AI研习社经授权转载发布。欢迎关注 邹佳敏 的知乎专栏及 AI研习社博客专栏（文末可识别社区名片直达）。

社长提醒：本文的相关链接请点击文末【阅读原文】进行查看

一、凸优化初步：

机器学习中几乎所有的问题到最后都能归结到一个优化问题，即求解损失函数的最小值。我们知道，梯度下降法和牛顿法都是通过逼近的方式到达极值点，如何使损失函数的极值点成为它的最值点就是凸函数和凸优化关注的内容。

凸优化，即在一系列以凸函数为条件的限制下，求解目标凸函数的最小值。即使目标函数本身是非凸函数，我们也可以使用一个凸函数去逼近它，以图寻找到一个最优的初始点来求解非凸函数的最小值问题。

凸集合：在集合U中任意2点之间作线段，如果线段上的所有点仍然在集合U中，我们就说U为凸集合。凸函数：定义在凸集上的函数，在定义域中任意2个点之间作线段，如果线段上任意一个点所对应的函数值都位于线段下方时，即为凸函数。函数的上镜图，定义在凸集上的函数，对于函数上方任意大于等于函数值的点所构成的集合就是该函数的上镜图。一个函数是凸函数当且仅当其上镜图是凸集合，因此函数的上镜图是联系凸集合和凸函数关系的纽带。

在非负权重系数和为1的前提下，任意n个点的加权平均所指示的位置就是一个凸组合。由同一组n个点所指示的所有凸组合就构成一个凸包。如果C’是函数f上镜图C的凸包，那么以C’为上镜图的函数g称为f的凸闭包。其中，上镜图C包含于凸包C’，两者各自的支撑平面互为支撑平面。同时，g的函数值小于等于f，两者的下确界相同。这里，支撑平面就是在一个空间中能够将凸集合与其他部分完整分离的平面。

因为凸集合O的任意子集的凸包包含于O，而又由前文上镜图C包含于其凸包C’，因此凸集合的凸包就是其本身。对于凸函数，任意n个所对应构成的凸组合要大于等于本身凸组合所对应的，直观上的理解就是凸函数的上镜图肯定都位于凸函数上方，这就是Jesen不等式。有意思的是，只要能找到合适的凸函数f和对应的权重表达式，很多数学界著名的不等式，例如算术平均不等式和柯西不等式，都可由Jesen不等式推导而来。事实上，大部分的不等式，要么来自于 >=0，要么就是来自Jesen不等式。

凸集合和凸函数有各种各样的性质，但这些性质都可由上镜图对应和联系起来。比如，任意多个凸集合的交集仍是凸集合，那么以这些凸集合为上镜图的凸函数逐点上确界仍是凸函数。同时，凸函数向任意一个低维空间的投影也是一个凸函数，因为其投影的上镜图仍然是个凸集。另外，由于凸集合的凸包就是其本身，而凸包描述的是一个线性组合的性质，因此线性空间中凸集合的正逆变换仍是一个凸集合，凸函数的非负线性组合也仍然是一个凸函数。除此之外，凸集合和凸函数还有一些在微分和光学投影上的性质，例如，凸集合可微边界上的切线就是凸集合的支撑线，凸函数的一阶线性逼近小于等于函数本身，同时其二阶导数或Henssen矩阵半正定。凸集合的平行光源投影、点光源投影以及以点光源为中心的椎体发散都是凸集合，凸函数的下确界和特定方式的升维函数也是一个凸函数等等。

对于任意两个不交的非空凸集，一定能找到一个超平面将两个凸集完整分开，即凸集分离定理。

二、凸优化进阶：

凸优化初步中介绍了凸优化问题中的诸多概念，而进阶部分描述的就是应用凸优化技术如何求解凸函数的最优化问题。

共轭函数，描述的是原函数f(x)自变量x的线性组合与其本身之间的最大距离，即。共轭函数线性组合的特征提供了凸优化问题的另一个视角：如果优化问题的限制条件是线性条件时，我们可以方便的利用共轭函数求解其对偶问题。共轭函数有很多重要的基本性质，比如共轭函数是凸函数，如果原函数是凸函数，其共轭的共轭等于其本身等等。

一般意义上的优化问题，已知损失函数在一系列不等式条件和等式条件的基础上，在定义域内满足不等式和等式条件的可行域中，寻找优化点，求解得到最优化值。

根据原问题，定义拉格朗日量

若取遍x的定义域，求解拉格朗日量关于和u的下确界函数，即为拉格朗日对偶函数。定义对偶问题的一般形式，在所有不使g趋近于负无穷大，同时的可行域下，最大化，记为d’。

这里有个极其容易误解和忽视的地方，拉格朗日对偶函数是可以取遍定义域内所有范围的，而不仅仅是可行域。同时，对偶问题解出来的东西通常并不会直接产生一个对应的x’，在这里一般只研究对偶问题的最优解和原问题最优解之间的关系。因此，可以认为原问题的定义域跟对偶问题的定义域，和原问题的可行域跟对偶问题的可行域完全是描述不同的变量，虽然他们有关系但分离的。

当优化问题的限制条件是线性条件时，可以利用共轭函数的某些性质极其方便的得到其对偶问题。因为线性条件下的优化问题存在包含共轭函数的通式，因此遇见此类问题时只需要对应通式代入即可。

对偶函数有一个极其简单又易于证明的性质，即在x的可行域中，若限制，则有d’<=p’！此时，对偶函数为原问题提供下界。当然，我们最关心的还是最大化g，使其更接近最小化的，同时取到等号。这也就引出了强弱对偶性之分，弱对偶性d’<=p’由对偶问题可行域来保证，始终都是正确的。但由于我们要确定一个最优解x’，所以我们总是想取到等号，即d’=p’，这便是强对偶性，但它并不总是成立的。但原问题为凸优化问题，基本上都满足强对偶性！即，若可行域中存在一点x，使得不等式条件均成立，那么该凸优化问题就满足强对偶条件。