机器学习笔记之最优化理论与方法(九)无约束优化问题——常用求解方法(下)

机器学习笔记之最优化理论与方法——基于无约束优化问题的常用求解方法[下]

• 引言
• • 回顾：经典牛顿法的缺陷与拟牛顿法思想
  • 拟牛顿法之 DFP \text{DFP} DFP方法
  • 拟牛顿法之 BFGS \text{BFGS} BFGS方法
  • Broyden \text{Broyden} Broyden族
  • 拟牛顿法之 SR-1 \text{SR-1} SR-1方法

引言

上一节介绍了牛顿法、拟牛顿法。本节将继续以拟牛顿法为基础，介绍 DFP , BFGS \text{DFP},\text{BFGS} DFP,BFGS方法。

回顾：经典牛顿法的缺陷与拟牛顿法思想

经典牛顿法缺陷与修正牛顿法

关于经典牛顿法中关于下降方向 D k ( k = 1 , 2 , ⋯   , ∞ ) \mathcal D_k(k=1,2,\cdots,\infty) Dk​(k=1,2,⋯,∞)的数学符号表示如下：
D k = − [ ∇ 2 f ( x k ) ] − 1 ∇ f ( x k ) \mathcal D_k = - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k) Dk​=−[∇2f(xk​)]−1∇f(xk​)
其中 ∇ f ( x k ) \nabla f(x_k) ∇f(xk​)表示目标函数 f ( ⋅ ) f(\cdot) f(⋅)在 x k x_k xk​位置的梯度向量结果； ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇2f(xk​)表示目标函数在 x k x_k xk​位置的 Hessian Matrix \text{Hessian Matrix} Hessian Matrix。问题在于： ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇2f(xk​)可能不是正定矩阵，从而无法求解 [ ∇ 2 f ( x k ) ] − 1 [\nabla^2 f(x_k)]^{-1} [∇2f(xk​)]−1，最终无法执行迭代过程。

