04无约束优化-二阶方法

Lingfeng 2024-10-10

04无约束优化-二阶方法

1. Newton方法

1.1 基本Newton方法

Definition (基本Newton方法)

\boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}-G_{k}^{-1}g_{k}

对 $f(\boldsymbol{x})$ 在 $\boldsymbol{x}_{k}$ 处进行泰勒展开 $f(\boldsymbol{x}_{k}+\boldsymbol{d})=f(\boldsymbol{x}_{k})+g_{k}^{T}\boldsymbol{d}+\frac{1}{2}\boldsymbol{d}^{T}G_{k}\boldsymbol{d}+o(\left\lVert \boldsymbol{d} \right\rVert ^{2})$ 此时用二次函数近似求解 $\min_{\boldsymbol{d}} q_{k}(\boldsymbol{d})=\min_{\boldsymbol{d}}\left( f(\boldsymbol{x}_{k})+g_{k}^{T}\boldsymbol{d}+\frac{1}{2}\boldsymbol{d}^{T}G_{k}\boldsymbol{d} \right)$ 得到 $\boldsymbol{d}_{k}=-G_{k}^{-1}g_{k}$

Theorem (Newton方法局部收敛性)

设 $f(\boldsymbol{x})$ 二次可微， $f(\boldsymbol{x})$ 的Hessian矩阵 $G(\boldsymbol{x})$ 在 $\boldsymbol{x}^{*}$ 的邻域 $\delta$ 内满足Lipschitz条件 $\left\lVert G(\boldsymbol{x})-G(\boldsymbol{y}) \right\rVert \leq L\left\lVert \boldsymbol{x}-\boldsymbol{y} \right\rVert$ 则当 $\boldsymbol{x}_{0}$ 充分接近 $f(\boldsymbol{x})$ 的局部极小点 $\boldsymbol{x}^{*}$ ，且 $G(\boldsymbol{x}^{*})$ 正定，则Newton方法具有二次收敛速度。同时梯度序列 $g_{k}$ 二次收敛到0。

证明
首先由于 $g^{*}=0$ ，此时 $\begin{align*} \boldsymbol{x}_{k+1}-\boldsymbol{x}^{*} & =\boldsymbol{x}_{k}-\boldsymbol{x}^{* }-G_{k}^{-1}g_{k} \\ & = G_{k}^{-1}(G_{k}(\boldsymbol{x}_{k}-\boldsymbol{x}^{*})-(g_{k}-g^{*})) \end{align*}$ 同时注意到 $g_{k}-g^{*}=\int _{0}^{1}G(\boldsymbol{x}_{k}+t(\boldsymbol{x}^{*}-\boldsymbol{x}_{k}))(\boldsymbol{x}_{k}-\boldsymbol{x}^{*}) \, dt$ 因此 $\begin{align*} \left\lVert G_{k}(\boldsymbol{x}_{k}-\boldsymbol{x}^{*})-(g_{k}-g^{*})\right\rVert & =\left\lVert \int _{0}^{1}(G_{k}-G(\boldsymbol{x}_{k}+t(\boldsymbol{x}^{*}-\boldsymbol{x}_{k})))(\boldsymbol{x}_{k}-\boldsymbol{x}^{*}) \, dt \right\rVert \\ & \leq \int _{0}^{1}\left\lVert G_{k}- G(\boldsymbol{x}_{k}+t(\boldsymbol{x}^{*}-\boldsymbol{x}_{k})) \right\rVert \left\lVert \boldsymbol{x}_{k}-\boldsymbol{x}^{*} \right\rVert \, dt \\ & \leq L\left\lVert \boldsymbol{x}_{k}-\boldsymbol{x}^{*} \right\rVert ^{2}\int _{0}^{1} t \, dt= \frac{1}{2}L\left\lVert \boldsymbol{x}_{k}-\boldsymbol{x}^{*} \right\rVert ^{2} \end{align*}$ 同时 $\exists r>0$ ，当 $\left\lVert \boldsymbol{x}_{k}-\boldsymbol{x}^{*} \right\rVert\leq r$ 时，有 $\left\lVert G(x)^{-1} \right\rVert \leq 2\left\lVert G(\boldsymbol{x}^{*})^{-1} \right\rVert$ 有界。因此 $\{ \boldsymbol{x}_{k} \}$ 二次收敛到 $\boldsymbol{x}^{*}$ 。

