机器学习笔记之优化算法(八)简单认识Wolfe Condition的收敛性证明

机器学习笔记之优化算法——简单认识Wolfe Condition收敛性证明

引言

上一节介绍了非精确搜索方法—— Wolfe \text{Wolfe} Wolfe准则。本节将简单认识: Wolfe \text{Wolfe} Wolfe准则的收敛性证明

回顾: Wolfe \text{Wolfe} Wolfe准则

关于先搜索方法表示如下:
x k + 1 = x k + α k ⋅ P k x_{k+1} = x_k + \alpha_k \cdot \mathcal P_k xk+1=xk+αkPk
数值解迭代过程中,当前时刻的迭代步长结果 α k \alpha_k αk未确定的情况下,将步长设为变量 α \alpha α。在下降方向 P k \mathcal P_k Pk确定的条件下,关于 x k + 1 x_{k+1} xk+1目标函数结果 f ( x k + 1 ) f(x_{k+1}) f(xk+1)可表示为关于变量 α \alpha α的函数 ϕ ( α ) \phi(\alpha) ϕ(α)
f ( x k + 1 ) = f ( x k + α ⋅ P k ) = ϕ ( α ) f(x_{k+1}) = f(x_k + \alpha \cdot \mathcal P_k) = \phi(\alpha) f(xk+1)=f(xk+αPk)=ϕ(α)
由于 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk)}k=0服从严格的单调性仅是目标函数收敛至最优解 { f ( x k ) } k = 0 ∞ ⇒ f ∗ \{f(x_k)\}_{k=0}^{\infty} \Rightarrow f^* {f(xk)}k=0f必要不充分条件;因而需要相比更严格的条件使目标函数收敛至最优解: Armijo \text{Armijo} Armijo准则 Glodstein \text{Glodstein} Glodstein准则 Wolfe \text{Wolfe} Wolfe准则
Armijo Condition :  { ϕ ( α ) < f ( x k ) + C 1 ⋅ [ ∇ f ( x k ) ] T P k ⋅ α C 1 ∈ ( 0 , 1 ) Glodstein Condition :  { f ( x k ) + ( 1 − C ) ⋅ [ ∇ f ( x k ) ] T P k ⋅ α ≤ ϕ ( α ) ≤ f ( x k ) + C ⋅ [ ∇ f ( x k ) ] T P k ⋅ α C ∈ ( 0 , 1 2 ) \begin{aligned} & \text{Armijo Condition : } \begin{cases} \phi(\alpha) < f(x_k) + \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha \\ \quad \\ \mathcal C_1 \in (0,1) \end{cases} \\ & \text{Glodstein Condition : } \begin{cases} f(x_k) + (1 - \mathcal C) \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha \leq \phi(\alpha) \leq f(x_k) + \mathcal C \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha \\ \quad \\ \mathcal C \in \begin{aligned}\left(0,\frac{1}{2}\right)\end{aligned} \end{cases} \end{aligned} Armijo Condition :  ϕ(α)<f(xk)+C1[f(xk)]TPkαC1(0,1)Glodstein Condition :  f(xk)+(1C)[f(xk)]TPkαϕ(α)f(xk)+C[f(xk)]TPkαC(0,21)

Wolfe \text{Wolfe} Wolfe准则的初衷是为了处理 Armijo \text{Armijo} Armijo准则与 Goldstein \text{Goldstein} Goldstein准则的共同弊端:仅通过划分边界 ( Armijo ) (\text{Armijo}) (Armijo)或者划分边界构成的范围 ( Glodstein ) (\text{Glodstein}) (Glodstein)对相应的 α \alpha α结果进行筛选,而被选择的 α \alpha α结果是否存在意义 ? ? ? 未知

基于上述因素, Wlofe \text{Wlofe} Wlofe准则 Armijo \text{Armijo} Armijo准则的基础上,建立软性规则以筛选优质的 α \alpha α结果
其中 ϕ ′ ( α ) = ∂ f ( x k + α ⋅ P k ) ∂ α = [ ∇ f ( x k + α ⋅ P k ) ] T P k \begin{aligned}\phi'(\alpha) = \frac{\partial f(x_k + \alpha \cdot \mathcal P_k)}{\partial \alpha} = \left[\nabla f(x_k + \alpha \cdot \mathcal P_k)\right]^T \mathcal P_k \end{aligned} ϕ(α)=αf(xk+αPk)=[f(xk+αPk)]TPk
{ ϕ ( α ) ≤ f ( x k ) + C 1 ⋅ [ ∇ f ( x k ) ] T P k ⋅ α ϕ ′ ( α ) ≥ C 2 ⋅ [ ∇ f ( x k ) ] T P k C 1 ∈ ( 0 , 1 ) C 2 ∈ ( C 1 , 1 ) \begin{cases} \phi(\alpha) \leq f(x_k) +\mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha \\ \phi'(\alpha) \geq \mathcal C_2 \cdot [\nabla f(x_k)]^T \mathcal P_k \\ \mathcal C_1 \in (0,1) \\ \mathcal C_2 \in (\mathcal C_1,1) \end{cases} ϕ(α)f(xk)+C1[f(xk)]TPkαϕ(α)C2[f(xk)]TPkC1(0,1)C2(C1,1)
本节以 Wolfe \text{Wolfe} Wolfe准则为例,简单介绍该准则的收敛性证明

准备工作

推导条件介绍

  • 关于目标函数优化的终极目标 min ⁡ X ∈ R n f ( X ) \mathop{\min}\limits_{\mathcal X \in \mathbb R^n} f(\mathcal X) XRnminf(X),因而对于目标函数 f ( X ) f(\mathcal X) f(X),需要满足:向下有界,并且在定义域内连续可微
    这属于函数自身的性质,在迭代过程中不能无限地小下去。

  • 关于 f ( X ) f(\mathcal X) f(X)梯度函数 ∇ f ( X ) \nabla f(\mathcal X) f(X),需要在定义域内满足利普希茨连续 ( Lipschitz Continuity ) (\text{Lipschitz Continuity}) (Lipschitz Continuity)。对应数学符号表示如下:
    其中 L \mathcal L L是一个常数。
    ∀ x , x ^ ∈ R n , ∃ L : s . t . ∣ ∣ ∇ f ( x ) − ∇ f ( x ^ ) ∣ ∣ ≤ L ⋅ ∣ ∣ x − x ^ ∣ ∣ \forall x,\hat x \in \mathbb R^n, \exist \mathcal L :\quad s.t. ||\nabla f(x) - \nabla f(\hat x)|| \leq \mathcal L \cdot ||x - \hat x|| x,x^Rn,L:s.t.∣∣∇f(x)f(x^)∣∣L∣∣xx^∣∣
    如果一个普通函数 G ( x ) \mathcal G(x) G(x)满足利普希兹连续,可以将上述描述使用 G ( x ) \mathcal G(x) G(x)进行替换,并进行简单变换:
    ∣ ∣ G ( x ) − G ( x ^ ) ∣ ∣ ≤ L ⋅ ∣ ∣ x − x ^ ∣ ∣ ⇒ ∣ ∣ G ( x ) − G ( x ^ ) x − x ^ ∣ ∣ ≤ L ||\mathcal G(x) - \mathcal G(\hat x)|| \leq \mathcal L \cdot ||x - \hat x|| \Rightarrow \left|\left|\frac{\mathcal G(x) - \mathcal G(\hat x)}{x - \hat x}\right|\right| \leq \mathcal L ∣∣G(x)G(x^)∣∣L∣∣xx^∣∣ xx^G(x)G(x^) L
    关于小于号左侧的式子格式: ∣ ∣ G ( x ) − G ( x ^ ) x − x ^ ∣ ∣ \begin{aligned}\left|\left|\frac{\mathcal G(x) - \mathcal G(\hat x)}{x - \hat x}\right|\right|\end{aligned} xx^G(x)G(x^) ,根据拉格朗日中值定理,可将该式表示为如下形式:
    ∃ ξ ∈ ( x , x ^ ) ⇒ ∣ ∣ G ( x ) − G ( x ^ ) x − x ^ ∣ ∣ = G ′ ( ξ ) \exist \xi \in (x,\hat x) \Rightarrow \begin{aligned}\left|\left|\frac{\mathcal G(x) - \mathcal G(\hat x)}{x - \hat x}\right|\right|\end{aligned} = \mathcal G'(\xi) ξ(x,x^) xx^G(x)G(x^) =G(ξ)
    从而将利普希兹连续描述为如下形式:
    ∃ ξ ∈ ( x , x ^ ) ⇒ ∣ ∣ G ′ ( ξ ) ∣ ∣ ≤ L \exist \xi \in (x,\hat x) \Rightarrow ||\mathcal G'(\xi)|| \leq \mathcal L ξ(x,x^)∣∣G(ξ)∣∣L
    这意味着(不严谨):关于函数 G ( x ) \mathcal G(x) G(x)一阶导函数 G ′ ( x ) \mathcal G'(x) G(x)存在上界 L \mathcal L L。回到条件中,关于 ∇ f ( X ) \nabla f(\mathcal X) f(X)服从利普希兹连续可理解为:对目标函数的二阶梯度结果进行约束
    ∂ ∇ f ( X ) ∂ X ≤ L \begin{aligned}\frac{\partial \nabla f(\mathcal X)}{\partial \mathcal X}\end{aligned} \leq \mathcal L Xf(X)L
    根据二阶梯度的几何意义,该条件本质上是对目标函数 f ( X ) f(\mathcal X) f(X)中斜率的变化量进行约束。关于不满足利普希兹连续的函数示例: f ( x ) = x 2 f(x) = x^2 f(x)=x2。对应函数图像表示如下:
    不满足利普希兹连续的连续函数示例1
    关于该函数的一阶导函数 ∂ f ∂ x = 2 x \begin{aligned}\frac{\partial f}{\partial x} = 2x\end{aligned} xf=2x,是一个关于 x x x一次函数,在定义域 x ∈ R x \in \mathbb R xR中,其并不受某常数 L \mathcal L L的约束。
    x ⇒ ∞ x \Rightarrow \infty x时,对应的 ∂ f ∂ x ⇒ ∞ \begin{aligned}\frac{\partial f}{\partial x} \Rightarrow \infty \end{aligned} xf
    再如: f ( x ) = 1 x \begin{aligned}f(x) = \frac{1}{x}\end{aligned} f(x)=x1。对应函数图像表示如下:
    不满足利普希兹连续的连续函数示例2
    同理,关于该函数的一阶导函数 ∂ f ∂ x = − 1 x 2 \begin{aligned}\frac{\partial f}{\partial x} = -\frac{1}{x^2}\end{aligned} xf=x21,在其定义域 x > 0 x > 0 x>0中,其同样不受某常数 L \mathcal L L的约束。
    x ⇒ 0 x \Rightarrow 0 x0时,对应的 ∂ f ∂ x = − ∞ \begin{aligned}\frac{\partial f}{\partial x} = -\infty\end{aligned} xf=
    可以看出:上述两个例子在其对应的定义域内均是连续的,但它们不满足利普希兹连续。也就是说:利普希兹连续的条件更强
    关于连续相关概念按照条件强度对比表示为:连续 < < < 一致连续 < < < 利普希兹连续(利普希兹条件)

    • 上述条件强度可理解为:
      若某函数在其定义域内满足利普希兹连续,那么该函数一定满足一致连续连续,反之不行;
      同理,若某函数在其定义域内满足一致连续,那么该函数一定满足连续,反之不行
    • 其中一致连续连续之间的区别可描述为:连续仅要求函数在其定义域内没有断点或者跳跃的情况;而一致连续在没有断点或者跳跃的基础上,还需要满足:函数 f ( ⋅ ) f(\cdot) f()在定义域内任意的两个点 x 、 y x、y xy,如果 x x x y y y充分接近时,对应的 f ( x ) f(x) f(x) f ( y ) f(y) f(y)也要充分接近。很明显,上例中的 f ( x ) = 1 x \begin{aligned}f(x) = \frac{1}{x}\end{aligned} f(x)=x1就不是一致连续:首先 f ( x ) f(x) f(x)在其定义域 ( 0 , + ∞ ) (0,+\infty) (0,+)连续,但如果选择无限靠近 0 0 0的两个比较接近的点,它们的函数值并不充分接近 ( ∞ ) (\infty) ()
  • 条件 3 3 3 P k \mathcal P_k Pk下降方向 ( Descent Direction ) (\text{Descent Direction}) (Descent Direction)
    这里使用的是更加泛化的‘下降方向’,而不仅仅是最速下降方向。其在非精确搜索方法中被确定下的。关于下降方向详见线搜索方法——精确搜索。
    P k \mathcal P_k Pk作为下降方向,必然有:
    − [ ∇ f ( x k ) ] T P k = ∣ ∣ ∇ f ( x k ) ∣ ∣ ⋅ ∣ P k ∣ ∣ cos ⁡ θ k > 0 - [\nabla f(x_k)]^T \mathcal P_k = ||\nabla f(x_k)|| \cdot |\mathcal P_k|| \cos \theta_k> 0 [f(xk)]TPk=∣∣∇f(xk)∣∣Pk∣∣cosθk>0
    其中 θ k \theta_k θk负梯度方向 − ∇ f ( x k ) -\nabla f(x_k) f(xk)下降方向 P k \mathcal P_k Pk之间的夹角,因而该夹角的范围必然在 ( − π 2 , π 2 ) \begin{aligned}\left(-\frac{\pi}{2},\frac{\pi}{2}\right)\end{aligned} (2π,2π)之间。也就是说: cos ⁡ θ k > 0 \cos \theta_k >0 cosθk>0恒成立
    也可以理解为 − ∇ f ( x k ) -\nabla f(x_k) f(xk) P k \mathcal P_k Pk两者之间的夹角是锐角(没有先后顺序),对应的范围是 ( 0 , π 2 ) \begin{aligned}\left(0,\frac{\pi}{2}\right)\end{aligned} (0,2π)
    cos ⁡ θ k = − [ ∇ f ( x k ) ] T P k ∣ ∣ ∇ f ( x k ) ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ > 0 \begin{aligned} \cos \theta_k = \frac{-[\nabla f(x_k)]^T \mathcal P_k}{||\nabla f(x_k)||\cdot ||\mathcal P_k||} > 0 \end{aligned} cosθk=∣∣∇f(xk)∣∣∣∣Pk∣∣[f(xk)]TPk>0

  • 迭代过程中的最优步长 α k ( k = 1 , 2 , 3 , ⋯ ) \alpha_k(k=1,2,3,\cdots) αk(k=1,2,3,)满足 Wolfe \text{Wolfe} Wolfe准则
    该条件不再赘述。
    { f ( x k + 1 ) < f ( x k ) + C 1 ⋅ [ ∇ f ( x k ) ] T P k ⋅ α k [ ∇ f ( x k + 1 ) ] T P k ≥ C 2 ⋅ [ ∇ f ( x k ) ] T P k C 1 ∈ ( 0 , 1 ) C 2 ∈ ( C 1 , 1 ) \begin{cases} f(x_{k+1}) < f(x_k) + \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha_k \\ [\nabla f(x_{k+1})]^T \mathcal P_k \geq \mathcal C_2 \cdot [\nabla f(x_k)]^T \mathcal P_k \\ \mathcal C_1 \in (0,1) \\ \mathcal C_2 \in (\mathcal C_1,1) \end{cases} f(xk+1)<f(xk)+C1[f(xk)]TPkαk[f(xk+1)]TPkC2[f(xk)]TPkC1(0,1)C2(C1,1)

推导结论介绍

关于最终需要证明的收敛性,自然是数值解序列 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk}k=0对应的目标函数结果 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk)}k=0收敛到某最优解 f ∗ f^* f
{ f ( x k ) } k = 0 ∞ ⇒ f ∗ \{f(x_k)\}_{k=0}^{\infty} \Rightarrow f^* {f(xk)}k=0f
如果从梯度的角度观察,关于数值解序列对应的目标函数梯度结果 { ∇ f ( x k ) } k = 0 ∞ \{\nabla f(x_k)\}_{k=0}^{\infty} {f(xk)}k=0收敛到 0 0 0即可:
常数函数对应的梯度范数就是 0 0 0
lim ⁡ k ⇒ + ∞ ∣ ∣ ∇ f ( x k ) ∣ ∣ = 0 \mathop{\lim}\limits_{k \Rightarrow + \infty} ||\nabla f(x_k)|| = 0 k+lim∣∣∇f(xk)∣∣=0
根据上面关于 θ k \theta_k θk的描述,将其控制为:
[ cos ⁡ θ k ] 2 ≥ η [\cos \theta_k]^2 \geq \eta [cosθk]2η
其中 η \eta η表示一个 > 0 > 0 >0的小的常数。基于此,关于 ∑ k = 0 ∞ [ cos ⁡ θ k ] 2 \begin{aligned}\sum_{k=0}^{\infty} [\cos \theta_k]^2\end{aligned} k=0[cosθk]2的结果必定发散。也就是说: + ∞ +\infty + > 0 >0 >0的较小常数相加必然还是 + ∞ +\infty +
∑ k = 0 + ∞ [ cos ⁡ θ k ] 2 = + ∞ \sum_{k=0}^{+\infty} [\cos \theta_k]^2 = +\infty k=0+[cosθk]2=+
如果将推导结论设置为如下形式:
∑ k = 0 + ∞ [ cos ⁡ θ k ] 2 ⋅ ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 < + ∞ \sum_{k=0}^{+\infty} [\cos \theta_k]^2 \cdot ||\nabla f(x_k)||^2 < +\infty k=0+[cosθk]2∣∣∇f(xk)2<+
那么该式子必然等价于:
之所以等价是因为上式中的项 ∑ k = 0 + ∞ [ cos ⁡ θ k ] 2 ⋅ ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 \sum_{k=0}^{+\infty} [\cos \theta_k]^2 \cdot ||\nabla f(x_k)||^2 k=0+[cosθk]2∣∣∇f(xk)2与关于 cos ⁡ θ k \cos \theta_k cosθk的项 ∑ k = 0 + ∞ [ cos ⁡ θ k ] 2 \sum_{k=0}^{+\infty} [\cos \theta_k]^2 k=0+[cosθk]2相矛盾。这只有一种解释:

  • 随着 k k k值的增加,使得 lim ⁡ k ⇒ + ∞ ∣ ∣ ∇ f ( x k ) ∣ ∣ = 0 \mathop{\lim}\limits_{k \Rightarrow +\infty} ||\nabla f(x_k)|| = 0 k+lim∣∣∇f(xk)∣∣=0
  • 从而使 lim ⁡ k ⇒ + ∞ ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 = 0 \mathop{\lim}\limits_{k \Rightarrow +\infty} ||\nabla f(x_k)||^2 = 0 k+lim∣∣∇f(xk)2=0
  • 从而使 lim ⁡ k ⇒ + ∞ [ cos ⁡ θ k ] 2 ⋅ ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 < lim ⁡ k ⇒ + ∞ [ cos ⁡ θ k ] 2 = η \mathop{\lim}\limits_{k \Rightarrow +\infty}[\cos \theta_k]^2 \cdot ||\nabla f(x_k)||^2 < \mathop{\lim}\limits_{k \Rightarrow +\infty} [\cos \theta_k]^2 = \eta k+lim[cosθk]2∣∣∇f(xk)2<k+lim[cosθk]2=η
  • 最终使 ∑ k = 0 + ∞ [ cos ⁡ θ k ] 2 ⋅ ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 < ∑ k = 0 + ∞ [ cos ⁡ θ k ] 2 = + ∞ \sum_{k=0}^{+\infty} [\cos \theta_k]^2 \cdot ||\nabla f(x_k)||^2 < \sum_{k=0}^{+\infty}[\cos \theta_k]^2 = +\infty k=0+[cosθk]2∣∣∇f(xk)2<k=0+[cosθk]2=+
    ∑ k = 0 + ∞ [ cos ⁡ θ k ] 2 ⋅ ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 < + ∞ ⇔ lim ⁡ k ⇒ ∞ ∣ ∣ ∇ f ( x k ) ∣ ∣ = 0 \sum_{k=0}^{+\infty} [\cos \theta_k]^2 \cdot ||\nabla f(x_k)||^2 < +\infty \Leftrightarrow \lim_{k \Rightarrow \infty} ||\nabla f(x_k)|| = 0 k=0+[cosθk]2∣∣∇f(xk)2<+klim∣∣∇f(xk)∣∣=0

最终可以描述出 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk)}k=0可以收敛到最优解