关于这类问题，可以使用正则化法对 ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇2f(xk​)进行修正：
∇ 2 f ( x k ) : = ∇ 2 f ( x k ) + λ I \nabla^2 f(x_k):= \nabla^2 f(x_k) + \lambda \mathcal I ∇2f(xk​):=∇2f(xk​)+λI
其中 I \mathcal I I表示单位矩阵。执行该操作的目的是：保持 ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇2f(xk​)是正定矩阵状态。但这种方法同样存在弊端：
λ > max ⁡ i = 1 , 2 , ⋯   , n { − λ i } \lambda > \mathop{\max}\limits_{i=1,2,\cdots,n} \{- \lambda_i\} λ>i=1,2,⋯,nmax​{−λi​}
如果 λ \lambda λ数值过大，可能会发生原始 ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇2f(xk​)中各特征值被 λ \lambda λ分掉相应权重，从而导致修正后的 ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇2f(xk​)中关于 x k x_k xk​的二阶梯度信息减少，甚至无效。当然，也可以基于正则化法的思想，对 ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇2f(xk​)进行优化：
实际上，正则化法中 λ \lambda λ过大最终影响当前迭代步骤的下降方向,并使其收敛到 ∇ f ( x k ) α \begin{aligned}\frac{\nabla f(x_k)}{\alpha}\end{aligned} α∇f(xk​)​​。
∇ 2 f ( x k ) = Q T Diag ( τ i ) Q τ i = { τ i if  τ i ≥ δ δ Otherwise \begin{aligned} & \nabla^2 f(x_k) = \mathcal Q^T \text{Diag}(\tau_i) \mathcal Q \\ & \tau_i = \begin{cases} \tau_{i} \quad \text{if } \tau_i \geq \delta \\ \delta \quad \text{Otherwise} \end{cases} \end{aligned} ​∇2f(xk​)=QTDiag(τi​)Qτi​={τi​if τi​≥δδOtherwise​​
其中 δ \delta δ是一个适当正数；虽然该方式相比正则化法要缓和不少——仅调整非正特征值的结果，其余正特征值保持不变。但该方法依然存在逻辑上的缺失：通过强行修改二阶梯度信息的方式使其收敛。

拟牛顿法与矩阵 B k + 1 \mathcal B_{k+1} Bk+1​的选择

而拟牛顿法的思想是：选择一个既包含 x k + 1 x_{k+1} xk+1​处的二阶梯度信息，并且容易获取的正定矩阵 B k + 1 \mathcal B_{k+1} Bk+1​来替代 ∇ 2 f ( x k + 1 ) \nabla^2 f(x_{k+1}) ∇2f(xk+1​)。
由于 [ ∇ 2 f ( x k + 1 ) ] n × n [\nabla^2 f(x_{k+1})]_{n \times n} [∇2f(xk+1​)]n×n​自身计算量较大: O ( n 3 ) \mathcal O(n^3) O(n3),从而不容易获取。

关于矩阵 B k + 1 \mathcal B_{k+1} Bk+1​满足的基本要求表示如下：
∇ f ( x k + 1 ) − ∇ f ( x k ) = B k + 1 ( x k + 1 − x k ) \nabla f(x_{k+1} )- \nabla f(x_k) = \mathcal B_{k+1} (x_{k+1} - x_k) ∇f(xk+1​)−∇f(xk​)=Bk+1​(xk+1​−xk​)
可以发现：该式子是关于 n n n个方程构成的方程组；而未知量包含 n ( n + 1 ) 2 \begin{aligned}\frac{n(n+1)}{2}\end{aligned} 2n(n+1)​​个( B k + 1 \mathcal B_{k+1} Bk+1​上/下三角阵元素数量)，并且： n ( n + 1 ) 2 ≥ n ; n ∈ N + \begin{aligned}\frac{n(n+1)}{2} \geq n;n \in \mathbb N^{+}\end{aligned} 2n(n+1)​≥n;n∈N+​。这意味着拟牛顿方程的解 B k + 1 \mathcal B_{k+1} Bk+1​不唯一。

既然满足基本要求的解不唯一，可以尝试从这些解中选择与 B k / H k \mathcal B_k/\mathcal H_k Bk​/Hk​相似的矩阵作为 B k + 1 / H k + 1 \mathcal B_{k+1}/\mathcal H_{k+1} Bk+1​/Hk+1​：

• 其中: { S k = x k + 1 − x k y k = ∇ f ( x k + 1 ) − ∇ f ( x k ) H k = B k − 1 \begin{cases} \mathcal S_k = x_{k+1} - x_k \\ y_k = \nabla f(x_{k+1}) - \nabla f(x_k) \\ \mathcal H_k = \mathcal B_k^{-1} \end{cases} ⎩ ⎨ ⎧​Sk​=xk+1​−xk​yk​=∇f(xk+1​)−∇f(xk​)Hk​=Bk−1​​
• 通过这种相似性来保证二阶梯度信息的有效性。
• 无论是 B k + 1 \mathcal B_{k+1} Bk+1​还是 H k + 1 \mathcal H_{k+1} Hk+1​都可以作为我们的求解目标。因为最终都可以对下降方向 D k + 1 \mathcal D_{k+1} Dk+1​进行表示: D k + 1 = − B k + 1 − 1 ∇ f ( x k + 1 ) = − H k + 1 ∇ f ( x k + 1 ) \mathcal D_{k+1} = - \mathcal B_{k+1}^{-1} \nabla f(x_{k+1}) = -\mathcal H_{k+1}\nabla f(x_{k+1}) Dk+1​=−Bk+1−1​∇f(xk+1​)=−Hk+1​∇f(xk+1​)。
  { B k + 1 ⇒ B : { min ⁡ ∥ B − B k ∥ s.t.  B ⋅ S k = y k ; B T = B H k + 1 ⇒ H : { min ⁡ ∥ H − H k ∥ s.t.  H ⋅ y k = S k ; H T = H \begin{cases} \mathcal B_{k+1} \Rightarrow \mathcal B: \begin{cases} \min \|\mathcal B - \mathcal B_k\| \\ \text{s.t. } \mathcal B \cdot \mathcal S_k = y_k;\mathcal B^T = \mathcal B \end{cases} \\ \quad \\ \mathcal H_{k+1} \Rightarrow \mathcal H:\begin{cases} \min \|\mathcal H - \mathcal H_k\| \\ \text{s.t. } \mathcal H \cdot y_k = \mathcal S_k;\mathcal H^T = \mathcal H \end{cases} \end{cases} ⎩ ⎨ ⎧​Bk+1​⇒B:{min∥B−Bk​∥s.t. B⋅Sk​=yk​;BT=B​Hk+1​⇒H:{min∥H−Hk​∥s.t. H⋅yk​=Sk​;HT=H​​

也可以尝试：将 B k + 1 / H k + 1 \mathcal B_{k+1}/\mathcal H_{k+1} Bk+1​/Hk+1​看作是 B k / H k \mathcal B_k/\mathcal H_k Bk​/Hk​的校正/优化后的结果。令 B k + 1 = B k + Δ B \mathcal B_{k+1} = \mathcal B_k + \Delta\mathcal B Bk+1​=Bk​+ΔB或者 H k + 1 = H k + Δ H \mathcal H_{k+1} = \mathcal H_{k} + \Delta \mathcal H Hk+1​=Hk​+ΔH，其中：

• SR-1 \text{SR-1} SR-1方法是 Rank-1 \text{Rank-1} Rank-1校正： Δ B 、 Δ H \Delta \mathcal B、\Delta \mathcal H ΔB、ΔH的秩为 1 1 1的代表方法；
• DFP,BFGS \text{DFP,BFGS} DFP,BFGS方法是 Rank-2 \text{Rank-2} Rank-2校正： Δ B 、 Δ H \Delta \mathcal B、\Delta \mathcal H ΔB、ΔH的秩为 2 2 2的代表方法。

拟牛顿法之 DFP \text{DFP} DFP方法

关于 DFP(Davidon-Fletcher-Power) \text{DFP(Davidon-Fletcher-Power)} DFP(Davidon-Fletcher-Power)方法可看做是对 H k \mathcal H_k Hk​进行 Rank-2 \text{Rank-2} Rank-2校正。对应迭代公式表示如下：
H k + 1 = H k − H k y k y k T H k y k T H k y k + S k S k T y k T S k \mathcal H_{k+1} = \mathcal H_k - \frac{\mathcal H_ky_ky_k^T \mathcal H_k}{y_k^T \mathcal H_k y_k} + \frac{\mathcal S_k\mathcal S_k^T}{y_k^T \mathcal S_k} Hk+1​=Hk​−ykT​Hk​yk​Hk​yk​ykT​Hk​​+ykT​Sk​Sk​SkT​​

DFP \text{DFP} DFP迭代公式的推导过程

DFP \text{DFP} DFP是一个 Rank-2 \text{Rank-2} Rank-2校正方法，那么如何表示一个秩为 2 2 2的矩阵 ? ? ?首先，先观察秩为 1 1 1的矩阵如何表示：某矩阵 A n × n \mathcal A_{n \times n} An×n​可表示为如下形式：
该矩阵的所有行均相同。
A = U V T U , V ∈ R n ; U , V ≠ 0 \mathcal A = \mathcal U\mathcal V^T \quad \mathcal U,\mathcal V \in \mathbb R^n;\mathcal U,\mathcal V \neq 0 A=UVTU,V∈Rn;U,V=0
此时 A \mathcal A A就是一个秩为 1 1 1的矩阵。但由于 H k \mathcal H_k Hk​必然是一个对称矩阵，相比于上式， Δ H \Delta \mathcal H ΔH想满足是秩为 1 1 1仅需要满足：
Δ H = U U T U ∈ R n ; U ≠ 0 \Delta \mathcal H = \mathcal U \mathcal U^T \quad \mathcal U \in \mathbb R^n;\mathcal U \neq 0 ΔH=UUTU∈Rn;U=0
这是秩为 1 1 1的情况。那秩为 2 2 2呢 ? ? ?只需要满足：
Δ H = U U T + V V T { U , V ∈ R n U , V ≠ 0 U ≠ V \Delta \mathcal H = \mathcal U \mathcal U^T + \mathcal V \mathcal V^T \quad \begin{cases}\mathcal U,\mathcal V \in \mathbb R^n \\ \mathcal U,\mathcal V \neq 0 \\ \mathcal U \neq \mathcal V \end{cases} ΔH=UUT+VVT⎩ ⎨ ⎧​U,V∈RnU,V=0U=V​
综上，将迭代关系： H k + 1 = H k + Δ H \mathcal H_{k+1} = \mathcal H_k + \Delta \mathcal H Hk+1​=Hk​+ΔH表示为如下形式：
其中 a , b a,b a,b是系数，均是标量~
H k + 1 = H k + a ⋅ U U T + b ⋅ V V T \mathcal H_{k+1} = \mathcal H_k + a \cdot \mathcal U \mathcal U^T + b \cdot \mathcal V \mathcal V^T Hk+1​=Hk​+a⋅UUT+b⋅VVT
由于 H k + 1 \mathcal H_{k+1} Hk+1​需要满足基本要求： H k + 1 ⋅ y k = S k \mathcal H_{k+1} \cdot y_k = \mathcal S_k Hk+1​⋅yk​=Sk​，因而将上式带入。有：
H k y k + a ⋅ U U T y k + b ⋅ V V T y k − S k = 0 \mathcal H_k y_k + a \cdot \mathcal U\mathcal U^T y_k + b\cdot \mathcal V\mathcal V^T y_k - \mathcal S_k = 0 Hk​yk​+a⋅UUTyk​+b⋅VVTyk​−Sk​=0
其中：

• 由于 H k ∈ R n × n , y k ∈ R n \mathcal H_k \in \mathbb R^{n \times n},y_k \in \mathbb R^n Hk​∈Rn×n,yk​∈Rn，因而 H k y k ∈ R n \mathcal H_k y_k \in \mathbb R^n Hk​yk​∈Rn，是一个 n n n维向量；
• 由于 U T y k ∈ R \mathcal U^T y_k \in \mathbb R UTyk​∈R，因而 a ⋅ U ( U T y k ) ∈ R n a \cdot \mathcal U (\mathcal U^T y_k) \in \mathbb R^n a⋅U(UTyk​)∈Rn，可看做向量 U \mathcal U U的 a ⋅ ( U T y k ) a \cdot (\mathcal U^T y_k) a⋅(UTyk​)倍；
• 同理， b ⋅ V ( V T y k ) ∈ R n b \cdot \mathcal V(\mathcal V^T y_k) \in \mathbb R^n b⋅V(VTyk​)∈Rn，可看做向量 V \mathcal V V的 b ⋅ ( V T y k ) b \cdot (\mathcal V^T y_k) b⋅(VTyk​)倍。
• S k = x k + 1 − x k ∈ R n \mathcal S_k = x_{k+1} - x_k \in \mathbb R^n Sk​=xk+1​−xk​∈Rn

对 U , V \mathcal U,\mathcal V U,V进行取值。将项 H k , a ⋅ U ( U T y k ) \mathcal H_k,a \cdot \mathcal U (\mathcal U^T y_k) Hk​,a⋅U(UTyk​)关联在一起；项 b ⋅ V ( V T y k ) , S k b \cdot \mathcal V (\mathcal V^T y_k),\mathcal S_k b⋅V(VTyk​),Sk​关联在一起：
[ H k y k + a ⋅ U ( U T y k ) ] ⏟ = 0 + [ b ⋅ V ( V T y k ) − S k ] ⏟ = 0 = 0 \underbrace{\left[\mathcal H_k y_k + a \cdot \mathcal U (\mathcal U^T y_k) \right]}_{=0} + \underbrace{\left[b \cdot \mathcal V ( \mathcal V^T y_k) - \mathcal S_k\right]}_{=0} = 0 =0 [Hk​yk​+a⋅U(UTyk​)]​​+=0 [b⋅V(VTyk​)−Sk​]​​=0
观察第一项：令 U = H k y k \mathcal U = \mathcal H_k y_k U=Hk​yk​，带入有：
H k y k + a ⋅ U ( U T y k ) = H k y k + a ⋅ H k y k [ ( H k y k ) T y k ] = ( H k y k ) [ 1 + a ⋅ ( H k y k ) T y k ] = 0 ⇒ 1 + a ⋅ ( H k y k ) T y k = 0 \begin{aligned} \mathcal H_k y_k + a \cdot \mathcal U (\mathcal U^T y_k) & = \mathcal H_ky_k + a \cdot\mathcal H_k y_k [(\mathcal H_k y_k)^Ty_k] \\ & = (\mathcal H_k y_k)[1 + a \cdot (\mathcal H_k y_k)^T y_k] \\ & = 0 \\ & \Rightarrow1 + a \cdot (\mathcal H_k y_k)^T y_k = 0 \end{aligned} Hk​yk​+a⋅U(UTyk​)​=Hk​yk​+a⋅Hk​yk​[(Hk​yk​)Tyk​]=(Hk​yk​)[1+a⋅(Hk​yk​)Tyk​]=0⇒1+a⋅(Hk​yk​)Tyk​=0​
整理得： a = − 1 y k T H k T y k \begin{aligned}a = - \frac{1}{y_k^T \mathcal H_k^T y_k}\end{aligned} a=−ykT​HkT​yk​1​​。
同理，观察第二项：令 V = S k \mathcal V = \mathcal S_k V=Sk​，带入有：
b ⋅ S k T y k − 1 = 0 ⇒ b = 1 S k T y k b \cdot \mathcal S_k^T y_k - 1 = 0 \Rightarrow b = \frac{1}{\mathcal S_k^T y_k} b⋅SkT​yk​−1=0⇒b=SkT​yk​1​
至此，关于向量 U , V \mathcal U,\mathcal V U,V，系数 a , b a,b a,b均已取值完毕，将该结果带入 H k + 1 = H k + a ⋅ U U T + b ⋅ V V T \mathcal H_{k+1} = \mathcal H_k + a \cdot \mathcal U \mathcal U^T + b \cdot \mathcal V \mathcal V^T Hk+1​=Hk​+a⋅UUT+b⋅VVT，即可得到 DFP \text{DFP} DFP公式中 H k + 1 \mathcal H_{k+1} Hk+1​与 H k \mathcal H_k Hk​之间的迭代关系。

小插曲： DFP \text{DFP} DFP方法与最小范数方法

关于最小范数方法： B k + 1 ⇒ B : { min ⁡ ∥ B − B k ∥ s.t.  B ⋅ S k = y k ; B T = B \mathcal B_{k+1} \Rightarrow \mathcal B: \begin{cases} \min \|\mathcal B - \mathcal B_k\| \\ \text{s.t. } \mathcal B \cdot \mathcal S_k = y_k;\mathcal B^T = \mathcal B \end{cases} Bk+1​⇒B:{min∥B−Bk​∥s.t. B⋅Sk​=yk​;BT=B​，如果使用 Frobenius \text{Frobenius} Frobenius范数对 ∥ B − B k ∥ \|\mathcal B - \mathcal B_k\| ∥B−Bk​∥进行表示：
可以看成是关于矩阵的 L 2 L_2 L2​范数。
∥ B − B k ∥ F = ∑ i = 1 n ∑ j = 1 n [ b i j − b i j ( k ) ] 2 \|\mathcal B - \mathcal B_k\|_{F} = \sqrt{\sum_{i=1}^n \sum_{j=1}^n \left[b_{ij} - b_{ij}^{(k)}\right]^2} ∥B−Bk​∥F​=i=1∑n​j=1∑n​[bij​−bij(k)​]2 ​
通过该范数求解出的 B k + 1 \mathcal B_{k+1} Bk+1​，它的逆： B k + 1 − 1 \mathcal B_{k+1}^{-1} Bk+1−1​就是 DFP \text{DFP} DFP方法求解出的 H k + 1 \mathcal H_{k+1} Hk+1​。
世界真奇妙~

拟牛顿法之 BFGS \text{BFGS} BFGS方法

关于 BFGS(Broyden-Fletch-Goldfarb-Shannon) \text{BFGS(Broyden-Fletch-Goldfarb-Shannon)} BFGS(Broyden-Fletch-Goldfarb-Shannon)方法可看做是对 B k \mathcal B_k Bk​进行 Rank-2 \text{Rank-2} Rank-2校正。对应迭代公式表示如下：
B k + 1 = B k − B k S k S k T B k S k T B k S k + y k y k T y k T S k \mathcal B_{k+1} = \mathcal B_k - \frac{\mathcal B_k \mathcal S_k \mathcal S_k^T \mathcal B_k}{\mathcal S_k^T \mathcal B_k \mathcal S_k} + \frac{y_k y_k^T}{y_k^T \mathcal S_k} Bk+1​=Bk​−SkT​Bk​Sk​Bk​Sk​SkT​Bk​​+ykT​Sk​yk​ykT​​

关于 BFGS \text{BFGS} BFGS公式的推导，它与 DFP \text{DFP} DFP公式的推导完全对称。只不过它使用的基本要求是： B k + 1 ⋅ S k = y k \mathcal B_{k+1} \cdot \mathcal S_k = y_k Bk+1​⋅Sk​=yk​。

• 对比 DFP \text{DFP} DFP公式：仅需要将第一项中的 y k y_k yk​改成 S k \mathcal S_k Sk​， H k \mathcal H_k Hk​改成 B k \mathcal B_k Bk​；第二项将分子中的 S k \mathcal S_k Sk​改成 y k y_k yk​即可。
• 关于 BFGS \text{BFGS} BFGS公式的推导不再赘述。

新的疑问：在使用 BFGS \text{BFGS} BFGS求解出 B k + 1 \mathcal B_{k+1} Bk+1​后，在后续求解下降方向 D k = − B k + 1 − 1 ∇ f ( x k + 1 ) \mathcal D_k = - \mathcal B_{k+1}^{-1} \nabla f(x_{k+1}) Dk​=−Bk+1−1​∇f(xk+1​)中，依然不可避免地需要求解逆： B k + 1 − 1 \mathcal B_{k+1}^{-1} Bk+1−1​。而求逆同样是一个非常麻烦的操作，为什么还会使用 BFGS \text{BFGS} BFGS方法 ? ? ?主要有两点原因：

• 具备 B k + 1 = B k + a ⋅ U U T + b ⋅ V V T \mathcal B_{k+1} = \mathcal B_k + a \cdot \mathcal U \mathcal U^T + b \cdot \mathcal V \mathcal V^T Bk+1​=Bk​+a⋅UUT+b⋅VVT格式的逆可以使用 Sherman-Morrison \text{Sherman-Morrison} Sherman-Morrison公式直接求解：
  可以看出，求逆操作自身并不麻烦。
  ( A + U V T ) − 1 = A − 1 − A − 1 U V T A − 1 1 + V T A − 1 U (\mathcal A + \mathcal U \mathcal V^T)^{-1} = \mathcal A^{-1} - \frac{\mathcal A^{-1} \mathcal U \mathcal V^T \mathcal A^{-1}}{1 + \mathcal V^T \mathcal A^{-1} \mathcal U} (A+UVT)−1=A−1−1+VTA−1UA−1UVTA−1​
• DFP \text{DFP} DFP方法求解，其结果稳定性较差。在迭代过程中可能出现 H k + 1 \mathcal H_{k+1} Hk+1​变成奇异矩阵。相反， BFGS \text{BFGS} BFGS迭代过程中的数值稳定性更强。并且 BFGS \text{BFGS} BFGS被认为是最有效的拟牛顿法，它的收敛速度可达到超线性收敛。

相比于牛顿法中直接求解 Hessian Matrix ⇒ ∇ 2 f ( x k ) \text{Hessian Matrix} \Rightarrow \nabla^2 f(x_k) Hessian Matrix⇒∇2f(xk​)， DFP,BFGS \text{DFP,BFGS} DFP,BFGS方法需要求解梯度 ∇ f ( x k ) , ∇ f ( x k + 1 ) \nabla f(x_k),\nabla f(x_{k+1}) ∇f(xk​),∇f(xk+1​)，以及套用求逆公式。其计算量远小于求解 Hessian Matrix \text{Hessian Matrix} Hessian Matrix。

Broyden \text{Broyden} Broyden族

假设使用 DFP \text{DFP} DFP方法求解出 H k + 1 \mathcal H_{k+1} Hk+1​，将该结果求逆，将其还原：
B DFP ; k + 1 = H k + 1 − 1 \mathcal B_{\text{DFP};k+1} = \mathcal H_{k+1}^{-1} BDFP;k+1​=Hk+1−1​
然后通过 BFGS \text{BFGS} BFGS方法直接求解出 B k + 1 \mathcal B_{k+1} Bk+1​。对这两个矩阵进行线性组合：
{ λ ⋅ B DFP ; k + 1 + ( 1 − λ ) ⋅ B k + 1 } λ ∈ [ 0 , 1 ] \{\lambda \cdot \mathcal B_{\text{DFP};k+1} + (1 - \lambda) \cdot \mathcal B_{k+1}\} \quad \lambda \in [0,1] {λ⋅BDFP;k+1​+(1−λ)⋅Bk+1​}λ∈[0,1]
这明显是一个集合。如果迭代过程中，矩阵 B k + 1 \mathcal B_{k+1} Bk+1​落在集合内，对应的方法被称作 Broyden \text{Broyden} Broyden族。

拟牛顿法之 SR-1 \text{SR-1} SR-1方法

关于 SR-1 \text{SR-1} SR-1方法可看做是对 B k \mathcal B_k Bk​进行 Rank-1 \text{Rank-1} Rank-1校正。对应迭代公式表示如下：
B k + 1 = B k + ( y k − B k S k ) ( y k − B k S k ) T ( y k − B k S k ) T S k \mathcal B_{k+1} = \mathcal B_k + \frac{(y_k - \mathcal B_k \mathcal S_k)(y_k - \mathcal B_k \mathcal S_k)^T}{(y_k - \mathcal B_k \mathcal S_k)^T \mathcal S_k} Bk+1​=Bk​+(yk​−Bk​Sk​)TSk​(yk​−Bk​Sk​)(yk​−Bk​Sk​)T​

SR-1 \text{SR-1} SR-1迭代公式的推导过程

与 DFP \text{DFP} DFP方法的推导过程类似。将迭代关系： B k + 1 = B k + Δ B \mathcal B_{k+1} = \mathcal B_k + \Delta \mathcal B Bk+1​=Bk​+ΔB表示为如下形式：
B k + 1 = B k + a ⋅ U U T \mathcal B_{k+1} = \mathcal B_{k} + a \cdot \mathcal U \mathcal U^T Bk+1​=Bk​+a⋅UUT
由于 B k + 1 \mathcal B_{k+1} Bk+1​需要满足基本要求： B k + 1 ⋅ S k = y k \mathcal B_{k+1} \cdot \mathcal S_k = y_k Bk+1​⋅Sk​=yk​。因而将上式带入，有：
B k S k + a ⋅ U ( U T S k ) = y k ⇒ a ⋅ U ( U T S k ) = y k − B k S k \mathcal B_k \mathcal S_k + a \cdot \mathcal U( \mathcal U^T \mathcal S_k) = y_k \Rightarrow a \cdot \mathcal U(\mathcal U^T \mathcal S_k) = y_k - \mathcal B_k \mathcal S_k Bk​Sk​+a⋅U(UTSk​)=yk​⇒a⋅U(UTSk​)=yk​−Bk​Sk​
令 U = y k − B k S k \mathcal U = y_k - \mathcal B_k \mathcal S_k U=yk​−Bk​Sk​，有：系数 a ⋅ ( U T S k ) = 1 a \cdot (\mathcal U^T \mathcal S_k) = 1 a⋅(UTSk​)=1，最终可求出 a a a：
a = 1 U T S k = 1 ( y k − B k S k ) T S k a = \frac{1}{\mathcal U^T \mathcal S_k} = \frac{1}{(y_k - \mathcal B_k \mathcal S_k)^T \mathcal S_k} a=UTSk​1​=(yk​−Bk​Sk​)TSk​1​
将 a , U a,\mathcal U a,U带回 B k + 1 = B k + a ⋅ U U T \mathcal B_{k+1} = \mathcal B_{k} + a \cdot \mathcal U\mathcal U^T Bk+1​=Bk​+a⋅UUT，就有 SR-1 \text{SR-1} SR-1迭代公式。

不可否认： SR-1 \text{SR-1} SR-1方法的迭代公式更加简便，但它不能保证迭代过程中 B k + 1 \mathcal B_{k+1} Bk+1​的正定性。在适当条件下， SR-1 \text{SR-1} SR-1算法可达到 n n n步超线性收敛。
这里的 n n n步超线性收敛是指：当前步骤与执行 n n n步之后的结果呈超线性收敛趋势。对比超线性收敛，其数学符号表示如下：
{ lim ⁡ k → ∞ ∥ x k + 1 − x ∗ ∥ ∥ x k − x ∗ ∥ = 0 lim ⁡ k ⇒ ∞ ∥ x k + n − x ∗ ∥ ∥ x k − x ∗ ∥ = 0 \begin{cases} \begin{aligned} \mathop{\lim}\limits_{k \rightarrow \infty} \frac{\|x_{k+1} - x^*\|}{\|x_k - x^*\|} = 0\\ \mathop{\lim}\limits_{k \Rightarrow \infty} \frac{\|x_{k+n} - x^*\|}{\|x_k - x^*\|} = 0 \end{aligned} \end{cases} ⎩ ⎨ ⎧​k→∞lim​∥xk​−x∗∥∥xk+1​−x∗∥​=0k⇒∞lim​∥xk​−x∗∥∥xk+n​−x∗∥​=0​​

Reference \text{Reference} Reference：
最优化理论与方法-第六讲-无约束优化问题（二）