Quasi-Newton and BFGS
Published:
整理了伪牛顿法的相关内容，篇幅大部分在于BFGS算法的收敛性和超线性收敛性的证明。
Quasi-Newton Method
伪牛顿法基于牛顿法的思想，我们知道牛顿法可以做到二次收敛，但牛顿法涉及Hesson矩阵的信息，伪牛顿法的思想是在不知道Hesson矩阵的前提下，仅仅利用一阶梯度信息，使用某个矩阵近似Hesson，从而达到比普通梯度算法更强的效果。可以证明，伪牛顿法可以做到超线性收敛。
BFGS Update
给定Hesson的近似$H_k$之后，拟牛顿法只要通过 线搜索算法 寻找满足Wolfe条件的点不断进行优化。
\[\begin{align} x_{k+1} = x_k - \alpha_k H_k^{-1} \nabla f_k \end{align}\]下面介绍如何给出伪牛顿法的迭代形式，首先更新的矩阵需要满足Secant方程，
\[\begin{align} H_{k+1} (x_{k+1} -x_k) &= \nabla f_{k+1} - \nabla f_k \end{align}\]我们希望在满足上述方程的前提之下，迭代前后的两个矩阵差异尽可能小，如果将Hesson矩阵看作正态分布的协方差矩阵，我们希望尽可能减小两个正态分布之间的 相对熵，并且我们希望该矩阵为对称正定矩阵，
\[\begin{align} &\min KL(\mathcal{N}(0,X) \Vert \mathcal{N}(0,H_k)) ,\text{st.} X s = y \\ =&\min tr(H_k X^{-1}) - \log \det (H_k X^{-1}) - n, \text{st.} X s = y \\ &\text{With } s = x_{k+1} - x_k , y = \nabla f_{k+1} - \nabla f_k \end{align}\]利用Lagrange乘子法求解上述方程，
\[\begin{align} L &= tr(H_k^{-1} X) - \log \det (H_k^{-1}X ) - n - v^T(X s- y)- tr(\Gamma^T(X-X^T)) \\ dL &= tr(H_k^{-1} dX) - tr(X^{-1} dX) - tr(sv^T dX) - tr((\Gamma - \Gamma^T)dX)= 0 \\ \frac{dL}{dX} &= H_{k}^{-1} - X^{-1} - sv^T - (\Gamma - \Gamma^T) =0 \end{align}\]下面求解$X$, 第一步是消去乘子$\Gamma$, \(\begin{align} H_{k+1}^{-1} &= H_k^{-1} - sv^T - (\Gamma - \Gamma^T) \\ H_{k+1}^{-1} &= H_k^{-1} - sv^T - (\Gamma^T - \Gamma) \\ H_{k+1}^{-1} &= H_k^{-1} - \frac{1}{2} (sv^T +vs^T) \\ \end{align}\)
在此基础上解得乘子$v$
\[\begin{align} s &= (H_k^{-1} - \frac{1}{2} (sv^T +vs^T) ) y \\ v &= \frac{2H_k^{-1}y - sv^T y- 2s}{y^T s} \\ v^T &= \frac{2y^TH_k^{-1} - s^Tv^T y- 2s^T}{y^T s} \\ \end{align}\]计算右端中的$v^Ty$一项，
\(\begin{align} v^T y &= \frac{2y^TH_k^{-1}y - v^T ys ^T y- 2s^Ty}{s^T y} \\ v^T y &= \frac{y^T H_k^{-1} y}{s^T y} - 1 \\ \end{align}\) 代入就可以计算得到$H_{k+1}$,
\[\begin{align} sv^T &= \frac{2sy^TH_k^{-1} - ss^Tv^T y- 2ss^T}{y^T s} \\ vs^T &= \frac{2H_k^{-1}ys^T - ss^Tv^T y- 2ss^T}{y^T s} \\ H_{k+1}^{-1} &= H_k^{-1} - \frac{1}{2} (sv^T +vs^T) \\ &=H_k^{-1} - \frac{sy^T H_k^{-1}+H_k^{-1}ys^T- ss^Tv^T y- 2ss^T}{y^T s} \\ &=H_k^{-1} - \frac{sy^T H_k^{-1}+H_k^{-1}ys^T- (\frac{y^T H_k^{-1} y}{s^T y} - 1)ss^T- 2ss^T}{y^T s} \\ &=H_k^{-1} - \frac{sy^T H_k^{-1}+H_k^{-1}ys^T- (\frac{y^T H_k^{-1} y}{s^T y} +1)ss^T}{y^T s} \\ &=(I - \frac{sy^T}{y^Ts}) H_k^{-1}(I- \frac{ys^T}{y^Ts}) + \frac{ss^T}{y^Ts} \end{align}\]最终得到了BFGS的迭代公式，可以看到其相当于对Hesson矩阵的逆做了修正, 后面我们还会看到利用Woodbury公式，其相当于Hesson矩阵做了秩二修正。
\[\begin{align} B_{k+1} &= (I - \frac{sy^T}{y^Ts}) B_k(I- \frac{ys^T}{y^Ts}) + \frac{ss^T}{y^Ts},\text{With }B_k = H_k^{-1} \end{align}\]而如果直接对其Hesson矩阵进行修正，可以类似地得到DFP迭代方法，
\[\begin{align} H_{k+1} &= (I - \frac{sy^T}{y^Ts}) H_k(I- \frac{ys^T}{y^Ts}) + \frac{ss^T}{y^Ts} \end{align}\]DFP方法可以看作是最小化下面的问题，因此其和BFGS是完全对称的，其算法性质都比较类似，
\[\min KL(\mathcal{N}(0,H_k) \Vert \mathcal{N}(0,H_{k+1})) ,\text{st.} H_{k+1} s = y \\\]而其他的方法也可以通过秩一修正得到更新后的近似Hesson矩阵，可以参见 Broyden Method
Convergence
本节讲解BFGS算法的收敛性，证明的技巧性非常强，但其中蕴含了非常多的信息。
收敛性的关键在于下降方向和梯度方向之间的夹角，我们利用其更新公式进行分析，
\[\begin{align} B_{k+1} &= (I - \frac{sy^T}{y^Ts}) B_k(I- \frac{ys^T}{y^Ts}) + \frac{ss^T}{y^Ts} \end{align}\]利用Woodbury公式直接对Hesson矩阵进行更新，
\[\begin{align} \text{Recall } (A+ U B V^T)^{-1} &= A^{-1} - A^{-1} U (B^{-1}- V^T A^{-1} U)^{-1} V^T A^{-1} \\ B_{k+1} &= (I - \frac{sy^T}{y^Ts}) B_k(I- \frac{ys^T}{y^Ts}) + \frac{ss^T}{y^Ts} \\ &=B_k - \gamma sy^T B_k - \gamma B_ky s^T + \gamma^2 sy^T B_k ys^T + \gamma ss^T, \text{With } \gamma = \frac{1}{y^T s} \\ &= B_k - \gamma [sy^T B_k - B_ky s^T + \gamma sy^T B_k ys^T + ss^T] \\ &= B_k - \gamma [sy^T B_k - B_ky s^T + (\gamma y^T B_k y+1)ss^T] \\ &= B_k - \gamma [s , Hy] \begin{bmatrix} \gamma y^T B_k y+1 & -1 \\ -1 & 0 \end{bmatrix} [s,B_k y]^T \\ B_{k+1}^{-1} &=B_k^{-1} -B_k^{-1} \frac{1}{s^T y}[s,B_ky] \begin{pmatrix} - \begin{bmatrix} 0 & 1 \\ 1 & 1+ \frac{y^T B_k y}{s^T y} \end{bmatrix} +\frac{1}{s^Ty}[s,B_ky]^TB_k^{-1} [s,B_ky] \end{pmatrix}^{-1} [s,B_ky]^T B_k^{-1} \\ &=B_k^{-1} -B_k^{-1} \frac{1}{s^T y}[s,B_ky] \begin{pmatrix} - \begin{bmatrix} 0 & 1 \\ 1 & 1+ \frac{y^T B_k y}{s^T y} \end{bmatrix} + \begin{bmatrix} \frac{s^TB_k^{-1}s }{s^T y} & 1\\ 1 & \frac{y^T B_k y}{s^T y } \end{bmatrix} \end{pmatrix}^{-1} [s,B_ky]^T B_k^{-1} \\ &= B_k^{-1} -B_k^{-1}[s, B_ky] \begin{pmatrix} \frac{1}{s^T B_k^{-1} s} & 0 \\ 0 &- \frac{1}{s^T y} \end{pmatrix} [s,B_ky]^T B_k^{-1} \\ &=B_k^{-1} - \frac{B_k^{-1}s s^T B_k^{-1}}{s^T B_k^{-1} s} + \frac{y^T y}{s^Ty} \\ H_{k+1} &= H_k - \frac{H_k ss^TH_k}{s^T H_ks} + \frac{yy^T}{s^Ty} \end{align}\]为了将其转化为相对熵，同时取迹和行列式，
\[\begin{align} tr(H_{k+1}) &= tr(H_k) + \frac{\Vert H_k s \Vert_2^2}{s^T H_k s} + \frac{\Vert y \Vert_2^2}{s^Ty} \\ \text{Use } \det(I +xy^T + uv^T) &= (1+y^T x)(1+v^T u) - (x^T v)(y^T u) \\ \det (H_{k+1}) &= \det(H_k) \det(I-\frac{ss^TH_k}{s^T H_ks} + \frac{H_k^{-1}yy^T}{s^Ty}) = \det(H_k) \frac{s^Ty}{s^T H_ks} \end{align}\]为了证明收敛性的成立，我们需要一个小的假设，假设函数的二阶导数$G(x) = \nabla^2 f(x)$ 在给定的区域内满足以下条件，
\[m \Vert x \Vert_2^2 \le x^T G x \le M \Vert x \Vert_2^2 , \exists m,M, \forall x,z\]该假设的含义是函数是一个$m$-强凸函数，同时是一个$M$-光滑函数，其实该假设也可以被放宽为仅仅在$f(x) \le f(x_0)$ 的区域上成立。
根据中值定理，并且利用上述的假设，
\[\begin{align} s_k &= \bar G_k y_k, \exists \bar G_k \\ m_k &=\frac{y_k^T s_k}{s_k^T s_k} = \frac{y_k^T \bar G_k y_k}{s_k^T s_k} \ge m \\ M_k &=\frac{y_k^T y_k}{y_k^T s_k} = \frac{y_k^T \bar G_k^2 y_k}{y_k^T \bar G_k y_k} \le M \end{align}\]利用上述得到的界，对函数进行放缩，我们知道在线搜索方法中，下降方向与最速下降方向的夹角与收敛率相关，定义如下的量，
\[\begin{align} \cos \theta_k &= \langle s_k,H_k s_k \rangle = \frac{s_k^T H_k s_k}{\Vert s_k \Vert \Vert H_k s_k \Vert} \\ q_k &= \frac{s_k^T H_ks_k}{s_k^Ts_k} \end{align}\]在线搜索满足Wolfe 条件的时候，我们有著名的结论，该证明可以阅读 线搜索算法
\[\begin{align} \lim_{n \rightarrow \infty} \cos^2 \theta_k \Vert \nabla f_k \Vert_2^2 = 0 \end{align}\]因此我们关心夹角的极限性质，例如如果其极限方向与最速方向相同，那么显然方法是收敛的
经过下面的简单推导可以发现，取学习率$\alpha=1$的时候，上述定义的正是我们所需要的夹角， \(\begin{align} \cos \theta_k &= \langle p_k ,\nabla f_k \rangle \\ &= \langle H_k^{-1}\nabla f_k,\nabla f_k \rangle \\ &=\langle p_k, H_k p_k \rangle \\ &=\langle s_k, H_k s_k \rangle, \text{With } s_k = x_{k+1} - x_k = \alpha p_k, \alpha=1 \end{align}\)
定义正态分布的熵为$\phi(x)$, 我们同样关心其递推关系，
\[\begin{align} \phi(H_{k+1}) &= tr(H_{k+1}) - \log \det (H_k) - n \\ &= tr(H_k) - \frac{\Vert H_k s_k \Vert_2^2}{s_k^T H_k s_k} + \frac{\Vert y_k \Vert_2^2}{y_k^T s_k} - \log \det (H_k) - \log \frac{s_k^Ty_k}{s_k^T H_ks_k} - n \\ &=\phi(H_k) - \frac{\Vert H_k s_k \Vert_2^2}{s_k^T H_k s_k} + \frac{\Vert y_k \Vert_2^2}{y_k^T s_k} - \log (s_k^Ty_k) + \log(s_k^T H_ks_k) \\ &= \phi(H_k) - \frac{q_k}{\cos^2 \theta_k} + M_k - \log m_k + \log q_k \\ &= \phi(H_k) +(M_k - \log m_k - 1) +(1- \frac{q_k}{\cos^2 \theta_k} + \log \frac{q_k}{\cos^2 \theta_k}) + \log \cos^2 \theta_k \\ & \le \phi(H_k) +(M- \log m -1) +(1- \frac{q_k}{\cos^2 \theta_k} + \log \frac{q_k}{\cos^2 \theta_k}) + \log \cos^2 \theta_k \\ & \le \phi(H_k) +(M- \log m -1) + \log \cos^2 \theta_k ,\text{By } x- 1 \ge \log x\\ \end{align}\]进行所有$k$步的求和可以得到，
\[\begin{align} \phi(H_{k+1}) \le \phi(H_0) + k(M- \log m - 1) +\sum_{j=0}^k \log \cos^2 \theta_j \end{align}\]根据线搜索的结论，我们只需要证明 $\lim_{k \rightarrow \infty} \cos^2 \theta_k \ne0$ 即可，我们使用反证法可以导出矛盾，因为我们已知熵是非负的
\[\begin{align} \text{If } \lim_{k \rightarrow \infty} \cos^2 \theta_k &\rightarrow 0 \\ \log \cos^2 \theta_k &\rightarrow -\infty \\ \log \cos^2 \theta_k &< -2(M- \log m -1), \forall k > k',\exists k' \\ \end{align}\]由此推出了矛盾，
\[\begin{align} 0 &\le \phi(H_{k+1}) \\ &\le\phi(H_0) + k(M- \log m - 1) +\sum_{j=0}^k \log \cos^2 \theta_j \\ &\le \phi(H_0) + k(M- \log m - 1) +\sum_{j=0}^{k'} \log \cos^2 \theta_j +\sum_{j=k'}^{k} \log \cos^2 \theta_j\\ &\le \phi(H_0) +\sum_{j=0}^{k'} [\log \cos^2 \theta_j+(M - \log m-1)] -(k-k')(M- \log m -1) \\ &<0 \end{align}\]因此我们可以得到BFGS算法的收敛性，采用类似的方法可以证明此类算法的收敛性
\[\begin{align} \lim_{k \rightarrow \infty} \cos^2 \theta_k \Vert \nabla f_k \Vert_2^2 &= 0 \\ \lim_{k \rightarrow \infty} \cos^2 \theta_k &\ne 0 \\ \text{Then } \lim_{k \rightarrow \infty} \inf\Vert \nabla f_k \Vert_2 &=0 \end{align}\]最后我们可以得到一个梯度趋于0的子列，这对于优化算法的收敛性来说已经足够了。
如果对上述证明做适当的延申，我们可以得到更强的命题，此处证明过程暂略，
\[\begin{align} \Vert \nabla f_k \Vert & \rightarrow 0 \\ \Vert x_k - x_{\star} \Vert & \rightarrow 0 \\ \sum_{j=0}^{\infty} \Vert x_k - x_{\star} \Vert & \rightarrow 0 \\ \end{align}\]前两个结论是直接得到的，而最后一个结论虽然没有给出证明，但其对于算法超线性收敛的证明是至关重要的，如果忽略证明过程，也可以将其当成一个强假设来看，以不影响后续的继续证明。
SuperLinear Convergence
我们显然不满足于简单的收敛性的证明，我们需要二阶导数局部Lipschitz连续的条件，
\[\begin{align} \Vert G(x) - G(x_{\star}) \Vert &\le L \Vert x - x_{\star} \Vert \\ \text{Or } \Vert G_k - G_{\star} \Vert &\le L \Vert x - x_{\star} \Vert \\ \end{align}\]证明中用到了一个预处理技巧，定义一个完全相同的更新，
我们后面将在看到，由于范数的等价性，对预处理后的更新证明收敛性，可以转化为对原本的更新的收敛性
\[\begin{align} H_{k+1} &= H_k - \frac{H_k s_ks_k^TH_k}{s_k^T H_ks_k} + \frac{y_ky_k^T}{s_k^Ty_k} \\ G_{\star}^{-\frac{1}{2}} H_{k+1} G_{\star}^{-\frac{1}{2}} &= G_{\star}^{-\frac{1}{2}} (H_k - \frac{H_k s_ks_k^TH_k}{s_k^T H_ks_k} + \frac{y_ky_k^T}{s_k^Ty_k})G_{\star}^{-\frac{1}{2}} \\ \tilde H_{k+1} &= \tilde H_k - \frac{\tilde H_k \tilde s_k \tilde s_k^T \tilde H_k}{\tilde s_k^T \tilde H_k \tilde s_k} + \frac{\tilde y_k \tilde y_k^T}{\tilde s_k^T\tilde y_k} \\ \text{With } \tilde H_k &=G_{\star}^{-\frac{1}{2}} H_{k} G_{\star}^{-\frac{1}{2}}, \tilde s_k =G_{\star}^{\frac{1}{2}}s_k, \tilde y_k =G_{\star}^{-\frac{1}{2}}y_k, \end{align}\]有了上述的定义，并且利用其局部连续性的假设，
\[\begin{align} \Vert \tilde y_k - \tilde s_k \Vert &= \Vert G_{\star}^{-\frac{1}{2}}y_k - G_{\star}^{\frac{1}{2}} s_k \Vert \\ &= \Vert G_{\star}^{-\frac{1}{2}} \bar G_k s_k - G_{\star}^{-\frac{1}{2}} G_{\star}s_k \Vert \\ &= \Vert G_{\star}^{-\frac{1}{2}} (\bar G_k -G_{\star}) G_{\star}^{-\frac{1}{2}} \tilde s_k \Vert \\ &\le \Vert G_{\star}^{-\frac{1}{2}} \Vert^2 \Vert \tilde s_k \Vert \Vert \bar G_k -G_{\star} \Vert \\ &\le L r\Vert G_{\star}^{-\frac{1}{2}} \Vert^2 \Vert \tilde s_k \Vert \\ \text{With } r&= \max(\vert x_k - x_{\star} \vert, \vert x_{k+1} - x_{\star} \vert) \end{align}\]综合上述式子，得到了关键的引理，
\[\begin{align} \frac{\Vert \tilde y_k - \tilde s_k \Vert}{\Vert \tilde s_k \Vert} \le cr , \exists \text{ const }c \end{align}\]根据上述的重要引理，可以给出预处理后的更新公式的界，回顾上式我们知道，
\[\begin{align} \phi(\tilde H_{k+1}) &\le \phi(\tilde H_{k}) + (\tilde M_k- \log \tilde m_k - 1) +\sum_{j=0}^k \log \cos^2 \tilde \theta_j \\ \end{align}\]利用距离的三角不等式，可以得到$\tilde m_k, \tilde M_k$更准的估计，
\[\begin{align} \Vert \tilde y_k - \tilde s_k \Vert &\le cr \Vert \tilde s_k \Vert \\ \Vert \tilde y_k \Vert - \Vert \tilde s_k \Vert &\le cr \Vert \tilde s_k \Vert \\ \Vert \tilde s_k \Vert - \Vert \tilde y_k \Vert &\le cr \Vert \tilde s_k \Vert \\ \end{align}\]综合起来就有，
\[\begin{align} (1-cr) \Vert \tilde s_k \Vert &\le \Vert \tilde y_k \Vert \le (1+cr) \Vert \tilde s_k \Vert \\ \end{align}\]对引理两边同时平方，
\[\begin{align} \Vert \tilde y_k \Vert^2 - 2 \tilde y_k^T \tilde s_k + \Vert \tilde s_k \Vert^2 &\le c^2r^2 \Vert \tilde s_k \Vert^2 \\ (1-cr)^2 \Vert \tilde s_k \Vert^2 - 2 \tilde y_k^T \tilde s_k + \Vert \tilde s_k \Vert^2 &\le c^2r^2 \Vert \tilde s_k \Vert^2 \\ (1-cr) \Vert \tilde s_k \Vert^2 &\le \tilde y_k^T\tilde s_k \end{align}\]经过一番放缩，我们终于得到了$\tilde m_k, \tilde M_k$的估计
\[\begin{align} \tilde m_k &= \frac{\tilde y_k^T \tilde s_k}{\Vert \tilde s_k \Vert^2} \ge 1-cr \\ \tilde M_k &= \frac{\Vert \tilde y_k \Vert^2}{\tilde y_k^T \tilde s_k} \le \frac{(1+cr) \Vert \tilde s_k \Vert^2}{\tilde y_k^T \tilde s_k} \le \frac{1+cr}{1-cr} \end{align}\]更进一步，利用上一节中的结论，我们知道$x \rightarrow x_{\star},r \rightarrow 0$, 因此可以得到$\tilde M_k$更为简单形式的上界，
\[\tilde M_k \le \frac{1+cr}{1-cr} \le1+ \frac{2cr}{1-cr} \le 1+dr, \exists d>c\]由此我们可以得到，
\[\begin{align} \phi(\tilde H_{k+1}) &\le \phi(\tilde H_{k}) + (\tilde M_k- \log \tilde m_k - 1) +\log \cos^2 \tilde \theta_k +(1- \frac{\tilde q_k}{\cos^2 \tilde \theta_k} + \log \frac{\tilde q_k}{\cos^2 \tilde\theta_k})\\ &\le \phi(\tilde H_k) +dr - \log \tilde m_k+ \log \cos^2 \tilde \theta_k +(1- \frac{\tilde q_k}{\cos^2 \tilde \theta_k} + \log \frac{\tilde q_k}{\cos^2 \tilde\theta_k})\\ &=\le \phi(\tilde H_k) +dr + \log (1-cr)+\log \cos^2 \tilde \theta_k +(1- \frac{\tilde q_k}{\cos^2 \tilde \theta_k} + \log \frac{\tilde q_k}{\cos^2 \tilde\theta_k})\\ &\le \phi(\tilde H_k) +dr +\frac{cr}{1-cr}+\log \cos^2 \tilde \theta_k +(1- \frac{\tilde q_k}{\cos^2 \tilde \theta_k} + \log \frac{\tilde q_k}{\cos^2 \tilde\theta_k}) ,\text{By } \log(1-x) \le \frac{x}{1-x}\\ &\le\phi(\tilde H_k) +dr +2cr+\log \cos^2 \tilde \theta_k +(1- \frac{\tilde q_k}{\cos^2 \tilde \theta_k} + \log \frac{\tilde q_k}{\cos^2 \tilde\theta_k}),\text{Let } cr <\frac{1}{2} \\ &<\phi(\tilde H_k) +3dr+\log \cos^2 \tilde \theta_k +(1- \frac{\tilde q_k}{\cos^2 \tilde \theta_k} + \log \frac{\tilde q_k}{\cos^2 \tilde\theta_k}), \text{By } c<d \\ \end{align}\]进行求和可以得到，
\[\begin{align} 0 \le \tilde \phi(H_{k+1}) &< \phi(\tilde H_0) +\sum_{j=1}^{k}[3dr+\log \cos^2 \tilde \theta_j +(1- \frac{\tilde q_j}{\cos^2 \tilde \theta_j} + \log \frac{\tilde q_j}{\cos^2 \tilde\theta_j})]\\ \sum_{j=1}^{k} [\log \cos^2 \tilde \theta_j +(1- \frac{\tilde q_j}{\cos^2 \tilde \theta_j} + \log \frac{\tilde q_j}{\cos^2 \tilde\theta_j})] &\le \phi(\tilde H_0) + 3d\sum_{j=1}^k\vert x_{j} - x_{\star} \vert < \infty \end{align}\]根据级数有界的性质，可以得到，
\[\begin{align} \lim_{j \rightarrow \infty} \log \cos^2 \tilde \theta_j &= 0 ,\lim_{j \rightarrow \infty} (1- \frac{\tilde q_j}{\cos^2 \tilde \theta_j} + \log \frac{\tilde q_j}{\cos^2 \tilde\theta_j}) =0 \\ \lim_{j \rightarrow \infty} \cos^2 \tilde \theta_j &= 1, \lim_{j \rightarrow \infty} \tilde q_j = 1, \end{align}\]距离最终的结果仅仅差最后一步了，
\[\begin{align} \frac{\Vert G_{\star}^{-\frac{1}{2}}(H_k -G_{\star}) s_k \Vert^2}{ \Vert G_{\star}^{\frac{1}{2} }s_k \Vert^2} &= \frac{\Vert \tilde H_k \tilde s_k - \tilde s_k \Vert^2}{ \Vert \tilde s_k \Vert^2} \\ &= \frac{\Vert \tilde H_k \tilde s_k \Vert^2 -2 \tilde s_k^T \tilde H_k \tilde s_k+ \Vert \tilde s_k \Vert^2}{\Vert \tilde s_k \Vert^2} \\ &= \frac{\tilde q_k^2}{\cos^2 \tilde \theta_k} - 2 \tilde q_k +1 \end{align}\]根据极限以及范数的等价性可以得到，
\[\begin{align} \lim_{k \rightarrow \infty} \frac{\Vert G_{\star}^{-\frac{1}{2}}(H_k -G_{\star}) s_k \Vert^2}{ \Vert G_{\star}^{\frac{1}{2} }s_k \Vert^2} &= \lim_{k \rightarrow \infty} \frac{\tilde q_k^2}{\cos^2 \tilde \theta_k} - 2 \tilde q_k +1 =0 \\ \lim_{k \rightarrow \infty} \frac{\Vert(H_k -G_{\star}) s_k \Vert}{ \Vert s_k \Vert} &= \lim_{k \rightarrow \infty} \frac{\Vert(H_k -G_{\star}) p_k \Vert}{ \Vert p_k \Vert} 0 \end{align}\]最后一个条件等价于在算法行进的方向上收敛，这与函数的值收敛是等价的，只需要简单地证明即可，
已知的结论是 Newton迭代法 具有很快的收敛速度，我们想办法将上式的条件将Newton迭代法的迭代方向上靠拢，
\[\begin{align} &\lim_{k \rightarrow \infty} \frac{\Vert (H_k -G_{\star}) p_k \Vert}{\Vert p_k \Vert } =0 \\ &\lim_{k \rightarrow \infty} \frac{\Vert G_{\star} p_k-H_k p_k \Vert}{\Vert p_k \Vert } =0 \\ &\lim_{k \rightarrow \infty} \frac{\Vert (G_{\star} H_k^{-1}\nabla f_k -\nabla f_k \Vert}{\Vert p_k \Vert } =0 \\ &\lim_{k \rightarrow \infty} \frac{\Vert (H_k^{-1}- G_{\star}^{-1})\nabla f_k \Vert}{\Vert p_k \Vert } =0 \\ &\lim_{k \rightarrow \infty} \frac{\Vert p_k - p_k^G \Vert}{\Vert p_k \Vert } = 0 ,\text{Define } p_k^G = -G_{\star}^{-1} \nabla f_k \\ &\lim_{k \rightarrow \infty} \frac{\Vert p_k - p_k^N \Vert}{\Vert p_k \Vert } = 0 ,\text{Define } p_k^N = -\nabla^2 f_{k}^{-1} \nabla f_k \\ \end{align}\]最后一步利用极限证明，可以直接写为分析的形式，得到上面极限关系之后，我们再利用一个较为经典的结论，
\[\begin{align} \Vert x_k + p_k^N - x_{\star} \Vert &= \Vert x_k - x_{\star} - \nabla ^2 f_k^{-1} \nabla f_k\Vert \\ &=\Vert \nabla ^2 f_k^{-1}(\nabla ^2 f_k(x_k - x_{\star}) - \ \nabla f_k)\Vert \\ & \le 2 \Vert G_{\star}^{-1} \Vert \Vert \nabla ^2 f_k(x_k - x_{\star})- \nabla f_k \Vert \\ &= 2 \Vert G_{\star}^{-1} \Vert \Vert H_k(x_k - x_{\star})- \nabla f_k \Vert \\ &= 2 \Vert G_{\star}^{-1} \Vert \Vert H_k(x_k - x_{\star})- \bar H_k (x_k -x_{\star}) \Vert ,\exists \bar H_k\\ &\le 2\Vert G_{\star}^{-1} \Vert \Vert H_k - \bar H_k \Vert \Vert x_k - x_{\star} \Vert \\ &\le 2L\Vert G_{\star}^{-1} \Vert \Vert x_k - x_{\star} \Vert^2 \\ \end{align}\]同时可以知道，
\[\begin{align} \Vert x_k + p_k -x_{\star} \Vert &\le \Vert x_k + p_k^N -x_{\star} \Vert + \Vert p_k - p_k^N \Vert \\ &\le 2L\Vert G_{\star}^{-1} \Vert \Vert x_k - x_{\star} \Vert^2 + \Vert p_k - p_k^N \Vert \end{align}\]利用上面的不等式，我们也关心 $p_k$ 的范数，
\[\begin{align} \Vert p_k \Vert &\le \Vert x_k + p_k -x_{\star} \Vert + \Vert x_k - x_{\star} \Vert \\ &\le 2L\Vert G_{\star}^{-1} \Vert \Vert x_k - x_{\star} \Vert^2 + \Vert x_k - x_{\star} \Vert +\Vert p_k - p_k^N \Vert\\ &\le 2L\Vert G_{\star}^{-1} \Vert \Vert x_k - x_{\star} \Vert^2 + \Vert x_k - x_{\star} \Vert+ \frac{1}{2}\Vert p_k \Vert ,\text{With } \lim_{k \rightarrow \infty} \frac{\Vert p_k - p_k^N \Vert}{\Vert p_k \Vert } = 0\\ \Vert p_k \Vert &\le 4L \Vert G_{\star}^{-1} \Vert \Vert x_k - x_{\star} \Vert^2 + \Vert x_k - x_{\star} \Vert \\ &\le (4L \Vert G_{\star}^{-1} \Vert+1 ) \Vert x_k - x_{\star} \Vert \end{align}\]因此得到了最终的结论，
\[\begin{align} \lim_{k \rightarrow \infty} \frac{\Vert x_{k+1} - x_{\star} \Vert}{\Vert x_k - x_{\star} \Vert} &=\lim_{k \rightarrow \infty} \frac{\Vert x_k + p_k -x_{\star} \Vert}{\Vert x_k -x_{\star} \Vert} \\ &\le \lim_{k \rightarrow \infty} \frac{2L\Vert G_{\star}^{-1} \Vert \Vert x_k - x_{\star} \Vert^2 + \Vert p_k - p_k^N \Vert}{\Vert x_k -x_{\star} \Vert} \\ &= \lim_{k \rightarrow \infty} \frac{\Vert p_k - p_k^N \Vert}{\Vert x_k -x_{\star} \Vert} \\ &\le \lim_{k \rightarrow \infty} \frac{\Vert p_k - p_k^N \Vert}{\Vert p_k \Vert} \\ &=0 \end{align}\]