机器学习笔记之优化算法(十五)Baillon Haddad Theorem简单认识

引言

本节将简单认识 Baillon Haddad Theorem \text{Baillon Haddad Theorem} Baillon Haddad Theorem(白老爹定理),并提供相关证明。

Baillon Haddad Theorem \text{Baillon Haddad Theorem} Baillon Haddad Theorem简单认识

如果函数 f ( ⋅ ) f(\cdot) f()在其定义域内可微,并且是凸函数,则存在如下等价条件
以下几个条件之间相互等价。

  • 关于 f ( ⋅ ) f(\cdot) f()梯度 ∇ f ( ⋅ ) \nabla f(\cdot) f()满足 L \mathcal L L-利普希兹连续
    { ∀ x , x ^ ∈ R n , ∃ L : s . t . ∣ ∣ f ( x ) − f ( x ^ ) ∣ ∣ ≤ L ⋅ ∣ ∣ x − x ^ ∣ ∣ ∃ ξ ∈ ( x , x ^ ) ⇒ ∣ ∣ f ( x ) − f ( x ^ ) ∣ ∣ ∣ ∣ x − x ^ ∣ ∣ = f ′ ( ξ ) ≤ L \begin{cases} \forall x,\hat x \in \mathbb R^n ,\exist \mathcal L: \quad s.t.||f(x) - f(\hat x)|| \leq \mathcal L \cdot ||x - \hat x|| \\ \quad \\ \begin{aligned} \exist \xi \in (x,\hat x) \Rightarrow \frac{||f(x) - f(\hat x)||}{||x - \hat x||} = f'(\xi) \leq \mathcal L \end{aligned} \end{cases} x,x^Rn,L:s.t.∣∣f(x)f(x^)∣∣L∣∣xx^∣∣ξ(x,x^)∣∣xx^∣∣∣∣f(x)f(x^)∣∣=f(ξ)L
    关于利普希兹连续详见二次上界引理。从逻辑的角度理解,这意味着:函数 f ( ⋅ ) f(\cdot) f()斜率的变化量利普希兹常数 L \mathcal L L约束。从图像的角度模糊观察,由于 L \mathcal L L的限制,不会出现斜率过于陡峭的情况
    见下图。从 x ⇒ y x \Rightarrow y xy的过程中, ∇ f ( x ) ⇒ ∇ f ( y ) \nabla f(x) \Rightarrow \nabla f(y) f(x)f(y)发生了剧烈的变化。这本质上说明 f ( ⋅ ) f(\cdot) f() [ x , y ] [x,y] [x,y]区间内过于陡峭的原因。
    斜率过大的情况

  • 关于函数 G ( x ) = L 2 x T x − f ( x ) \begin{aligned}\mathcal G(x) = \frac{\mathcal L}{2} x^T x - f(x)\end{aligned} G(x)=2LxTxf(x)同样是凸函数

    观察 G ( x ) \mathcal G(x) G(x),可以发现它由两部分组成:系数是 L 2 \begin{aligned}\frac{\mathcal L}{2}\end{aligned} 2L,关于变量 x x x的二次项结果;以及 f ( x ) f(x) f(x)自身。而二次函数 L 2 x T x \begin{aligned}\frac{\mathcal L}{2}x^Tx\end{aligned} 2LxTx其自身一定是个凸函数。该条件意味着:这两个凸函数的差也是凸函数

    如果从逻辑角度对 L 2 x T x − f ( x ) \begin{aligned}\frac{\mathcal L}{2}x^Tx - f(x)\end{aligned} 2LxTxf(x)进行认知:两个凸函数之间做减法,若 f ( x ) f(x) f(x)的陡峭程度要高于 L 2 x T x \begin{aligned}\frac{\mathcal L}{2}x^Tx\end{aligned} 2LxTx,这势必使得减法结果可能不是凸函数;因而该等价条件的本质依然是:约束 f ( x ) f(x) f(x)斜率的变化率,而该变化率的约束与利普希兹常数 L \mathcal L L存在关联关系

  • 关于函数的梯度 ∇ f ( ⋅ ) \nabla f(\cdot) f()具有余强制性 ( Co-coercive ) (\text{Co-coercive}) (Co-coercive)。即:
    [ ∇ f ( x ) − ∇ f ( y ) ] T ( x − y ) ≥ 1 L ∣ ∣ ∇ f ( x ) − ∇ f ( y ) ∣ ∣ 2 \left[\nabla f(x) - \nabla f(y)\right]^T(x - y) \geq \frac{1}{\mathcal L} ||\nabla f(x) - \nabla f(y)||^2 [f(x)f(y)]T(xy)L1∣∣∇f(x)f(y)2
    首先解释一下强制性 ( Coercive ) (\text{Coercive}) (Coercive)。它也被称作强单调性 ( Strongly monotonicity ) (\text{Strongly monotonicity}) (Strongly monotonicity)。从名字可以看出来——它比一般的单调性更强。关于 f ( ⋅ ) : R ↦ R f(\cdot) :\mathbb R \mapsto \mathbb R f():RR,其单调性的定义表示为:

    • 自变量的差异性与对应函数差异性之间同号。
    • 关于 n n n维的特征空间 f ( ⋅ ) : R n ↦ R n f(\cdot):\mathbb R^n \mapsto \mathbb R^n f():RnRn,那么此时的 f ( x ) − f ( y ) f(x) - f(y) f(x)f(y) x − y x - y xy都是向量。对应单调性的定义即: [ f ( x ) − f ( y ) ] T ( x − y ) ≥ 0 [f(x) - f(y)]^T(x - y) \geq 0 [f(x)f(y)]T(xy)0
      ∀ x , y ∈ R s . t . [ f ( x ) − f ( y ) ] ⋅ ( x − y ) ≥ 0 \forall x,y \in \mathbb R \quad s.t. [f(x) - f(y)] \cdot (x - y) \geq 0 x,yRs.t.[f(x)f(y)](xy)0

    强单调性单调性同号的基础上,进行了更强的约束:将式子右侧的 0 0 0替换为一个恒正的值。该值通常表示为:系数 α \alpha α x x x的增量 ∣ ∣ x − y ∣ ∣ 2 ||x - y||^2 ∣∣xy2的乘积形式
    [ f ( x ) − f ( y ) ] T ( x − y ) ≥ α ⋅ ∣ ∣ x − y ∣ ∣ 2 [f(x) - f(y)]^T (x - y) \geq \alpha \cdot ||x - y||^2 [f(x)f(y)]T(xy)α∣∣xy2
    若该值使用 f ( x ) f(x) f(x)的增量进行表示,我们称之为余强制性,也被称作逆向强单调性 ( Inverse Strongly monotonicity ) (\text{Inverse Strongly monotonicity}) (Inverse Strongly monotonicity)
    [ f ( x ) − f ( y ) ] T ( x − y ) ≥ α ⋅ ∣ ∣ f ( x ) − f ( y ) ∣ ∣ 2 [f(x) - f(y)]^T (x - y) \geq \alpha \cdot ||f(x) - f(y)||^2 [f(x)f(y)]T(xy)α∣∣f(x)f(y)2
    回顾等价条件 3 3 3:不等式左侧就是 ∇ f ( ⋅ ) \nabla f(\cdot) f()单调性的定义;不等式右侧则是关于余强制性的表述。需要关注的点在于:参与描述正值系数 α \alpha α利普希兹常数 L \mathcal L L之间存在关联关系 α = 1 L \begin{aligned}\alpha = \frac{1}{\mathcal L}\end{aligned} α=L1

证明过程

通过证明:条件 1 ⇒ 1 \Rightarrow 1条件 2 2 2条件 2 ⇒ 2 \Rightarrow 2条件 3 3 3,条件 3 ⇒ 3 \Rightarrow 3条件 1 1 1来实现 3 3 3个条件之间的等价关系。

证明:条件 1 ⇒ 1 \Rightarrow 1 条件 2 2 2

f ( ⋅ ) f(\cdot) f()凸函数,在定义域内可微;并且梯度函数 ∇ f ( ⋅ ) \nabla f(\cdot) f()满足 L \mathcal L L-利普希兹连续,求证:函数 G ( x ) = L 2 x T x − f ( x ) \begin{aligned}\mathcal G(x) = \frac{\mathcal L}{2} x^Tx - f(x)\end{aligned} G(x)=2LxTxf(x)凸函数
关于凸函数的一种证法在于,证明该函数的梯度满足单调性。之所以引入梯度的另一个原因是可以将 L 2 x T x \begin{aligned}\frac{\mathcal L}{2} x^Tx\end{aligned} 2LxTx化成一次项。

证明过程:由 G ( x ) = L 2 x T x − f ( x ) \begin{aligned}\mathcal G(x) = \frac{\mathcal L}{2} x^Tx -f(x)\end{aligned} G(x)=2LxTxf(x)可知,关于 G ( x ) \mathcal G(x) G(x)梯度 ∇ G ( x ) \nabla \mathcal G(x) G(x)可表示为
∇ G ( x ) = L ⋅ x − ∇ f ( x ) \nabla \mathcal G(x) = \mathcal L \cdot x - \nabla f(x) G(x)=Lxf(x)
至此,观察 ∇ G ( x ) \nabla \mathcal G(x) G(x)的单调性:
仅需证明 I ≥ 0 \mathcal I \geq 0 I0恒成立即可。
∀ x 1 , x 2 ∈ R n ⇒ I = [ ∇ G ( x 1 ) − ∇ G ( x 2 ) ] T ( x 1 − x 2 ) \forall x_1,x_2 \in \mathbb R^n \Rightarrow \mathcal I = [\nabla \mathcal G(x_1) - \nabla \mathcal G(x_2)]^T (x_1 - x_2) x1,x2RnI=[G(x1)G(x2)]T(x1x2)
将上述梯度结果代入,有:
继续展开~
I = [ L ⋅ x 1 − ∇ f ( x 1 ) − L ⋅ x 2 + ∇ f ( x 2 ) ] T ( x 1 − x 2 ) = L ⋅ ( x 1 − x 2 ) T ( x 1 − x 2 ) − [ ∇ f ( x 1 ) − ∇ f ( x 2 ) ] T ( x 1 − x 2 ) \begin{aligned} \mathcal I & = [\mathcal L \cdot x_1 - \nabla f(x_1) - \mathcal L \cdot x_2 + \nabla f(x_2)]^T (x_1 - x_2) \\ & = \mathcal L\cdot (x_1 - x_2)^T(x_1 - x _2) - [\nabla f(x_1) - \nabla f(x_2)]^T(x_1 - x_2) \end{aligned} I=[Lx1f(x1)Lx2+f(x2)]T(x1x2)=L(x1x2)T(x1x2)[f(x1)f(x2)]T(x1x2)
观察后一项: − [ ∇ f ( x 1 ) − ∇ f ( x 2 ) ] T ( x 1 − x 2 ) -[\nabla f(x_1) - \nabla f(x_2)]^T (x_1 - x_2) [f(x1)f(x2)]T(x1x2),这明显是两个向量的内积形式。可以根据柯西施瓦茨不等式,得到如下结果:
该部分同样可以使用向量乘法描述: a T b = ∣ a ∣ ⋅ ∣ b ∣ ⋅ cos ⁡ θ ≤ ∣ a ∣ ⋅ ∣ b ∣ a^Tb = |a|\cdot|b| \cdot \cos \theta \leq |a| \cdot |b| aTb=abcosθab因为 cos ⁡ θ ∈ [ − 1 , 1 ] ≤ 1 \cos \theta \in [-1,1] \leq 1 cosθ[1,1]1
[ ∇ f ( x 1 ) − ∇ f ( x 2 ) ] T ( x 1 − x 2 ) ≤ ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ [\nabla f(x_1) - \nabla f(x_2)]^T(x_1 - x_2) \leq ||\nabla f(x_1) - \nabla f(x_2)|| \cdot ||x_1 - x_2|| [f(x1)f(x2)]T(x1x2)∣∣∇f(x1)f(x2)∣∣∣∣x1x2∣∣
加上负号与前一项,从而有:
至于 ( x 1 − x 2 ) T ( x 1 − x 2 ) = ∣ ∣ x 1 − x 2 ∣ ∣ 2 (x_1 - x_2)^T(x_1 - x_2) = ||x_1 - x_2||^2 (x1x2)T(x1x2)=∣∣x1x22,两向量重合,夹角为 0 0 0
I ≥ L ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ 2 − ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ \mathcal I \geq \mathcal L \cdot ||x_1 - x_2||^2 - ||\nabla f(x_1) - \nabla f(x_2)|| \cdot ||x_1 - x_2|| IL∣∣x1x22∣∣∇f(x1)f(x2)∣∣∣∣x1x2∣∣
由于梯度函数 ∇ f ( ⋅ ) \nabla f(\cdot) f()满足 L \mathcal L L-利普希兹连续,因而将 ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ ≤ L ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ ||\nabla f(x_1) - \nabla f(x_2)|| \leq \mathcal L \cdot ||x_1 - x_2|| ∣∣∇f(x1)f(x2)∣∣L∣∣x1x2∣∣,对上式中的 ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ ||\nabla f(x_1) - \nabla f(x_2)|| ∣∣∇f(x1)f(x2)∣∣进行替换,最终不等号的方向不发生变化
{ − ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ ≥ − L ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ I ≥ L ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ 2 − ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ ≥ L ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ 2 − ( L ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ ) ⋅ ∣ ∣ ∣ x 1 − x 2 ∣ ∣ = 0 \begin{cases} -||\nabla f(x_1) - \nabla f(x_2)|| \geq -\mathcal L \cdot ||x_1 - x_2|| \\ \quad \\ \begin{aligned} \mathcal I & \geq \mathcal L \cdot ||x_1 - x_2||^2 - ||\nabla f(x_1) - \nabla f(x_2)|| \cdot ||x_1 - x_2|| \\ & \geq \mathcal L \cdot ||x_1 - x_2||^2 - (\mathcal L \cdot ||x_1 - x_2||) \cdot |||x_1 - x_2|| \\ & = 0 \end{aligned} \end{cases} ∣∣∇f(x1)f(x2)∣∣L∣∣x1x2∣∣IL∣∣x1x22∣∣∇f(x1)f(x2)∣∣∣∣x1x2∣∣L∣∣x1x22(L∣∣x1x2∣∣)∣∣∣x1x2∣∣=0

最终可证明: I ≥ 0 ⇒ \mathcal I \geq 0 \Rightarrow I0梯度函数 ∇ G ( x ) \nabla \mathcal G(x) G(x)有单调性。从而函数 G ( x ) \mathcal G(x) G(x)凸函数

证明:条件 3 ⇒ 3 \Rightarrow 3条件 1 1 1

梯度函数 ∇ f ( ⋅ ) \nabla f(\cdot) f()余强制性,那么该梯度函数 ∇ f ( ⋅ ) \nabla f(\cdot) f()满足 L \mathcal L L-利普希兹连续

证明过程:基于 ∇ f ( ⋅ ) \nabla f(\cdot) f()余强制性,结合柯西施瓦茨不等式,有:
使用柯西施瓦茨不等式将不等式左侧表示为模的乘积形式。
{ [ ∇ f ( x ) − ∇ f ( y ) ] T ( x − y ) ≥ 1 L ∣ ∣ ∇ f ( x ) − ∇ f ( y ) ∣ ∣ 2 ⇓ ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ ≥ [ ∇ f ( x 1 ) − ∇ f ( x 2 ) ] T ( x 1 − x 2 ) ≥ 1 L ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ 2 \begin{cases} \begin{aligned} \left[\nabla f(x) - \nabla f(y)\right]^T(x - y) & \geq \frac{1}{\mathcal L} ||\nabla f(x) - \nabla f(y)||^2 \\ & \Downarrow \\ ||\nabla f(x_1) - \nabla f(x_2)|| \cdot ||x_1 - x_2|| & \geq [\nabla f(x_1) - \nabla f(x_2)]^T (x_1 - x_2) \\ & \geq \frac{1}{\mathcal L} ||\nabla f(x_1) - \nabla f(x_2)||^2 \end{aligned} \end{cases} [f(x)f(y)]T(xy)∣∣∇f(x1)f(x2)∣∣∣∣x1x2∣∣L1∣∣∇f(x)f(y)2[f(x1)f(x2)]T(x1x2)L1∣∣∇f(x1)f(x2)2
消去 ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ ||\nabla f(x_1) - \nabla f(x_2)|| ∣∣∇f(x1)f(x2)∣∣,整理有:
∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ ≤ L ⋅ ∣ ∣ x 1 − x 2 ∣ ∣ ||\nabla f(x_1) - \nabla f(x_2)|| \leq \mathcal L \cdot ||x_1 - x_2|| ∣∣∇f(x1)f(x2)∣∣L∣∣x1x2∣∣
从而得证: ∇ f ( ⋅ ) \nabla f(\cdot) f()满足 L \mathcal L L-利普希兹连续

证明:条件 2 ⇒ 2 \Rightarrow 2条件 3 3 3

G ( x ) = L 2 x T x − f ( x ) \begin{aligned}\mathcal G(x) = \frac{\mathcal L}{2}x^Tx - f(x)\end{aligned} G(x)=2LxTxf(x)凸函数,那么关于梯度函数 ∇ f ( ⋅ ) \nabla f(\cdot) f()余强制性

证明思路:在证明之前,引入几个辅助变量:
余强制性不等式左侧 [ ∇ f ( x 1 ) − ∇ f ( x 2 ) ] T ( x 1 − x 2 ) [\nabla f(x_1) - \nabla f(x_2)]^T (x_1 - x_2) [f(x1)f(x2)]T(x1x2)记作 Δ \Delta Δ,并将其分解为如下形式:

  • 其中将 x 1 − x 2 x_1 - x_2 x1x2转化成 − ( x 2 − x 1 ) -(x_2 - x_1) (x2x1),并将负号提出来。
  • 其中 [ ∇ f ( x 1 ) − ∇ f ( x 2 ) ] T = { [ ∇ f ( x 1 ) ] T − [ ∇ f ( x 2 ) ] T } [\nabla f(x_1) - \nabla f(x_2)]^T = \left\{[\nabla f(x_1)]^T - [\nabla f(x_2)]^T\right\} [f(x1)f(x2)]T={[f(x1)]T[f(x2)]T}
    Δ = [ f ( x 1 ) + f ( x 2 ) ] − [ f ( x 1 ) + f ( x 2 ) ] ⏟ = 0 − { [ ∇ f ( x 1 ) ] T − [ ∇ f ( x 2 ) ] T } ( x 2 − x 1 ) = f ( x 2 ) − { f ( x 1 ) + [ ∇ f ( x 1 ) ] T ( x 2 − x 1 ) } ⏟ Δ 1 + f ( x 1 ) − { f ( x 2 ) + [ ∇ f ( x 2 ) ] T ( x 1 − x 2 ) } ⏟ Δ 2 = Δ 1 + Δ 2 \begin{aligned} \Delta & = \underbrace{[f(x_1) + f(x_2)] - [f(x_1) + f(x_2)]}_{=0} - \left\{[\nabla f(x_1)]^T - [\nabla f(x_2)]^T\right\}(x_2 - x_1) \\ & = \underbrace{f(x_2) - \{f(x_1) + [\nabla f(x_1)]^T (x_2 - x_1)\}}_{\Delta_1} + \underbrace{f(x_1) - \left\{f(x_2) + [\nabla f(x_2)]^T(x_1 - x_2)\right\}}_{\Delta_2} \\ & = \Delta_1 + \Delta_2 \end{aligned} Δ==0 [f(x1)+f(x2)][f(x1)+f(x2)]{[f(x1)]T[f(x2)]T}(x2x1)=Δ1 f(x2){f(x1)+[f(x1)]T(x2x1)}+Δ2 f(x1){f(x2)+[f(x2)]T(x1x2)}=Δ1+Δ2

可以在图像中描述出 Δ 1 , Δ 2 \Delta_1,\Delta_2 Δ1,Δ2的表示:

  • 其中 f ( x 1 ) + [ ∇ f ( x 1 ) ] T ( x 2 − x 1 ) f(x_1) + [\nabla f(x_1)]^T (x_2 - x_1) f(x1)+[f(x1)]T(x2x1)表示过点 x 1 x_1 x1 f ( ⋅ ) f(\cdot) f()的切线,与 x = x 2 x= x_2 x=x2相交后,到点 x 2 x_2 x2的距离。见黄色实线部分;
  • 对应 Δ 1 \Delta_1 Δ1则表示: f ( x 2 ) f(x_2) f(x2) f ( x 1 ) + [ ∇ f ( x 1 ) ] T ( x 2 − x 1 ) f(x_1) + [\nabla f(x_1)]^T (x_2 - x_1) f(x1)+[f(x1)]T(x2x1)之间的距离差值。见红色实线部分。
  • 同理,关于 Δ 2 \Delta_2 Δ2的图像描述表示为:
    对应的 Δ 2 \Delta_2 Δ2表示为图中的绿色实线部分。
    描述示例
    如果 Δ 1 \Delta_1 Δ1或者 Δ 2 \Delta_2 Δ2满足: Δ 1 ; Δ 2 ≥ 1 2 L ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ 2 \begin{aligned}\Delta_1;\Delta_2 \geq \frac{1}{2\mathcal L} ||\nabla f(x_1) - \nabla f(x_2)||^2\end{aligned} Δ1;Δ22L1∣∣∇f(x1)f(x2)2即可。

证明过程
这里以 Δ 1 \Delta_1 Δ1为例,将 Δ 1 \Delta_1 Δ1展开,有:
Δ 1 = f ( x 2 ) − [ ∇ f ( x 1 ) ] T x 2 ⏟ 1 − { f ( x 1 ) − [ ∇ f ( x 1 ) ] T x 1 } ⏟ 2 \begin{aligned} \Delta_1 & = \underbrace{f(x_2) - [\nabla f(x_1)]^T x_2}_{1} - \underbrace{\left\{f(x_1) - [\nabla f(x_1)]^T x_1 \right\}}_{2} \end{aligned} Δ1=1 f(x2)[f(x1)]Tx22 {f(x1)[f(x1)]Tx1}
可以发现,上述的 1 , 2 1,2 1,2两个部分存在相同的格式。因此假设一个函数:
关于函数 H x 1 ( Z ) \mathcal H_{x_1}(\mathcal Z) Hx1(Z),其中 Z \mathcal Z Z是自变量,而内部的 x 1 x_1 x1被视作可变参数。
H x 1 ( Z ) = f ( Z ) − [ ∇ f ( x 1 ) ] T Z \mathcal H_{x_1}(\mathcal Z) = f(\mathcal Z) - [\nabla f(x_1)]^T \mathcal Z Hx1(Z)=f(Z)[f(x1)]TZ
从而 Δ 1 \Delta_1 Δ1可表示为:
Δ 1 = H x 1 ( x 2 ) − H x 1 ( x 1 ) \Delta_1 = \mathcal H_{x_1}(x_2) - \mathcal H_{x_1}(x_1) Δ1=Hx1(x2)Hx1(x1)
观察 H x 1 ( Z ) \mathcal H_{x_1}(\mathcal Z) Hx1(Z)函数,其中 f ( Z ) f(\mathcal Z) f(Z)是关于 Z \mathcal Z Z凸函数;而 − [ ∇ f ( x 1 ) ] T Z -[\nabla f(x_1)]^T \mathcal Z [f(x1)]TZ本质上是关于 Z \mathcal Z Z一次函数,自然也是凸函数。根据保凸运算可知, H x 1 ( Z ) \mathcal H_{x_1}(\mathcal Z) Hx1(Z)一定是一个凸函数;并且由于 f ( Z ) f(\mathcal Z) f(Z) − [ ∇ f ( x 1 ) ] T Z -[\nabla f(x_1)]^T \mathcal Z [f(x1)]TZ均在 Z \mathcal Z Z定义域内可微,因而 H x 1 ( Z ) \mathcal H_{x_1}(\mathcal Z) Hx1(Z)同样可微。因而 H x 1 ( Z ) \mathcal H_{x_1}(\mathcal Z) Hx1(Z)关于 Z \mathcal Z Z梯度 ∇ H x 1 ( Z ) \nabla \mathcal H_{x_1}(\mathcal Z) Hx1(Z)可表示为:
∇ H x 1 ( Z ) = ∇ f ( Z ) − ∇ f ( x 1 ) \begin{aligned}\nabla \mathcal H_{x_1}(\mathcal Z) = \nabla f(\mathcal Z) - \nabla f(x_1) \end{aligned} Hx1(Z)=f(Z)f(x1)
Z = x 1 \mathcal Z = x_1 Z=x1时,有: ∇ H x 1 ( x 1 ) = 0 \nabla \mathcal H_{x_1}(x_1) = 0 Hx1(x1)=0。这意味着: Z = x 1 \mathcal Z = x_1 Z=x1是函数 H x 1 ( Z ) \mathcal H_{x_1}(\mathcal Z) Hx1(Z)的极值点。而又因为 H x 1 ( Z ) \mathcal H_{x_1}(\mathcal Z) Hx1(Z)凸函数性质,因而该点一定是最小值点。记 H x 1 ( Z ) \mathcal H_{x_1}(\mathcal Z) Hx1(Z)最小值结果为 H x 1 ∗ \mathcal H_{x_1}^* Hx1,从而可得:
H x 1 ∗ = H x 1 ( x 1 ) \mathcal H_{x_1}^* = \mathcal H_{x_1}(x_1) Hx1=Hx1(x1)
根据条件 2 2 2 G ( Z ) = L 2 Z T Z − f ( Z ) \begin{aligned}\mathcal G(\mathcal Z) = \frac{\mathcal L}{2} \mathcal Z^T \mathcal Z - f(\mathcal Z) \end{aligned} G(Z)=2LZTZf(Z)是凸函数,将 f ( Z ) = H x 1 ( Z ) + [ ∇ f ( x 1 ) ] T Z f(\mathcal Z) = \mathcal H_{x_1}(\mathcal Z) + [\nabla f(x_1)]^T \mathcal Z f(Z)=Hx1(Z)+[f(x1)]TZ代入到条件 2 2 2中有:
这里将变量符号 x x x替换成变量符号 Z \mathcal Z Z,便于下面的计算,并将 Z T Z \mathcal Z^T\mathcal Z ZTZ使用 ∣ ∣ Z ∣ ∣ 2 ||\mathcal Z||^2 ∣∣Z2替代。
G ( Z ) = L 2 ∣ ∣ Z ∣ ∣ 2 − f ( Z ) = L 2 ∣ ∣ Z ∣ ∣ 2 − H x 1 ( Z ) − [ ∇ f ( x 1 ) ] T Z ⇒ G ( Z ) + [ ∇ f ( x 1 ) ] T Z = L 2 ∣ ∣ Z ∣ ∣ 2 − H x 1 ( Z ) \begin{aligned} \mathcal G(\mathcal Z) & = \frac{\mathcal L}{2}||\mathcal Z||^2 - f(\mathcal Z) \\ & = \frac{\mathcal L}{2}||\mathcal Z||^2 - \mathcal H_{x_1}(\mathcal Z) - [\nabla f(x_1)]^T \mathcal Z \\ & \quad \\ \Rightarrow \mathcal G(\mathcal Z) + & [\nabla f(x_1)]^T \mathcal Z = \frac{\mathcal L}{2}||\mathcal Z||^2 - \mathcal H_{x_1}(\mathcal Z) \end{aligned} G(Z)G(Z)+=2L∣∣Z2f(Z)=2L∣∣Z2Hx1(Z)[f(x1)]TZ[f(x1)]TZ=2L∣∣Z2Hx1(Z)
观察上式的等号左侧 G ( Z ) + [ ∇ f ( x 1 ) ] T Z \mathcal G(\mathcal Z) + [\nabla f(x_1)]^T \mathcal Z G(Z)+[f(x1)]TZ,同样可以如法炮制 H x 1 ( Z ) = f ( Z ) + [ ∇ f ( x 1 ) ] T Z \mathcal H_{x_1}(\mathcal Z) = f(\mathcal Z) + [\nabla f(x_1)]^T \mathcal Z Hx1(Z)=f(Z)+[f(x1)]TZ一样,定义一个符号 G x 1 ( Z ) \mathcal G_{x_1}(\mathcal Z) Gx1(Z),使得:
G x 1 ( Z ) = G ( Z ) + [ ∇ f ( x 1 ) ] T Z \mathcal G_{x_1}(\mathcal Z) = \mathcal G(\mathcal Z) + [\nabla f(x_1)]^T \mathcal Z Gx1(Z)=G(Z)+[f(x1)]TZ
观察 G x 1 ( Z ) \mathcal G_{x_1}(\mathcal Z) Gx1(Z)相关性质

  • 关于第一项,根据条件 2 2 2描述: G ( Z ) \mathcal G(\mathcal Z) G(Z)自身是凸函数,可微
  • 关于第二项与 H x 1 ( Z ) \mathcal H_{x_1}(\mathcal Z) Hx1(Z)的第二项相同:关于 Z \mathcal Z Z一次函数 [ ∇ f ( x 1 ) ] T Z [\nabla f(x_1)]^T \mathcal Z [f(x1)]TZ同样是凸函数,并在自身定义域内可微

综上,依然可以根据保凸运算,关于函数 G x 1 ( Z ) \mathcal G_{x_1}(\mathcal Z) Gx1(Z)也是凸函数,并在定义域内可微。从而该函数的梯度 ∇ G x 1 ( Z ) \nabla \mathcal G_{x_1}(\mathcal Z) Gx1(Z)表示如下:
∇ G x 1 ( Z ) = L 2 ⋅ 2 ⋅ Z − ∇ H x 1 ( Z ) = L ⋅ Z − ∇ H x 1 ( Z ) \begin{aligned} \nabla \mathcal G_{x_1}(\mathcal Z) & = \frac{\mathcal L}{2} \cdot 2 \cdot \mathcal Z - \nabla \mathcal H_{x_1}(\mathcal Z) \\ & = \mathcal L \cdot \mathcal Z - \nabla \mathcal H_{x_1}(\mathcal Z) \end{aligned} Gx1(Z)=2L2ZHx1(Z)=LZHx1(Z)
根据 G x 1 ( Z ) \mathcal G_{x_1}(\mathcal Z) Gx1(Z)凸函数的性质,在 Z \mathcal Z Z定义域内取 z 1 ≤ z 2 , z 1 , z 2 ∈ R z_1 \leq z_2,z_1,z_2 \in \mathbb R z1z2,z1,z2R,必然有:
G x 1 ( z 2 ) ≥ G x 1 ( z 1 ) + [ ∇ G x 1 ( z 1 ) ] T ( z 2 − z 1 ) \mathcal G_{x_1}(z_2) \geq \mathcal G_{x_1}(z_1) + \left[\nabla \mathcal G_{x_1}(z_1)\right]^T(z_2 - z_1) Gx1(z2)Gx1(z1)+[Gx1(z1)]T(z2z1)
从上述图像中观察更加直观。也就是说: Δ 1 ≥ 0 \Delta_1 \geq 0 Δ10恒成立。将上述 G x 1 ( Z ) = L 2 ∣ ∣ Z ∣ ∣ 2 − H x 1 ( Z ) \begin{aligned}\mathcal G_{x_1}(\mathcal Z) = \frac{\mathcal L}{2}||\mathcal Z||^2 - \mathcal H_{x_1}(\mathcal Z)\end{aligned} Gx1(Z)=2L∣∣Z2Hx1(Z)代入,有:
L 2 ∣ ∣ z 2 ∣ ∣ 2 − H x 1 ( z 2 ) ⏟ G x 1 ( z 2 ) ≥ L 2 ∣ ∣ z 1 ∣ ∣ 2 − H x 1 ( z 1 ) ⏟ G x 1 ( x 1 ) + [ L ⋅ z 1 − ∇ H x 1 ( z 1 ) ] T ⏟ [ G x 1 ( z 1 ) ] T ⋅ ( z 2 − z 1 ) \underbrace{\frac{\mathcal L}{2} ||z_2||^2 - \mathcal H_{x_1}(z_2)}_{\mathcal G_{x_1}(z_2)} \geq \underbrace{\frac{\mathcal L}{2}||z_1||^2 - \mathcal H_{x_1}(z_1)}_{\mathcal G_{x_1}(x_1)} + \underbrace{[\mathcal L \cdot z_1 - \nabla \mathcal H_{x_1}(z_1)]^T}_{[\mathcal G_{x_1}(z_1)]^T} \cdot (z_2 - z_1) Gx1(z2) 2L∣∣z22Hx1(z2)Gx1(x1) 2L∣∣z12Hx1(z1)+[Gx1(z1)]T [Lz1Hx1(z1)]T(z2z1)
至此,描述 G x 1 ( Z ) \mathcal G_{x_1}(\mathcal Z) Gx1(Z)凸函数性质的式子全部由 H x 1 ( Z ) \mathcal H_{x_1}(\mathcal Z) Hx1(Z)进行代替。经过整理,有:
对比一下二次上界引理,它们确实比较相似,但并不是。因为 L 2 ∣ ∣ z 2 ∣ ∣ 2 − L 2 ∣ ∣ z 1 ∣ ∣ 2 \begin{aligned}\frac{\mathcal L}{2}||z_2||^2 - \frac{\mathcal L}{2}||z_1||^2\end{aligned} 2L∣∣z222L∣∣z12 L 2 ∣ ∣ z 2 − z 1 ∣ ∣ 2 \begin{aligned}\frac{\mathcal L}{2}||z_2 - z_1||^2\end{aligned} 2L∣∣z2z12绝大多数情况不相等。
H x 1 ( z 2 ) ≤ L 2 ∣ ∣ z 2 ∣ ∣ 2 − L 2 ∣ ∣ z 1 ∣ ∣ 2 + H x 1 ( z 1 ) + [ ∇ H x 1 ( z 1 ) − L ⋅ z 1 ] T ( z 2 − z 1 ) \mathcal H_{x_1}(z_2) \leq \frac{\mathcal L}{2}||z_2||^2 - \frac{\mathcal L}{2} ||z_1||^2 + \mathcal H_{x_1}(z_1) + \left[\nabla \mathcal H_{x_1}(z_1) - \mathcal L \cdot z_1\right]^T(z_2 - z_1) Hx1(z2)2L∣∣z222L∣∣z12+Hx1(z1)+[Hx1(z1)Lz1]T(z2z1)
但该式子并不影响我们使用二次上界引理中的操作: z 1 z_1 z1视作上一次迭代产生的数值解,因而 z 1 z_1 z1是已知项,从而不等式右侧是关于 z 2 z_2 z2的函数,记作 ϕ ( z 2 ) \phi(z_2) ϕ(z2)
H x 1 ( z 2 ) ≤ ϕ ( z 2 ) ≜ L 2 ∣ ∣ z 2 ∣ ∣ 2 − L 2 ∣ ∣ z 1 ∣ ∣ 2 + H x 1 ( z 1 ) + [ ∇ H x 1 ( z 1 ) − L ⋅ z 1 ] T ( z 2 − z 1 ) \mathcal H_{x_1}(z_2) \leq \phi(z_2) \triangleq \frac{\mathcal L}{2}||z_2||^2 - \frac{\mathcal L}{2} ||z_1||^2 + \mathcal H_{x_1}(z_1) + \left[\nabla \mathcal H_{x_1}(z_1) - \mathcal L \cdot z_1\right]^T(z_2 - z_1) Hx1(z2)ϕ(z2)2L∣∣z222L∣∣z12+Hx1(z1)+[Hx1(z1)Lz1]T(z2z1)
再次观察 ϕ ( z 2 ) \phi(z_2) ϕ(z2) z 2 z_2 z2相关的项(其中仅与 z 1 z_1 z1相关的项被视作常数):

  • L 2 ∣ ∣ z 2 ∣ ∣ 2 \begin{aligned}\frac{\mathcal L}{2}||z_2||^2\end{aligned} 2L∣∣z22是关于 z 2 z_2 z2二次项,是凸函数;且二次项系数 L 2 ≥ 0 \begin{aligned}\frac{\mathcal L}{2} \geq 0\end{aligned} 2L0,必然存在最小值
  • [ ∇ H x 1 ( z 1 ) − L ⋅ z 1 ] T ( z 2 − z 1 ) \left[\nabla \mathcal H_{x_1}(z_1) - \mathcal L \cdot z_1\right]^T(z_2 - z_1) [Hx1(z1)Lz1]T(z2z1)是关于 z 1 z_1 z1一次函数,同样是凸函数。

最终通过保凸运算,能够确定 ϕ ( z 2 ) \phi(z_2) ϕ(z2)是一个凸二次函数。由于 H x 1 ( z 2 ) ≤ ϕ ( z 2 ) \mathcal H_{x_1}(z_2) \leq \phi(z_2) Hx1(z2)ϕ(z2),必然也小于 ϕ ( z 2 ) \phi(z_2) ϕ(z2)最小值,也就是下界 inf ⁡ { ϕ ( z 2 ) } = min ⁡ ϕ ( z 2 ) \inf \{\phi(z_2)\} = \mathop{\min} \phi(z_2) inf{ϕ(z2)}=minϕ(z2)
H x 1 ( z 2 ) ≤ inf ⁡ { ϕ ( z 2 ) } \mathcal H_{x_1}(z_2) \leq \inf \{\phi(z_2)\} Hx1(z2)inf{ϕ(z2)}
下面关于 inf ⁡ { ϕ ( z 2 ) } \inf\{\phi(z_2)\} inf{ϕ(z2)}进行求解:

  • 求解梯度 ∇ ϕ ( z 2 ) \nabla \phi(z_2) ϕ(z2)
    ∇ ϕ ( z 2 ) = L ⋅ z 2 + ∇ H x 1 ( z 1 ) − L ⋅ z 1 \nabla \phi(z_2) = \mathcal L \cdot z_2 + \nabla \mathcal H_{x_1}(z_1) - \mathcal L \cdot z_1 ϕ(z2)=Lz2+Hx1(z1)Lz1
  • ∇ ϕ ( z 2 ) ≜ 0 \nabla \phi(z_2) \triangleq 0 ϕ(z2)0,有:
    也就是说: ϕ ( z 2 ; m i n ) = min ⁡ ϕ ( z 2 ) \phi(z_{2;min}) = \min \phi(z_2) ϕ(z2;min)=minϕ(z2)
    z 2 ; m i n = z 1 − ∇ H x 1 ( z 1 ) L z_{2;min} =z_1 - \frac{\nabla \mathcal H_{x_1}(z_1)}{\mathcal L} z2;min=z1LHx1(z1)
  • z 2 ; m i n z_{2;min} z2;min带回原式,得到 min ⁡ ϕ ( z 2 ) \min \phi(z_2) minϕ(z2)有:
    ϕ ( z 2 ; m i n ) = L 2 ∣ ∣ L ⋅ z 1 − ∇ H x 1 ( z 1 ) L ∣ ∣ 2 − L 2 ∣ ∣ z 1 ∣ ∣ 2 + H x 1 ( z 1 ) + [ ∇ H x 1 ( z 1 ) − L ⋅ z 1 ] T [ − ∇ H x 1 ( z 1 ) L ] \phi(z_{2;min}) = \frac{\mathcal L}{2} ||\frac{\mathcal L\cdot z_1 - \nabla \mathcal H_{x_1}(z_1)}{\mathcal L}||^2 - \frac{\mathcal L}{2}||z_1||^2 + \mathcal H_{x_1}(z_1) + [\nabla \mathcal H_{x_1}(z_1) - \mathcal L \cdot z_1]^T\left[- \frac{\nabla \mathcal H_{x_1}(z_1)}{\mathcal L}\right] ϕ(z2;min)=2L∣∣LLz1Hx1(z1)22L∣∣z12+Hx1(z1)+[Hx1(z1)Lz1]T[LHx1(z1)]
  • 很明显,只剩下了已知项 z 1 z_1 z1。整理有:
    • 提出公因式 1 2 L [ L ⋅ z 1 − ∇ H x 1 ( z 1 ) ] \begin{aligned}\frac{1}{2\mathcal L}[\mathcal L \cdot z_1 - \nabla \mathcal H_{x_1}(z_1)]\end{aligned} 2L1[Lz1Hx1(z1)]
    • 使用乘法分配律~
      ϕ ( z 2 ; m i n ) = 1 2 L ∣ ∣ L ⋅ z 1 − ∇ H x 1 ( z 1 ) ∣ ∣ 2 − L 2 ∣ ∣ z 1 ∣ ∣ 2 + H x 1 ( z 1 ) + 1 L [ L ⋅ z 1 − ∇ H x 1 ( z 1 ) ] T ∇ H x 1 ( z 1 ) = 1 2 L [ L ⋅ z 1 − ∇ H x 1 ( z 1 ) ] T { L ⋅ z 1 − ∇ H x 1 ( z 1 ) + 2 ∇ H x 1 ( z 1 ) } + h x 1 ( z 1 ) − L 2 ∣ ∣ z 1 ∣ ∣ 2 = 1 2 L [ L ⋅ z 1 − ∇ H x 1 ( z 1 ) ] T { L ⋅ z 1 + ∇ H x 1 ( z 1 ) } ⏟ 分配律 + h x 1 ( z 1 ) − L 2 ∣ ∣ z 1 ∣ ∣ 2 = 1 2 L [ L 2 ⋅ ∣ ∣ z 1 ∣ ∣ 2 − ∣ ∣ ∇ H x 1 ( z 1 ) ∣ ∣ 2 ] + H x 1 ( z 1 ) − L 2 ∣ ∣ z 1 ∣ ∣ 2 = H x 1 ( z 1 ) − 1 2 L ∣ ∣ ∇ H x 1 ( z 1 ) ∣ ∣ 2 \begin{aligned} \phi(z_{2;min}) & = \frac{1}{2\mathcal L}||\mathcal L \cdot z_1 - \nabla \mathcal H_{x_1}(z_1)||^2 - \frac{\mathcal L}{2}||z_1||^2 + \mathcal H_{x_1}(z_1) + \frac{1}{\mathcal L} [\mathcal L \cdot z_1 - \nabla \mathcal H_{x_1}(z_1)]^T \nabla \mathcal H_{x_1}(z_1) \\ & = \frac{1}{2\mathcal L} [\mathcal L \cdot z_1 - \nabla \mathcal H_{x_1}(z_1)]^T \left\{\mathcal L \cdot z_1 - \nabla \mathcal H_{x_1}(z_1) + 2 \nabla \mathcal H_{x_1}(z_1)\right\} + h_{x_1}(z_1) - \frac{\mathcal L}{2}||z_1||^2 \\ & = \frac{1}{2\mathcal L} \underbrace{[\mathcal L \cdot z_1 - \nabla \mathcal H_{x_1}(z_1)]^T \left\{\mathcal L \cdot z_1 + \nabla \mathcal H_{x_1}(z_1) \right\}}_{分配律} + h_{x_1}(z_1) - \frac{\mathcal L}{2}||z_1||^2 \\ & = \frac{1}{2\mathcal L} \left[\mathcal L^2 \cdot ||z_1||^2 - ||\nabla \mathcal H_{x_1}(z_1)||^2\right] + \mathcal H_{x_1}(z_1) - \frac{\mathcal L}{2}||z_1||^2 \\ & = \mathcal H_{x_1}(z_1) - \frac{1}{2\mathcal L}||\nabla \mathcal H_{x_1}(z_1)||^2 \end{aligned} ϕ(z2;min)=2L1∣∣Lz1Hx1(z1)22L∣∣z12+Hx1(z1)+L1[Lz1Hx1(z1)]THx1(z1)=2L1[Lz1Hx1(z1)]T{Lz1Hx1(z1)+2∇Hx1(z1)}+hx1(z1)2L∣∣z12=2L1分配律 [Lz1Hx1(z1)]T{Lz1+Hx1(z1)}+hx1(z1)2L∣∣z12=2L1[L2∣∣z12∣∣∇Hx1(z1)2]+Hx1(z1)2L∣∣z12=Hx1(z1)2L1∣∣∇Hx1(z1)2

至此,我们找到了关于 H x 1 ( z 2 ) \mathcal H_{x_1}(z_2) Hx1(z2)二次上界
H x 1 ( z 2 ) ≤ H x 1 ( z 1 ) − 1 2 L ∣ ∣ ∇ H x 1 ( z 1 ) ∣ ∣ 2 \mathcal H_{x_1}(z_2) \leq \mathcal H_{x_1}(z_1) - \frac{1}{2\mathcal L}||\nabla \mathcal H_{x_1}(z_1)||^2 Hx1(z2)Hx1(z1)2L1∣∣∇Hx1(z1)2
H x 1 ( ⋅ ) \mathcal H_{x_1}(\cdot) Hx1()函数的收敛过程中,其最小值 H x 1 ∗ \mathcal H_{x_1}^* Hx1必然有:
通过数值解只能无限接近最小值。
H x 1 ∗ ≤ H x 1 ( z 2 ) ≤ H x 1 ( z 1 ) − 1 2 L ∣ ∣ ∇ H x 1 ( z 1 ) ∣ ∣ 2 \mathcal H_{x_1}^* \leq \mathcal H_{x_1}(z_2) \leq \mathcal H_{x_1}(z_1) - \frac{1}{2\mathcal L}||\nabla \mathcal H_{x_1}(z_1)||^2 Hx1Hx1(z2)Hx1(z1)2L1∣∣∇Hx1(z1)2
因为 H x 1 ( ⋅ ) \mathcal H_{x_1}(\cdot) Hx1()函数在 x 1 x_1 x1处取得最小值: H x 1 ( x 1 ) = H x 1 ∗ \mathcal H_{x_1}(x_1) = \mathcal H_{x_1}^* Hx1(x1)=Hx1,并且 z 1 z_1 z1 x 1 x_1 x1定义域相同,不妨设: z 1 = x 2 z_1 = x_2 z1=x2,有:
H x 1 ( x 1 ) ≤ H x 1 ( x 2 ) − 1 2 L ∣ ∣ ∇ H x 1 ( x 2 ) ∣ ∣ 2 ⇒ H x 1 ( x 2 ) − H x 1 ( x 1 ) ≥ 1 2 L ∣ ∣ ∇ H x 1 ( x 2 ) ∣ ∣ 2 \begin{aligned} & \mathcal H_{x_1}(x_1) \leq \mathcal H_{x_1}(x_2) - \frac{1}{2\mathcal L}||\nabla \mathcal H_{x_1}(x_2)||^2 \\ \Rightarrow & \mathcal H_{x_1}(x_2) - \mathcal H_{x_1}(x_1) \geq \frac{1}{2\mathcal L}||\nabla \mathcal H_{x_1}(x_2)||^2 \end{aligned} Hx1(x1)Hx1(x2)2L1∣∣∇Hx1(x2)2Hx1(x2)Hx1(x1)2L1∣∣∇Hx1(x2)2
由于 Δ 1 = H x 1 ( x 2 ) − H x 1 ( x 1 ) \Delta_1 = \mathcal H_{x_1}(x_2) - \mathcal H_{x_1}(x_1) Δ1=Hx1(x2)Hx1(x1),因而最终有:
∇ H x 1 ( Z = x 2 ) = ∇ f ( x 2 ) − ∇ f ( x 1 ) \nabla \mathcal H_{x_1}(\mathcal Z = x_2) = \nabla f(x_2) - \nabla f(x_1) Hx1(Z=x2)=f(x2)f(x1)代入:
Δ 1 ≥ 1 2 L ∣ ∣ ∇ H x 1 ( x 2 ) ∣ ∣ 2 = 1 2 L ∣ ∣ ∇ f ( x 2 ) − ∇ f ( x 1 ) ∣ ∣ 2 = 1 2 L ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ 2 \begin{aligned} \Delta_1 & \geq \frac{1}{2\mathcal L}||\nabla \mathcal H_{x_1}(x_2)||^2 \\ & = \frac{1}{2\mathcal L} ||\nabla f(x_2) - \nabla f(x_1)||^2 \\ & = \frac{1}{2\mathcal L} ||\nabla f(x_1) - \nabla f(x_2)||^2 \end{aligned} Δ12L1∣∣∇Hx1(x2)2=2L1∣∣∇f(x2)f(x1)2=2L1∣∣∇f(x1)f(x2)2
当然,这仅仅证明了一半,我们同样需要针对 Δ 2 \Delta_2 Δ2执行上述流程:
和上述流程完全相同,只不过可变参数由 x 1 x_1 x1变成了 x 2 x_2 x2,这里不再赘述。
Δ 2 = [ f ( x 1 ) − f ( x 2 ) ] − { [ ∇ f ( x 2 ) ] T x 1 − [ ∇ f ( x 2 ) ] T x 2 } = f ( x 1 ) − [ ∇ f ( x 2 ) ] T x 1 ⏟ 1 − { f ( x 2 ) − [ ∇ f ( x 2 ) ] T x 2 } ⏟ 2 = H x 2 ( x 1 ) − H x 2 ( x 2 ) \begin{aligned} \Delta_2 & = [f(x_1) - f(x_2)] - \left\{[\nabla f(x_2)]^T x_1 - [\nabla f(x_2)]^T x_2 \right\} \\ & = \underbrace{f(x_1) - [\nabla f(x_2)]^T x_1}_{1} - \underbrace{\{f(x_2) - [\nabla f(x_2)]^T x_2\}}_{2} \\ & = \mathcal H_{x_2}(x_1) - \mathcal H_{x_2}(x_2) \end{aligned} Δ2=[f(x1)f(x2)]{[f(x2)]Tx1[f(x2)]Tx2}=1 f(x1)[f(x2)]Tx12 {f(x2)[f(x2)]Tx2}=Hx2(x1)Hx2(x2)
最终也可以得到一个类似结果:
Δ 2 ≥ 1 2 L ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ 2 \Delta_2 \geq \frac{1}{2\mathcal L} ||\nabla f(x_1) - \nabla f(x_2)||^2 Δ22L1∣∣∇f(x1)f(x2)2
从而最终可得:
Δ 1 + Δ 2 ≥ 2 ⋅ 1 2 L ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ 2 = 1 L ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ 2 \begin{aligned} \Delta_1 + \Delta_2 & \geq 2 \cdot \frac{1}{2\mathcal L}||\nabla f(x_1) - \nabla f(x_2)||^2 \\ & = \frac{1}{\mathcal L} ||\nabla f(x_1) - \nabla f(x_2)||^2 \end{aligned} Δ1+Δ222L1∣∣∇f(x1)f(x2)2=L1∣∣∇f(x1)f(x2)2
即:
[ ∇ f ( x 1 ) − ∇ f ( x 2 ) ] T ( x 1 − x 2 ) ≥ 1 L ∣ ∣ ∇ f ( x 1 ) − ∇ f ( x 2 ) ∣ ∣ 2 [\nabla f(x_1) - \nabla f(x_2)]^T(x_1 - x_2) \geq \frac{1}{\mathcal L} ||\nabla f(x_1) - \nabla f(x_2)||^2 [f(x1)f(x2)]T(x1x2)L1∣∣∇f(x1)f(x2)2
梯度函数 ∇ f ( ⋅ ) \nabla f(\cdot) f()具备余强制性,证毕。

相关参考:
【优化算法】梯度下降法-白老爹定理(上)
【优化算法】梯度下降法-白老爹定理(下)

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

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

相关文章

YOLO目标检测——动漫头像数据集下载分享

动漫头像数据集是用于研究和分析动漫头像相关问题的数据集,它包含了大量的动漫风格的头像图像。动漫头像是指以动漫风格绘制的虚构人物的头像图像,常见于动画、漫画、游戏等媒体。 数据集点击下载:YOLO动漫头像数据集50800图片.rar

mysql之host is blocked问题

程序上线一段时间之后,更新程序总是遇到这个问题 每次都是重启几次程序,或者执行 flush hosts; 毕竟指标不治本,抽出时间决定分析一下问题,查阅了几篇博客。(感谢这几位大佬) https://blog.51cto.com/u_…

SpringCloud学习笔记(二)_Eureka注册中心

一、Eureka简介 Eureka是一项基于REST(代表性状态转移)的服务,主要在AWS云中用于定位服务,以实现负载均衡和中间层服务器的故障转移。我们称此服务为Eureka Server。Eureka还带有一个基于Java的客户端组件Eureka Client&#xff…

入耳式无线耳机哪个款式好?无线蓝牙耳机音质排行榜

本着要买就认认真真的挑选一台的想法。和有线耳机相比,无线耳机确实有一定优势,比如说它的实用性明显要高不少。那么如何挑选,一款合适自己的耳机呢,首先,还是挑选出当前的热门款式,和各种网红推荐款&#…

Android Studio实现解析HTML获取json,解析json图片URL,将URL存到list,进行瀑布流展示

目录 效果build.gradle(app)添加的依赖(用不上的可以不加)AndroidManifest.xml错误activity_main.xmlitem_image.xmlMainActivityImage适配器ImageModel 接收图片URL 效果 build.gradle(app)添加的依赖&…

网络安全设备篇——加密机

加密机是一种专门用于数据加密和解密的网络安全设备。它通过使用密码学算法对数据进行加密,从而保护数据的机密性和完整性。加密机通常被用于保护敏感数据,如金融信息、个人身份信息等。 加密机的主要功能包括: 数据加密:加密机使…

安卓系列机型-禁止安装某软件 防止“沉迷游戏的小孩”操作解析

如何禁止安装某软件。这里以好课帮app为例做个演示步骤说明。这个博文的目的在于可以阻止他人用手机安装你指定的一些软件。 💔💔💔首先手机上安装好课帮这个软件。打开应用详情找到包名。或者使用第三方工具打开获取这个软件的包名。记住是…

PHP服饰文化网站系统Dreamweaver开发mysql数据库web结构php编程计算机网页项目

一、源码特点 PHP 服饰文化网站系统是一套完善的web设计系统,对理解php编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。 源码下载 https://download.csdn.net/download/qq_41221322/88236778 PHP服饰文化网站…

Python在文件中对字母、单词频度统计

读入给定的文本文件“hamlet.txt”,编写两个函数分别实现: 1) 统计所有字母的出现频度,依据频度从高到低,显示前5个字母及其频度,同时把结果写入文件“hamlet_字母频度.txt”。 2) 统计所有单词的出现频度,依据频度从高到低,显示…

MyBatis的动态语句且如何实现模糊查询及MyBatis的结果映射---详细介绍

前言 前面我们学习了如何使用Mybatis实现简单的增删改查。今天我们来学习如何使用动态语句来根据不同的条件生成不同的SQL语句。这在实际开发中非常有用,因为通常查询条件是多样化的,需要根据实际情况来拼接SQL语句,那什么是MyBatis动态语句呢…

生物识别技术与身份认证:探讨生物识别技术在强化身份认证和访问控制方面的应用

第一章:引言 在数字化时代,随着信息技术的飞速发展,身份认证和访问控制变得越来越重要。传统的用户名和密码方式逐渐暴露出安全性不足的问题,为此,生物识别技术应运而生。生物识别技术利用人体生物特征来识别个体身份…

解决IDEA tomcat控制台只有server日志

解决IDEA tomcat控制台只有server日志 确认tomcatxxx/conf/logging.properties文件是否存在,存在就会有。前提是在run configuration配置了打印多个日志

CSSCI、北核期刊投稿指南(2023年更新)

该数据为经管类的期刊投稿指南,包含发表难度,文章数量,影响因子,用户评价等指标。共5份文件,分别为国内所有期刊信息库、投稿指南(CSSCI版本、CSSCI扩展版本、北大核刊版本、建议期刊版本) 一、…

[.NET/WPF] CommunityToolkit.Mvvm 异步指令

我们在开发中, 经常会有这样的需求: 点击按钮后, 进行一些耗时的工作工作进行时, 按钮不可再次被点击工作进行时, 会显示进度条, 或者 “加载中” 的动画 RelayCommand CommunityToolkit.Mvvm 中的 RelayCommand 除了支持最简单的同步方法, 还支持以 Task 作为返回值的异步方…

一文详解4种聚类算法及可视化(Python)

在这篇文章中,基于20家公司的股票价格时间序列数据。根据股票价格之间的相关性,看一下对这些公司进行聚类的四种不同方式。 苹果(AAPL),亚马逊(AMZN),Facebook(META&…

OPTEE3.17+ubuntu20.04+qemu_v8搭建OPTEE开发环境

参考文章: https://blog.csdn.net/capodexi/article/details/123548850 https://blog.csdn.net/qq_42557044/article/details/130973200 https://blog.csdn.net/zhuwade/article/details/125513873 https://zhuanlan.zhihu.com/p/521196386 https://blog.csdn.net/…

Stable Diffusion的使用以及各种资源

Stable Diffsuion资源目录 SD简述sd安装模型下载关键词,描述语句插件管理controlNet自己训练模型 SD简述 Stable Diffusion是2022年发布的深度学习文本到图像生成模型。它主要用于根据文本的描述产生详细图像,尽管它也可以应用于其他任务,如…

数据暴涨时代,该如何数据治理?_光点科技

随着信息技术的迅猛发展,数据已经成为现代社会的核心资源。在这个被称为"数据暴涨时代"的时代里,大量的数据源源不断地被产生和积累,但如何有效地管理、分析和利用这些数据成为了一个迫切需要解决的问题。数据治理,作为…

C#学习....

1.基础 //引用命名空间using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;//项目名或者命名空间 namespace _01_MY_First_Demo {//Program类class Program{//程序的主入口或者Main函数static void Main(S…

常见的网络设备有哪些?分别有什么作用?

个人主页:insist--个人主页​​​​​​ 本文专栏:网络基础——带你走进网络世界 本专栏会持续更新网络基础知识,希望大家多多支持,让我们一起探索这个神奇而广阔的网络世界。 目录 一、网络设备的概述 二、常见的网络设备 1、…