机器学习概念篇：一文详解凸函数和凸优化，干货满满

在机器学习各种优化问题中，凸集、凸函数和凸优化等概念经常出现，其是各种证明的前提条件，因此认识其性质对于优化问题的理解尤为重要，本文便就凸集、凸函数和凸优化等各种性质进行阐述

一、几何体的向量表示

在介绍凸集等概念之前，首先介绍一下空间几何体的向量表示，下面在定义凸集概念时便用到了线段的线段表示。先通过一个例子来认识一下如何使用向量表示线段

已知二维平面上两定点A(5, 1)、B(2, 3)，给出线段AB的方程表示如下：

如果将点A看成向量a，点B看成向量b，则线段AB的向量表示为：

而直线的向量表示是：

由此衍生推广到高维，可得以下几何体的向量表示，三角形的向量表示：

三维平面的向量表示：

超几何体的向量表示：

超平面的向量表示：

二、凸集凸函数定义

1、凸集

集合C内任意两点间的线段也均在集合C内，则称集合C为凸集，数学定义为：

上面凸集定义中便用到了线段的向量表示，含义是如果点x1和点x2在集合C内，则线段x1x2上所有点都在集合c内，凸集的交集仍是凸集，下面展示几个凸集示例：

2、凸函数

凸函数定义为：

则成 f(x) 为定义在凸集C上的凸函数

严格凸函数定义：设f ⊆ Rn–> R1，C是凸集，对于x1, x2∈C都有：

则成f(x)为定义在凸集C上的严格凸函数

凸函数的等价定义：设f ⊆ Rn–> R1，C是凸集，对于x1, x2, x3∈C且x1

3、凸函数定义几何解释

对于凸函数公式描述：

如下图所示，设A1、A2是凸函数曲线上的两个点，他们对应的横坐标x10且 α1+ α2=1，使得x= α1x1+ α2x2，过点x做x轴的垂线交函数于A，交直线A1A2于B点，则上式左端即为A的纵坐标，右端即为B的纵坐标：

因此，凸函数的几何含义是：函数任意两点A1和A2之间的部分位于弦A1A2的下方或曲线任一点切线上方，不严谨一个说法：割线始终位于两点间函数曲线的上方

三、凸函数各种性质及其证明

1、性质1：设 f ⊆ Rn–> R1，C是凸集，若f是凸函数，则对于∀β，证明下面水平集Dβ是凸集

证明一个集合是凸集，按照凸集性质即证明凸集中任意两点构成的线段仍然在凸集内，证明见下图：

2、性质2：凸优化问题的局部极小值是全局极小值

这个性质是凸优化问题一个良好的性质，在机器学习任务中我们只需将非凸问题转化为凸优化问题，便可直接求出问题的全局极值，下面给出证明：

我们观察下面两幅图，形象感受一下为什么凸优化问题的局部最优解是全局最优解，(1) 从下图可以看出当函数不是凸函数时，当对非凸函数f(x)进行最优化时，便可能得到局部最优解，无法获得全局最优解

(2) 从下图可以看出当目标函数可行域是非凸时，则此时对函数进行优化时也可能错过全局最优解

3、性质3：设 f ⊆ Rn–> R1，C是凸集，对于x1, x2∈C

(1) f为凸函数的充要条件是：对于∀x1, x2∈C且x1≠x2都有：

(2) f为严格凸函数的充要条件是：对于∀x1, x2∈C且x1≠x2都有：

证明过程如下：

性质3描述的凸函数一阶可微时具有的性质，下面给出该性质的几何解释

看上图，凸函数f(x)，在函数f(x)上取一点(x, f(x))做曲线的切线，切线的斜率为k，可以看出对于凸函数f(x)来说，切线始终是凸函数f(x)的下界，我们看点A、B，B是曲线上一点，A点是切线上一点，且A、B的横坐标都为y，则B点的纵坐标始终大于A点的纵坐标，于是便可得到上述性质：

当y不断逼近x时，则上式等号成立

4、性质4：凸函数其Hessian矩阵半正定

性质4描述的凸函数二阶可微时满足的性质，即凸函数Hessian矩阵半正定，此性质可通过泰勒公式进行，在给出该性质证明之前，Hessian矩阵和泰勒公式定义

Hessian矩阵是一个多元函数的二阶偏导数构成的方阵，一个多元函数Hessian矩阵定义如下：

泰勒公式是用若干项连加来表示一个函数，这些相加的项由函数在某一点的导数求得，下面给出一个函数f(x)在x=a点的泰勒展开式：

上述性质凸函数其Hessian矩阵半正定的证明如下：

5、性质5：若 x ⊆ Rn，y⊆ Rn，Q为半正定对称阵，证明f(x) = XTQX为凸函数

6、性质6：凸函数f(x)，其中Q1+Q2+…+Qn=1,0

7、Jessen不等式，f(x)为凸函数，其中E(x)是x的期望，证明：

四、凸优化定义

1、凸优化问题定义

一个凸优化问题可描述为：

通过以下凸优化性质便可理解何为凸优化问题：

(1)目的是求解目标函数的最小值；

(2)目标函数f(x)和不等式约束函数g(x)都是凸函数，定义域是凸集；

(3)若存在等式约束函数，则等式约束函数h(x)为仿射函数；仿射函数指的是最高次数为1的多项式函数，一般形式为f(x)= Ax + b，A是m*k矩阵，x是一个k向量，b是一个m向量

(4)凸优化问题有一个良好的性质即：局部最优解便是全局最优解

2、常见凸优化问题

(1) 线性规划LinearProgramming(LP)

如果目标函数和不等式约束函数都是仿射函数，则凸优化问题称为线性规划，数学表示为：

(2) 二次规划QuadraticProgramming(QP)

如果目标函数是凸二次函数，而不等式约束仍是仿射函数，则凸优化问题称为二次规划，数学表示为：

(3) 二次约束的二次规划Quadratically Constrained Quadratic Programming(QCQP)

如果目标函数和不等书约束均为凸二次函数，则凸优化问题称为二次约束的二次规划，数学表示为：

(4) 半正定规划Semidefinite Programming(SDP)

半正定规划较前面的复杂，在机器学习中也经常用到，下面给出数学描述：

其中符号tr(A)表示矩阵A的迹，矩阵A的迹是指A的对角线上各个元素的总和

五、浅谈凸优化问题为何如此重要

1、凸优化具有良好性质，如局部最优解是全局最优解，且凸优化问题是多项式时间可解问题，如：线性规划问题；

2、很多非凸优化或NP-Hard问题可以转化成凸优化问题，方法：对偶、松弛(扩大可行域，去掉部分约束条件)，在SVM算法中，为了对目标函数进行优化，便使用了拉格朗日乘子法、对偶问题、引入松弛因子等

欢迎转载，转载请注明出处【机器学习与TensorFlow实战】 作者【CHEONG】，谢谢！博文每周一更新，欢迎大家交流！