机器学习笔记之最优化理论与方法(四) 凸函数：定义与基本性质

引言

本节将介绍凸函数定义及其基本性质。

本文是关于梯度下降法：凸函数$\text{VS}$强凸函数的逻辑补充。涉及的证明过程如：

• 凸函数的一阶条件；
• 凸函数的梯度单调性；
• 凸函数的二阶条件

详见上述链接。

凸函数的定义

关于凸函数的基本定义表示如下：
假设$\mathcal{C}$是非空凸集，$f(\cdot )$是定义在$\mathcal{C}$上的函数，如果对于$\forall x,y\in \mathcal{C}$且$\alpha \in (0,1)$，均有：
关于凸集的概念、基本性质、凸组合详见凸集的简单认识。
$$f[\alpha \cdot x+(1-\alpha )\cdot y]\le \alpha \cdot f(x)+(1-\alpha )\cdot f(y)$$
则称函数$f(\cdot )$为凸集$\mathcal{C}$上的凸函数。

• 观察不等式左侧：其中$\alpha \cdot x+(1-\alpha )\cdot y$是点$x,y$的凸组合，也就是连接点$x,y$的线段上的点；而$f[\alpha \cdot x+(1-\alpha )\cdot y]$则表示连接点$x,y$线段上点的函数值。
• 观察不等式右侧：同左侧，它描述的是：点$f(x),f(y)$的凸组合，并始终满足小于等于的关系。

凸函数的几何意义解释如下图所示：

• 很明显，橙色点相比于黄色点对应的函数值要小。
• 当$x,y$两点重合时，上式取等。
  
  相反，某函数的函数图像表示如下：
  在$x,y$这种取值的情况下，并不满足上述函数。因而该函数不是一个凸函数。
  

严格凸函数

严格凸函数是在凸函数的基础上增加了相关要求。它的定义方式仅将凸函数的定义修改为：
从而对$x,y\in \mathcal{C}$条件下增加了新的要求：点$x,y$不能重合。
$$f[\alpha \cdot x+(1-\alpha )\cdot y]<\alpha \cdot f(x)+(1-\alpha )\cdot f(y)$$
很明显，上面描述的第一个图像对应的函数是严格凸函数；相反：什么样的函数是凸函数，但不是严格凸函数$?$例如线性函数$f(x)=x$，它的函数图像就是一条直线：

上述函数完全满足凸函数的定义；但不满足严格凸函数的定义。

凸函数的推论：凹函数

如果从定义的角度表述，那么凹函数的定义方式仅将凸函数的定义修改为：
其他条件不变~
$$f[\alpha \cdot x+(1-\alpha )\cdot y]\ge \alpha \cdot f(x)+(1-\alpha )\cdot f(y)$$
同上，凹函数的函数图像示例如下：

从凸函数的角度观察，可以得到推论：若$-f(\cdot )$是凸函数，则$f(\cdot )$是凹函数。
延伸：如果是关于凹函数$f(x)$的优化问题，如$\max f(x)$;可以将其转化为相应凸函数的优化问题：$\min -f(x)$。

常见凸函数

常见凸函数有如下几种：

• 线性函数：$f(x)={\mathcal{A}}^{T}x+b$；需要注意的是：线性函数是唯一一类既是凸函数，也是凹函数的函数。
• 二次函数：它由二次型$x^T\mathcal{Q}x$与线性函数${\mathcal{A}}^{T}x+b$组成：
  $$f(x)=x^T\mathcal{Q}x+{\mathcal{A}}^{T}x+b$$
  其中$\mathcal{Q}\in {\mathcal{S}}_{+}^n$。在凸集的简单认识(上)中介绍过，${\mathcal{S}}_{+}^n$描述的可行域是半定矩阵锥：所有$n$阶半正定矩阵组成的集合：
  其中集合${\mathcal{S}}^n$描述所有$n$阶对称矩阵组成的集合。
  S + n { X ∈ S n ∣ X ≽ 0 } \mathcal S_{+}^n \{\mathcal X \in \mathcal S^n \mid \mathcal X \succcurlyeq 0\} S+n​{X∈Sn∣X≽0}
  并且${\mathcal{S}}_{+}^n$是一个凸集；也就是说：矩阵$\mathcal{Q}$必然至少是一个半正定矩阵。相反，如果对称矩阵$\mathcal{Q}$的特征值存在负值(如不定矩阵)甚至是负定矩阵，那么对应二次型$x^T\mathcal{Q}x$展开后其二次项系数可能是负值，对应的二次函数就不是凸函数。
