机器学习笔记之优化算法(十九)经典牛顿法的收敛性分析

引言

上一节整体介绍了经典牛顿法，并讨论了其更新方向${\mathcal{P}}_k$是否为下降方向。本节将对经典牛顿法在迭代过程中的收敛性进行分析。

回顾：算法的收敛性分析

在这些迭代算法中，我们关注的重点在于算法在迭代过程中是否收敛，以及它的收敛速度。

$\text{Wolfe}$准则的收敛性分析

在简单认识$\text{Wolfe Condition}$收敛性证明一节中，对于线搜索方法使用非精确搜索在迭代过程中使用$\text{Wolfe}$准则选取优质步长，并证明该方法能够使目标函数结果 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk​)}k=0∞​收敛到最优解$f^{\ast }$。对应条件、结论表示如下：

条件：

• 关于函数$f(\cdot )$，需要满足向下有界，并且在其定义域内连续可微；
• 关于梯度函数$\nabla f(\cdot )$，需要在定义域内满足$\mathcal{L}$-利普希兹连续；
• 关于更新方向${\mathcal{P}}_k(k=1,2,\cdots )$至少是下降方向$(\text{Descent Direction})$；
• 迭代过程中选择的优质步长${\alpha }_k(k=1,2,\cdots )$满足$\text{Wolfe}$准则；
  $$\{\begin{array}{l}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\ge {\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{array}$$

结论：关于 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk​)}k=0∞​收敛到最优解$f^{\ast }$的延展性结果：
$$\sum _{k=0}^{+\infty }[\cos {\theta }_k{]}^2\cdot ||\nabla f(x_k)|{|}^2<+\infty$$

关于证明过程不再赘述，详见链接，后续同理。观察$\text{Wolfe}$准则的收敛性定理，可以发现：

• 该方法对于函数$f(\cdot )$、更新方向的约束是较宽松的：$f(\cdot )$有下界、可微、$\nabla f(\cdot )$利普希兹连续；而且证明过程中使用的是较泛化的线搜索方法。
• 但对最终的收敛性仅仅证明了其可以收敛，但并没有描述具体的收敛速度。

梯度下降法在凸函数的收敛性分析

在梯度下降法——凸函数上的收敛性一节中，使用梯度下降法在更新方向${\mathcal{P}}_k$确定为最速下降方向(负梯度方向)的条件下，对于凸函数$f(\cdot )$选取优质步长，证明了目标函数结果 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk​)}k=0∞​收敛至目标函数最优解$f^{\ast }$，并以次线性收敛级别的收敛速度进行收敛。对应条件、结论表示如下：

条件：

• 关于函数$f(\cdot )$向下有界，在定义域内可微，并且$f(\cdot )$是凸函数；
• 关于梯度函数$\nabla f(\cdot )$满足$\mathcal{L}$-利普希兹连续；
• 在迭代过程中，关于步长${\alpha }_k(k=1,2,\cdots )$存在明确的约束范围：$\begin{array}{r}{\alpha }_k\in \left(0,\frac{1}{\mathcal{L}}\right]\end{array}$；

结论：目标函数结果 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk​)}k=0∞​以$\begin{array}{r}\mathcal{G}(k)=\mathcal{C}\cdot \frac{1}{k}\end{array}$收敛类型$\begin{array}{r}\mathcal{O}\left(\frac{1}{k}\right)\end{array}$的次线性收敛级别的收敛速度。
关于收敛速度的类型与级别，详见收敛速度的简单认识。

观察梯度下降法关于凸函数的收敛性定理，可以发现：

