机器学习笔记之优化算法(十二)梯度下降法:凸函数VS强凸函数

机器学习笔记之优化算法——梯度下降法:凸函数VS强凸函数

  • 引言
    • 凸函数:
      • 凸函数的定义与判定条件
      • 凸函数的一阶条件
      • 凸函数的梯度单调性
      • 凸函数的二阶条件
    • 强凸函数
      • 强凸函数的定义
      • 强凸函数的判定条件
      • 强凸函数的一阶条件
      • 强凸函数的梯度单调性
      • 强突函数的二阶条件

引言

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

凸函数:

凸函数的定义与判定条件

关于凸函数的定义表示如下: f ( ⋅ ) f(\cdot) f()为定义在空间 I \mathcal I I上的函数,若对 I \mathcal I I上的任意两点 x 1 , x 2 x_1,x_2 x1,x2任意实数 λ ∈ ( 0 , 1 ) \lambda \in (0,1) λ(0,1)总有
通常将空间 I \mathcal I I设置为实数域与空间 ⇒ R n \Rightarrow \mathbb R^n Rn
f [ λ ⋅ x 2 + ( 1 − λ ) ⋅ x 1 ] ≤ λ ⋅ f ( x 2 ) + ( 1 − λ ) ⋅ f ( x 1 ) f[\lambda \cdot x_2 + (1 - \lambda) \cdot x_1] \leq \lambda \cdot f(x_2) + (1 - \lambda) \cdot f(x_1) f[λx2+(1λ)x1]λf(x2)+(1λ)f(x1)
则称:函数 f ( ⋅ ) f(\cdot) f() I \mathcal I I上的凸函数。对应示例图像表示如下:
将其转化: λ ⋅ x 2 + ( 1 − λ ) ⋅ x 1 = x 1 + λ ⋅ ( x 2 − x 1 ) \lambda \cdot x_2 + (1 - \lambda)\cdot x_1 = x_1 + \lambda \cdot (x_2 - x_1) λx2+(1λ)x1=x1+λ(x2x1),那么 λ ( x 2 − x 1 ) \lambda(x_2 - x_1) λ(x2x1)可看作增量,而 λ \lambda λ可看作控制增量的参数。
凸函数定义示例
凸函数的一种判定条件:构造一个函数 G ( t ) \mathcal G(t) G(t),满足:
G ( t ) ≜ f ( x + v ⋅ t ) ∀ x , v ∈ R n , t ∈ R \mathcal G(t) \triangleq f(x + v \cdot t) \quad \forall x,v \in \mathbb R^n,t \in \mathbb R G(t)f(x+vt)x,vRn,tR
则有推论: f ( ⋅ ) f(\cdot) f()是凸函数 ⇔ G ( t ) \Leftrightarrow \mathcal G(t) G(t)是凸函数。在一般情况下,我们面对的权重空间是一个高维空间,而在高维空间中的目标函数 f ( ⋅ ) f(\cdot) f()也通常是一个高维函数。假设:权重空间是一个 2 2 2维空间,对应的目标函数 f ( ⋅ ) f(\cdot) f()也是一个 2 2 2维函数
即:输入变量的维度是 2 2 2维,而目标函数的输出结果是 1 1 1维标量。
f ( ⋅ ) : R 2 ↦ R f(\cdot):\mathbb R^2 \mapsto \mathbb R f():R2R
那么如何验证 f ( ⋅ ) f(\cdot) f()描述的图像在高维空间中的曲面是否为凸的 ? ? ?在介绍方向导数中提到:关于某一点 ( x 0 , y 0 ) (x_0,y_0) (x0,y0)关于函数 f ( ⋅ ) f(\cdot) f()在方向 l ⃗ \vec l l 方向导数 ∂ Z ∂ l ⃗ ∣ ( x 0 , y 0 ) \begin{aligned}\frac{\partial \mathcal Z}{\partial \vec l}|_{(x_0,y_0)}\end{aligned} l Z(x0,y0)表示为下图中在 l ⃗ \vec l l 方向上过 ( x 0 , y 0 ) (x_0,y_0) (x0,y0)做一个垂直于 X O Y \mathcal X\mathcal O\mathcal Y XOY的平面,平面与 f ( ⋅ ) f(\cdot) f()相交的图像在 ( x 0 , y 0 ) (x_0,y_0) (x0,y0)处的斜率结果

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

方向导数定义——示例
但这里我们并不关注方向导数,而是关注平面与函数图像之间相交所产生的截线的形状。可以观察上述图像对应的俯视图结果:
无论是上图还是俯视图,都没有对 f ( x , y ) f(x,y) f(x,y)进行完全表示,这仅仅是其中一部分图像。
俯视图效果
从俯视图角度可以看到:黄色截面简化成了一条直线。这实际上可看做上述判定条件中函数 x + v ⋅ t x+v \cdot t x+vt的某一种结果。而对应的 f ( x + v ⋅ t ) f(x + v \cdot t) f(x+vt)则表达:截面与函数图像之间相交产生的截线

