首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

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

  • 23-09-05 19:02
  • 2123
  • 6929
blog.csdn.net

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

  • 引言
    • 回顾: Wolfe ext{Wolfe} Wolfe准则
    • 准备工作
      • 推导条件介绍
      • 推导结论介绍
    • 关于 Wolfe ext{Wolfe} Wolfe准则收敛性证明的推导过程

引言

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

回顾: Wolfe ext{Wolfe} Wolfe准则

关于先搜索方法表示如下:
x k + 1 = x k + α k ⋅ P k x_{k+1} = x_k + alpha_k cdot mathcal P_k xk+1​=xk​+αk​⋅Pk​
在数值解迭代过程中,当前时刻的迭代步长结果 α 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=0∞​⇒f∗的必要不充分条件;因而需要相比更严格的条件使目标函数收敛至最优解: Armijo ext{Armijo} Armijo准则、 Glodstein ext{Glodstein} Glodstein准则与 Wolfe ext{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 ) egin{aligned} &  ext{Armijo Condition : } egin{cases} phi(alpha) < f(x_k) + mathcal C_1 cdot [ abla f(x_k)]^T mathcal P_k cdot alpha \ quad \ mathcal C_1 in (0,1) end{cases} \ &  ext{Glodstein Condition : } egin{cases} f(x_k) + (1 - mathcal C) cdot [ abla f(x_k)]^T mathcal P_k cdot alpha leq phi(alpha) leq f(x_k) + mathcal C cdot [ abla f(x_k)]^T mathcal P_k cdot alpha \ quad \ mathcal C in egin{aligned}left(0,frac{1}{2} ight)end{aligned} end{cases} end{aligned} ​Armijo Condition : ⎩ ⎨ ⎧​ϕ(α)<f(xk​)+C1​⋅[∇f(xk​)]TPk​⋅αC1​∈(0,1)​Glodstein Condition : ⎩ ⎨ ⎧​f(xk​)+(1−C)⋅[∇f(xk​)]TPk​⋅α≤ϕ(α)≤f(xk​)+C⋅[∇f(xk​)]TPk​⋅αC∈(0,21​)​​​

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