• 相比于$\text{Wolfe}$准则中线搜索方法对于更新方向${\mathcal{P}}_k$是下降方向的要求，梯度下降法关于更新方向的要求更加严格：最速下降方向。
• 关于目标函数$f(\cdot )$的要求也更加严格：$f(\cdot )$必须是凸函数；
• 相比于$\text{Wolfe}$准则关于${\alpha }_k$的约束条件：
  关于$\text{Wolfe}$准则关于步长的约束，这里使用图像进行示例表示。其中上界是$f(x_{k+1})<f(x_k)+{\mathcal{C}}_1\cdot [\nabla f(x_k){]}^T{\mathcal{P}}_k\cdot {\alpha }_k$(函数$\mathcal{L}(\alpha )$所在斜线以下);下界是$[\nabla f(x_{k+1}){]}^T{\mathcal{P}}_k\ge {\mathcal{C}}_2\cdot [\nabla f(x_k){]}^T{\mathcal{P}}_k$(斜率大于绿色点的横坐标范围)
  
  由于$f(\cdot )$是凸函数，因而步长${\alpha }_k$的选择范围被限制在$\begin{array}{r}\left(0,\frac{1}{\mathcal{L}}\right]\end{array}$。
  详见二次上界引理。
• 从结论的角度，相比于$\text{Wolfe}$准则，它有了明显的关于收敛速度的描述。

梯度下降法在强凸函数的收敛性分析

在梯度下降法——强凸函数的收敛性证明中，在$f(\cdot )$$m$-强凸函数的基础上，选取优质步长${\alpha }_k$，证明了数值解序列 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk​}k=0∞​收敛至最优数值解$x^{\ast }$，并以$\mathcal{Q}$-线性收敛级别的收敛速度进行收敛。对应条件、结论表示如下：

条件：

• 关于函数$f(\cdot )$向下有界，在其定义域内可微，并且$f(\cdot )$是$m$-强凸函数；
• 关于梯度函数$\nabla f(\cdot )$满足$\mathcal{L}$-利普希兹连续；
• 在迭代过程中，步长${\alpha }_k(k=1,2,3,\cdots )$存在明确的约束范围：$\begin{array}{r}\left(0,\frac{2}{\mathcal{L}+m}\right)\end{array}$

结论：数值解序列 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk​}k=0∞​以$\mathcal{Q}$-线性收敛的收敛速度收敛于最优数值解$x^{\ast }$。

观察梯度下降法关于强凸函数的收敛性定理，可以发现：

• 相比于凸函数的收敛性定理，关于目标函数$f(\cdot )$的要求更加严格：$m$-强凸函数。
• 关于${\alpha }_k$的约束条件更加严格：$\begin{array}{r}\left(0,\frac{1}{\mathcal{L}}\right)\Rightarrow \left(0,\frac{2}{\mathcal{L}+m}\right),\frac{2}{\mathcal{L}+m}\le \frac{1}{\mathcal{L}}\end{array}$。
• 从结论的角度，其收敛速度级别高于相应凸函数的收敛速度级别。

经典牛顿法的收敛性分析

收敛性定理介绍

经典牛顿法收敛性定理的描述表示如下：

条件：

• 关于函数$f(\cdot )$在其定义域内二阶连续可微；
  • 这意味着$\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(\cdot )$不仅存在，并且函数${\nabla }^{2}f(\cdot )$在定义域内同样连续。
  • 个人关于${\nabla }^{2}f(\cdot )$的误区更正:${\nabla }^{2}f(\cdot )$自身是一个函数，关于某向量$x\in {\mathbb{R}}^n$的结果$[{\nabla }^{2}f(x){]}_{n\times n}$是一个$\text{Hessian Matrix}$矩阵。
• 关于二阶梯度函数${\nabla }^{2}f(\cdot )$在最优值$x^{\ast }$的${\mathcal{N}}_{\sigma }(x^{\ast })$内满足$\mathcal{L}$-利普希兹连续；
  • 其中${\mathcal{N}}_{\sigma }(x^{\ast })$表示在最优值$x^{\ast }$为中心的$\sigma$邻域。如果$x^{\ast }$是一维的，那么它的邻域可表示为$(x-\sigma ,x+\sigma )$。
  • 相比于条件$1$,条件$2$使${\nabla }^{2}f(\cdot )$在其定义域内连续的基础上，进一步增强了约束:使最优值的邻域满足$\mathcal{L}$-利普希兹连续。关于连续、一致连续、$\mathcal{L}$-利普希兹连续的强度差异,详见传送门
