引言

本节将介绍凸函数、强凸函数以及它们之间的联系(补梯度下降法：总体介绍中的坑)。

凸函数：

凸函数的定义与判定条件

关于凸函数的定义表示如下：设$f(\cdot )$为定义在空间$\mathcal{I}$上的函数，若对$\mathcal{I}$上的任意两点$x_1,x_2$与任意实数$\lambda \in (0,1)$总有：
通常将空间$\mathcal{I}$设置为实数域与空间$\Rightarrow {\mathbb{R}}^n$。
$$f[\lambda \cdot x_2+(1-\lambda )\cdot x_1]\le \lambda \cdot f(x_2)+(1-\lambda )\cdot f(x_1)$$
则称：函数$f(\cdot )$为$\mathcal{I}$上的凸函数。对应示例图像表示如下：
将其转化:$\lambda \cdot x_2+(1-\lambda )\cdot x_1=x_1+\lambda \cdot (x_2-x_1)$,那么$\lambda (x_2-x_1)$可看作增量，而$\lambda$可看作控制增量的参数。

凸函数的一种判定条件：构造一个函数$\mathcal{G}(t)$，满足：
$$\mathcal{G}(t)\triangleq f(x+v\cdot t)\forall x,v\in {\mathbb{R}}^n,t\in \mathbb{R}$$
则有推论：$f(\cdot )$是凸函数 $\iff \mathcal{G}(t)$是凸函数。在一般情况下，我们面对的权重空间是一个高维空间，而在高维空间中的目标函数$f(\cdot )$也通常是一个高维函数。假设：权重空间是一个$2$维空间，对应的目标函数$f(\cdot )$也是一个$2$维函数：
即：输入变量的维度是$2$维，而目标函数的输出结果是$1$维标量。
$$f(\cdot ):{\mathbb{R}}^2\mapsto \mathbb{R}$$
那么如何验证$f(\cdot )$描述的图像在高维空间中的曲面是否为凸的$?$在介绍方向导数中提到：关于某一点$(x_0,y_0)$关于函数$f(\cdot )$在方向$\vec{l}$的方向导数 ∂ Z ∂ l ⃗ ∣ ( x 0 , y 0 )

$$egin{aligned}frac{partial mathcal Z}{partial vec l}|_{(x_0,y_0)}end{aligned}$$ ∂l ∂Z​∣(x0​,y0​)​​表示为下图中在$\vec{l}$方向上过$(x_0,y_0)$做一个垂直于$\mathcal{X}\mathcal{O}\mathcal{Y}$的平面，平面与$f(\cdot )$相交的图像在$(x_0,y_0)$处的斜率结果：

• 其中黄色菱形部分表示垂直于$\mathcal{X}\mathcal{O}\mathcal{Y}$平面在$\vec{l}$方向上并过$(x_0,y_0)$黄色点的平面;红色点则表示$(x_0,y_0)$在函数$f(\cdot )$上的结果;而黑色实线则表示过映射点与函数图像相切的直线，其斜率即方向导数$\begin{array}{r}\frac{\partial \mathcal{Z}}{\partial \vec{l}}{|}_{(x_0,y_0)}\end{array}$。

但这里我们并不关注方向导数，而是关注平面与函数图像之间相交所产生的截线的形状。可以观察上述图像对应的俯视图结果：
无论是上图还是俯视图，都没有对$f(x,y)$进行完全表示，这仅仅是其中一部分图像。

从俯视图角度可以看到：黄色截面简化成了一条直线。这实际上可看做上述判定条件中函数$x+v\cdot t$的某一种结果。而对应的$f(x+v\cdot t)$则表达：截面与函数图像之间相交产生的截线。

如果从向量的角度认识，以下面红色直线为例：

其中$x,v$是任意${\mathbb{R}}^n$的向量，从而$x+v\cdot t$可表示为该图黑色虚线的结果。由于$t\in \mathbb{R}$，如果我们将所有的$t$全部取到，那么最终构成$x+v\cdot t$构成向量的集合就是红色直线的结果。

• 关于向量$v$,我们通常将其视作单位向量。因为即便不是单位向量，在转化为单位向量过程中得到的标量系数$k$也可以与$t$进行合并:$t\in \mathbb{R}\Rightarrow k\cdot t\in \mathbb{R}$。
• 如果将$v$看作单位向量$\vec{e}(\cos \alpha ,\cos \beta )$,那么过点$\mathcal{P}(x_0,y_0)$，并且方向与$\vec{e}$平行的直线参数方程可表示为：
  $$\mathcal{Y}=(x_0,y_0)+t\cdot \vec{e}=(x_0,y_0)+t\cdot (\cos \alpha ,\cos \beta )$$