同时 $\begin{align*} \left\lVert g_{k+1} \right\rVert & = \left\lVert g_{k+1}-g_{k}-G_{k}\boldsymbol{d}_{k} \right\rVert \\ & = \left\lVert \int _{0}^{1}G(\boldsymbol{x}_{k}+t\boldsymbol{d}_{k})\boldsymbol{d}_{k} \, dt-G_{k}\boldsymbol{d}_{k} \right\rVert \\ & = \int _{0}^{1}\left\lVert G(\boldsymbol{x}_{k}+t\boldsymbol{d}_{k})-G(\boldsymbol{x}_{k}) \right\rVert \left\lVert \boldsymbol{d}_{k} \right\rVert \, dt \\ & = \frac{1}{2}L\left\lVert \boldsymbol{d}_{k} \right\rVert^{2} \leq \frac{1}{2}L\left\lVert G_{k}^{-1} \right\rVert ^{2 }\left\lVert g_{k} \right\rVert ^{2} \end{align*}$

1.2 阻尼Newton方法

Definition (阻尼Newton方法)

在Newton方法的基础上，使用一维搜索计算步长 $\boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k}$

1.3 混合方法

Definition (混合方法)

将Newton方法与负梯度方法混合。当Hesse矩阵 $G_{k}$ 奇异或者 $g_{k}$ 与 $\boldsymbol{d}_{k}$ 几乎正交时，采用负梯度方向；在 $G_{k}$ 负定，但 $G_{k}^{-1}$ 存在时，取 $\boldsymbol{d}_{k}=G_{k}^{-1}g_{k}$ 。

1.4 LM方法

Definition (LM方法)

对于 $G_{k}$ 奇异或者不正定的情况，我们求解 $(G_{k}+\boldsymbol{v}_{k}I)\boldsymbol{d}_{k}=-g_{k}$ 当 $\boldsymbol{v}_{k}$ 充分大时，可以保证 $G_{k}+\boldsymbol{v}_{k}I$ 正定。当 $\boldsymbol{v}_{k}$ 较小时， $\boldsymbol{d}_{k}$ 偏向Newton方法；较大时则偏向负梯度方向。

2. 拟Newton方法

Definition (拟Newton条件)

$B_{k+1}\boldsymbol{s}_{k}=\boldsymbol{y}_{k}$ 或 $H_{k+1}\boldsymbol{y}_{k}=\boldsymbol{s}_{k}$ 其中 $\boldsymbol{s}_{k}=\boldsymbol{x}_{k+1}-\boldsymbol{x}_{k}$ ， $\boldsymbol{y}_{k}=g_{k+1}-g_{k}$ 。

解
注意到 $\boldsymbol{x}_{k}$ 靠近 $\boldsymbol{x}_{k+1}$ 时，有 $g_{k}-g_{k+1}\approx G_{k+1}(\boldsymbol{x}_{k}-\boldsymbol{x}_{k+1})$ 因此即得条件。

2.1 SR1方法

Definition (对称秩方法, SR1)

B_{k+1}=B_{k}+ \frac{(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}}{(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}\boldsymbol{s}_{k}}

解
设 $B_{k+1}=B_{k}+ \boldsymbol{v}\boldsymbol{v}^{T}$ 代入拟Newton方程有 $\begin{align*} \boldsymbol{y}_{k} & =B_{k}\boldsymbol{s}_{k}+\boldsymbol{v}\boldsymbol{v}^{T}\boldsymbol{s}_{k} \\ & = B_{k}\boldsymbol{s}_{k}+ ( \boldsymbol{v}^{T}\boldsymbol{s}_{k})\boldsymbol{v} \end{align*}$ 此时必有 $\boldsymbol{v}$ 与 $\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k}$ 共线。因此设 $\boldsymbol{v}=\delta(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})$ ，此时 $\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k}=\delta^{2}((\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}\boldsymbol{s}_{k})(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})$ 因此 $\delta^{2}= \frac{1}{(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}\boldsymbol{s}_{k}}$ 故 $\begin{align*} \boldsymbol{v}\boldsymbol{v}^{T} & =\delta^{2}(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T} \\ & = \frac{(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}}{(\boldsymbol{y}_{k}-B_{k}\boldsymbol{s}_{k})^{T}\boldsymbol{s}_{k}} \end{align*}$