• 关于梯度函数在$x^{\ast }$处的结果$\nabla f(x^{\ast })=0$，并且对应二阶梯度在$x^{\ast }$的结果${\nabla }^{2}f(\cdot )\succ 0$；
  • 该条件是条件$x^{\ast }$是函数$f(\cdot )$极小值点的充分不必要条件。
  • 个人理解 -> 单看这一个条件，我们需要警惕的是：这里并没有说$f(\cdot )$是一个凸函数/$m$-强凸函数，它可能仅是一个普通的复杂函数。因而该条件仅能确定$x^{\ast }$是$f(\cdot )$极小值点中的某一个。

结论：
若$x_0$与$x^{\ast }$足够近，那么数值解序列 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk​}k=0∞​以$\mathcal{Q}$-二次收敛的收敛速度收敛于最优数值解$x^{\ast }$。

• 这里本质上说的是$x_0$,但实际上该结论要求数值解序列 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk​}k=0∞​中的所有点都要离$x^{\ast }$足够近。因为$x_0$是随机初始化的结果，如果$x_0$离$x^{\ast }$足够近，那么其他迭代点$x_1,x_2,\cdots$必然只会离$x^{\ast }$足够近。
• 根据$\mathcal{Q}$-二次收敛的定义，需要满足：
  $$\begin{array}{r}\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }|{|}^2}\le \mathcal{C}\in (0,+\infty )\end{array}$$

证明过程

首先观察分子：$||x_{k+1}-x^{\ast }||$，关于$x_{k+1}$，在经典牛顿法中，它的步长${\alpha }_k=1$；假设在$x_k$点处的$\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(x_k)$是正定的，根据牛顿方程，当前迭代步骤的最优方向${\mathcal{P}}_k$表示为：
实际上，整个迭代过程，每个步骤产生的$x_k$对应的${\nabla }^{2}f(x_k)$都被认为是正定的。
$$\{\begin{array}{l}{x}_{k+1}=x_k+1\cdot {\mathcal{P}}_k\\ {\mathcal{P}}_k=-[{\nabla }^{2}f(x_k){]}^{-1}\nabla f(x_k)\end{array}$$
那么最终分子部分可表示为：

• 将$[{\nabla }^{2}f(x_k)]$提出来，由于$x_{k+1},x^{\ast }$的系数都是单位矩阵$\mathcal{I}$,因此根据$\mathcal{I}=[{\nabla }^{2}f(x_k){]}^{-1}[{\nabla }^{2}f(x_k)]$,从而提出公因式$[{\nabla }^{2}f(x_k){]}^{-1}$。
• 为了与$(x_k-x^{\ast })$的格式匹配，并且根据条件:$\nabla f(x^{\ast })=0$,因此在末尾添加一个$\nabla f(x^{\ast })$并不影响等号的变化。
  ∥ x k + 1 − x ∗ ∥ = ∥ x k − [ ∇ 2 f ( x k ) ] − 1 ∇ f ( x k ) − x ∗ ∥ = ∥ [ ∇ 2 f ( x k ) ] − 1 [ ∇ 2 f ( x k ) ] x k ⏟ x k − [ ∇ 2 f ( x k ) ] − 1 ∇ f ( x k ) − [ ∇ 2 f ( x k ) ] − 1 [ ∇ 2 f ( x k ) ] x ∗ ⏟ x ∗ ∥ = ∥ [ ∇ 2 f ( x k ) ] − 1 [ ∇ 2 f ( x k ) ⋅ ( x k − x ∗ ) − ∇ f ( x k ) ] ∥ = ∥ [ ∇ 2 f ( x k ) ] − 1 [ ∇ 2 f ( x k ) ⋅ ( x k − x ∗ ) − ( ∇ f ( x k ) − ∇ f ( x ∗ ) ⏟ ∇ f ( x k ) ; ∇ f ( x ∗ ) = 0 ) ] ∥ \begin{aligned} \|x_{k+1} - x^*\| & = \left\|x_k - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k) - x^* \right\| \\ & = \left\Vert\underbrace{[\nabla^2 f(x_k)]^{-1} [\nabla^2 f(x_k)] x_k}_{x_k} - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k) - \underbrace{[\nabla^2 f(x_k)]^{-1} [\nabla^2 f(x_k)] x^*}_{x^*}\right\Vert \\ & = \left\|[\nabla^2 f(x_k)]^{-1} \left[\nabla^2 f(x_k) \cdot (x_k - x^*) - \nabla f(x_k)\right]\right\| \\ & = \left\|[\nabla^2 f(x_k)]^{-1} \left[\nabla^2 f(x_k) \cdot (x_k - x^*) - (\underbrace{\nabla f(x_k) - \nabla f(x^*)}_{\nabla f(x_k);\nabla f(x^*) = 0})\right]\right\| \end{aligned} ∥xk+1​−x∗∥​= ​xk​−[∇2f(xk​)]−1∇f(xk​)−x∗ ​= ​xk​ [∇2f(xk​)]−1[∇2f(xk​)]xk​​​−[∇2f(xk​)]−1∇f(xk​)−x∗ [∇2f(xk​)]−1[∇2f(xk​)]x∗​​ ​= ​[∇2f(xk​)]−1[∇2f(xk​)⋅(xk​−x∗)−∇f(xk​)] ​= ​[∇2f(xk​)]−1 ​∇2f(xk​)⋅(xk​−x∗)−(∇f(xk​);∇f(x∗)=0 ∇f(xk​)−∇f(x∗)​​) ​ ​​