因此，关于该判定条件的另一种表达有：如果$x+v\cdot t$在该权重空间中描述的任意一个截面，其与函数$f(\cdot )$相交产生的任意一条截线对应的函数均是凸函数，那么函数$f(\cdot )$也是一个凸函数，反之同理。
这是一个充分必要条件。

凸函数的一阶条件

在函数$f(\cdot )$可微的条件下，有：
相比于上述的定义与判定条件，并没有要求函数$f(\cdot )$一定是可微的。也就是说：一个函数是凸函数，并不要求该函数一定可微。
$$f(\cdot )\text{ is Convex}\iff f(x_2)\ge f(x_1)+[\nabla f(x_1){]}^T\cdot (x_2-x_1)$$
这是一个充分必要条件。可以在图像中看到这个现象：

$(\text{2023/8/10})$补充
证明：充分性

• 要证：$f[\lambda \cdot x_1+(1-\lambda )\cdot x_2]\le \lambda \cdot f(x_1)+(1-\lambda )\cdot f(x_2),\forall x_1,x_2\in \mathcal{C},\lambda \in (0,1)$
• 将$\lambda \cdot x_1+(1-\lambda )\cdot x_2$记作$\mathcal{Z}$，从而有：$\mathcal{Z}\in \mathcal{C}$。既然$\mathcal{Z}$同样是定义域$\mathcal{C}$上一点，根据假设条件必然有：
  $$\{\begin{array}{ll}f(x_1)& \ge f(\mathcal{Z})+[\nabla f(\mathcal{Z}){]}^T\cdot (x_1-\mathcal{Z})\\ f(x_2)& \ge f(\mathcal{Z})+[\nabla f(\mathcal{Z}){]}^T\cdot (x_2-\mathcal{Z})\end{array}$$
• 将上述两个不等式的左右两端分别乘以$\lambda ,1-\lambda$。由于$\lambda \in (0,1)$，因而不等式符号不发生变化：
  $$\{\begin{array}{l}\begin{array}{rl}\lambda \cdot f(x_1)& \ge \lambda \cdot f(\mathcal{Z})+\lambda [\nabla f(\mathcal{Z}){]}^T\cdot (x_1-\mathcal{Z})\\ (1-\lambda )\cdot f(x_2)& \ge (1-\lambda )\cdot f(\mathcal{Z})+(1-\lambda )\cdot [\nabla f(\mathcal{Z}){]}^T\cdot (x_2-\mathcal{Z})\end{array}\end{array}$$
  将上述两不等式对应位置相加，有：
  $$\begin{array}{rl}\lambda f(x_1)+(1-\lambda )\cdot f(x_2)& \ge (\lambda +1-\lambda )\cdot f(\mathcal{Z})+[\nabla f(\mathcal{Z}){]}^T\cdot [(\lambda \cdot x_1-\lambda \cdot \mathcal{Z})+(1-\lambda )\cdot x_2-(1-\lambda )\cdot \mathcal{Z}]\\ & \ge f(\mathcal{Z})+[\nabla f(\mathcal{Z}){]}^T\cdot [\lambda \cdot x_1+(1-\lambda )\cdot x_2-\mathcal{Z}]\end{array}$$
  由于：$\lambda \cdot x_1+(1-\lambda )\cdot x_2$记作$\mathcal{Z}$，因此后一项：$[\nabla f(\mathcal{Z}){]}^T\cdot [\lambda \cdot x_1+(1-\lambda )\cdot x_2-\mathcal{Z}]=0$。最后将$\mathcal{Z}$带入，整理有：
  这正是凸函数的定义。
  $$\lambda f(x_1)+(1-\lambda )\cdot f(x_2)\ge f(\mathcal{Z})=f[\lambda \cdot x_1+(1-\lambda )\cdot x_2]$$

证明：必要性

• 在已知$f(\cdot )$是凸函数的条件下：
  即便将$x_1,x_2$调换位置，也不会影响公式的成立。
  $$f[\lambda \cdot x_2+(1-\lambda )\cdot x_1]\le \lambda \cdot f(x_2)+(1-\lambda )\cdot f(x_1)x_1,x_2\in \mathcal{C};\lambda \in (0,1)$$

  • 观察不等式左侧，有：
    $$f[\lambda \cdot x_2+(1-\lambda )\cdot x_1]=f[x_1+\lambda \cdot (x_2-x_1)]$$
  • 观察不等式右侧，有：
    $$\lambda \cdot f(x_2)+(1-\lambda )\cdot f(x_1)=f(x_1)+\lambda \cdot [f(x_2)-f(x_1)]$$

  最终将上式整理得：
  将$f(x_2)$以外的其他项移到不等号左侧，不等号不发生变化。
  $$\frac{f[x_1+\lambda \cdot (x_2-x_1)]-f(x_1)}{\lambda }+f(x_1)\le f(x_2)$$

• 对项$f[x_1+\lambda \cdot (x_2-x_1)]$关于$x_1$进行泰勒展开：
  其中$\mathcal{O}(\cdot )$表示高阶无穷小。
  f [ x 1 + λ ⋅ ( x 2 − x 1 ) ] = f ( x 1 ) + 1 1 ! λ ⋅ [ ∇ f ( x 1 ) ] T ( x 2 − x 1 ) + O ( λ ⋅ ∣ ∣ x 2 − x 1 ∣ ∣ )

  $$egin{aligned} f[x_1 + lambda cdot (x_2 - x_1)] = f(x_1) + frac{1}{1!}lambda cdot [ abla f(x_1)]^T (x_2 - x_1) + mathcal O(lambda cdot ||x_2 - x_1||) end{aligned}$$ f[x1​+λ⋅(x2​−x1​)]=f(x1​)+1!1​λ⋅[∇f(x1​)]T(x2​−x1​)+O(λ⋅∣∣x2​−x1​∣∣)​
  将上式的$f(x_1)$移至等号左侧，并将等式左右两侧同时除以$\lambda$，有：
  $$\frac{f[x_1+\lambda \cdot (x_2-x_1)]-f(x_1)}{\lambda }=[\nabla f(x_1){]}^T(x_2-x_1)+\frac{\mathcal{O}(\lambda \cdot ||x_2-x_1||)}{\lambda }$$
  由于$\lambda \in (0,1)$，因此这里令$\lambda \Rightarrow 0$，有：
  关于$\begin{array}{r}\underset{\lambda \Rightarrow 0}{\lim }\frac{\mathcal{O}(\lambda \cdot ||x_2-x_1||)}{\lambda }\end{array}$,其中分子是关于$\lambda$的高阶无穷小，而分子仅是一阶。因此该项分子趋近$0$的速度要快于分母，从而为$0$。
  $$\frac{f[x_1+\lambda \cdot (x_2-x_1)]-f(x_1)}{\lambda }=[\nabla f(x_1){]}^T(x_2-x_1)$$

• 将该式带入到上述步骤，有：
  $$[\nabla f(x_1){]}^T(x_2-x_1)+f(x_1)\le f(x_2)$$

凸函数的梯度单调性

在函数$f(\cdot )$可微的条件下，$[\nabla f(x)-\nabla f(y)]$与$x-y$之间同号。即：
$$f(\cdot )\text{ is Convex }\iff [\nabla f(x)-\nabla f(y){]}^T(x-y)\ge 0$$

证明：必要性
如果$f(\cdot )$是可微的凸函数，根据凸函数的一阶条件，有：
{ f ( y ) ≥ f ( x ) + [ ∇ f ( x ) ] T ⋅ ( y − x ) f ( x ) ≥ f ( y ) + [ ∇ f ( y ) ] T ⋅ ( x − y )

$$egin{cases} egin{aligned} f(y) geq f(x) + [ abla f(x)]^T cdot (y - x) \ f(x) geq f(y) + [ abla f(y)]^T cdot (x - y) end{aligned} end{cases}$$ {f(y)≥f(x)+[∇f(x)]T⋅(y−x)f(x)≥f(y)+[∇f(y)]T⋅(x−y)​​
将上述式子相加，有：
$$[\nabla f(x)-\nabla f(y){]}^T\cdot (x-y)\ge 0$$
证明：充分性
如果$f(\cdot )$的梯度$\nabla f(\cdot )$是单调的，定义关于$t\in [0,1]$的函数$\mathcal{G}(t)$：
$$\mathcal{G}(t)=f[x+t\cdot (y-x)]$$
对应$\mathcal{G}(t)$的导数${\mathcal{G}}^{\prime }(t)$：
$${\mathcal{G}}^{\prime }(t)=[\nabla f(x+t\cdot (y-x)){]}^T\cdot (y-x)$$
由于${\mathcal{G}}^{\prime }(t)$在$t\in [0,1]$上连续，且：
$$[\nabla f(x)-\nabla f(y){]}^T\cdot (x-y)\ge 0$$
从而有：
消了两个负号~
$${\mathcal{G}}^{\prime }(t)\ge {\mathcal{G}}^{\prime }(0)\Leftarrow \{\begin{array}{l}{\mathcal{G}}^{\prime }(1)-{\mathcal{G}}^{\prime }(0)=[\nabla f(y)-\nabla f(x){]}^T\cdot (y-x)\ge 0\\ {\mathcal{G}}^{\prime }(0)-{\mathcal{G}}^{\prime }(0)=0\end{array}$$
最终有：
$$f(y)=\mathcal{G}(1)=\mathcal{G}(0)+{\int }_0^1{\mathcal{G}}^{\prime }(t)dt\ge \mathcal{G}(0)+{\mathcal{G}}^{\prime }(0)=f(x)+[\nabla f(x){]}^T(y-x)$$
即：$f(\cdot )$为凸函数。

凸函数的二阶条件

在函数$f(\cdot )$二阶可微的条件下，说明关于$f(\cdot )$的二阶梯度${\nabla }^{2}f(\cdot )$存在，即对应的$\text{Hessian Matrix}$存在。从而有该矩阵是一个半正定矩阵：
简单注意一下，这里的$0$指的是$0$矩阵。
$$f(\cdot )\text{ is Convex }\iff {\nabla }^{2}f(x)\succcurlyeq 0$$
$(2023/8/10)$补充
证明：充分性
已知$\text{Hessian Matrix}$是半正定矩阵$({\nabla }^{2}f(x)\succcurlyeq 0,\forall x\in \mathcal{C})$：

• 基于$y\in \mathcal{C}$，针对$f(y)$关于某点$x$进行泰勒展开：
  • 其中$\xi$表示$(x,y)$范围内的一点，标准表示：$\xi =x+\lambda \cdot (y-x);\lambda \in (0,1)$
  • 不否认$\xi \in \mathcal{C}$。
    $$f(y)=f(x)+\frac{1}{1!}[\nabla f(x){]}^T(y-x)+\frac{1}{2!}(y-x{)}^T[{\nabla }^{2}f(\xi )](y-x)+\mathcal{O}(\cdot )$$
• 由于${\nabla }^{2}f(\xi )\succcurlyeq 0$，必然有：
  $$f(y)\ge f(x)+[\nabla f(x){]}^T(y-x)$$
• 根据上述凸函数的一阶条件，自然得证：$f(\cdot )$是凸函数。

证明：必要性
已知$f(\cdot )$是凸函数，要证：${\nabla }^{2}f(x)\succcurlyeq 0,\forall x\in \mathcal{C}$。

• 从定义域$\mathcal{C}$中任取一点$x$，观察：从$x$开始，沿着$d$方向移动了较小步长$\alpha$后位置的函数结果$f(x+\alpha \cdot d)$，并针对该结果关于$x$进行泰勒展开：
  其中$x+\alpha \cdot d\in \mathcal{C}$。
  $$f(x+\alpha \cdot d)=\underset{一阶条件}{\underbrace{f(x)+\frac{1}{1!}\alpha \cdot [\nabla f(x){]}^{T}d}}+\frac{1}{2!}{\alpha }^2\cdot d^T[{\nabla }^{2}f(x)]\cdot d+\mathcal{O}({\alpha }^2\cdot ||d|{|}^2)$$
• 根据凸函数的一阶条件，必然有：
  这依然依赖移动后的结果依然$\in \mathcal{C}$。
  $$f(x+\alpha \cdot d)\ge f(x)+\alpha \cdot [\nabla f(x){]}^{T}d$$
  将该结果带入上式，有：
  $$\frac{1}{2!}{\alpha }^2\cdot d^T[{\nabla }^{2}f(x)]\cdot d+\mathcal{O}({\alpha }^2\cdot ||d|{|}^2)\ge 0$$
• 将不等式两侧同时除以${\alpha }^2$，不等式符号不发生变化：
  $$\frac{1}{2}{d}^T[{\nabla }^{2}f(x)]\cdot d+\frac{\mathcal{O}({\alpha }^2\cdot ||d|{|}^2)}{{\alpha }^2}\ge 0$$
  在此基础上，令$\alpha \Rightarrow 0$，最终有：
  • 与凸函数一阶条件证明中的情况相似，其分子趋近$0$远远高于分母，因而有：$\begin{array}{r}\underset{\alpha \Rightarrow 0}{\lim }\frac{\mathcal{O}({\alpha }^2\cdot ||d|{|}^2)}{{\alpha }^2}=0\end{array}$
  • 系数$\begin{array}{r}\frac{1}{2}\end{array}$被忽略了~
    $$d^T[{\nabla }^{2}f(x)]\cdot d\ge 0$$

这实际上就是半正定矩阵的定义。
从几何意义的角度观察，当$\alpha \Rightarrow 0$时，方向$d$任意取都不会影响$d^T[{\nabla }^{2}f(x)]\cdot d\ge 0$,这说明$[{\nabla }^{2}f(x)]$是半正定的。

强凸函数

强凸函数的定义

关于强凸函数的定义表示如下：设$f(\cdot )$为定义在空间$\mathcal{I}$上的函数，若存在$m>0$，使其对$\mathcal{I}$上的任意两点$x_1,x_2$与任意实数$\lambda \in (0,1)$总有：
$$\lambda \cdot f(x_1)+(1-\lambda )\cdot f(x_2)\ge f[\lambda \cdot x_1+(1-\lambda )\cdot x_2]+\frac{m}{2}\cdot \lambda (1-\lambda )\cdot ||x_1-x_2|{|}^2$$
相比于凸函数的定义，强凸函数明显多了一个部分： m 2 ⋅ θ ( 1 − θ ) ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ 2

$$egin{aligned}frac{m}{2} cdot heta(1 - heta) cdot ||x_1 -x _2||^2end{aligned}$$ 2m​⋅θ(1−θ)⋅∣∣x1​−x2​∣∣2​。并且这个部分一定是正数。这相比凸函数仅仅$\ge 0$的约束要更强。
也被称作$m$-强凸，其与凸函数定义的本质区别是相比凸函数多了一个$>0$下界的保证。

强凸函数的判定条件

和凸函数的判定条件相类似，关于强凸的判定条件同样没有直接对$f(\cdot )$进行描述。对应条件表示如下：

• 定义$\begin{array}{r}\mathcal{G}(x)\triangleq f(x)-\frac{1}{2}m\cdot ||x|{|}^2\end{array}$，有：
  $$f(\cdot )\text{ is m-Strong Convex }\iff \mathcal{G}(x)\text{ is Convex}$$

强凸函数的一阶条件

关于强凸函数的一阶条件是在对应凸函数一阶条件的基础上，加入一个二次下界：
和$f(\cdot )$梯度满足利普希兹连续对应的二次上界引理不同：
$$\nabla f(\cdot )\text{ Lipschitz}\iff f(x_2)\le f(x_1)+[\nabla f(x_1){]}^T(x_2-x_1)+\frac{\mathcal{L}}{2}||x_2-x_1|{|}^2$$
利普希兹连续强调的是限制梯度变化量的上界；而$m$-强凸强调一个$>0$的二次下界。
$$f(\cdot )\text{ is m-Strong Convex }\iff f(x_2)\ge f(x_1)+[\nabla f(x_1){]}^T(x_2-x_1)+\frac{m}{2}||x_2-x_1|{|}^2$$

强凸函数的梯度单调性

和凸函数的梯度单调性基本类似，只不过下界由$0$换成了：
证明过程略。
$$f(\cdot )\text{ is m-Strong Convex }\iff [\nabla f(x)-\nabla f(y){]}^T(x-y)\ge m\cdot ||x-y|{|}^2$$

强凸函数的二阶条件

在$f(\cdot )$二阶可微的条件下，有：
其中$\mathcal{I}$指单位矩阵。
$$f(\cdot )\text{ is m-Strong Convex }\iff {\nabla }^{2}f(x)\succcurlyeq m\cdot \mathcal{I}$$

相关参考：
【优化算法】梯度下降法-基础补充-凸函数vs强凸函数vs严格凸函数（上）
【优化算法】梯度下降法-基础补充-凸函数vs强凸函数vs严格凸函数（下）
最优化理论与方法-第三讲-凸函数：定义与基本性质