关于 Wolfe \text{Wolfe} Wolfe准则收敛性证明的推导过程

证明:

  • 基于 Wolfe \text{Wolfe} Wolfe准则中的 [ ∇ f ( x k + 1 ) ] T P k ≥ C 2 ⋅ [ ∇ f ( x k ) ] T P k [\nabla f(x_{k+1})]^T \mathcal P_k \geq \mathcal C_2 \cdot [\nabla f(x_k)]^T \mathcal P_k [f(xk+1)]TPkC2[f(xk)]TPk,将不等式两端同时减去 [ ∇ f ( x k ) ] T P k [\nabla f(x_k)]^T \mathcal P_k [f(xk)]TPk,目的是凑出利普希兹条件
    [ ∇ f ( x k + 1 ) ] T P k − [ ∇ f ( x k ) ] T P k ≥ C 2 ⋅ [ ∇ f ( x k ) ] T P k − [ ∇ f ( x k ) ] T P k ⇒ { [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] } T P k ≥ ( C 2 − 1 ) ⋅ [ ∇ f ( x k ) ] T P k \begin{aligned} & \quad [\nabla f(x_{k+1})]^T \mathcal P_k - [\nabla f(x_k)]^T \mathcal P_k \geq \mathcal C_2 \cdot [\nabla f(x_k)]^T \mathcal P_k - [\nabla f(x_k)]^T \mathcal P_k \\ & \Rightarrow \left\{ [\nabla f(x_{k+1})] - [\nabla f(x_k)] \right\}^T \mathcal P_k \geq (\mathcal C_2 -1) \cdot [\nabla f(x_k)]^T \mathcal P_k \end{aligned} [f(xk+1)]TPk[f(xk)]TPkC2[f(xk)]TPk[f(xk)]TPk{[f(xk+1)][f(xk)]}TPk(C21)[f(xk)]TPk
    观察不等式左侧,可以将 { [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] } T P k \left\{ [\nabla f(x_{k+1})] - [\nabla f(x_k)] \right\}^T \mathcal P_k {[f(xk+1)][f(xk)]}TPk视作两个向量之间的内积。基于此,必然满足如下表达:
    因为 cos ⁡ θ \cos \theta cosθ的值域是 [ − 1 , 1 ] [-1,1] [1,1]。其中 θ \theta θ表示向量 [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] [\nabla f(x_{k+1})] - [\nabla f(x_k)] [f(xk+1)][f(xk)]与向量 P k \mathcal P_k Pk之间的夹角。
    { [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] } T P k = ∣ ∣ [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ ⋅ cos ⁡ θ ∣ ∣ [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ ⋅ cos ⁡ θ ≤ ∣ ∣ [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ \left\{ [\nabla f(x_{k+1})] - [\nabla f(x_k)] \right\}^T \mathcal P_k = ||[\nabla f(x_{k+1})] - [\nabla f(x_k)]|| \cdot ||\mathcal P_k|| \cdot \cos \theta \\ \quad \\ ||[\nabla f(x_{k+1})] - [\nabla f(x_k)]|| \cdot ||\mathcal P_k|| \cdot \cos \theta \leq ||[\nabla f(x_{k+1})] - [\nabla f(x_k)]|| \cdot ||\mathcal P_k|| {[f(xk+1)][f(xk)]}TPk=∣∣[f(xk+1)][f(xk)]∣∣∣∣Pk∣∣cosθ∣∣[f(xk+1)][f(xk)]∣∣∣∣Pk∣∣cosθ∣∣[f(xk+1)][f(xk)]∣∣∣∣Pk∣∣
    综上,可将式子整理为:
    ∣ ∣ [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ ≥ { [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] } T P k ≥ ( C 2 − 1 ) ⋅ [ ∇ f ( x k ) ] T P k ||[\nabla f(x_{k+1})] - [\nabla f(x_k)]|| \cdot ||\mathcal P_k|| \geq \left\{ [\nabla f(x_{k+1})] - [\nabla f(x_k)] \right\}^T \mathcal P_k \geq (\mathcal C_2 -1) \cdot [\nabla f(x_k)]^T \mathcal P_k ∣∣[f(xk+1)][f(xk)]∣∣∣∣Pk∣∣{[f(xk+1)][f(xk)]}TPk(C21)[f(xk)]TPk

  • 观察式子 ∣ ∣ [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ ||[\nabla f(x_{k+1})] - [\nabla f(x_k)]|| \cdot ||\mathcal P_k|| ∣∣[f(xk+1)][f(xk)]∣∣∣∣Pk∣∣,使用利普希兹条件将其转化为:

    • 其中 L \mathcal L L利普希兹条件中的常数;
    • x k + 1 = x k + α k ⋅ P k x_{k+1} = x_k + \alpha_k \cdot \mathcal P_k xk+1=xk+αkPk代入。

    ∣ ∣ [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ ≤ L ⋅ ∣ ∣ x k + 1 − x k ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ = L ⋅ ∣ ∣ α k ⋅ P k ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ = L ⋅ α k ⋅ ∣ ∣ P k ∣ ∣ 2 \begin{aligned} ||[\nabla f(x_{k+1})] - [\nabla f(x_k)]|| \cdot ||\mathcal P_k|| & \leq \mathcal L \cdot ||x_{k+1} - x_k|| \cdot ||\mathcal P_k||\\ & = \mathcal L \cdot ||\alpha_k \cdot \mathcal P_k|| \cdot ||\mathcal P_k||\\ & = \mathcal L \cdot \alpha_k \cdot ||\mathcal P_k||^2 \end{aligned} ∣∣[f(xk+1)][f(xk)]∣∣∣∣Pk∣∣L∣∣xk+1xk∣∣∣∣Pk∣∣=L∣∣αkPk∣∣∣∣Pk∣∣=Lαk∣∣Pk2
    至此,可以得到式子:
    由于 α k , ∣ ∣ P k ∣ ∣ 2 \alpha_k,||\mathcal P_k||^2 αk,∣∣Pk2均恒正;且不等式右侧 C 2 − 1 < 0 , [ ∇ f ( x k ) ] T P k < 0 \mathcal C_2 -1 <0,[\nabla f(x_k)]^T \mathcal P_k <0 C21<0,[f(xk)]TPk<0恒成立;因此 L \mathcal L L必然是一个 > 0 >0 >0的值。
    L ⋅ α k ⋅ ∣ ∣ P k ∣ ∣ 2 ≥ ( C 2 − 1 ) ⋅ [ ∇ f ( x k ) ] T P k \mathcal L \cdot \alpha_k \cdot ||\mathcal P_k||^2 \geq (\mathcal C_2 -1) \cdot [\nabla f(x_k)]^T \mathcal P_k Lαk∣∣Pk2(C21)[f(xk)]TPk
    L , ∣ ∣ P k ∣ ∣ 2 \mathcal L,||\mathcal P_k||^2 L,∣∣Pk2移到大于等于号右侧,符号不发生变化:
    α k ≥ C 2 − 1 L ⋅ [ ∇ f ( x k ) ] T P k ∣ ∣ P k ∣ ∣ 2 \alpha_k \geq \frac{\mathcal C_2 - 1}{\mathcal L} \cdot \frac{[\nabla f(x_k)]^T \mathcal P_k}{||\mathcal P_k||^2} αkLC21∣∣Pk2[f(xk)]TPk

  • 至此,将上式与 Wolfe \text{Wolfe} Wolfe准则的第一项关联起来
    由于 C 1 ⋅ [ ∇ f ( x k ) ] T P k < 0 \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k < 0 C1[f(xk)]TPk<0那么将上式代入,必然有:
    就是‘负的不那么厉害了~’
    C 1 ⋅ [ ∇ f ( x k ) ] T P k ⋅ ( C 2 − 1 L ⋅ [ ∇ f ( x k ) ] T P k ∣ ∣ P k ∣ ∣ 2 ) ≥ C 1 ⋅ [ ∇ f ( x k ) ] T P k ⋅ α k \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \left(\frac{\mathcal C_2 - 1}{\mathcal L} \cdot \frac{[\nabla f(x_k)]^T \mathcal P_k}{||\mathcal P_k||^2}\right) \geq \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \alpha_k C1[f(xk)]TPk(LC21∣∣Pk2[f(xk)]TPk)C1[f(xk)]TPkαk
    从而有:
    f ( x k + 1 ) ≤ f ( x k ) + C 1 ⋅ [ ∇ f ( x k ) ] T P k ⋅ ( C 2 − 1 L ⋅ [ ∇ f ( x k ) ] T P k ∣ ∣ P k ∣ ∣ 2 ) f(x_{k+1}) \leq f(x_k) + \mathcal C_1 \cdot [\nabla f(x_k)]^T \mathcal P_k \cdot \left(\frac{\mathcal C_2 - 1}{\mathcal L} \cdot \frac{[\nabla f(x_k)]^T \mathcal P_k}{||\mathcal P_k||^2}\right) f(xk+1)f(xk)+C1[f(xk)]TPk(LC21∣∣Pk2[f(xk)]TPk)
    观察小于等于号右侧后一项:将其描述成分式形式,会包含一个关于 [ ∇ f ( x k ) ] T P k [\nabla f(x_k)]^T \mathcal P_k [f(xk)]TPk平方项,因此使用 [ ∇ f ( x k ) ] T P k = − ∣ ∣ ∇ f ( x k ) ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ ⋅ cos ⁡ θ k [\nabla f(x_k)]^T \mathcal P_k = -||\nabla f(x_k)|| \cdot ||\mathcal P_k|| \cdot \cos \theta_k [f(xk)]TPk=∣∣∇f(xk)∣∣∣∣Pk∣∣cosθk进行替换:

    • 其中负号消掉了;
    • ∣ ∣ P k ∣ ∣ 2 ||\mathcal P_k||^2 ∣∣Pk2消掉了。
      f ( x k + 1 ) ≤ f ( x k ) + C 1 ⋅ ( C 2 − 1 ) L ⋅ ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 ⋅ ∣ ∣ P k ∣ ∣ 2 ⋅ [ cos ⁡ θ k ] 2 ∣ ∣ P k ∣ ∣ 2 = f ( x k ) + C 1 ⋅ ( C 2 − 1 ) L ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 ⋅ [ cos ⁡ θ k ] 2 \begin{aligned} f(x_{k+1}) & \leq f(x_k) + \frac{\mathcal C_1 \cdot (\mathcal C_2 - 1)}{\mathcal L} \cdot \frac{||\nabla f(x_k)||^2 \cdot ||\mathcal P_k||^2 \cdot [\cos \theta_k]^2}{||\mathcal P_k||^2} \\ & = f(x_k) + \frac{\mathcal C_1 \cdot (\mathcal C_2 - 1)}{\mathcal L} ||\nabla f(x_k)||^2 \cdot [\cos \theta_k]^2 \end{aligned} f(xk+1)f(xk)+LC1(C21)∣∣Pk2∣∣∇f(xk)2∣∣Pk2[cosθk]2=f(xk)+LC1(C21)∣∣∇f(xk)2[cosθk]2

    此时得到一个新的关于 { f ( x k ) } k = 0 ∞ \{f(x_{k})\}_{k=0}^{\infty} {f(xk)}k=0的递推式。从而可以得到 f ( x k + 1 ) f(x_{k+1}) f(xk+1) f ( x 0 ) f(x_0) f(x0)之间的关联关系:

    • 相当于将每一次迭代中间结果累加。
    • C 1 ⋅ ( C 2 − 1 ) L ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 ⋅ [ cos ⁡ θ k ] 2 \begin{aligned}\frac{\mathcal C_1 \cdot (\mathcal C_2 - 1)}{\mathcal L} ||\nabla f(x_k)||^2 \cdot [\cos \theta_k]^2\end{aligned} LC1(C21)∣∣∇f(xk)2[cosθk]2记作 I k \mathcal I_k Ik
    • 展开过程中由于 C 1 ⋅ ( C 2 − 1 ) L < 0 \begin{aligned}\frac{\mathcal C_1 \cdot (\mathcal C_2 - 1)}{\mathcal L} < 0\end{aligned} LC1(C21)<0是一个常数,直接提出即可。
      f ( x k + 1 ) ≤ f ( x k ) + I k ≤ f ( x k − 1 ) + I k − 1 + I k ≤ ⋯ ≤ f ( x 0 ) + C 1 ⋅ ( C 2 − 1 ) L ∑ j = 0 k I j = f ( x 0 ) + C 1 ⋅ ( C 2 − 1 ) L ∑ j = 0 k ∣ ∣ ∇ f ( x j ) ∣ ∣ 2 ⋅ [ cos ⁡ θ j ] 2 \begin{aligned} f(x_{k+1}) & \leq f(x_k) + \mathcal I_k \\ & \leq f(x_{k-1}) + \mathcal I_{k-1} + \mathcal I_k \\ & \leq \cdots \\ & \leq f(x_0) + \frac{\mathcal C_1 \cdot(\mathcal C_2 - 1)}{\mathcal L} \sum_{j=0}^{k} \mathcal I_j \\ & = f(x_0) + \frac{\mathcal C_1 \cdot (\mathcal C_2 - 1)}{\mathcal L} \sum_{j=0}^k ||\nabla f(x_j)||^2 \cdot [\cos \theta_j]^2 \end{aligned} f(xk+1)f(xk)+Ikf(xk1)+Ik1+Ikf(x0)+LC1(C21)j=0kIj=f(x0)+LC1(C21)j=0k∣∣∇f(xj)2[cosθj]2
  • 观察上式,由于目标函数 f ( ⋅ ) f(\cdot) f()是向下有界的,这意味着: f ( x 0 ) f(x_0) f(x0)开始迭代的过程中,每一次迭代减少的程度
    因为描述迭代过程中减小的幅度,那么 C 1 ⋅ ( C 2 − 1 ) L \begin{aligned}\frac{\mathcal C_1 \cdot (\mathcal C_2 - 1)}{\mathcal L}\end{aligned} LC1(C21)的负号就消掉了,而对应数值部分作为常数不会对极限产生影响,因而整个项都可以被忽略掉。
    ∣ f ( x j + 1 ) − f ( x j ) ∣ < ∞ j ∈ { 0 , 1 , 2 , 3 , ⋯ } |f(x_{j+1}) - f(x_j)| < \infty \quad j \in \{0,1,2,3,\cdots\} f(xj+1)f(xj)<j{0,1,2,3,}
    恒成立。因为优化目标是 min ⁡ X ∈ R n f ( X ) \mathop{\min}\limits_{\mathcal X \in \mathbb R^n} f(\mathcal X) XRnminf(X),而不是让这个迭代结果一直无限地小下去。

    从而 j → ∞ j \to \infty j时,由于迭代的 j j j项中每一项均 < ∞ < \infty <,那么最终的累加结果必然也 < ∞ < \infty <
    lim ⁡ k ⇒ ∞ ∑ j = 0 k ∣ ∣ ∇ f ( x j ) ∣ ∣ 2 ⋅ [ cos ⁡ θ j ] 2 < ∞ \mathop{\lim}\limits_{k \Rightarrow \infty} \sum_{j=0}^{k} ||\nabla f(x_j)||^2 \cdot [\cos \theta_j]^2 < \infty klimj=0k∣∣∇f(xj)2[cosθj]2<
    整理可得:
    ∑ j = 0 ∞ ∣ ∣ ∇ f ( x j ) ∣ ∣ 2 ⋅ [ cos ⁡ θ j ] 2 < ∞ \sum_{j=0}^{\infty}||\nabla f(x_j)||^2 \cdot [\cos \theta_j]^2 < \infty j=0∣∣∇f(xj)2[cosθj]2<

证毕。

相关参考:
【优化算法】线搜索方法-收敛性证明
Lagrange’s Mean Value Theorem - 拉格朗日中值定理

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

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

相关文章

【Python】从同步到异步多核:测试桩性能优化,加速应用的开发和验证

目录 测试工作中常用到的测试桩mock能力 应用场景 简单测试桩 http.server扩展&#xff1a;一行命令实现一个静态文件服务器 性能优化&#xff1a;使用异步响应 异步响应 能优化&#xff1a;利用多核 gunicorn 安装 gunicorn 使用 gunicorn 启动服务 性能优化&#…

linuxARM裸机学习笔记(2)----汇编LED灯实验

MX6ULL 的 IO IO的复用功能 这里的只使用了低五位&#xff0c;用来配置io口&#xff0c;其中bit0~bit3(MUX_MODE)就是设置 GPIO1_IO00 的复用功能的&#xff0c;GPIO1_IO00 一共可以复用为 9种功能 IO&#xff0c;分别对应 ALT0~ALT8。每种对应了不同的功能 io的属性配置 HY…

MATLAB(R2023a)添加工具箱TooLbox的方法-以GPOPS为例

一、找到工具箱存放位置 首先我们需要找到工具箱的存放位置&#xff0c;点击这个设置路径可以看到 我们的matlab工具箱的存放位置 C:\Program Files\MATLAB\R2023a\toolbox\matlab 从资源管理器中打开这个位置&#xff0c;可以看到里面各种工具箱 二、放入工具箱 解压我们…

【docker】docker私有仓库

目录 一、说明二、私有仓库搭建三、上传镜像到私有仓库四、从私有仓库拉取镜像 一、说明 1.docker官方的docker hub(https://hub.docker.com)是一个用于管理公共镜像的仓库&#xff0c;可以从上面拉取镜像到本地&#xff0c;也可以把自己的镜像推送上去 2.若服务器无法访问互联…

FreeRTOS(vTaskList与vTaskGetRunTimeStats)

目录 1、Cube配置 ①配置SYS ②配置TIM3 ③配置USART2 ④配置FreeRTOS ⑤配置中断优先级 2、代码添加改动 ①在main函数合适位置开启TIM3中断 ②修改HAL_TIM_PeriodElapsedCallback函数 ③完善两个相关函数 ④vTaskList与vTaskGetRunTimeStats的使用 vTaskList&#xff…

关于多媒体视频翻译,你了解多少?

近年来&#xff0c;随着多媒体视频行业的快速发展&#xff0c;观看中外视频已成为数千万人的日常习惯&#xff0c;进而促进了视频翻译需求量的不断增加。那么&#xff0c;如何做好多媒体视频翻译服务&#xff0c;关于多媒体视频翻译&#xff0c;你了解多少&#xff1f; 据了解&…

day5 6 7-牛客67道剑指offer-JZ43、45、49、50、51、52、53、55、79、数组中只出现一次的数字

文章目录 1. JZ43 整数中1出现的次数&#xff08;从1到n整数中1出现的次数&#xff09;2. JZ45 把数组排成最小的数3. JZ49 丑数最小堆三指针法 动态规划 4. JZ50 第一个只出现一次的字符5. JZ51 数组中的逆序对6. JZ52 两个链表的第一个公共结点迭代递归 7. JZ53 数字在升序数…

当编程式事务写在了声明式事务的代码中,会怎么样?

1、背景 上一篇文章&#xff0c;为解决大事务问题&#xff0c;将for循环的每个订单的处理放在了编程式事务的代码中&#xff0c;但是在落地的时候&#xff0c;遇到了一个比较特殊的情况&#xff0c;外层方法中使用了 Transactional注解&#xff0c;内部再用编程式事务&#xf…

大数据技术之Hadoop(二)

目录 一、Hadoop的诞生 二、大数据概述 三、大数据软件生态 3.1 数据存储相关技术 3.2 数据计算相关技术 3.3 数据传输相关技术 四、什么是Hadoop 本篇主要讲解大数据的核心概念以及Hadoop的基本介绍。 一、Hadoop的诞生 大数据的发展与日益庞大的数据量是密不可分的。从…

chaitin-Nginx+Docker

Nginx实战 任务一 1、源码包安装NGINX A&#xff0c;搭建Web Server&#xff0c;任意HTML页面&#xff0c;其8080端口提供Web访问服务&#xff0c;截图成功访问http(s)&#x1f615;/[Server1]:8080并且回显Web页面 官网地址&#xff1a;http://nginx.org/en/download.html 步骤…

webpack基础知识十:与webpack类似的工具还有哪些?区别?

一、模块化工具 模块化是一种处理复杂系统分解为更好的可管理模块的方式 可以用来分割&#xff0c;组织和打包应用。每个模块完成一个特定的子功能&#xff0c;所有的模块按某种方法组装起来&#xff0c;成为一个整体(bundle) 在前端领域中&#xff0c;并非只有webpack这一款…

力扣初级算法(二分查找)

力扣初级算法(二分法)&#xff1a; 每日一算法&#xff1a;二分法查找 学习内容&#xff1a; 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 2.二分查找流程&…

深度学习——划分自定义数据集

深度学习——划分自定义数据集 以人脸表情数据集raf_db为例&#xff0c;初始目录如下&#xff1a; 需要经过处理后返回 train_images, train_label, val_images, val_label 定义 read_split_data(root: str, val_rate: float 0.2) 方法来解决&#xff0c;代码如下&#xff1a…

[openCV]基于拟合中线的智能车巡线方案V3

import cv2 as cv import os import numpy as np# 遍历文件夹函数 def getFileList(dir, Filelist, extNone):"""获取文件夹及其子文件夹中文件列表输入 dir&#xff1a;文件夹根目录输入 ext: 扩展名返回&#xff1a; 文件路径列表"""newDir d…

SpringBoot 自动配置--常用配置

&#x1f600;前言 本篇博文是关于SpringBoot 自动配置的一些分享&#xff0c;希望能够帮助到您&#x1f60a; &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到大家&#xff0c;您…

关于安卓jar包修改并且重新发布

背景&#xff1a; 对于某些jar包&#xff0c;其内部是存在bug的&#xff0c;解决的方法无外乎就有以下几种方法&#xff1a; &#xff08;1&#xff09;通过反射&#xff0c;修改其赋值逻辑 &#xff08;2&#xff09;通过继承&#xff0c;重写其方法 &#xff08;3&#xff0…

【java安全】CommonsBeanUtils1

文章目录 【java安全】CommonsBeanUtils1前言Apache Commons BeanutilsBeanComparator如何调用BeanComparator#compare()方法&#xff1f;构造POC完整POC 调用链 【java安全】CommonsBeanUtils1 前言 在之前我们学习了java.util.PriorityQueue&#xff0c;它是java中的一个优…

MyCat水平分表

1.水平拆分案例场景 2.MyCat配置 这个表只是在 schema.xml配置的逻辑表&#xff0c;在具体的数据库里面是没有的 根据id的模确定数据存在哪个节点上&#xff01;&#xff01;

数据结构与算法基础到高级,直击BTAJ,刷爆Letcode

数据结构与算法基础到高级&#xff0c;直击BTAJ&#xff0c;刷爆Letcode &#x1f384;前序补充&#x1f355;异或&#x1f354;对数器 &#x1f384;时间、空间复杂度&#x1f35f;空间复杂度基本概念&#x1f32d;时间复杂度基本概念&#x1f37f;基本的排序算法的时间复杂度…

在linux系统上安装Nginx

1、关闭防火墙 systemctl disable firewalld.service 2、上传压缩包并解压到目标文件 cd /usr/local tar -zxvf nginx-1.22.0.tar.gz 3、安装Nginx相关依赖 yum install -y gcc-c zlib zlib-developenssl openssl-devel pcre pcre-devel 4、安装完毕后&#xff0c;进入ng…