• 最小二乘函数：在线性回归一节中介绍了最小二乘法$(\text{Least Square Method})$：它通常在线性回归任务中描述模型预测结果与真实标签之间差异性的考量：
  $$\mathcal{L}(\mathcal{W})=\sum _{i=1}^N\Vert {\mathcal{W}}^T{x}^{(i)}-y^{(i)}{\Vert }_2^2$$
  其中$(x^{(i)},y^{(i)})\in \mathcal{D}=\{(x^{(i)},y^{(i)}){\}}_{i=1}^N$。而最小二乘函数定义为如下形式：
  $$f(x)=\Vert \mathcal{A}x-b{\Vert }_2^2$$
  实际上，该函数可将其描述为二次函数：
  $$\begin{array}{rl}f(x)& =\Vert \mathcal{A}x-b{\Vert }_2^2\\ & =(\mathcal{A}x-b{)}^T(\mathcal{A}x-b)\\ & =(\mathcal{A}x{)}^T\mathcal{A}x-b^T\mathcal{A}x-(\mathcal{A}x{)}^{T}b+b^{T}b\\ & =x^T{\mathcal{A}}^T\mathcal{A}x+b^T\mathcal{A}x-x^T{\mathcal{A}}^{T}b+b^{T}b\end{array}$$
  很明显，对应上式中的二次型是：$x^T{\mathcal{A}}^T\mathcal{A}x$，而矩阵${\mathcal{A}}^T\mathcal{A}$必然至少是一个半正定矩阵。因此：最小二乘函数一定是凸函数。
• $m$范数函数：在正则化——拉格朗日乘数法角度中介绍过明可夫斯基距离$(\text{Minikowski Distance})$。关于向量$x^{(i)}\in {\mathbb{R}}^p$与$p$维空间原点之间的明可夫斯基距离表示如下：
  $$\Vert x^{(i)}{\Vert }_p={\left[\sum _{k=1}^p|x_k^{(i)}-0{|}^m\right]}^{\frac{1}{m}}$$
  可以将上述函数描述为关于向量$x^{(i)}$的函数$f[x^{(i)}]$：
  $$f(x)={\left[\sum _{k=1}^p|x_k{|}^m\right]}^{\frac{1}{m}}$$
  其中关于$m\ge 0$时，函数$f(x)$在$m$不同取值的函数图像示例表示如下：
  其中当$m=0$时，$f(x)=\Vert x{\Vert }_0$即$x$非零分量的个数。它是一个非凸函数~
  
  根据凸函数定义可以看出：当$m\ge 1$时，该函数是凸函数；该函数围城的区域是凸集。因而，在$m\ge 1$时，$m$范函数才是凸函数。

凸函数的基本性质

• 如果$f(x)$是凸函数，那么$f(x)$自身在其定义域内一定是连续函数。