观察项：$\nabla f(x_k)-\nabla f(x^{\ast })$，它本质上是：函数一阶梯度$\nabla f(\cdot )$在$x_k,x^{\ast }$两点处的差值。而条件大多在二阶梯度上存在约束性。因此，这里通过技巧将$\nabla f(x_k)-\nabla f(x^{\ast })$进行转化：

• 对于$\forall x,y\in {\mathbb{R}}^n$，可以令$\lambda \in [0,1]$，将$\nabla f(y)-\nabla f(x)$转化成如下形式：
  • 当$\lambda =0$时，$x+\lambda \cdot (y-x)=x;$同理，当$\lambda =1$时，$x+\lambda \cdot (y-x)=y$。
  • 将最终结果表示成二阶梯度的定积分形式。
    $$\begin{array}{rl}\nabla f(y)-\nabla f(x)& =\nabla f[x+\lambda \cdot (y-x)]{|}_{\lambda =0}^1\\ & ={\int }_0^1{\nabla }^{2}f[x+\lambda \cdot (y-x)]\cdot (y-x)d\lambda \end{array}$$
• 令上例中$y=x^{\ast },x=x_k$，从而有：
  $$\nabla f(x_k)-\nabla f(x^{\ast })={\int }_0^1{\nabla }^{2}f[x_k+\lambda \cdot (x^{\ast }-x_k)]\cdot (x_k-x^{\ast })d\lambda$$

基于此，上述分子部分$\Vert x_{k+1}-x^{\ast }\Vert$可继续整理为：