基于上述因素, Wlofe ext{Wlofe} Wlofe准则在 Armijo ext{Armijo} Armijo准则的基础上,建立软性规则以筛选优质的 α alpha α结果:
其中 ϕ ′ ( α ) = ∂ f ( x k + α ⋅ P k ) ∂ α = [ ∇ f ( x k + α ⋅ P k ) ] T P k ϕ′(α)=∂f(xk+α⋅Pk)∂α=[∇f(xk+α⋅Pk)]TPk ϕ′(α)=∂α∂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 ) {ϕ(α)≤f(xk)+C1⋅[∇f(xk)]TPk⋅αϕ′(α)≥C2⋅[∇f(xk)]TPkC1∈(0,1)C2∈(C1,1) ⎩ ⎨ ⎧​ϕ(α)≤f(xk​)+C1​⋅[∇f(xk​)]TPk​⋅αϕ′(α)≥C2​⋅[∇f(xk​)]TPk​C1​∈(0,1)C2​∈(C1​,1)​
本节以 Wolfe ext{Wolfe} Wolfe准则为例,简单介绍该准则的收敛性证明。

准备工作

推导条件介绍

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

  • 关于 f ( X ) f(mathcal X) f(X)的梯度函数 ∇ f ( X ) abla f(mathcal X) ∇f(X),需要在定义域内满足利普希茨连续 ( Lipschitz Continuity ) ( ext{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. || abla f(x) - abla f(hat x)|| leq mathcal L cdot ||x - hat x|| ∀x,x^∈Rn,∃L:s.t.∣∣∇f(x)−∇f(x^)∣∣≤L⋅∣∣x−x^∣∣
    如果一个普通函数 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} ight| ight| leq mathcal L ∣∣G(x)−G(x^)∣∣≤L⋅∣∣x−x^∣∣⇒ ​ ​x−x^G(x)−G(x^)​ ​ ​≤L
    关于小于号左侧的式子格式: ∣ ∣ G ( x ) − G ( x ^ ) x − x ^ ∣ ∣ ||G(x)−G(ˆx)x−ˆx|| ​ ​x−x^G(x)−G(x^)​ ​ ​​,根据拉格朗日中值定理,可将该式表示为如下形式:
    ∃ ξ ∈ ( x , x ^ ) ⇒ ∣ ∣ G ( x ) − G ( x ^ ) x − x ^ ∣ ∣ = G ′ ( ξ ) exist xi in (x,hat x) Rightarrow ||G(x)−G(ˆx)x−ˆx|| = mathcal G'(xi) ∃ξ∈(x,x^)⇒ ​ ​x−x^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 ) abla f(mathcal X) ∇f(X)服从利普希兹连续可理解为:对目标函数的二阶梯度结果进行约束:
    ∂ ∇ f ( X ) ∂ X ≤ L ∂∇f(X)∂X leq mathcal L ∂X∂∇f(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 ∂f∂x=2x ∂x∂f​=2x​,是一个关于 x x x的一次函数,在定义域 x ∈ R x in mathbb R x∈R中,其并不受某常数 L mathcal L L的约束。
    当 x ⇒ ∞ x Rightarrow infty x⇒∞时,对应的 ∂ f ∂ x ⇒ ∞ ∂f∂x⇒∞ ∂x∂f​⇒∞​。
    再如: f ( x ) = 1 x f(x)=1x f(x)=x1​​。对应函数图像表示如下:
    不满足利普希兹连续的连续函数示例2
    同理,关于该函数的一阶导函数 ∂ f ∂ x = − 1 x 2 ∂f∂x=−1x2 ∂x∂f​=−x21​​,在其定义域 x > 0 x > 0 x>0中,其同样不受某常数 L mathcal L L的约束。
    当 x ⇒ 0 x Rightarrow 0 x⇒0时,对应的 ∂ f ∂ x = − ∞ ∂f∂x=−∞ ∂x∂f​=−∞​。
    可以看出:上述两个例子在其对应的定义域内均是连续的,但它们不满足利普希兹连续。也就是说:利普希兹连续的条件更强。
    关于连续相关概念按照条件强度对比表示为:连续 < < < 一致连续 < < < 利普希兹连续(利普希兹条件)。

    • 上述条件强度可理解为:
      若某函数在其定义域内满足利普希兹连续,那么该函数一定满足一致连续和连续,反之不行;
      同理,若某函数在其定义域内满足一致连续,那么该函数一定满足连续,反之不行
      。
    • 其中一致连续与连续之间的区别可描述为:连续仅要求函数在其定义域内没有断点或者跳跃的情况;而一致连续在没有断点或者跳跃的基础上,还需要满足:函数 f ( ⋅ ) f(cdot) f(⋅)在定义域内任意的两个点 x 、 y x、y x、y,如果 x x x与 y y y充分接近时,对应的 f ( x ) f(x) f(x)与 f ( y ) f(y) f(y)也要充分接近。很明显,上例中的 f ( x ) = 1 x f(x)=1x
      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 ) ( ext{Descent Direction}) (Descent Direction)。
    这里使用的是更加泛化的‘下降方向’,而不仅仅是最速下降方向。其在非精确搜索方法中被确定下的。关于下降方向详见线搜索方法——精确搜索。
    P k mathcal P_k Pk​作为下降方向,必然有:
    − [ ∇ f ( x k ) ] T P k = ∣ ∣ ∇ f ( x k ) ∣ ∣ ⋅ ∣ P k ∣ ∣ cos ⁡ θ k > 0 - [ abla f(x_k)]^T mathcal P_k = || abla f(x_k)|| cdot |mathcal P_k|| cos heta_k> 0 −[∇f(xk​)]TPk​=∣∣∇f(xk​)∣∣⋅∣Pk​∣∣cosθk​>0
    其中 θ k heta_k θk​是负梯度方向 − ∇ f ( x k ) - abla f(x_k) −∇f(xk​)与下降方向 P k mathcal P_k Pk​之间的夹角,因而该夹角的范围必然在 ( − π 2 , π 2 ) (−π2,π2) (−2π​,2π​)​之间。也就是说: cos ⁡ θ k > 0 cos heta_k >0 cosθk​>0恒成立:
    也可以理解为 − ∇ f ( x k ) - abla f(x_k) −∇f(xk​)与 P k mathcal P_k Pk​两者之间的夹角是锐角(没有先后顺序),对应的范围是 ( 0 , π 2 ) (0,π2) (0,2π​)​。
    cos ⁡ θ k = − [ ∇ f ( x k ) ] T P k ∣ ∣ ∇ f ( x k ) ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ > 0 cosθk=−[∇f(xk)]TPk||∇f(xk)||⋅||Pk||>0 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 ext{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 ) {f(xk+1)<f(xk)+C1⋅[∇f(xk)]TPk⋅αk[∇f(xk+1)]TPk≥C2⋅[∇f(xk)]TPkC1∈(0,1)C2∈(C1,1) ⎩ ⎨ ⎧​f(xk+1​)<f(xk​)+C1​⋅[∇f(xk​)]TPk​⋅αk​[∇f(xk+1​)]TPk​≥C2​⋅[∇f(xk​)]TPk​C1​∈(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=0∞​⇒f∗
如果从梯度的角度观察,关于数值解序列对应的目标函数梯度结果 { ∇ f ( x k ) } k = 0 ∞ { abla 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} || abla f(x_k)|| = 0 k⇒+∞lim​∣∣∇f(xk​)∣∣=0
根据上面关于 θ k heta_k θk​的描述,将其控制为:
[ cos ⁡ θ k ] 2 ≥ η [cos heta_k]^2 geq eta [cosθk​]2≥η
其中 η eta η表示一个 > 0 > 0 >0的小的常数。基于此,关于 ∑ k = 0 ∞ [ cos ⁡ θ k ] 2 ∞∑k=0[cosθk]2 k=0∑∞​[cosθk​]2​的结果必定是发散的。也就是说: + ∞ +infty +∞个 > 0 >0 >0的较小常数相加必然还是 + ∞ +infty +∞。
∑ k = 0 + ∞ [ cos ⁡ θ k ] 2 = + ∞ sum_{k=0}^{+infty} [cos heta_k]^2 = +infty k=0∑+∞​[cosθk​]2=+∞
如果将推导结论设置为如下形式:
∑ k = 0 + ∞ [ cos ⁡ θ k ] 2 ⋅ ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 < + ∞ sum_{k=0}^{+infty} [cos heta_k]^2 cdot || abla 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 heta_k]^2 cdot || abla f(x_k)||^2 ∑k=0+∞​[cosθk​]2⋅∣∣∇f(xk​)∣∣2与关于 cos ⁡ θ k cos heta_k cosθk​的项 ∑ k = 0 + ∞ [ cos ⁡ θ k ] 2 sum_{k=0}^{+infty} [cos heta_k]^2 ∑k=0+∞​[cosθk​]2相矛盾。这只有一种解释:

  • 随着 k k k值的增加,使得 lim ⁡ k ⇒ + ∞ ∣ ∣ ∇ f ( x k ) ∣ ∣ = 0 mathop{lim}limits_{k Rightarrow +infty} || abla f(x_k)|| = 0 k⇒+∞lim​∣∣∇f(xk​)∣∣=0;
  • 从而使 lim ⁡ k ⇒ + ∞ ∣ ∣ ∇ f ( x k ) ∣ ∣ 2 = 0 mathop{lim}limits_{k Rightarrow +infty} || abla 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 heta_k]^2 cdot || abla f(x_k)||^2 < mathop{lim}limits_{k Rightarrow +infty} [cos heta_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 heta_k]^2 cdot || abla f(x_k)||^2 < sum_{k=0}^{+infty}[cos heta_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 heta_k]^2 cdot || abla f(x_k)||^2 < +infty Leftrightarrow lim_{k Rightarrow infty} || abla f(x_k)|| = 0 k=0∑+∞​[cosθk​]2⋅∣∣∇f(xk​)∣∣2<+∞⇔k⇒∞lim​∣∣∇f(xk​)∣∣=0

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

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

证明:

  • 基于 Wolfe ext{Wolfe} Wolfe准则中的 [ ∇ f ( x k + 1 ) ] T P k ≥ C 2 ⋅ [ ∇ f ( x k ) ] T P k [ abla f(x_{k+1})]^T mathcal P_k geq mathcal C_2 cdot [ abla f(x_k)]^T mathcal P_k [∇f(xk+1​)]TPk​≥C2​⋅[∇f(xk​)]TPk​,将不等式两端同时减去 [ ∇ f ( x k ) ] T P k [ abla 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 [∇f(xk+1)]TPk−[∇f(xk)]TPk≥C2⋅[∇f(xk)]TPk−[∇f(xk)]TPk⇒{[∇f(xk+1)]−[∇f(xk)]}TPk≥(C2−1)⋅[∇f(xk)]TPk ​[∇f(xk+1​)]TPk​−[∇f(xk​)]TPk​≥C2​⋅[∇f(xk​)]TPk​−[∇f(xk​)]TPk​⇒{[∇f(xk+1​)]−[∇f(xk​)]}TPk​≥(C2​−1)⋅[∇f(xk​)]TPk​​
    观察不等式左侧,可以将 { [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] } T P k left{ [ abla f(x_{k+1})] - [ abla f(x_k)] ight}^T mathcal P_k {[∇f(xk+1​)]−[∇f(xk​)]}TPk​视作两个向量之间的内积。基于此,必然满足如下表达:
    因为 cos ⁡ θ cos heta cosθ的值域是 [ − 1 , 1 ] [-1,1] [−1,1]。其中 θ heta θ表示向量 [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] [ abla f(x_{k+1})] - [ abla 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{ [ abla f(x_{k+1})] - [ abla f(x_k)] ight}^T mathcal P_k = ||[ abla f(x_{k+1})] - [ abla f(x_k)]|| cdot ||mathcal P_k|| cdot cos heta \ quad \ ||[ abla f(x_{k+1})] - [ abla f(x_k)]|| cdot ||mathcal P_k|| cdot cos heta leq ||[ abla f(x_{k+1})] - [ abla 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 ||[ abla f(x_{k+1})] - [ abla f(x_k)]|| cdot ||mathcal P_k|| geq left{ [ abla f(x_{k+1})] - [ abla f(x_k)] ight}^T mathcal P_k geq (mathcal C_2 -1) cdot [ abla f(x_k)]^T mathcal P_k ∣∣[∇f(xk+1​)]−[∇f(xk​)]∣∣⋅∣∣Pk​∣∣≥{[∇f(xk+1​)]−[∇f(xk​)]}TPk​≥(C2​−1)⋅[∇f(xk​)]TPk​

  • 观察式子 ∣ ∣ [ ∇ f ( x k + 1 ) ] − [ ∇ f ( x k ) ] ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ ||[ abla f(x_{k+1})] - [ abla 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​+αk​⋅Pk​代入。

    ∣ ∣ [ ∇ 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 ||[∇f(xk+1)]−[∇f(xk)]||⋅||Pk||≤L⋅||xk+1−xk||⋅||Pk||=L⋅||αk⋅Pk||⋅||Pk||=L⋅αk⋅||Pk||2 ∣∣[∇f(xk+1​)]−[∇f(xk​)]∣∣⋅∣∣Pk​∣∣​≤L⋅∣∣xk+1​−xk​∣∣⋅∣∣Pk​∣∣=L⋅∣∣αk​⋅Pk​∣∣⋅∣∣Pk​∣∣=L⋅αk​⋅∣∣Pk​∣∣2​
    至此,可以得到式子:
    由于 α k , ∣ ∣ P k ∣ ∣ 2 alpha_k,||mathcal P_k||^2 αk​,∣∣Pk​∣∣2均恒正;且不等式右侧 C 2 − 1 < 0 , [ ∇ f ( x k ) ] T P k < 0 mathcal C_2 -1 <0,[ abla f(x_k)]^T mathcal P_k <0 C2​−1<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 [ abla f(x_k)]^T mathcal P_k L⋅αk​⋅∣∣Pk​∣∣2≥(C2​−1)⋅[∇f(xk​)]TPk​
    将 L , ∣ ∣ P k ∣ ∣ 2 mathcal L,||mathcal P_k||^2 L,∣∣Pk​∣∣2移到大于等于号右侧,符号不发生变化:
    α 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{[ abla f(x_k)]^T mathcal P_k}{||mathcal P_k||^2} αk​≥LC2​−1​⋅∣∣Pk​∣∣2[∇f(xk​)]TPk​​

  • 至此,将上式与 Wolfe ext{Wolfe} Wolfe准则的第一项关联起来:
    由于 C 1 ⋅ [ ∇ f ( x k ) ] T P k < 0 mathcal C_1 cdot [ abla 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 [ abla f(x_k)]^T mathcal P_k cdot left(frac{mathcal C_2 - 1}{mathcal L} cdot frac{[ abla f(x_k)]^T mathcal P_k}{||mathcal P_k||^2} ight) geq mathcal C_1 cdot [ abla f(x_k)]^T mathcal P_k cdot alpha_k C1​⋅[∇f(xk​)]TPk​⋅(LC2​−1​⋅∣∣Pk​∣∣2[∇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 [ abla f(x_k)]^T mathcal P_k cdot left(frac{mathcal C_2 - 1}{mathcal L} cdot frac{[ abla f(x_k)]^T mathcal P_k}{||mathcal P_k||^2} ight) f(xk+1​)≤f(xk​)+C1​⋅[∇f(xk​)]TPk​⋅(LC2​−1​⋅∣∣Pk​∣∣2[∇f(xk​)]TPk​​)
    观察小于等于号右侧后一项:将其描述成分式形式,会包含一个关于 [ ∇ f ( x k ) ] T P k [ abla f(x_k)]^T mathcal P_k [∇f(xk​)]TPk​的平方项,因此使用 [ ∇ f ( x k ) ] T P k = − ∣ ∣ ∇ f ( x k ) ∣ ∣ ⋅ ∣ ∣ P k ∣ ∣ ⋅ cos ⁡ θ k [ abla f(x_k)]^T mathcal P_k = -|| abla f(x_k)|| cdot ||mathcal P_k|| cdot cos heta_k [∇f(xk​)]TPk​=−∣∣∇f(xk​)∣∣⋅∣∣Pk​∣∣⋅cosθk​进行替换:

    • 其中负号消掉了;
    • ∣ ∣ P k ∣ ∣ 2 ||mathcal P_k||^2 ∣∣Pk​∣∣2消掉了。
      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 f(xk+1)≤f(xk)+C1⋅(C2−1)L⋅||∇f(xk)||2⋅||Pk||2⋅[cosθk]2||Pk||2=f(xk)+C1⋅(C2−1)L||∇f(xk)||2⋅[cosθk]2
      f(xk+1​)​≤f(xk​)+LC1​⋅(C2​−1)​⋅∣∣Pk​∣∣2∣∣∇f(xk​)∣∣2⋅∣∣Pk​∣∣2⋅[cosθk​]2​=f(xk​)+LC1​⋅(C2​−1)​∣∣∇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 C1⋅(C2−1)L||∇f(xk)||2⋅[cosθk]2
      LC1​⋅(C2​−1)​∣∣∇f(xk​)∣∣2⋅[cosθk​]2​
      记作 I k mathcal I_k Ik​。
    • 展开过程中由于 C 1 ⋅ ( C 2 − 1 ) L < 0 C1⋅(C2−1)L<0
      LC1​⋅(C2​−1)​<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 f(xk+1)≤f(xk)+Ik≤f(xk−1)+Ik−1+Ik≤⋯≤f(x0)+C1⋅(C2−1)Lk∑j=0Ij=f(x0)+C1⋅(C2−1)Lk∑j=0||∇f(xj)||2⋅[cosθj]2
      f(xk+1​)​≤f(xk​)+Ik​≤f(xk−1​)+Ik−1​+Ik​≤⋯≤f(x0​)+LC1​⋅(C2​−1)​j=0∑k​Ij​=f(x0​)+LC1​⋅(C2​−1)​j=0∑k​∣∣∇f(xj​)∣∣2⋅[cosθj​]2​
  • 观察上式,由于目标函数 f ( ⋅ ) f(cdot) f(⋅)是向下有界的,这意味着:从 f ( x 0 ) f(x_0) f(x0​)开始迭代的过程中,每一次迭代减少的程度:
    因为描述迭代过程中减小的幅度,那么 C 1 ⋅ ( C 2 − 1 ) L C1⋅(C2−1)L LC1​⋅(C2​−1)​​的负号就消掉了,而对应数值部分作为常数不会对极限产生影响,因而整个项都可以被忽略掉。
    ∣ 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) X∈Rnmin​f(X),而不是让这个迭代结果一直无限地小下去。

    从而当 j → ∞ j o 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} || abla f(x_j)||^2 cdot [cos heta_j]^2 < infty k⇒∞lim​j=0∑k​∣∣∇f(xj​)∣∣2⋅[cosθj​]2<∞
    整理可得:
    ∑ j = 0 ∞ ∣ ∣ ∇ f ( x j ) ∣ ∣ 2 ⋅ [ cos ⁡ θ j ] 2 < ∞ sum_{j=0}^{infty}|| abla f(x_j)||^2 cdot [cos heta_j]^2 < infty j=0∑∞​∣∣∇f(xj​)∣∣2⋅[cosθj​]2<∞

证毕。

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

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览51117 人正在系统学习中
注:本文转载自blog.csdn.net的静静的喝酒的文章"https://blog.csdn.net/qq_34758157/article/details/132062800"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top