• 如果$f(x)$是凸函数 $\iff \forall x,y\in {\mathbb{R}}^n$，一元函数$\varphi (\alpha )$表示如下：
  $$\varphi (\alpha )=f(x+\alpha \cdot y)$$
  并且该函数是凸函数。

  如果从几何意义的角度解释：由于向量$x,y$已知，那么向量$x+\alpha \cdot y$可看作是：从向量$x$所在位置出发，沿着向量$y$的方向，移动一段距离后的向量结果。只不过这个距离由$\alpha$控制。对应图像表示如下：

  • 如果$\alpha$是负值,相当于沿着向量$y$的反方向移动相应的距离。
  • 下图中的$y$更多表示移动的方向;而$\alpha \in \mathbb{R}$控制移动的距离。

  那么关于$\varphi (\alpha )=f(x+\alpha \cdot y)$它的函数图像示例如下：
  其中黄色平面描述$x+\alpha \cdot y$的函数图像，而$f(x+\alpha \cdot y)$则表示$x+\alpha \cdot y$的函数图像与凸函数$f(\cdot )$对应函数图像切面产生的图像黄色虚线，可以看出，这个切面图像也是一个凸函数。
  

• 凸函数的一阶条件：$f(x)$是$\mathcal{C}$上的凸函数充要条件是：
  $$f(y)\ge f(x)+[\nabla f(x){]}^T(y-x)\forall x,y\in \mathcal{C}$$
  该条件的几何图像描述表示如下：
  假设将$x$固定住，此时$\nabla f(x)$是一个常量，它表示函数$f(\cdot )$在$x$点处的斜率从而不等式右侧是关于$y$的一次函数，并且经过点$[x,f(x)]$。可以发现:$f(y)$的图像总是在$\varphi (y)$的上方(可以重合)。
  
  相反，非凸函数并不具备这个性质。示例如下：
  此时$f(y)<\varphi (y)$。
  
  其证明过程见开头链接，这里不再赘述。

• 凸函数的二阶条件：假设$\mathcal{C}\subset {\mathbb{R}}^n$是非空开凸集，并且函数$f(x)$在$\mathcal{C}$上二阶连续可微，则有：
  $$f(x)\text{ is Convex }\iff {\nabla }^{2}f(x)\succcurlyeq 0,\forall x\in \mathcal{C}$$
  如果$x$是一个标量，那么它关于函数$f(\cdot )$在$x$点处的$\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(x)$则退化成二阶导数$f^{\prime \prime }(x)$。这意味着：$f^{\prime \prime }(x)\ge 0\Rightarrow f^{\prime }(x)$的变化率随着$x$的增加，处于一个增加/稳定的状态。

  同上，这里的证明见开头链接，这里不再赘述。

几种保持函数凸性的运算

在函数$f(x)$是凸函数的基础上，对$f(x)$执行一些运算/变换，运算结果其凸函数性质保持不变。

• 透视函数$(\text{Perspective Function})$：若$f(x)$是凸函数，$x\in {\mathbb{R}}^n$。令：
  此时$\mathcal{G}(\cdot )$函数内的变量有$n+1$个。
  $$\mathcal{G}(x,t)=t\cdot f\left(\frac{x}{t}\right)t>0$$
  则$\mathcal{G}(x,t)$也是凸函数。
  这里假设$f(x)$是一元函数，且$f(x)=x^2$，那么对应的$\begin{array}{r}\mathcal{G}(x,t)=\frac{x^2}{t}\end{array}$。该二元函数对应的函数图像表示如下：
  即虚线描述的范围，如一个展开的光幕~凑合看吧。其中$[0,1]$的部分这里没有表示~
  
• 非负组合：若$f_i(x)(i=1,2,\cdots ,m)$均是凸函数，对于${\mathcal{W}}_i\ge 0(i=1,2,\cdots ,m)$，有：
  $$\mathcal{G}(x)=\sum _{i=1}^m{\mathcal{W}}_i\cdot f_i(x)$$
  那么$\mathcal{G}(x)$是凸函数。
  可以观察$\mathcal{G}(x)$函数在$x$点处的$\text{Hessian Matrix}\Rightarrow {\nabla }^2\mathcal{G}(x)$：
  $${\nabla }^2\mathcal{G}(x)=\sum _{i=1}^m{\mathcal{W}}_i\cdot {\nabla }^2{f}_i(x)$$
  很明显，${\nabla }^2{f}_i(x)(i=1,2,\cdots ,m)$必然是半正定的；各${\nabla }^2{f}_i(x)$对应的线性组合$({\mathcal{W}}_i\ge 0)$，其最终结果必然也是半正定的。