2.2 BFGS公式

Definition (BFGS公式)

\begin{align*} B_{k+1}&=B_{k}+ \frac{y_{k}y_{k}^{T}}{y_{k}^{T}s_{k}}- \frac{B_{k}s_{k}s_{k}^{T}B_{k}}{s_{k}^{T}B_{k}s_{k}} \\ H_{k+1}&= H_{k}+\left( 1+\frac{y_{k}^{T}H_{k}y_{k}}{y_{k}^{T}s_{k}} \right) \frac{s_{k}s_{k}^{T}}{y_{k}^{T}s_{k}}-\left( \frac{s_{k}y_{k}^{T}H_{k}+H_{k}y_{k}s_{k}^{T}}{y_{k}^{T}s_{k}} \right)\end{align*}

证明
考虑构造 $B_{k+1}=B_{k}+ u u^{T}+ v v ^{T}$ 此时有 $y_{k}=B_{k}s_{k}+ uu^{T}s_{k}+ v v^{T}s_{k}$
取特解 $\begin{align*} u=y_{k},\quad u^{T}s_{k}=1 \\ v=B_{k}s_{k},\quad v^{T}s_{k}=-1 \end{align*}$ 即得。

2.3 DFP公式

Definition (DFP公式)

\begin{align*} H_{k+1}&=H_{k}+ \frac{s_{k}s_{k}^{T}}{s_{k}^{T}y_{k}}- \frac{H_{k}y_{k}y_{k}^{T}H_{k}}{y_{k}^{T}H_{k}y_{k}} \\ B_{k+1}&= B_{k}+\left( 1+\frac{s_{k}^{T}B_{k}s_{k}}{s_{k}^{T}y_{k}} \right) \frac{y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}}-\left( \frac{y_{k}s_{k}^{T}B_{k}+B_{k}s_{k}y_{k}^{T}}{s_{k}^{T}y_{k}} \right)\end{align*}

证明
类似于BFGS方法，只是从 $H_{k+1}$ 方向进行构造。

Theorem ( $B_{k+1}^{DFP}$ 性质)

$B_{k+1}^{DFP}$ 是下面问题的解 $\begin{align*} \min\left\lVert W^{-T}(B-B_{k})W^{-1} \right\rVert_{F} \\ s.t. B=B^{T},\quad Bs_{k}=y_{k} \end{align*}$ 其中 $W^{T}W=B$ 。即满足对称与拟Newton条件中，在Frobenius范数意义下与 $B_{k}$ 距离最近的矩阵。

Theorem ( $B_{k+1}$ 与 $H_{k+1}$ 对称正定性)

若 $H_{k}$ 对称正定，则如果 $s_{k}^{T}y_{k}>0$ ，则DFP构造出的 $H_{k+1}^{DFP}$ 也是对称正定。此时使用精确线搜索或者非精确线搜索Wolfe准则的DFP方法和BFGS方法有 $s_{k}^{T}y_{k}>0$ 。

证明
$\begin{align*} x^{T}H_{k+1}^{DFP}x & = x^{T}H_{k}x+ \frac{(x^{T}s_{k})^{2}}{s_{k}^{T}y_{k}}-\frac{(x^{T}H_{k}y_{k})^{2}}{y_{k}^{T}H_{k}y_{k}} \\ & = \frac{(x^{T}H_{k}x)(y_{k}^{T}H_{k}y_{k})-(x^{T}H_{k}y_{k})^{2}}{y_{k}^{T}H_{k}y_{k}}+ \frac{(x^{T}s_{k})^{2}}{s_{k}^{T}y_{k}} \end{align*}$
而使用精确线搜索 $s_{k}^{T}y_{k}=\alpha_{k}d_{k}^{T}(g_{k+1}-g_{k})=-\alpha_{k}d_{k}^{T}g_{k}=\alpha_{k}g_{k}^{T}H_{k}g_{k}>0$ 而wolfe准则 $s_{k}^{T}y_{k}=\alpha_{k}d_{k}^{T}(g_{k+1}-g_{k})\geq-\alpha_{k}(1-\sigma)d_{k}^{T}g_{k}>0$

2.4 Broyden族方法

Definition (Broyden族方法)

