机器学习中的凸优化

机器学习中为什么要强调凸优化？

        凸优化在数学规划领域具有非常重要的地位。工程中大量的问题最终都可以归结为一个优化问题，包括且不限于雷达、通信、信息处理、机器学习、模式识别、图像处理、自动控制、金融等学科。

在一些数学问题中很可能遇到复杂的函数、高阶函数等一些不易求解的目标函数。如图1所示的函数，其可能有多个局部极值点，而我们想找到全局最优点。

图1

对于一个复杂函数或一个上图所示的函数，找其全局最优点无疑比较困难或者说比较复杂，在实际工程中可能很难求解，这时我们想将一个复杂的目标函数转化为一个如图2所示的函数。这样其局部最优便是全局最优的解。

图2

        而图2所示的函数图像便是一个典型的凸函数图像，对应的优化称为凸优化。

所以凸优化问题便是便是机器学习的一个根本性问题。在工程中的很多问题可以抽象化为一个凸问题，很多非凸问题可以通过一定的手段或方法转化为一个凸问题，一旦转化为一个凸问题，那么理论上来说，这个问题便得到了解决。所以如何将工程中的问题或一个非凸问题转化为一个凸优化问题才是真正的考验一个人的能力。

一些基本概念

1、凸集

凸集的定义（直接上图片了，简书上不好写公式）

        简单的来说，凸集的定义就是在凸集内部任意选取两个点，则这两个点的连线上的任意一点也还在这个集合内，如图3.   直观上来说，凸集的图像外观就是外形往外凸不能有内凹的 部分。

图3.

2、常见的凸集：

（1）超平面（Hyperplane）：

图4

（2）半空间（Halfspace）

图5

（3）多面体（Polyhedron）

图6

此外还有欧式球、椭球等凸集。

欧式球（Euclidean ball） 椭球（Ellipsoid）

        特别注意的是：一个凸优化的问题他的可行域必须是一个凸集，这也是凸集在优化问题中的重要性。

3、凸函数

        其几何解释，如图7所示凸函数的图上任取两个点连成一条直线，在这条直线的范围内，凹函数图上的值小于这个直线上的值。

图7

关于凸函数，它有两个充要条件。

（1）凸函数的一阶充要条件

几何解释：

图8

        运用几何可以很直观的解释上式的关系，总结起来就是凸函数总是在其任意一点的切线的上方，对于函数在定义域的任意取值，函数的值都大于或者等于对函数在这点的一阶近似。但是，具体在应用中，这个条件并不好用，我们不可能对每一个点都去计算函数的一阶导数，因此后面会说道利用凸函数的二阶特征来进行判断一个函数是否是一个凸函数。

（2）凸函数的二阶充要条件

        其中要求函数f二阶可微，则函数f在定义域上是凸函数的充要条件是：函数的二阶导数（即Hessian矩阵）是半正定的，也就是所有的特征值都是大于等于0的。特殊的，对于一元函数，可以退化为f′′(x)≥0。

4、凸函数的重要定理

        （1）f(x)在区间[a,b]上连续，在(a,b)内二阶可导，那么：

                         若f′′(x)>0，则f(x)是凸函数；

                         若f′′(x)<0，则f(x)是凹函数。

        即：当且仅当f(x)的二阶导数是非负的，一元二阶可微的函数在区间上是凸的。

        （2）凸函数的表述

        f(x)为凸函数，则有：

其中0<=θi<=1，θ1+θ2+  ...+θn=1

        在确定函数的凸凹性之后，可根据上式对函数进行不等式替换。

        对于复杂函数和约束函数的优化一般采用拉格朗日乘子法和KKT条件，这个将在下一篇进行介绍。