• 由于项${\nabla }^{2}f(x_k)\cdot (x_k-x^{\ast })$中不含$\lambda$,可以将这一项继续改写成积分形式，从而进行合并。
• 在合并过程中，提出$x_k-x^{\ast }$。
  ∥ x k + 1 − x ∗ ∥ = ∥ [ ∇ 2 f ( x k ) ] − 1 ⋅ [ ∇ 2 f ( x k ) ⋅ ( x k − x ∗ ) − ∫ 0 1 ∇ 2 f [ x k + λ ⋅ ( x ∗ − x k ) ] ( x k − x ∗ ) d λ ] ∥ = ∥ [ ∇ 2 f ( x k ) ] − 1 ⋅ [ ∫ 0 1 ∇ 2 f ( x k ) ⋅ ( x k − x ∗ ) d λ ⏟ ∇ 2 f ( x k ) ⋅ ( x k − x ∗ ) − ∫ 0 1 ∇ 2 f [ x k + λ ⋅ ( x ∗ − x k ) ] ( x k − x ∗ ) d λ ] ∥ = ∥ [ ∇ 2 f ( x k ) ] − 1 ⋅ [ ∫ 0 1 ( x k − x ∗ ) ⋅ [ ∇ 2 f ( x k ) − ∇ 2 f [ x k + λ ⋅ ( x ∗ − x k ) ] ] d λ ] ∥ \begin{aligned} \|x_{k+1} - x^*\| & = \left\| [\nabla^2 f(x_k)]^{-1} \cdot \left[ \nabla^2 f(x_k) \cdot (x_k - x^*) - \int_{0}^1 \nabla^2 f[x_k + \lambda \cdot (x^* - x_k)](x_k - x^*) d\lambda \right] \right\| \\ & = \left\| [\nabla^2 f(x_k)]^{-1} \cdot \left[\underbrace{\int_0^1\nabla^2 f(x_k) \cdot (x_k - x^*) d \lambda}_{\nabla^2 f(x_k) \cdot (x_k - x^*)} - \int_{0}^1 \nabla^2 f[x_k + \lambda \cdot (x^* - x_k)](x_k - x^*) d\lambda \right] \right\| \\ & = \left\|[\nabla^2 f(x_k)]^{-1} \cdot \left[\int_0^1 (x_k - x^*) \cdot \left[\nabla^2 f(x_k) - \nabla^2 f[x_k + \lambda \cdot (x^* - x_k)] \right] d \lambda \right] \right\| \end{aligned} ∥xk+1​−x∗∥​= ​[∇2f(xk​)]−1⋅[∇2f(xk​)⋅(xk​−x∗)−∫01​∇2f[xk​+λ⋅(x∗−xk​)](xk​−x∗)dλ] ​= ​[∇2f(xk​)]−1⋅ ​∇2f(xk​)⋅(xk​−x∗) ∫01​∇2f(xk​)⋅(xk​−x∗)dλ​​−∫01​∇2f[xk​+λ⋅(x∗−xk​)](xk​−x∗)dλ ​ ​= ​[∇2f(xk​)]−1⋅[∫01​(xk​−x∗)⋅[∇2f(xk​)−∇2f[xk​+λ⋅(x∗−xk​)]]dλ] ​​

接下来，根据柯西施瓦茨不等式与积分的范数小于等于范数的积分两种方式对上式进行放缩：
关于积分的范数小于范数的积分的证明过程，这里推荐一篇文章，链接见文章末尾。
∥ x k + 1 − x ∗ ∥ = ∥ [ ∇ 2 f ( x k ) ] − 1 ⋅ [ ∫ 0 1 ( x k − x ∗ ) ⋅ [ ∇ 2 f ( x k ) − ∇ 2 f [ x k + λ ⋅ ( x ∗ − x k ) ] ] d λ ] ∥ ≤ ∥ ∇ 2 f ( x k ) ] − 1 ∥ ⋅ ∥ ∫ 0 1 ( x k − x ∗ ) ⋅ [ ∇ 2 f ( x k ) − ∇ 2 f [ x k + λ ⋅ ( x ∗ − x k ) ] ] d λ ∥ ≤ ∥ ∇ 2 f ( x k ) ] − 1 ∥ ⋅ ∫ 0 1 ∥ ( x k − x ∗ ) ⋅ [ ∇ 2 f ( x k ) − ∇ 2 f [ x k + λ ⋅ ( x ∗ − x k ) ] ] ∥ d λ ≤ ∥ ∇ 2 f ( x k ) ] − 1 ∥ ⋅ ∫ 0 1 ∥ x k − x ∗ ∥ ⋅ ∥ ∇ 2 f ( x k ) − ∇ 2 f [ x k + λ ⋅ ( x ∗ − x k ) ] ∥ d λ \begin{aligned} \|x_{k+1} - x^*\| & = \left\|[\nabla^2 f(x_k)]^{-1} \cdot \left[\int_0^1 (x_k - x^*) \cdot \left[\nabla^2 f(x_k) - \nabla^2 f[x_k + \lambda \cdot (x^* - x_k)] \right] d \lambda \right] \right\| \\ & \leq \left\|\nabla^2 f(x_k)]^{-1} \right\| \cdot \left\| \int_0^1 (x_k - x^*) \cdot \left[\nabla^2 f(x_k) - \nabla^2 f[x_k + \lambda \cdot (x^* - x_k)] \right] d \lambda\right\| \\ & \leq \left\|\nabla^2 f(x_k)]^{-1} \right\| \cdot \int_0^1 \left\|(x_k - x^*) \cdot \left[\nabla^2 f(x_k) - \nabla^2 f[x_k + \lambda \cdot (x^* - x_k)] \right] \right\| d\lambda \\ & \leq \left\|\nabla^2 f(x_k)]^{-1} \right\| \cdot \int_0^1 \left\|x_k - x^*\right\| \cdot \left\| \nabla^2 f(x_k) - \nabla^2 f[x_k + \lambda \cdot (x^* - x_k)] \right\| d\lambda \end{aligned} ∥xk+1​−x∗∥​= ​[∇2f(xk​)]−1⋅[∫01​(xk​−x∗)⋅[∇2f(xk​)−∇2f[xk​+λ⋅(x∗−xk​)]]dλ] ​≤ ​∇2f(xk​)]−1 ​⋅ ​∫01​(xk​−x∗)⋅[∇2f(xk​)−∇2f[xk​+λ⋅(x∗−xk​)]]dλ ​≤ ​∇2f(xk​)]−1 ​⋅∫01​ ​(xk​−x∗)⋅[∇2f(xk​)−∇2f[xk​+λ⋅(x∗−xk​)]] ​dλ≤ ​∇2f(xk​)]−1 ​⋅∫01​∥xk​−x∗∥⋅ ​∇2f(xk​)−∇2f[xk​+λ⋅(x∗−xk​)] ​dλ​
观察上式中积分号第二项： ∥ ∇ 2 f ( x k ) − ∇ 2 f [ x k + λ ⋅ ( x ∗ − x k ) ] ∥ \left\| \nabla^2 f(x_k) - \nabla^2 f[x_k + \lambda \cdot (x^* - x_k)] \right\| ​∇2f(xk​)−∇2f[xk​+λ⋅(x∗−xk​)] ​，它明显是一个二阶梯度减法的范数形式。根据条件：${\nabla }^{2}f(\cdot )$在$x^{\ast }$的$\sigma$邻域${\mathcal{N}}_{\sigma }(x^{\ast })$内满足$\mathcal{L}$-利普希兹连续，将该项继续进行放缩：