$\begin{align*}B_{k+1}&=(1-\phi)B_{k+1}^{BFGS}+\phi B_{k+1}^{DFP} \\ &= B_{k+1}^{BFGS}+\phi v_{k}v_{k}^{T}\end{align*}$ 其中 $v_{k}=(s_{k}^{T}B_{k}s_{k})^{1/2}\left( \frac{y_{k}}{y_{k}^{T}s_{k}}-\frac{B_{k}s_{k}}{s_{k}^{T}B_{k}s_{k}} \right)$

Theorem ( $B_{k+1}$ 的对称正定性)

若 $B_{k+1}^{BFGS}$ 为对称正定阵，则当 $\phi>0$ 时，Broyden族公式得到 $B_{k+1}$ 也是对称正定阵。

2.5 BB方法

Definition (BB方法)

$x_{k+1}=x_{k}-\alpha_{k}g_{k}$ 其中 $\alpha_{k}=\arg\min\left\lVert s_{k-1}-\alpha y_{k-1} \right\rVert _{2}^{2},\quad\alpha_{k}=\arg\min\left\lVert \alpha^{-1}s_{k-1}-y_{k-1} \right\rVert _{2}^{2}$ 得到 $\alpha_{k}= \frac{s_{k-1}^{T}y_{k-1}}{y_{k-1}^{T}y_{k_{1}}},\quad \alpha_{k}= \frac{s_{k-1}^{T}s_{k-1}}{s_{k-1}^{T}y_{k-1}}$

3. 共轭梯度方法

3.1 共轭梯度法

Definition (共轭方向)

设 $G$ 是对称正定矩阵，若非零向量组 $\{ d_{0},d_{1},\dots,d_{n} \}$ 满足 $d_{i}^{T}Gd_{j}=0,\quad i\neq j$ 则称非零向量组是矩阵 $G$ 的共轭方向。

Theorem (共轭方向线性无关性)

共轭向量组中的向量必然线性无关。

证明
定义内积 $\langle u,v \rangle_{A}=u^{T}Av$ 若共轭向量组向量线性相关，则设 $v=\sum_{i = 1}^{n} c_{i}d_{i}=0$ 此时 $\begin{align*} \langle v,v \rangle _{A} & =\left\langle \sum_{i = 1}^{n} c_{i}d_{i},\sum_{i = 1}^{n} c_{i}d_{i} \right\rangle_{A} \\ & = \sum_{i = 1}^{n} c_{i}^{2}\langle d_{i},d_{i} \rangle _{A}=0 \end{align*}$ 此时有且仅有 $c_{i}=0, i=1,\dots,n$ 。故证毕。

Theorem (共轭迭代定理)

对于正定二次函数，从任意初始点出发，依次沿共轭方向做精确线搜索，最多迭代n步就可以得到极小点。

证明
易知由精确线搜索 $g_{k+1}^{T}d_{k}=0$ 有 $\alpha_{k}=- \frac{d_{k}^{T}g_{k}}{d_{k}^{T}Gd_{k}}=-\frac{\langle d_{k},g_{k} \rangle }{\langle d_{k},d_{k} \rangle _{G}}$ 由于共轭方向线性无关，因此构成一组基底。此时 $x^{*}-x_{0}=\beta_{0}d_{0}+\dots+\beta_{n-1}d_{n-1}$ 两边与 $d_{k}$ 做内积有 $\beta_{k}= \frac{\langle d_{k}, x^{*}-x_{0}\rangle_{G} }{\langle d_{k},d_{k} \rangle _{G}}$ 注意到 $\langle d_{k},x_{k}-x_{0} \rangle _{G}=0$ 因此 $\begin{align*} -\langle d_{k},g_{k} \rangle & =\langle d_{k},(g(x^{*})-g_{k}) \rangle \\ & =\langle d_{k},G(x^{*}-x_{k})\rangle \\ & = \langle d_{k},x^{*}-x_{k} \rangle _{G} \\ & = \langle d_{k},x^{*}-x_{0} \rangle _{G} \end{align*}$ 故证毕。

Theorem (子空间扩展定理)

设 $f(x)=\frac{1}{2}x^{T}Gx-b^{T}x$ ， $G$ 为正定矩阵， $d_{0},\dots,d_{n-1}$ 为共轭方向，此时 $g_{k}^{T}d_{j}=0,\quad j=0,1,\dots,k-1$ 且 $x_{k}$ 是 $f(x)$ 在 $\{ x\mid x=x_{0}+span\{ d_{0},d_{1},\dots,d_{k-1} \} \}$ 上的最小点。

