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

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

一、几何体的向量表示

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

已知二维平面上两定点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】,谢谢!博文每周一更新,欢迎大家交流!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181029G1TU5S00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券