如何给网站绑定域名,衡阳网站建设要点推广,做百家好还是个人网站,滨州网站建设哪家好机器学习笔记之最优化理论与方法——基于无约束优化问题的常用求解方法[下] 引言回顾#xff1a;经典牛顿法的缺陷与拟牛顿法思想经典牛顿法缺陷与修正牛顿法拟牛顿法与矩阵 B k 1 \mathcal B_{k1} Bk1的选择 拟牛顿法之 DFP \text{DFP} DFP方法 DFP \text{DFP} DFP迭代公式… 机器学习笔记之最优化理论与方法——基于无约束优化问题的常用求解方法[下] 引言回顾经典牛顿法的缺陷与拟牛顿法思想经典牛顿法缺陷与修正牛顿法拟牛顿法与矩阵 B k 1 \mathcal B_{k1} Bk1的选择 拟牛顿法之 DFP \text{DFP} DFP方法 DFP \text{DFP} DFP迭代公式的推导过程小插曲 DFP \text{DFP} DFP方法与最小范数方法 拟牛顿法之 BFGS \text{BFGS} BFGS方法 Broyden \text{Broyden} Broyden族拟牛顿法之 SR-1 \text{SR-1} SR-1方法 SR-1 \text{SR-1} SR-1迭代公式的推导过程 引言
上一节介绍了牛顿法、拟牛顿法。本节将继续以拟牛顿法为基础介绍 DFP , BFGS \text{DFP},\text{BFGS} DFP,BFGS方法。
回顾经典牛顿法的缺陷与拟牛顿法思想
经典牛顿法缺陷与修正牛顿法
关于经典牛顿法中关于下降方向 D k ( k 1 , 2 , ⋯ , ∞ ) \mathcal D_k(k1,2,\cdots,\infty) Dk(k1,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_{i1,2,\cdots,n} \{- \lambda_i\} λi1,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)}{\lambda}\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{τiif τi≥δδOtherwise 其中 δ \delta δ是一个适当正数虽然该方式相比正则化法要缓和不少——仅调整非正特征值的结果其余正特征值保持不变。但该方法依然存在逻辑上的缺失通过强行修改二阶梯度信息的方式使其收敛。
拟牛顿法与矩阵 B k 1 \mathcal B_{k1} Bk1的选择
而拟牛顿法的思想是选择一个既包含 x k 1 x_{k1} xk1处的二阶梯度信息并且容易获取的正定矩阵 B k 1 \mathcal B_{k1} Bk1来替代 ∇ 2 f ( x k 1 ) \nabla^2 f(x_{k1}) ∇2f(xk1)。 由于 [ ∇ 2 f ( x k 1 ) ] n × n [\nabla^2 f(x_{k1})]_{n \times n} [∇2f(xk1)]n×n自身计算量较大: O ( n 3 ) \mathcal O(n^3) O(n3),从而不容易获取。
关于矩阵 B k 1 \mathcal B_{k1} Bk1满足的基本要求表示如下 ∇ f ( x k 1 ) − ∇ f ( x k ) B k 1 ( x k 1 − x k ) \nabla f(x_{k1} )- \nabla f(x_k) \mathcal B_{k1} (x_{k1} - x_k) ∇f(xk1)−∇f(xk)Bk1(xk1−xk) 可以发现该式子是关于 n n n个方程构成的方程组而未知量包含 n ( n 1 ) 2 \begin{aligned}\frac{n(n1)}{2}\end{aligned} 2n(n1)个( B k 1 \mathcal B_{k1} Bk1上/下三角阵元素数量)并且 n ( n 1 ) 2 ≥ n ; n ∈ N \begin{aligned}\frac{n(n1)}{2} \geq n;n \in \mathbb N^{}\end{aligned} 2n(n1)≥n;n∈N。这意味着拟牛顿方程的解 B k 1 \mathcal B_{k1} Bk1不唯一。
既然满足基本要求的解不唯一可以尝试从这些解中选择与 B k / H k \mathcal B_k/\mathcal H_k Bk/Hk相似的矩阵作为 B k 1 / H k 1 \mathcal B_{k1}/\mathcal H_{k1} Bk1/Hk1
其中: { 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_{k1} - x_k \\ y_k \nabla f(x_{k1}) - \nabla f(x_k) \\ \mathcal H_k \mathcal B_k^{-1} \end{cases} ⎩ ⎨ ⎧Skxk1−xkyk∇f(xk1)−∇f(xk)HkBk−1通过这种相似性来保证二阶梯度信息的有效性。无论是 B k 1 \mathcal B_{k1} Bk1还是 H k 1 \mathcal H_{k1} Hk1都可以作为我们的求解目标。因为最终都可以对下降方向 D k 1 \mathcal D_{k1} Dk1进行表示: D k 1 − B k 1 − 1 ∇ f ( x k 1 ) − H k 1 ∇ f ( x k 1 ) \mathcal D_{k1} - \mathcal B_{k1}^{-1} \nabla f(x_{k1}) -\mathcal H_{k1}\nabla f(x_{k1}) Dk1−Bk1−1∇f(xk1)−Hk1∇f(xk1)。 { 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_{k1} \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_{k1} \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} ⎩ ⎨ ⎧Bk1⇒B:{min∥B−Bk∥s.t. B⋅Skyk;BTBHk1⇒H:{min∥H−Hk∥s.t. H⋅ykSk;HTH
也可以尝试将 B k 1 / H k 1 \mathcal B_{k1}/\mathcal H_{k1} Bk1/Hk1看作是 B k / H k \mathcal B_k/\mathcal H_k Bk/Hk的校正/优化后的结果。令 B k 1 B k Δ B \mathcal B_{k1} \mathcal B_k \Delta\mathcal B Bk1BkΔB或者 H k 1 H k Δ H \mathcal H_{k1} \mathcal H_{k} \Delta \mathcal H Hk1HkΔ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_{k1} \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} Hk1Hk−ykTHkykHkykykTHkykTSkSkSkT 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 AUVTU,V∈Rn;U,V0 此时 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 ΔHUUTU∈Rn;U0 这是秩为 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} ΔHUUTVVT⎩ ⎨ ⎧U,V∈RnU,V0UV 综上将迭代关系 H k 1 H k Δ H \mathcal H_{k1} \mathcal H_k \Delta \mathcal H Hk1HkΔH表示为如下形式 其中 a , b a,b a,b是系数均是标量~ H k 1 H k a ⋅ U U T b ⋅ V V T \mathcal H_{k1} \mathcal H_k a \cdot \mathcal U \mathcal U^T b \cdot \mathcal V \mathcal V^T Hk1Hka⋅UUTb⋅VVT 由于 H k 1 \mathcal H_{k1} Hk1需要满足基本要求 H k 1 ⋅ y k S k \mathcal H_{k1} \cdot y_k \mathcal S_k Hk1⋅ykSk因而将上式带入。有 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 Hkyka⋅UUTykb⋅VVTyk−Sk0 其中
由于 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 Hkyk∈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_{k1} - x_k \in \mathbb R^n Skxk1−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 [Hkyka⋅U(UTyk)]0 [b⋅V(VTyk)−Sk]0 观察第一项令 U H k y k \mathcal U \mathcal H_k y_k UHkyk带入有 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} Hkyka⋅U(UTyk)Hkyka⋅Hkyk[(Hkyk)Tyk](Hkyk)[1a⋅(Hkyk)Tyk]0⇒1a⋅(Hkyk)Tyk0 整理得 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−ykTHkTyk1。 同理观察第二项令 V S k \mathcal V \mathcal S_k VSk带入有 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⋅SkTyk−10⇒bSkTyk1 至此关于向量 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_{k1} \mathcal H_k a \cdot \mathcal U \mathcal U^T b \cdot \mathcal V \mathcal V^T Hk1Hka⋅UUTb⋅VVT即可得到 DFP \text{DFP} DFP公式中 H k 1 \mathcal H_{k1} Hk1与 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_{k1} \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} Bk1⇒B:{min∥B−Bk∥s.t. B⋅Skyk;BTB如果使用 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_{i1}^n \sum_{j1}^n \left[b_{ij} - b_{ij}^{(k)}\right]^2} ∥B−Bk∥Fi1∑nj1∑n[bij−bij(k)]2 通过该范数求解出的 B k 1 \mathcal B_{k1} Bk1它的逆 B k 1 − 1 \mathcal B_{k1}^{-1} Bk1−1就是 DFP \text{DFP} DFP方法求解出的 H k 1 \mathcal H_{k1} Hk1。 世界真奇妙~
拟牛顿法之 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_{k1} \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} Bk1Bk−SkTBkSkBkSkSkTBkykTSkykykT
关于 BFGS \text{BFGS} BFGS公式的推导它与 DFP \text{DFP} DFP公式的推导完全对称。只不过它使用的基本要求是 B k 1 ⋅ S k y k \mathcal B_{k1} \cdot \mathcal S_k y_k Bk1⋅Skyk。
对比 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_{k1} Bk1后在后续求解下降方向 D k − B k 1 − 1 ∇ f ( x k 1 ) \mathcal D_k - \mathcal B_{k1}^{-1} \nabla f(x_{k1}) Dk−Bk1−1∇f(xk1)中依然不可避免地需要求解逆 B k 1 − 1 \mathcal B_{k1}^{-1} Bk1−1。而求逆同样是一个非常麻烦的操作为什么还会使用 BFGS \text{BFGS} BFGS方法 ? ? ?主要有两点原因
具备 B k 1 B k a ⋅ U U T b ⋅ V V T \mathcal B_{k1} \mathcal B_k a \cdot \mathcal U \mathcal U^T b \cdot \mathcal V \mathcal V^T Bk1Bka⋅UUTb⋅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} (AUVT)−1A−1−1VTA−1UA−1UVTA−1 DFP \text{DFP} DFP方法求解其结果稳定性较差。在迭代过程中可能出现 H k 1 \mathcal H_{k1} Hk1变成奇异矩阵。相反 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_{k1}) ∇f(xk),∇f(xk1)以及套用求逆公式。其计算量远小于求解 Hessian Matrix \text{Hessian Matrix} Hessian Matrix。 Broyden \text{Broyden} Broyden族
假设使用 DFP \text{DFP} DFP方法求解出 H k 1 \mathcal H_{k1} Hk1将该结果求逆将其还原 B DFP ; k 1 H k 1 − 1 \mathcal B_{\text{DFP};k1} \mathcal H_{k1}^{-1} BDFP;k1Hk1−1 然后通过 BFGS \text{BFGS} BFGS方法直接求解出 B k 1 \mathcal B_{k1} Bk1。对这两个矩阵进行线性组合 { λ ⋅ B DFP ; k 1 ( 1 − λ ) ⋅ B k 1 } λ ∈ [ 0 , 1 ] \{\lambda \cdot \mathcal B_{\text{DFP};k1} (1 - \lambda) \cdot \mathcal B_{k1}\} \quad \lambda \in [0,1] {λ⋅BDFP;k1(1−λ)⋅Bk1}λ∈[0,1] 这明显是一个集合。如果迭代过程中矩阵 B k 1 \mathcal B_{k1} Bk1落在集合内对应的方法被称作 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_{k1} \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} Bk1Bk(yk−BkSk)TSk(yk−BkSk)(yk−BkSk)T SR-1 \text{SR-1} SR-1迭代公式的推导过程
与 DFP \text{DFP} DFP方法的推导过程类似。将迭代关系 B k 1 B k Δ B \mathcal B_{k1} \mathcal B_k \Delta \mathcal B Bk1BkΔB表示为如下形式 B k 1 B k a ⋅ U U T \mathcal B_{k1} \mathcal B_{k} a \cdot \mathcal U \mathcal U^T Bk1Bka⋅UUT 由于 B k 1 \mathcal B_{k1} Bk1需要满足基本要求 B k 1 ⋅ S k y k \mathcal B_{k1} \cdot \mathcal S_k y_k Bk1⋅Skyk。因而将上式带入有 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 BkSka⋅U(UTSk)yk⇒a⋅U(UTSk)yk−BkSk 令 U y k − B k S k \mathcal U y_k - \mathcal B_k \mathcal S_k Uyk−BkSk有系数 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} aUTSk1(yk−BkSk)TSk1 将 a , U a,\mathcal U a,U带回 B k 1 B k a ⋅ U U T \mathcal B_{k1} \mathcal B_{k} a \cdot \mathcal U\mathcal U^T Bk1Bka⋅UUT就有 SR-1 \text{SR-1} SR-1迭代公式。
不可否认 SR-1 \text{SR-1} SR-1方法的迭代公式更加简便但它不能保证迭代过程中 B k 1 \mathcal B_{k1} Bk1的正定性。在适当条件下 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_{k1} - x^*\|}{\|x_k - x^*\|} 0\\ \mathop{\lim}\limits_{k \Rightarrow \infty} \frac{\|x_{kn} - x^*\|}{\|x_k - x^*\|} 0 \end{aligned} \end{cases} ⎩ ⎨ ⎧k→∞lim∥xk−x∗∥∥xk1−x∗∥0k⇒∞lim∥xk−x∗∥∥xkn−x∗∥0 Reference \text{Reference} Reference 最优化理论与方法-第六讲-无约束优化问题二