证明
类似的，注意到 $\begin{align*} -\langle d_{j},g_{k} \rangle & =\langle d_{j},G(x^{*}-x_{k}) \rangle \\ & =\langle d_{j},x^{*}-x_{k} \rangle _{G } \\ & = \left\langle d_{j},\sum_{i = k+1}^{n} \alpha_{i}d_{i} \right\rangle _{G} \end{align*}$ 故证毕。

Corollary (凸优化最优化条件)

对于凸函数，若一点的梯度与所有可行方向正交，则该点为可行集的最小点。

由凸函数，有 $f(x)-f(x^{*})\geq g(x^{*})(x-x^{*})$ 故证毕。

3.2 线性共轭梯度法

Definition (线性共轭梯度法)

对于正定二次函数，取迭代方向为 $d_{k}=-g_{k}+\beta_{k-1}d_{k-1}$ 其中取 $d_{0}=-g_{0}$ ，且 $\beta_{k-1}= \frac{g_{k}^{T}g_{k}}{g_{k-1}^{T}g_{k-1}}$ 此时 $\{ d_{i} \}$ 为一组共轭梯度，且有 $g_{k}^{T}g_{i}=0,\quad i=1,\dots,k-1$

证明
我们使用数学归纳法，当 $k=1$ 时，由于 $g_{1}^{T}d_{0}=0$ ，显然有 $g_{1}^{T}g_{0}=0$ 。而注意到 $\alpha_{0}Gd_{0}=G(x_{1}-x_{0})=g_{1}-g_{0}$ 因此 $\begin{align*} \alpha_{0} d_{1}^{T}Gd_{0} & =(-g_{1}+\beta_{0}d_{0})^{T}(g_{1}-g_{0}) \\ & = -g_{1}^{T}g_{1}-\beta_{0}d_{0}^{T}g_{0} \\ & = -g_{1}^{T}g_{1}+\beta_{0}g_{0}^{T}g_{0}=0 \end{align*}$ 满足。

此时假设 $d_{0},d_{1},\dots,d_{k-1}$ 都是 $G$ -共轭，且 $g_{i}^{T}g_{j}=0$ ， $0\leq i,j<k,i\neq j$ 。首先注意到 $g_{k}=g_{k-1}+\alpha_{k-1}Gd_{k-1}$ 由归纳假设知 $g_{k}^{T}g_{i}=0$ ， $i=0,\dots,k-2$ 。而对于 $g_{k-1}$ ，有 $g_{k-1}=-d_{k-1}+\beta _{k-2}d_{k-2}$ 显然 $g_{k}^{T}d_{k-2}=0$ ，而由精确线搜索 $g_{k}^{T}d_{k-1}=0$ ，因此 $g_{k}^{T}g_{k-1}=0$ ，进而 $g_{k}^{T}g_{i}=0,\quad i=0,\dots,k-1$ 此时 $\begin{align*} \alpha_{k-1}d_{k}^{T}Gd_{k-1} & = (-g_{k}+\beta_{k-1}d_{k-1})^{T}(g_{k}-g_{k-1}) \\ & = -g_{k}^{T}g_{k}-\beta_{k-1}(-g_{k-1}+\beta_{k-2}d_{k-2})^{T}g_{k-1} \\ & = -g_{k}^{T}g_{k}+\beta_{k-1}g_{k-1}^{T}g_{k-1}=0 \end{align*}$ 成立。故证毕。

3.3 非线性共轭梯度法

Definition (FR公式)

\beta_{k-1}^{FR}=\frac{g_{k}^{T}g_{k}}{g_{k-1}^{T}g_{k-1}}

Theorem (下降方向保证)

若FR方法步长由强Wolfe准则得到，且 $\sigma \in\left( 0, \frac{1}{2} \right)$ ，则迭代方向 $d_{k}$ 满足 $-\frac{1}{1-\sigma}\leq \frac{g_{k}^{T}d_{k}}{\left\lVert g_{k} \right\rVert ^{2}}\leq \frac{2\sigma-1}{1-\sigma}$ 从而 $d_{k}$ 是下降方向。