• 一组凸函数求最大值：已知$f_i(x)(i=1,2,\cdots ,m)$是凸函数，有：
  G ( x ) = max ⁡ { f i ( x ) } i = 1 , 2 , ⋯ , m \mathcal G(x) = \max \{f_i(x)\} \quad i=1,2,\cdots,m G(x)=max{fi​(x)}i=1,2,⋯,m
  那么$\mathcal{G}(x)$是凸函数。示例图像表示如下：
  求最大值实际上是求交集的一种情况。
  

凸集与凸函数之间的关联关系

• 工具$1$ - 水平集。其定义对应数学符号描述表示如下：
  L a = { x ∣ f ( x ) ≤ a , x ∈ C } \mathcal L_a = \{x \mid f(x) \leq a,x \in \mathcal C\} La​={x∣f(x)≤a,x∈C}
  任意函数都可以定义水平集，其中$a$被称作水平值。以二元凸函数为例，给定水平集$a$，相当于水平集所描述平面横截二元函数图像，并将处在水平集下方的函数图像进行投影。对应图像表示如下：
  
  可以明显观察到：投影产生的集合明显是一个凸集。可以使用凸集定义进行证明：

  • 假设$f(\cdot )$是凸函数，存在值$a$，其水平集表示为${\mathcal{L}}_a$。
  • $\forall x,y\in {\mathcal{L}}_a;\forall \lambda \in [0,1]$，仅需要判断：$\lambda \cdot x+(1-\lambda )\cdot y$是否也在${\mathcal{L}}_a$内即可。观察$f[\lambda \cdot x+(1-\lambda )\cdot y]$的结果：
    $$f[\lambda \cdot x+(1-\lambda )\cdot y]\le \lambda \cdot f(x)+(1-\lambda )\cdot f(y)$$
    由于$f(x)\le a$且$f(y)\le a$因而$\lambda \cdot f(x)+(1-\lambda )\cdot f(y)\le a$恒成立。从而$\lambda \cdot x+(1-\lambda )\cdot y$也在${\mathcal{L}}_a$内。因而${\mathcal{L}}_a$必然是一个凸集。
    \quad

  相反呢$?$如果任意取$a$，函数$f(x)$对应的水平集均是凸集，那么$f(\cdot )$是否为凸函数$?$不一定。如下图描述的函数：
  

• 工具$2$ - $\text{EpiGragh}$。关于函数$f(x)$的$\text{EpiGragh}$定义表示如下：
  $$\text{Epi}(f)=\left\{\left(\begin{array}{c}x\\ y\end{array}\right)\mid f(x)\le y,x\in \mathcal{C}\right\}$$
  其中$y$是一个变量，仅满足：$f(x)\le y$即可。很明显，若$x\in {\mathbb{R}}^n$，那么$\left(\begin{array}{c}x\\ y\end{array}\right)$是一个$n+1$维向量。而$\text{Epi(f)}$就是由该向量组成的集合。如果$f(x)$是一个一维函数，那么它对应的$\text{EpiGragh}$示例如下：
  由于$y$进满足$f(x)\le y$即可，因此阴影部分可以无限向上延伸$(y\Rightarrow \infty )$，这里没有画出来。
  
  其中阴影部分即$\text{Epi(f)}$描述的集合。很明显，它比$x$要高一维。

  关于$\text{EpiGraph}$的一个充要条件：
  $$f(\cdot )\text{ is Convex Function}\iff \text{Epi}(f)\text{ is Convex Set}$$

$\text{Reference}$：
最优化理论与方法-第三讲-凸函数：定义与基本性质