• 它实际上描述的是点$x_k$与$x_k,x^{\ast }$之间某一点$x_k+\lambda \cdot (x^{\ast }-x_k)$,两者的二阶梯度减法的范数。根据结论中描述的：如果$x_0$与$x^{\ast }$足够接近，那么$x_k$必然与$x^{\ast }$足够接近，从而$x_k+\lambda \cdot (x^{\ast }-x_k)$同样距离$x^{\ast }$足够接近。那么利普希兹连续的条件自然就满足了。
• 在本步骤中所描述的接近自然是指:$||x_k-x^{\ast }||\le \sigma$。
• 关于$\Vert x_k-x^{\ast }\Vert =\Vert x^{\ast }-x_k\Vert$，掉换一下位置并不影响范数的结果。并且$\lambda \in (0,1)$,将其提到范数外面。
  { ∥ ∇ 2 f ( x k ) − ∇ 2 f [ x k + λ ⋅ ( x ∗ − x k ) ] ∥ ≤ L ∥ [ x k + λ ( x ∗ − x k ) ] − x k ∥ = L ∣ ∣ λ ⋅ ( x ∗ − x k ) ∣ ∣ = L ⋅ λ ∥ x k − x ∗ ∥ ∥ x k + 1 − x ∗ ∥ ≤ ∥ ∇ 2 f ( x k ) ] − 1 ∥ ⋅ ∫ 0 1 ∥ x k − x ∗ ∥ ⋅ L ⋅ λ ∥ x k − x ∗ ∥ d λ = ∥ ∇ 2 f ( x k ) ] − 1 ∥ ⋅ ∥ x k − x ∗ ∥ 2 ⋅ L ∫ 0 1 λ d λ = ∥ ∇ 2 f ( x k ) ] − 1 ∥ ⋅ ∥ x k − x ∗ ∥ 2 ⋅ L 2 \begin{cases} \begin{aligned} \left\| \nabla^2 f(x_k) - \nabla^2 f[x_k + \lambda \cdot (x^* - x_k)] \right\| & \leq \mathcal L \left\|[x_k + \lambda (x^* - x_k)] - x_k\right\| \\ & = \mathcal L ||\lambda \cdot (x^* - x_k)|| \\ & = \mathcal L \cdot \lambda \left\|x_k - x^*\right\| \\ \|x_{k+1} - x^*\| & \leq \left\|\nabla^2 f(x_k)]^{-1} \right\| \cdot \int_0^1 \left\|x_k - x^*\right\| \cdot \mathcal L \cdot \lambda \left\|x_k - x^*\right\| d\lambda \\ & = \left\|\nabla^2 f(x_k)]^{-1} \right\| \cdot \left\|x_k - x^*\right\|^2 \cdot \mathcal L \int_0^1 \lambda d\lambda \\ & = \left\|\nabla^2 f(x_k)]^{-1} \right\| \cdot \left\|x_k - x^*\right\|^2 \cdot \frac{\mathcal L}{2} \end{aligned} \end{cases} ⎩ ⎨ ⎧​ ​∇2f(xk​)−∇2f[xk​+λ⋅(x∗−xk​)] ​∥xk+1​−x∗∥​≤L∥[xk​+λ(x∗−xk​)]−xk​∥=L∣∣λ⋅(x∗−xk​)∣∣=L⋅λ∥xk​−x∗∥≤ ​∇2f(xk​)]−1 ​⋅∫01​∥xk​−x∗∥⋅L⋅λ∥xk​−x∗∥dλ= ​∇2f(xk​)]−1 ​⋅∥xk​−x∗∥2⋅L∫01​λdλ= ​∇2f(xk​)]−1 ​⋅∥xk​−x∗∥2⋅2L​​​