证明
考虑数学归纳法，当 $k=0$ 时， $d_{0}=-g_{0}$ ，此时 $\frac{g_{0}^{T}d_{0}}{\left\lVert g_{0} \right\rVert ^{2}}=-1$ 成立。考虑 $k-1$ 均成立，此时 $\begin{align*} \frac{g_{k}^{T}d_{k}}{\left\lVert g_{k} \right\rVert ^{2}} & =-1+ \beta_{k-1} \frac{g_{k}^{T}d_{k-1}}{\left\lVert g_{k} \right\rVert ^{2}} \\ & = -1 + \frac{g_{k}^{T}d_{k-1}}{\left\lVert g_{k-1} \right\rVert^{2} } \end{align*}$ 一方面 $\frac{g_{k}^{T}d_{k}}{\left\lVert g_{k} \right\rVert^{2} }\geq-1+ \frac{\sigma g_{k-1}^{T}d_{k-1}}{\left\lVert g_{k-1} \right\rVert ^{2}}\geq-1-\frac{\sigma}{1-\sigma}=-\frac{1}{1-\sigma}$ 另方面 $\frac{g_{k}^{T}d_{k}}{\left\lVert g_{k} \right\rVert^{2} }\leq-1- \frac{\sigma g_{k-1}^{T}d_{k-1}}{\left\lVert g_{k-1} \right\rVert ^{2}}\leq-1+\frac{\sigma}{1-\sigma}=\frac{2\sigma-1}{1-\sigma}$ 故证毕。

Definition (PRP方法)

\beta^{PRP}_{k}=\frac{g_{k+1}^{T}(g_{k+1}-g_{k})}{g_{k}^{T}g_{k}}

Definition (共轭下降方法)

\beta_{k}=-\frac{g_{k+1}^{T}g_{k+1}}{d_{k}^{T}g_{k}}

Definition (DY方法)

\beta_{k}=-\frac{g_{k}^{T}g_{k}}{d_{k}^{T}(g_{k+1}-g_{k})}

Theorem (正定二次函数Broyden族性质)

对于正定二次函数，采用精确线搜索的Broyden族方法，有 $\begin{align*} H_{k}y_{i} &= s_{i}\\ d_{k}^{T}Gd_{i}&=0\end{align*}$

证明
仍然考虑数学归纳法。由Broyden族方法定义，迭代方向为 $d_{k}=-H_{k}g_{k}$ 当 $k=1$ 时， $H_{0}y_{0}=s_{0}$ ，同时 $\begin{align*} d_{1}^{T}Gd_{0} & = -\frac{1}{\alpha_{0}} (H_{1}g_{1})^{T}(Gs_{0}) \\ & =-\frac{1}{\alpha_{0}}(H_{1}g_{1})^{T}y_{0} \\ & =-g_{1}^{T}d_{0}=0 \end{align*}$ 此时对于 $k-1$ 均成立，此时 $H_{k}y_{i}=H_{k-1}y_{i}+ \frac{s_{k-1}s_{k-1}^{T}}{s_{k-1}^{T}y_{k-1}}y_{i}- \frac{H_{k-1}y_{k-1}y_{k-1}^{T}H_{k-1}}{y_{k-1}^{T}Hy_{k-1}}y_{i}+\varphi v_{k-1}v_{k-1}^{T}y_{i}$ 注意到 $\begin{align*} & s_{k-1}^{T}y_{i}=s_{k-1}^{T}Gs_{i} =0 \\ & y_{k-1}^{T}H_{k-1}y_{i}=y_{k-1}^{T}s_{i}=s_{k-1}^{T}Gs_{i}=0 \\ & v_{k-1}^{T}y_{i}=(y_{k-1}^{T}H_{k-1}y_{k-1})^{1/2}\left( \frac{s_{k-1}}{s_{k-1}^{T}y_{k-1}}-\frac{H_{k-1}y_{k-1}}{y_{k-1}^{T}H_{k-1}y_{k-1}} \right)^{T}y_{i}=0 \end{align*}$ 同时 $\begin{align*} d_{k}^{T}Gd_{i} & = -\frac{1}{\alpha_{i}}(H_{k}g_{k})^{T}y_{i} \\ & =-\frac{1}{\alpha_{i}}g_{k}^{T}s_{i} \\ & =-g_{k}^{T}d_{i} \\ & =-(g_{i+1}+y_{i+1}+\dots+y_{k-1})^{T}d_{i} \\ & =0 \end{align*}$