如果从向量的角度认识,以下面红色直线为例:
判定条件2示例
其中 x , v x,v x,v是任意 R n \mathbb R^n Rn的向量,从而 x + v ⋅ t x+v \cdot t x+vt可表示为该图黑色虚线的结果。由于 t ∈ R t \in \mathbb R tR,如果我们将所有的 t t t全部取到,那么最终构成 x + v ⋅ t x + v \cdot t x+vt构成向量的集合就是红色直线的结果。

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

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

凸函数的一阶条件

在函数 f ( ⋅ ) f(\cdot) f()可微的条件下,有:
相比于上述的定义与判定条件,并没有要求函数 f ( ⋅ ) f(\cdot) f()一定是可微的。也就是说:一个函数是凸函数,并不要求该函数一定可微
f ( ⋅ ) is Convex ⇔ f ( x 2 ) ≥ f ( x 1 ) + [ ∇ f ( x 1 ) ] T ⋅ ( x 2 − x 1 ) f(\cdot) \text{ is Convex} \Leftrightarrow f(x_2) \geq f(x_1) + [\nabla f(x_1)]^T \cdot (x_2-x_1) f() is Convexf(x2)f(x1)+[f(x1)]T(x2x1)
这是一个充分必要条件。可以在图像中看到这个现象:
凸函数的一阶条件示例
( 2023/8/10 ) (\text{2023/8/10}) (2023/8/10)补充
证明:充分性

  • 要证: f [ λ ⋅ x 1 + ( 1 − λ ) ⋅ x 2 ] ≤ λ ⋅ f ( x 1 ) + ( 1 − λ ) ⋅ f ( x 2 ) , ∀ x 1 , x 2 ∈ C , λ ∈ ( 0 , 1 ) f[\lambda \cdot x_1 + (1 - \lambda) \cdot x_2] \leq \lambda \cdot f(x_1) + (1 - \lambda) \cdot f(x_2),\forall x_1,x_2 \in \mathcal C,\lambda \in (0,1) f[λx1+(1λ)x2]λf(x1)+(1λ)f(x2),x1,x2C,λ(0,1)
  • λ ⋅ x 1 + ( 1 − λ ) ⋅ x 2 \lambda \cdot x_1 + (1 - \lambda) \cdot x_2 λx1+(1λ)x2记作 Z \mathcal Z Z,从而有: Z ∈ C \mathcal Z \in \mathcal C ZC。既然 Z \mathcal Z Z同样是定义域 C \mathcal C C上一点,根据假设条件必然有:
    { f ( x 1 ) ≥ f ( Z ) + [ ∇ f ( Z ) ] T ⋅ ( x 1 − Z ) f ( x 2 ) ≥ f ( Z ) + [ ∇ f ( Z ) ] T ⋅ ( x 2 − Z ) \begin{cases} f(x_1) & \geq f(\mathcal Z) + [\nabla f(\mathcal Z)]^T \cdot (x_1 - \mathcal Z) \\ f(x_2) & \geq f(\mathcal Z) + [\nabla f(\mathcal Z)]^T \cdot (x_2 - \mathcal Z)\end{cases} {f(x1)f(x2)f(Z)+[f(Z)]T(x1Z)f(Z)+[f(Z)]T(x2Z)
  • 将上述两个不等式的左右两端分别乘以 λ , 1 − λ \lambda,1 - \lambda λ,1λ。由于 λ ∈ ( 0 , 1 ) \lambda \in (0,1) λ(0,1),因而不等式符号不发生变化:
    { λ ⋅ f ( x 1 ) ≥ λ ⋅ f ( Z ) + λ [ ∇ f ( Z ) ] T ⋅ ( x 1 − Z ) ( 1 − λ ) ⋅ f ( x 2 ) ≥ ( 1 − λ ) ⋅ f ( Z ) + ( 1 − λ ) ⋅ [ ∇ f ( Z ) ] T ⋅ ( x 2 − Z ) \begin{cases} \begin{aligned} \lambda \cdot f(x_1) & \geq \lambda \cdot f(\mathcal Z) + \lambda [\nabla f(\mathcal Z)]^T \cdot (x_1 - \mathcal Z) \\ (1 - \lambda) \cdot f(x_2) & \geq (1 - \lambda) \cdot f(\mathcal Z) + (1 - \lambda) \cdot [\nabla f(\mathcal Z)]^T \cdot (x_2 - \mathcal Z) \end{aligned} \end{cases} {λf(x1)(1λ)f(x2)λf(Z)+λ[f(Z)]T(x1Z)(1λ)f(Z)+(1λ)[f(Z)]T(x2Z)
    将上述两不等式对应位置相加,有:
    λ f ( x 1 ) + ( 1 − λ ) ⋅ f ( x 2 ) ≥ ( λ + 1 − λ ) ⋅ f ( Z ) + [ ∇ f ( Z ) ] T ⋅ [ ( λ ⋅ x 1 − λ ⋅ Z ) + ( 1 − λ ) ⋅ x 2 − ( 1 − λ ) ⋅ Z ] ≥ f ( Z ) + [ ∇ f ( Z ) ] T ⋅ [ λ ⋅ x 1 + ( 1 − λ ) ⋅ x 2 − Z ] \begin{aligned} \lambda f(x_1) + (1 - \lambda) \cdot f(x_2) & \geq (\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] \\ & \geq f(\mathcal Z) + [\nabla f(\mathcal Z)]^T \cdot [\lambda \cdot x_1 + (1 - \lambda) \cdot x_2 - \mathcal Z] \end{aligned} λf(x1)+(1λ)f(x2)(λ+1λ)f(Z)+[f(Z)]T[(λx1λZ)+(1λ)x2(1λ)Z]f(Z)+[f(Z)]T[λx1+(1λ)x2Z]
    由于: λ ⋅ x 1 + ( 1 − λ ) ⋅ x 2 \lambda \cdot x_1 + (1 - \lambda) \cdot x_2 λx1+(1λ)x2记作 Z \mathcal Z Z,因此后一项: [ ∇ f ( Z ) ] T ⋅ [ λ ⋅ x 1 + ( 1 − λ ) ⋅ x 2 − Z ] = 0 [\nabla f(\mathcal Z)]^T \cdot [\lambda \cdot x_1 + (1 - \lambda) \cdot x_2 - \mathcal Z] = 0 [f(Z)]T[λx1+(1λ)x2Z]=0。最后将 Z \mathcal Z Z带入,整理有:
    这正是凸函数的定义。
    λ f ( x 1 ) + ( 1 − λ ) ⋅ f ( x 2 ) ≥ f ( Z ) = f [ λ ⋅ x 1 + ( 1 − λ ) ⋅ x 2 ] \lambda f(x_1) + (1 - \lambda) \cdot f(x_2) \geq f(\mathcal Z) = f[\lambda \cdot x_1 + (1 - \lambda) \cdot x_2] λf(x1)+(1λ)f(x2)f(Z)=f[λx1+(1λ)x2]

证明:必要性

  • 在已知 f ( ⋅ ) f(\cdot) f()凸函数的条件下:
    即便将 x 1 , x 2 x_1,x_2 x1,x2调换位置,也不会影响公式的成立。
    f [ λ ⋅ x 2 + ( 1 − λ ) ⋅ x 1 ] ≤ λ ⋅ f ( x 2 ) + ( 1 − λ ) ⋅ f ( x 1 ) x 1 , x 2 ∈ C ; λ ∈ ( 0 , 1 ) f [\lambda \cdot x_2 + (1 - \lambda) \cdot x_1] \leq \lambda \cdot f(x_2) + (1 - \lambda) \cdot f(x_1) \quad x_1,x_2 \in \mathcal C;\lambda \in (0,1) f[λx2+(1λ)x1]λf(x2)+(1λ)f(x1)x1,x2C;λ(0,1)

    • 观察不等式左侧,有:
      f [ λ ⋅ x 2 + ( 1 − λ ) ⋅ x 1 ] = f [ x 1 + λ ⋅ ( x 2 − x 1 ) ] f[\lambda \cdot x_2 + (1 - \lambda) \cdot x_1] = f [x_1 + \lambda \cdot (x_2 - x_1)] f[λx2+(1λ)x1]=f[x1+λ(x2x1)]
    • 观察不等式右侧,有:
      λ ⋅ f ( x 2 ) + ( 1 − λ ) ⋅ f ( x 1 ) = f ( x 1 ) + λ ⋅ [ f ( x 2 ) − f ( 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(x2)+(1λ)f(x1)=f(x1)+λ[f(x2)f(x1)]

    最终将上式整理得:
    f ( x 2 ) f(x_2) f(x2)以外的其他项移到不等号左侧,不等号不发生变化。
    f [ x 1 + λ ⋅ ( x 2 − x 1 ) ] − f ( x 1 ) λ + f ( x 1 ) ≤ f ( x 2 ) \frac{f [x_1 + \lambda \cdot (x_2 - x_1)] - f(x_1)}{\lambda} + f(x_1)\leq f(x_2) λf[x1+λ(x2x1)]f(x1)+f(x1)f(x2)

  • 对项 f [ x 1 + λ ⋅ ( x 2 − x 1 ) ] f [x_1 + \lambda \cdot (x_2 - x_1)] f[x1+λ(x2x1)]关于 x 1 x_1 x1进行泰勒展开
    其中 O ( ⋅ ) \mathcal O(\cdot) O()表示高阶无穷小。
    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 ∣ ∣ ) \begin{aligned} f[x_1 + \lambda \cdot (x_2 - x_1)] = f(x_1) + \frac{1}{1!}\lambda \cdot [\nabla f(x_1)]^T (x_2 - x_1) + \mathcal O(\lambda \cdot ||x_2 - x_1||) \end{aligned} f[x1+λ(x2x1)]=f(x1)+1!1λ[f(x1)]T(x2x1)+O(λ∣∣x2x1∣∣)
    将上式的 f ( x 1 ) f(x_1) f(x1)移至等号左侧,并将等式左右两侧同时除以 λ \lambda λ,有:
    f [ x 1 + λ ⋅ ( x 2 − x 1 ) ] − f ( x 1 ) λ = [ ∇ f ( x 1 ) ] T ( x 2 − x 1 ) + O ( λ ⋅ ∣ ∣ x 2 − x 1 ∣ ∣ ) λ \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} λf[x1+λ(x2x1)]f(x1)=[f(x1)]T(x2x1)+λO(λ∣∣x2x1∣∣)
    由于 λ ∈ ( 0 , 1 ) \lambda \in (0,1) λ(0,1),因此这里令 λ ⇒ 0 \lambda \Rightarrow 0 λ0,有:
    关于 lim ⁡ λ ⇒ 0 O ( λ ⋅ ∣ ∣ x 2 − x 1 ∣ ∣ ) λ \begin{aligned}\mathop{\lim}\limits_{\lambda \Rightarrow 0} \frac{\mathcal O(\lambda \cdot ||x_2 - x_1||)}{\lambda}\end{aligned} λ0limλO(λ∣∣x2x1∣∣),其中分子是关于 λ \lambda λ的高阶无穷小,而分子仅是一阶。因此该项分子趋近 0 0 0的速度要快于分母,从而为 0 0 0
    f [ x 1 + λ ⋅ ( x 2 − x 1 ) ] − f ( x 1 ) λ = [ ∇ f ( x 1 ) ] T ( x 2 − x 1 ) \frac{f[x_1 + \lambda \cdot (x_2 - x_1)] - f(x_1)}{\lambda} = [\nabla f(x_1)]^T (x_2 - x_1) λf[x1+λ(x2x1)]f(x1)=[f(x1)]T(x2x1)

  • 将该式带入到上述步骤,有:
    [ ∇ f ( x 1 ) ] T ( x 2 − x 1 ) + f ( x 1 ) ≤ f ( x 2 ) [\nabla f(x_1)]^T (x_2 - x_1) + f(x_1) \leq f(x_2) [f(x1)]T(x2x1)+f(x1)f(x2)

凸函数的梯度单调性

在函数 f ( ⋅ ) f(\cdot) f()可微的条件下, [ ∇ f ( x ) − ∇ f ( y ) ] [\nabla f(x) - \nabla f(y)] [f(x)f(y)] x − y x-y xy之间同号。即:
f ( ⋅ ) is Convex  ⇔ [ ∇ f ( x ) − ∇ f ( y ) ] T ( x − y ) ≥ 0 f(\cdot) \text{ is Convex } \Leftrightarrow [\nabla f(x) - \nabla f(y)]^T (x - y) \geq 0 f() is Convex [f(x)f(y)]T(xy)0

证明:必要性
如果 f ( ⋅ ) f(\cdot) f()可微的凸函数,根据凸函数的一阶条件,有:
{ f ( y ) ≥ f ( x ) + [ ∇ f ( x ) ] T ⋅ ( y − x ) f ( x ) ≥ f ( y ) + [ ∇ f ( y ) ] T ⋅ ( x − y ) \begin{cases} \begin{aligned} f(y) \geq f(x) + [\nabla f(x)]^T \cdot (y - x) \\ f(x) \geq f(y) + [\nabla f(y)]^T \cdot (x - y) \end{aligned} \end{cases} {f(y)f(x)+[f(x)]T(yx)f(x)f(y)+[f(y)]T(xy)
将上述式子相加,有:
[ ∇ f ( x ) − ∇ f ( y ) ] T ⋅ ( x − y ) ≥ 0 [\nabla f(x) - \nabla f(y)]^T \cdot (x - y) \geq 0 [f(x)f(y)]T(xy)0
证明:充分性
如果 f ( ⋅ ) f(\cdot) f()的梯度 ∇ f ( ⋅ ) \nabla f(\cdot) f()单调的,定义关于 t ∈ [ 0 , 1 ] t \in [0,1] t[0,1]的函数 G ( t ) \mathcal G(t) G(t)
G ( t ) = f [ x + t ⋅ ( y − x ) ] \mathcal G(t) = f[x + t \cdot (y - x)] G(t)=f[x+t(yx)]
对应 G ( t ) \mathcal G(t) G(t)的导数 G ′ ( t ) \mathcal G'(t) G(t)
G ′ ( t ) = [ ∇ f ( x + t ⋅ ( y − x ) ) ] T ⋅ ( y − x ) \mathcal G'(t) = [\nabla f(x + t \cdot (y-x))]^T \cdot (y-x) G(t)=[f(x+t(yx))]T(yx)
由于 G ′ ( t ) \mathcal G'(t) G(t) t ∈ [ 0 , 1 ] t \in [0,1] t[0,1]上连续,且:
[ ∇ f ( x ) − ∇ f ( y ) ] T ⋅ ( x − y ) ≥ 0 [\nabla f(x) - \nabla f(y)]^T \cdot (x - y) \geq 0 [f(x)f(y)]T(xy)0
从而有:
消了两个负号~
G ′ ( t ) ≥ G ′ ( 0 ) ⇐ { G ′ ( 1 ) − G ′ ( 0 ) = [ ∇ f ( y ) − ∇ f ( x ) ] T ⋅ ( y − x ) ≥ 0 G ′ ( 0 ) − G ′ ( 0 ) = 0 \mathcal G'(t) \geq \mathcal G'(0) \Leftarrow \begin{cases} \mathcal G'(1) - \mathcal G'(0) = [\nabla f(y) - \nabla f(x)]^T \cdot (y-x) \geq 0 \\ \mathcal G'(0) - \mathcal G'(0) = 0 \end{cases} G(t)G(0){G(1)G(0)=[f(y)f(x)]T(yx)0G(0)G(0)=0
最终有:
f ( y ) = G ( 1 ) = G ( 0 ) + ∫ 0 1 G ′ ( t ) d t ≥ G ( 0 ) + G ′ ( 0 ) = f ( x ) + [ ∇ f ( x ) ] T ( y − x ) f(y) = \mathcal G(1) = \mathcal G(0) + \int_0^1 \mathcal G'(t) dt \geq \mathcal G(0) + \mathcal G'(0) = f(x) + [\nabla f(x)]^T (y-x) f(y)=G(1)=G(0)+01G(t)dtG(0)+G(0)=f(x)+[f(x)]T(yx)
即: f ( ⋅ ) f(\cdot) f()为凸函数

凸函数的二阶条件

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

  • 基于 y ∈ C y \in \mathcal C yC,针对 f ( y ) f(y) f(y)关于某点 x x x进行泰勒展开
    • 其中 ξ \xi ξ表示 ( x , y ) (x,y) (x,y)范围内的一点,标准表示: ξ = x + λ ⋅ ( y − x ) ; λ ∈ ( 0 , 1 ) \xi = x + \lambda \cdot (y - x);\lambda \in (0,1) ξ=x+λ(yx);λ(0,1)
    • 不否认 ξ ∈ C \xi \in \mathcal C ξC
      f ( y ) = f ( x ) + 1 1 ! [ ∇ f ( x ) ] T ( y − x ) + 1 2 ! ( y − x ) T [ ∇ 2 f ( ξ ) ] ( y − x ) + O ( ⋅ ) 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) f(y)=f(x)+1!1[f(x)]T(yx)+2!1(yx)T[2f(ξ)](yx)+O()
  • 由于 ∇ 2 f ( ξ ) ≽ 0 \nabla^2 f(\xi) \succcurlyeq 0 2f(ξ)0,必然有:
    f ( y ) ≥ f ( x ) + [ ∇ f ( x ) ] T ( y − x ) f(y) \geq f(x) + [\nabla f(x)]^T (y-x) f(y)f(x)+[f(x)]T(yx)
  • 根据上述凸函数的一阶条件,自然得证: f ( ⋅ ) f(\cdot) f()是凸函数

证明:必要性
已知 f ( ⋅ ) f(\cdot) f()凸函数,要证: ∇ 2 f ( x ) ≽ 0 , ∀ x ∈ C \nabla^2 f(x) \succcurlyeq 0,\forall x \in \mathcal C 2f(x)0,xC

  • 从定义域 C \mathcal C C任取一点 x x x,观察: x x x开始,沿着 d d d方向移动了较小步长 α \alpha α位置的函数结果 f ( x + α ⋅ d ) f(x + \alpha \cdot d) f(x+αd),并针对该结果关于 x x x进行泰勒展开
    其中 x + α ⋅ d ∈ C x + \alpha \cdot d \in \mathcal C x+αdC
    f ( x + α ⋅ d ) = f ( x ) + 1 1 ! α ⋅ [ ∇ f ( x ) ] T d ⏟ 一阶条件 + 1 2 ! α 2 ⋅ d T [ ∇ 2 f ( x ) ] ⋅ d + O ( α 2 ⋅ ∣ ∣ d ∣ ∣ 2 ) f(x + \alpha \cdot d) = \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) f(x+αd)=一阶条件 f(x)+1!1α[f(x)]Td+2!1α2dT[2f(x)]d+O(α2∣∣d2)
  • 根据凸函数的一阶条件,必然有:
    这依然依赖移动后的结果依然 ∈ C \in \mathcal C C
    f ( x + α ⋅ d ) ≥ f ( x ) + α ⋅ [ ∇ f ( x ) ] T d f(x + \alpha \cdot d) \geq f(x) + \alpha \cdot [\nabla f(x)]^T d f(x+αd)f(x)+α[f(x)]Td
    将该结果带入上式,有:
    1 2 ! α 2 ⋅ d T [ ∇ 2 f ( x ) ] ⋅ d + O ( α 2 ⋅ ∣ ∣ d ∣ ∣ 2 ) ≥ 0 \frac{1}{2!} \alpha^2 \cdot d^T [\nabla^2 f(x)] \cdot d + \mathcal O(\alpha^2 \cdot ||d||^2) \geq 0 2!1α2dT[2f(x)]d+O(α2∣∣d2)0
  • 将不等式两侧同时除以 α 2 \alpha^2 α2,不等式符号不发生变化:
    1 2 d T [ ∇ 2 f ( x ) ] ⋅ d + O ( α 2 ⋅ ∣ ∣ d ∣ ∣ 2 ) α 2 ≥ 0 \frac{1}{2} d^T [\nabla^2 f(x)] \cdot d + \frac{\mathcal O(\alpha^2 \cdot ||d||^2)}{\alpha^2} \geq 0 21dT[2f(x)]d+α2O(α2∣∣d2)0
    在此基础上,令 α ⇒ 0 \alpha \Rightarrow 0 α0,最终有:
    • 凸函数一阶条件证明中的情况相似,其分子趋近 0 0 0远远高于分母,因而有: lim ⁡ α ⇒ 0 O ( α 2 ⋅ ∣ ∣ d ∣ ∣ 2 ) α 2 = 0 \begin{aligned}\mathop{\lim}\limits_{\alpha \Rightarrow 0} \frac{\mathcal O(\alpha^2 \cdot ||d||^2)}{\alpha^2} = 0\end{aligned} α0limα2O(α2∣∣d2)=0
    • 系数 1 2 \begin{aligned}\frac{1}{2}\end{aligned} 21被忽略了~
      d T [ ∇ 2 f ( x ) ] ⋅ d ≥ 0 d^T [\nabla^2 f(x)] \cdot d \geq 0 dT[2f(x)]d0

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

强凸函数

强凸函数的定义

关于强凸函数的定义表示如下: f ( ⋅ ) f(\cdot) f()为定义在空间 I \mathcal I I上的函数,若存在 m > 0 m>0 m>0,使其对 I \mathcal I I上的任意两点 x 1 , x 2 x_1,x_2 x1,x2任意实数 λ ∈ ( 0 , 1 ) \lambda \in (0,1) λ(0,1)总有
λ ⋅ f ( x 1 ) + ( 1 − λ ) ⋅ f ( x 2 ) ≥ f [ θ ⋅ x 1 + ( 1 − θ ) ⋅ x 2 ] + m 2 ⋅ θ ( 1 − θ ) ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ 2 \lambda\cdot f(x_1) + (1 - \lambda) \cdot f(x_2) \geq f[\theta \cdot x_1 + (1 - \theta) \cdot x_2] + \frac{m}{2} \cdot \theta(1 - \theta) \cdot ||x_1 -x _2||^2 λf(x1)+(1λ)f(x2)f[θx1+(1θ)x2]+2mθ(1θ)∣∣x1x22
相比于凸函数的定义,强凸函数明显多了一个部分: m 2 ⋅ θ ( 1 − θ ) ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ 2 \begin{aligned}\frac{m}{2} \cdot \theta(1 - \theta) \cdot ||x_1 -x _2||^2\end{aligned} 2mθ(1θ)∣∣x1x22。并且这个部分一定是正数。这相比凸函数仅仅 ≥ 0 \geq 0 0的约束要更强。
也被称作 m m m-强凸,其与凸函数定义的本质区别是相比凸函数多了一个 > 0 >0 >0下界的保证。

强凸函数的判定条件

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

  • 定义 G ( x ) ≜ f ( x ) − 1 2 m ⋅ ∣ ∣ x ∣ ∣ 2 \begin{aligned}\mathcal G(x) \triangleq f(x) - \frac{1}{2} m \cdot ||x||^2\end{aligned} G(x)f(x)21m∣∣x2,有:
    f ( ⋅ ) is m-Strong Convex  ⇔ G ( x ) is Convex f(\cdot) \text{ is m-Strong Convex } \Leftrightarrow \mathcal G(x) \text{ is Convex} f() is m-Strong Convex G(x) is Convex

强凸函数的一阶条件

关于强凸函数的一阶条件是在对应凸函数一阶条件的基础上,加入一个二次下界
f ( ⋅ ) f(\cdot) f()梯度满足利普希兹连续对应的二次上界引理不同:
∇ f ( ⋅ ) Lipschitz ⇔ f ( x 2 ) ≤ f ( x 1 ) + [ ∇ f ( x 1 ) ] T ( x 2 − x 1 ) + L 2 ∣ ∣ x 2 − x 1 ∣ ∣ 2 \nabla f(\cdot) \text{ Lipschitz} \Leftrightarrow f(x_2) \leq f(x_1) + [\nabla f(x_1)]^T (x_2 - x_1) + \frac{\mathcal L}{2}||x_2 - x_1||^2 f() Lipschitzf(x2)f(x1)+[f(x1)]T(x2x1)+2L∣∣x2x12
利普希兹连续强调的是限制梯度变化量的上界;而 m m m-强凸强调一个 > 0 >0 >0的二次下界。
f ( ⋅ ) is m-Strong Convex  ⇔ f ( x 2 ) ≥ f ( x 1 ) + [ ∇ f ( x 1 ) ] T ( x 2 − x 1 ) + m 2 ∣ ∣ x 2 − x 1 ∣ ∣ 2 f(\cdot) \text{ is m-Strong Convex } \Leftrightarrow f(x_2) \geq f(x_1) + [\nabla f(x_1)]^T (x_2-x_1) + \frac{m}{2}||x_2 - x_1||^2 f() is m-Strong Convex f(x2)f(x1)+[f(x1)]T(x2x1)+2m∣∣x2x12

强凸函数的梯度单调性

凸函数的梯度单调性基本类似,只不过下界由 0 0 0换成了:
证明过程略。
f ( ⋅ ) is m-Strong Convex  ⇔ [ ∇ f ( x ) − ∇ f ( y ) ] T ( x − y ) ≥ m ⋅ ∣ ∣ x − y ∣ ∣ 2 f(\cdot) \text{ is m-Strong Convex } \Leftrightarrow [\nabla f(x) - \nabla f(y)]^T (x - y) \geq m \cdot ||x - y||^2 f() is m-Strong Convex [f(x)f(y)]T(xy)m∣∣xy2

强突函数的二阶条件

f ( ⋅ ) f(\cdot) f()二阶可微的条件下,有:
其中 I \mathcal I I指单位矩阵。
f ( ⋅ ) is m-Strong Convex  ⇔ ∇ 2 f ( x ) ≽ m ⋅ I f(\cdot) \text{ is m-Strong Convex } \Leftrightarrow \nabla^2 f(x) \succcurlyeq m \cdot \mathcal I f() is m-Strong Convex 2f(x)mI

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/89952.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【从零学习python 】21.Python中的元组与字典

文章目录 元组一、访问元组二、修改元组三、count, index四、定义只有一个数据的元组五、交换两个变量的值 字典介绍一、列表的缺点二、字典的使用进阶案例 元组 Python的元组与列表类似,不同之处在于元组的元素不能修改。元组使用小括号,列表使用方括号…

C++初阶之一篇文章教会你queue和priority_queue(理解使用和模拟实现)

queue和priority_queue(理解使用和模拟实现) 什么是queuequeue的使用1.queue构造函数2.empty()3.size()4.front()5.back();6.push7.emplace8.pop()9.swap queue模拟实现什么是priority_queuepriority_queue的使用1.priority_queue构造函数1.1 模板参数 C…

论文阅读 RRNet: A Hybrid Detector for Object Detection in Drone-captured Images

文章目录 RRNet: A Hybrid Detector for Object Detection in Drone-captured ImagesAbstract1. Introduction2. Related work3. AdaResampling4. Re-Regression Net4.1. Coarse detector4.2. Re-Regression 5. Experiments5.1. Data augmentation5.2. Network details5.3. Tra…

DP(区间DP)

目录 石子合并 合并果子(贪心 Huffman树) 环形石子合并 石子合并 设有 N 堆石子排成一排,其编号为 1,2,3,…,N。 每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻…

全文检索与日志管理 Elasticsearch(上)

一、Elasticsearch介绍 1.1 全文检索索引 Elasticsearch是一个全文检索服务器,全文检索是一种非结构化数据的搜索方式。 那么什么是结构化数据和非结构化数据呢? 结构化数据:指具有固定格式固定长度的数据,如数据库中的字段。 …

如何有效开展网络安全事件调查工作

网络安全事件调查是现代企业网络安全体系建设的关键组成部分。为了防止网络攻击,仅仅关注于安全工具的应用效果远远不够,因为安全事件一直都在发生。安全团队只有充分了解攻击者的行踪和攻击路径,才能更好地防范更多攻击时间的发生。 做好网…

基于Python爬虫+词云图+情感分析对某东上完美日记的用户评论分析

🤵‍♂️ 个人主页:艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞&#x1f4…

【go语言学习笔记】05 Go 语言实战

文章目录 一、 RESTful API 服务1. RESTful API 定义1.1 HTTP Method1.2 RESTful API 规范 2. RESTful API 风格示例3. RESTful JSON API4. Gin 框架4.1 导入 Gin 框架4.2 使用 Gin 框架4.2.1 获取特定的用户(GET)4.2.2 新增一个用户(POST&am…

ElasticSearch安装与介绍

Elastic Stack简介 如果没有听说过Elastic Stack,那你一定听说过ELK,实际上ELK是三款软件的简称,分别是Elasticsearch、 Logstash、Kibana组成,在发展的过程中,又有新成员Beats的加入,所以就形成了Elastic…

9月大理,Move HackerHouse,成为全球数字游民的第一站

🚀世界各地的 hacker 们!即日起,我们正式向您发出 co-buiding & co-living 的邀请! 9.3日至9.24日,为期3周的 Move 主题Antalpha HackerHouse 将坐落于大理,邀请所有 Web3 开发者一起探索 Move 生态发…

基于Selenium模块实现无界面模式 执行JS脚本

此篇文章主要介绍如何使用 Selenium 模块实现 无界面模式 & 执行JS脚本(把滚动条拉到底部),并以具体的示例进行展示。 1、Selenium 设置无界面模式 创建浏览器对象之前,创建 options 功能对象 :options webdriver.ChromeOptions() 添加…

微服务系列(2)--注册中心

在博文:微服务系列(1)里我们提到过注册中心的概念,简单来说微服务注册中心是一个用于存储和管理微服务实例信息的组件,它提供了服务注册、服务发现、服务健康检查等功能,以确保微服务之间的稳定通信。在微服务架构中,各…

Python 图形界面框架TkInter(第八篇:理解pack布局)

前言 tkinter图形用户界面框架提供了3种布局方式,分别是 1、pack 2、grid 3、place 介绍下pack布局方式,这是我们最常用的布局方式,理解了pack布局,绝大多数需求都能满足。 第一次使用pack() import …

6. CSS(三)

目录 一、盒子模型 (一)网页布局的本质 (二)盒子模型组成 (三)边框(border) (四)表格的细线边框 (五)内边距(padding…

Android多屏幕支持-Android12

Android多屏幕支持-Android12 1、概览及相关文章2、屏幕窗口配置2.1 配置xml文件2.2 DisplayInfo#uniqueId 屏幕标识2.3 adb查看信息 3、配置文件解析3.1 xml字段读取3.2 简要时序图 4、每屏幕焦点 android12-release 1、概览及相关文章 AOSP > 文档 > 心主题 > 多屏…

【数据结构】栈与队列

1 栈 1.1 栈的概念及结构 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出 LIFO (Last In First Out) 的原则。 压栈:栈…

【Git】

Git 简介下载安装验证安装 简介 Git 是一个分布式版本控制系统,用于跟踪和管理软件开发项目的变化。它可以有效地记录文件的修改历史、协调多人协作开发、解决代码冲突,并提供了分支管理、版本回滚等功能,使团队能够更好地合作开发软件项目。…

Android实现超出固定行数折叠文字“查看全文“、“收起全文“

先上效果图 分析问题 网上有很多关于这个的代码,实现都过于复杂了,github上甚至还看到一篇文章600多行代码,结果一跑起来全是bug。还是自己写吧!!! 如果我们需要换行的"查看全文"、"收起全…

8.14 作业 ARM

.text .globl _gcd_gcd:mov r0,#9mov r1,#15cmp r0,r1 比较r0和r1寄存器中的值beq stopsubhi r0,r0,r1subcc r1,r1,r0stop:b stop .end用for循环实现1~100之间和: .text .globl _start_start:mov r0,#0 总和mov r1,#1 从1开始mov r2,#100 到100结束bl add_loopa…

安装elasticsearch

一、docker安装elasticsearch 1、下载镜像 docker pull elasticsearch:6.5.4 2、启动容器 docker run -p 9200:9200 -p 9300:9300 --name elasticsearch \ -e "discovery.typesingle-node" \ -e "cluster.nameelasticsearch" \ -e "ES_JAVA_OPTS-Xm…