至此，我们已经归纳出$\Vert x_{k+1}-x^{\ast }\Vert$与${\Vert x_k-x^{\ast }\Vert }^2$之间的关系。只需要证明：它们的比值$\le \mathcal{C}\in (0,+\infty )$即可。但项中 ∥ [ ∇ 2 f ( x k ) ] − 1 ∥ \left\|[\nabla^2 f(x_k)]^{-1}\right\| ​[∇2f(xk​)]−1 ​是与$x_k$相关的量，它并不是常数。因此需要借助条件，将其放缩到某常数。

由于函数$f(\cdot )$在其定义域二阶连续可微，那么二阶梯度函数${\nabla }^{2}f(\cdot )$在该定义域上连续。根据连续的定义，有：$\forall ϵ>0,\exists \gamma >0$,当$\Vert x_k-x^{\ast }\Vert \le \gamma$时， ∣ ∥ ∇ 2 f ( x k ) ∥ − ∥ ∇ 2 f ( x ∗ ) ∥ ∣ ≤ ϵ \left\vert \|\nabla^2 f(x_k)\| - \|\nabla^2 f(x^*)\| \right\vert \leq \epsilon ​∥∇2f(xk​)∥−∥∇2f(x∗)∥ ​≤ϵ

去掉绝对值符号，关于范数$\Vert {\nabla }^{2}f(x_k)\Vert$的范围可表示为：
$$\Vert {\nabla }^{2}f(x^{\ast })\Vert -ϵ\le \Vert {\nabla }^{2}f(x_k)\Vert \le \Vert {\nabla }^{2}f(x^{\ast })\Vert +ϵ$$

由于$ϵ$可以在$(0,+\infty )$内任意取值，因而不妨令$\begin{array}{r}ϵ=\frac{1}{2}||{\nabla }^{2}f(x^{\ast })||\end{array}$，从而有：
这里之所以设置系数$\begin{array}{r}\frac{1}{2}\end{array}$,目的是消除原式中$\begin{array}{r}\frac{\mathcal{L}}{2}\end{array}$内的$\begin{array}{r}\frac{1}{2}\end{array}$。
$$||{\nabla }^{2}f(x_k)||\ge \frac{1}{2}||{\nabla }^{2}f(x^{\ast })||$$
由于$x^{\ast }$是目标函数的最优解，它是一个不发生变化的常量，因此$\begin{array}{r}\frac{1}{2}||{\nabla }^{2}f(x^{\ast })||\end{array}$也同样是一个常量。因此，有：
∥ [ ∇ 2 f ( x k ) ] − 1 ∥ = 1 ∥ [ ∇ 2 f ( x k ) ] ∥ ≤ 2 ⋅ 1 ∣ ∣ ∇ 2 f ( x ∗ ) ∣ ∣ \left\|[\nabla^2 f(x_k)]^{-1}\right\| = \frac{1}{\left\|[\nabla^2 f(x_k)]\right\|} \leq 2 \cdot \frac{1}{||\nabla^2 f(x^*)||} ​[∇2f(xk​)]−1 ​=∥[∇2f(xk​)]∥1​≤2⋅∣∣∇2f(x∗)∣∣1​
回归原式，有：
∥ x k + 1 − x ∗ ∥ ≤ ∥ ∇ 2 f ( x k ) ] − 1 ∥ ⋅ ∥ x k − x ∗ ∥ 2 ⋅ L 2 ≤ 2 ⋅ 1 ∣ ∣ ∇ 2 f ( x ∗ ) ∣ ∣ ⋅ ∣ ∣ x k − x ∗ ∣ ∣ 2 ⋅ L 2 = ∣ ∣ x k − x ∗ ∣ ∣ 2 ⋅ L ⋅ 1 ∣ ∣ ∇ 2 f ( x ∗ ) ∣ ∣ \begin{aligned}\|x_{k+1} - x^*\| & \leq \left\|\nabla^2 f(x_k)]^{-1} \right\| \cdot \left\|x_k - x^*\right\|^2 \cdot \frac{\mathcal L}{2} \\ & \leq 2 \cdot \frac{1}{||\nabla^2 f(x^*)||} \cdot ||x_k - x^*||^2 \cdot \frac{\mathcal L}{2} \\ & = ||x_k - x^*||^2 \cdot \mathcal L \cdot \frac{1}{||\nabla^2 f(x^*)||} \end{aligned} ∥xk+1​−x∗∥​≤ ​∇2f(xk​)]−1 ​⋅∥xk​−x∗∥2⋅2L​≤2⋅∣∣∇2f(x∗)∣∣1​⋅∣∣xk​−x∗∣∣2⋅2L​=∣∣xk​−x∗∣∣2⋅L⋅∣∣∇2f(x∗)∣∣1​​
最终，有：
$$\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }|{|}^2}\le \frac{\mathcal{L}}{||{\nabla }^{2}f(x^{\ast })||}\in (0,+\infty )$$
得证。

关于隐含条件的说明

在上述证明过程中，我们令$\begin{array}{r}ϵ=\frac{1}{2}||{\nabla }^{2}f(x^{\ast })||\end{array}$，但真的可以这样取吗$?$换句话说：之所以可以这样取，是因为条件中存在隐含的嵌套条件，支持我们这样去取值：

观察条件$1$：函数$f(\cdot )$在定义域内二阶连续可微，可以知道${\nabla }^{2}f(\cdot )$在定义域内连续；
但又因为条件$2$，使得：${\nabla }^{2}f(\cdot )$在$x^{\ast }$的邻域${\mathcal{N}}_{\sigma }(x^{\ast })$内不仅连续，而且还是更强的$\mathcal{L}$-利普希兹连续；
根据$\mathcal{L}$-利普希兹连续与向量模的减法公式，可以得到如下的大小关系：
∣ ∥ ∇ 2 f ( x k ) ∥ − ∥ ∇ 2 f ( x ∗ ) ∥ ∣ ≤ ∥ ∇ 2 f ( x k ) − ∇ 2 f ( x ∗ ) ∥ ≤ L ⋅ ∥ x k − x ∗ ∥ \left\vert \|\nabla^2 f(x_k)\| - \|\nabla^2 f(x^*)\| \right\vert \leq \|\nabla^2 f(x_k) - \nabla^2 f(x^*)\| \leq \mathcal L \cdot \|x_k - x^*\| ​∥∇2f(xk​)∥−∥∇2f(x∗)∥ ​≤∥∇2f(xk​)−∇2f(x∗)∥≤L⋅∥xk​−x∗∥