网站备案期限,上海网站建设 百家号,ui设计师工作内容怎么写,个人手机网站开发文章目录 统计学习方法 牛顿法和拟牛顿法牛顿法拟牛顿法DFP 算法BFGS 算法Broyden 类算法 统计学习方法 牛顿法和拟牛顿法
学习李航的《统计学习方法》时#xff0c;关于牛顿法和拟牛顿法的笔记。
牛顿法#xff08;Newton method#xff09;和拟牛顿法#xff08;quasi-… 文章目录 统计学习方法 牛顿法和拟牛顿法牛顿法拟牛顿法DFP 算法BFGS 算法Broyden 类算法 统计学习方法 牛顿法和拟牛顿法
学习李航的《统计学习方法》时关于牛顿法和拟牛顿法的笔记。
牛顿法Newton method和拟牛顿法quasi-Newton method时求解无约束优化问题的常用方法有收敛速度快的优点。牛顿法时迭代算法每一步需要求解目标函数的 Hession 矩阵的逆矩阵计算较为复杂拟牛顿法通过正定矩阵近似 Hession 矩阵或其逆矩阵简化了计算过程。
牛顿法
牛顿法的推导考虑无约束最优化问题 min x ∈ R n f ( x ) \min\limits_{x\in \R^n} f(x) x∈Rnminf(x) 设 x ∗ x^\ast x∗ 是目标函数的极小点。
假设 f ( x ) f(x) f(x) 具有二姐连续偏导数若第 k k k 次迭代的值为 x ( k ) x^{(k)} x(k) 则对 f ( x ) f(x) f(x) 在 x ( k ) x^{(k)} x(k) 附近二阶泰勒展开 f ( x ) f ( x ( k ) ) g k T ( x − x ( k ) ) 1 2 ( x − x ( k ) ) H k ( x − x ( k ) ) f(x)f(x^{(k)})g_k^\mathrm{T}(x-x^{(k)})\frac{1}{2}(x-x^{(k)})H_k(x-x^{(k)}) f(x)f(x(k))gkT(x−x(k))21(x−x(k))Hk(x−x(k)) 其中 g k g_k gk 为 f ( x ) f(x) f(x) 在 x ( k ) x^{(k)} x(k) 处的梯度向量 H k H_k Hk 为 f ( x ) f(x) f(x) 的 Hession 矩阵在 x ( k ) x^{(k)} x(k) 处的值 g ( x ) ∇ f ( x ) [ ∂ f ∂ x i ] n × 1 , H ( x ) [ ∂ 2 f ∂ x i ∂ x j ] n × n g(x)\nabla f(x)\left[\frac{\partial f}{\partial x_i}\right]_{n\times 1},\quad H(x)\left[ \frac{\partial^2 f}{\partial x_i\partial x_j} \right]_{n\times n} g(x)∇f(x)[∂xi∂f]n×1,H(x)[∂xi∂xj∂2f]n×n 函数 f ( x ) f(x) f(x) 有极值的必要条件是在极值点处一阶导数即梯度向量为 0 0 0 。特别地当 H ( x ) H(x) H(x) 在极值点处是正定矩阵时函数 f ( x ) f(x) f(x) 的极值为极小值。
牛顿法利用极小点的必要条件每次从上一次迭代得到的极小点 x ( k ) x^{(k)} x(k) 开始得到当前目标函数的极小点 x ( k 1 ) x^{(k1)} x(k1) 即 ∇ f ( x ( k 1 ) ) g k ( x ( k 1 ) − x ( k ) ) 0 \nabla f(x^{(k1)})g_k(x^{(k1)}-x^{(k)})0 ∇f(x(k1))gk(x(k1)−x(k))0 解得 x ( k 1 ) x ( k ) − H k − 1 g k x^{(k1)}x^{(k)}-H_k^{-1}g_k x(k1)x(k)−Hk−1gk 假设 p k p_k pk 为一 n × 1 n\times 1 n×1 的列向量且满足 H k p k − g k H_kp_k-g_k Hkpk−gk 则迭代公式可写为 x ( k 1 ) x ( k ) p k x^{(k1)}x^{(k)}p_k x(k1)x(k)pk 算法牛顿法
输入目标函数 f ( x ) f(x) f(x) 梯度 g ( x ) ∇ f ( x ) g(x)\nabla f(x) g(x)∇f(x) Hession 矩阵 H ( x ) H(x) H(x) 精度 ε \varepsilon ε 输出 f ( x ) f(x) f(x) 的极小值点 x ∗ x^\ast x∗
取初始点 x ( 0 ) x^{(0)} x(0) 置 k 0 k0 k0 计算 g k g ( x ( k ) ) g_kg(x^{(k)}) gkg(x(k)) 若 ∥ g k ∥ ε \|g_k\|\lt \varepsilon ∥gk∥ε 则停止计算返回近似解 x ∗ x ( k ) x^\astx^{(k)} x∗x(k) 计算 H k H ( x ( k ) ) H_kH(x^{(k)}) HkH(x(k)) 并求 p k p_k pk H k p k − g k H_kp_k-g_k Hkpk−gk
更新 x ( k 1 ) x ( k ) p k x^{(k1)}x^{(k)}p_k x(k1)x(k)pk k k 1 kk1 kk1 跳转至 2
拟牛顿法
牛顿法中需要计算 H k − 1 H_k^{-1} Hk−1 比较耗时我们考虑使用一个与 Hession 矩阵具有类似性质的 n n n 阶矩阵 G k G ( x ( k ) ) G_kG(x^{(k)}) GkG(x(k)) 来近似代替 H k − 1 H_k^{-1} Hk−1 。
条件一首先对 x ( k ) x^{(k)} x(k) 处的二阶泰勒展开进行求导取 x ( k 1 ) x^{(k1)} x(k1) 得 g k 1 − g k H k ( x ( k 1 ) − x ( k ) ) g_{k1}-g_kH_k(x^{(k1)}-x^{(k)}) gk1−gkHk(x(k1)−x(k)) 记 y k g k 1 − g k y_kg_{k1}-g_k ykgk1−gk δ k x ( k 1 ) − x ( k ) \delta_{k}x^{(k1)}-x^{(k)} δkx(k1)−x(k) 则满足 y k H k δ k y_kH_k\delta_k ykHkδk 或 H k − 1 y k δ k H_k^{-1}y_k\delta_k Hk−1ykδk 该条件称为拟牛顿条件。
条件二如果 H k H_k Hk 是正定的 H k − 1 H_k^{-1} Hk−1 也是正定的那么可以保证牛顿法搜索方向 p k p_k pk 是下降方向因为 x ( k 1 ) x ( k ) λ p k x ( k ) − λ H k − 1 g k x^{(k1)}x^{(k)}\lambda p_kx^{(k)}-\lambda H_k^{-1}g_k x(k1)x(k)λpkx(k)−λHk−1gk 带入前面的泰勒展开式为 f ( x ( k 1 ) ) f ( x k ) − λ g k T H k − 1 g k 1 2 λ 2 g k T H k − T H k H k − 1 g k ≈ f ( x k ) − λ g k T H k − 1 g k f(x^{(k1)})f(x^{k})-\lambda g_k^{\mathrm{T}}H_k^{-1}g_k\frac{1}{2}\lambda^2g_k^\mathrm{T}H_k^{-\mathrm{T}}H_kH_{k}^{-1}g_k\approx f(x^{k})-\lambda g_k^{\mathrm{T}}H_k^{-1}g_k f(x(k1))f(xk)−λgkTHk−1gk21λ2gkTHk−THkHk−1gk≈f(xk)−λgkTHk−1gk 当 λ \lambda λ 为一个足够小的正数时由于 H k H_k Hk 正定即 λ g k T H k − 1 g k 0 \lambda g_k^{\mathrm{T}}H_k^{-1}g_k \gt 0 λgkTHk−1gk0 因此有 f ( x ( k 1 ) ) f ( x ( k ) ) f(x^{(k1)})\lt f(x^{(k)}) f(x(k1))f(x(k)) 也就是说 p k p_k pk 时下降方向。
综合前面两个条件我们在选择近似矩阵 G k G_k Gk 时首先要求每次迭代时 G k G_k Gk 是正定的其次 G k G_k Gk 需要满足以下的拟牛顿条件 G k 1 y k δ k G_{k1}y_{k}\delta_k Gk1ykδk 同时按照拟牛顿条件每次迭代可以选择更新矩阵 G k 1 G_{k1} Gk1 G k 1 G k Δ G k G_{k1}G_{k}\Delta G_{k} Gk1GkΔGk 有多种选择近似矩阵的方法
DFP 算法
DFP Davidon-Fletcher-Powell算法对 G k G_{k} Gk 的更新为 G k 1 G k P k Q k G_{k1}G_{k}P_kQ_k Gk1GkPkQk 其中 P k P_k Pk 和 Q k Q_k Qk 是待定矩阵此时 G k 1 y k G k y k P k y k Q k y k δ k G_{k1}y_{k}G_ky_kP_ky_kQ_ky_k\delta_k Gk1ykGkykPkykQkykδk 为了满足拟牛顿条件可以令 P k y k δ k , Q k y k − G k y k P_ky_k\delta_k,\quad Q_ky_k-G_ky_k Pkykδk,Qkyk−Gkyk 书上给了一个例子 P k δ k δ k T δ k T y k , Q k − G k y k y k T G k y k T G k y k P_k\frac{\delta_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k},\quad Q_k-\frac{G_ky_ky_k^{\mathrm{T}}G_k}{y_k^{\mathrm{T}}G_ky_k} PkδkTykδkδkT,Qk−ykTGkykGkykykTGk 可以证明咱也不知道怎么证明如果 G 0 G_0 G0 是正定的则迭代过程中的每个矩阵 G k G_k Gk 都是正定的。
算法DFP 算法
输入目标函数 f ( x ) f(x) f(x) 梯度 g ( x ) ∇ f ( x ) g(x)\nabla f(x) g(x)∇f(x) 精度 ε \varepsilon ε 输出 f ( x ) f(x) f(x) 的极小点 x ∗ x^\ast x∗
选定初始点 x ( 0 ) x^{(0)} x(0) 取 G 0 G_0 G0 为正定对称矩阵置 k 0 k0 k0 计算 g k g ( x ( k ) ) g_kg(x^{(k)}) gkg(x(k)) 若 ∥ g ( x ( k ) ) ∥ ε \|g(x^{(k)})\| \lt \varepsilon ∥g(x(k))∥ε 则停止计算返回近似解 x ∗ x ( k ) x^\astx^{(k)} x∗x(k) 否则继续计算 p k − G k g k p_k-G_kg_k pk−Gkgk 一维搜索求 λ k \lambda_k λk 使得 f ( x ( k ) λ k p k ) min λ ≥ 0 f ( x ( k ) λ p k ) f(x^{(k)}\lambda_kp_k)\min_{\lambda \geq 0}f(x^{(k)}\lambda p_k) f(x(k)λkpk)λ≥0minf(x(k)λpk)
置 x ( k 1 ) x ( k ) λ k p k x^{(k1)}x^{(k)}\lambda_kp_k x(k1)x(k)λkpk 计算 G k 1 G_{k1} Gk1 置 k k 1 kk1 kk1 转 2 G k 1 G k δ k δ k T δ k T y k − G k y k y k T G k y k T G k y k G_{k1}G_{k}\frac{\delta_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k}-\frac{G_ky_ky_k^{\mathrm{T}}G_k}{y_k^{\mathrm{T}}G_ky_k} Gk1GkδkTykδkδkT−ykTGkykGkykykTGk
BFGS 算法
BFGSBroyden-Fletcher-Goldfarb-Shanno算法是最流行的拟牛顿算法。此时考虑使用 B k B_k Bk 近似 H k H_k Hk 更新方法类似 B k 1 B k P k Q k B_{k1}B_{k}P_{k}Q_{k} Bk1BkPkQk 为了满足拟牛顿条件 B k 1 δ k B k δ k P k δ k Q k δ k y k B_{k1}\delta_kB_k\delta_kP_k\delta_kQ_k\delta_ky_k Bk1δkBkδkPkδkQkδkyk 取 P k δ k y k , Q k δ k − B k δ k P_k\delta_ky_k,\quad Q_k\delta_k-B_k\delta_k Pkδkyk,Qkδk−Bkδk 同样可令 P k y k y k T y k T δ k , Q k − B k δ k δ k T B k δ k T B k δ k P_k\frac{y_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k},\quad Q_k-\frac{B_k\delta_k\delta_k^{\mathrm{T}}B_k}{\delta_k^{\mathrm{T}}B_k\delta_k} PkykTδkykykT,Qk−δkTBkδkBkδkδkTBk 算法BFGS 算法
输入目标函数 f ( x ) f(x) f(x) 梯度 g ( x ) ∇ f ( x ) g(x)\nabla f(x) g(x)∇f(x) 精度 ε \varepsilon ε 输出 f ( x ) f(x) f(x) 的极小点 x ∗ x^\ast x∗
选定初始点 x ( 0 ) x^{(0)} x(0) 取 B 0 B_0 B0 为正定对称矩阵置 k 0 k0 k0 计算 g k g ( x ( k ) ) g_kg(x^{(k)}) gkg(x(k)) 若 ∥ g ( x ( k ) ) ∥ ε \|g(x^{(k)})\| \lt \varepsilon ∥g(x(k))∥ε 则停止计算返回近似解 x ∗ x ( k ) x^\astx^{(k)} x∗x(k) 否则继续由 B k p k − g k B_kp_k-g_k Bkpk−gk 计算 p k p_k pk一维搜索求 λ k \lambda_k λk 使得 f ( x ( k ) λ k p k ) min λ ≥ 0 f ( x ( k ) λ p k ) f(x^{(k)}\lambda_kp_k)\min_{\lambda \geq 0}f(x^{(k)}\lambda p_k) f(x(k)λkpk)λ≥0minf(x(k)λpk)
置 x ( k 1 ) x ( k ) λ k p k x^{(k1)}x^{(k)}\lambda_kp_k x(k1)x(k)λkpk 计算 B k 1 B_{k1} Bk1 置 k k 1 kk1 kk1 转 2 B k 1 B k y k y k T y k T δ k − B k δ k δ k T B k δ k T B k δ k B_{k1}B_{k}\frac{y_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k}-\frac{B_k\delta_k\delta_k^{\mathrm{T}}B_k}{\delta_k^{\mathrm{T}}B_k\delta_k} Bk1BkykTδkykykT−δkTBkδkBkδkδkTBk
Broyden 类算法
根据 BFGS 算法中 B k B_k Bk 矩阵的迭代公式我们可以得到对应的 G k G_k Gk 矩阵。有 G k B k − 1 G_kB_k^{-1} GkBk−1 G k 1 − 1 B k 1 − 1 G_{k1}^{-1}B_{k1}^{-1} Gk1−1Bk1−1 有 G k 1 − 1 G k − 1 y k y k T y k T δ k − G k − 1 δ k δ k T G k − 1 δ k T G k − 1 δ k ⇒ G k 1 ( G k − 1 y k y k T y k T δ k − G k − 1 δ k δ k T G k − 1 δ k T G k − 1 δ k ) − 1 \begin{aligned} G_{k1}^{-1}\, G_{k}^{-1}\frac{y_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k}-\frac{G_k^{-1}\delta_k\delta_k^{\mathrm{T}}G_k^{-1}}{\delta_k^{\mathrm{T}}G_k^{-1}\delta_k} \\ \Rightarrow G_{k1}\, \left( G_{k}^{-1}\frac{y_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k}\frac{-G_k^{-1}\delta_k\delta_k^{\mathrm{T}}G_k^{-1}}{\delta_k^{\mathrm{T}}G_k^{-1}\delta_k} \right)^{-1} \\ \end{aligned} Gk1−1⇒Gk1Gk−1ykTδkykykT−δkTGk−1δkGk−1δkδkTGk−1(Gk−1ykTδkykykTδkTGk−1δk−Gk−1δkδkTGk−1)−1 需要用到 Shermax-Morrison 公式 ( A u v T ) − 1 A − 1 − A − 1 u v T A − 1 1 v T A − 1 u (Auv^\mathrm{T})^{-1}A^{-1}-\frac{A^{-1}uv^\mathrm{T}A^{-1}}{1v^{\mathrm{T}}A^{-1}u} (AuvT)−1A−1−1vTA−1uA−1uvTA−1 其中 u u u 和 v v v 为 n n n 维向量 A A A 为可逆矩阵记 A G k − 1 y k y k T y k T δ k , u − G k − 1 δ k , v T δ k T G k − 1 δ k T G k − 1 δ k AG_k^{-1}\frac{y_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k},\quad u-G_k^{-1}\delta_k,\quad v^{\mathrm{T}}\frac{\delta_k^{\mathrm{T}}G_k^{-1}}{\delta_k^{\mathrm{T}}G_k^{-1}\delta_k} AGk−1ykTδkykykT,u−Gk−1δk,vTδkTGk−1δkδkTGk−1 则 G k 1 ( A − G k − 1 δ k δ k T G k − 1 δ k T G k − 1 δ k ) − 1 A − 1 A − 1 G k − 1 δ k δ k T G k − 1 δ k T G k − 1 δ k A − 1 1 − δ k T G k − 1 A − 1 G k − 1 δ k δ k T G k − 1 δ k A − 1 A − 1 G k − 1 δ k δ k T G k − 1 A − 1 δ k T G k − 1 δ k − δ k T G k − 1 A − 1 G k − 1 δ k \begin{aligned} G_{k1} \, \left(A\frac{-G_k^{-1}\delta_k\delta_k^{\mathrm{T}}G_k^{-1}}{\delta_k^{\mathrm{T}}G_k^{-1}\delta_k}\right)^{-1} \\ \, A^{-1}\frac{A^{-1}\frac{G_k^{-1}\delta_k\delta_k^{\mathrm{T}}G_k^{-1}}{\delta_k^{\mathrm{T}}G_k^{-1}\delta_k}A^{-1}}{1-\frac{\delta_k^{\mathrm{T}}G_k^{-1}A^{-1}G_k^{-1}\delta_{k}} {\delta_k^{\mathrm{T}}G_k^{-1}\delta_k}} \\ \, A^{-1}\frac{A^{-1}G_k^{-1}\delta_k\delta_k^{\mathrm{T}}G_k^{-1}A^{-1}}{\delta_k^{\mathrm{T}}G_k^{-1}\delta_k-\delta_k^{\mathrm{T}}G_k^{-1}A^{-1}G_k^{-1}\delta_{k}} \end{aligned} Gk1(AδkTGk−1δk−Gk−1δkδkTGk−1)−1A−11−δkTGk−1δkδkTGk−1A−1Gk−1δkA−1δkTGk−1δkGk−1δkδkTGk−1A−1A−1δkTGk−1δk−δkTGk−1A−1Gk−1δkA−1Gk−1δkδkTGk−1A−1 对 A A A 再次使用公式此时 u y k uy_k uyk v T y k T y k T δ k v^{\mathrm{T}}\frac{y_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k} vTykTδkykT 得到 A − 1 ( G k − 1 y k y k T y k T δ k ) − 1 G k − G k y k y k T y k T δ k G k 1 y k T G k y k y k T δ k G k − G k y k y k T G k y k T δ k y k T G k y k A^{-1}\left(G_k^{-1}\frac{y_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k}\right)^{-1} G_{k}-\frac{G_k\frac{y_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k}G_k} {1\frac{y_k^{\mathrm{T}}G_ky_k}{y_k^{\mathrm{T}}\delta_k}} G_{k}-\frac{G_ky_ky_k^{\mathrm{T}}G_k} {y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k} A−1(Gk−1ykTδkykykT)−1Gk−1ykTδkykTGkykGkykTδkykykTGkGk−ykTδkykTGkykGkykykTGk 将 A − 1 A^{-1} A−1 逐步代入 G k 1 G_{k1} Gk1 得到 G k 1 A − 1 A − 1 G k − 1 δ k δ k T G k − 1 A − 1 δ k T G k − 1 δ k − δ k T G k − 1 A − 1 G k − 1 δ k A − 1 A − 1 G k − 1 δ k δ k T G k − 1 A − 1 δ k T G k − 1 δ k − δ k T G k − 1 ( G k − G k y k y k T G k y k T δ k y k T G k y k ) G k − 1 δ k A − 1 A − 1 G k − 1 δ k δ k T G k − 1 A − 1 δ k T y k y k T δ k y k T δ k y k T G k y k A − 1 ( G k − G k y k y k T G k y k T δ k y k T G k y k ) ( G k − 1 δ k δ k T G k − 1 δ k T y k y k T δ k y k T δ k y k T G k y k ) ( G k − G k y k y k T G k y k T δ k y k T G k y k ) A − 1 ( I − G k y k y k T y k T δ k y k T G k y k ) ( δ k δ k T δ k T y k y k T δ k y k T δ k y k T G k y k ) ( I − y k y k T G k y k T δ k y k T G k y k ) A − 1 ( ( δ k δ k T ) ( y k T δ k y k T G k y k ) δ k T y k y k T δ k ) − ( δ k δ k T y k y k T G k δ k T y k y k T δ k ) − ( G k y k y k T δ k δ k T δ k T y k y k T δ k ) ( G k y k y k T δ k δ k T y k y k T G k ( δ k T y k y k T δ k ) ( y k T δ k y k T G k y k ) ) G k − G k y k y k T G k y k T δ k y k T G k y k ( ( δ k δ k T ) ( y k T δ k y k T G k y k ) δ k T y k y k T δ k ) − ( δ k δ k T y k y k T G k δ k T y k y k T δ k ) − ( G k y k y k T δ k δ k T δ k T y k y k T δ k ) ( G k y k y k T G k y k T δ k y k T G k y k ) G k ( ( δ k δ k T ) ( y k T δ k ) δ k T y k y k T δ k ) ( ( δ k δ k T ) ( y k T G k y k ) δ k T y k y k T δ k ) − ( δ k y k T G k y k T δ k ) − ( G k y k δ k T δ k T y k ) G k − ( G k y k δ k T δ k T y k ) − ( δ k y k T G k y k T δ k ) ( δ k ( y k T G k y k ) δ k T δ k T y k y k T δ k ) ( δ k δ k T δ k T y k ) G k ( I − y k δ k T δ k T y k ) − ( δ k y k T G k y k T δ k ) ( I − y k δ k T δ k T y k ) ( δ k δ k T δ k T y k ) ( I − δ k y k T y k T δ k ) G k ( I − y k δ k T δ k T y k ) ( δ k δ k T δ k T y k ) ( I − δ k y k T y k T δ k ) G k ( I − δ k y k T y k T δ k ) T ( δ k δ k T δ k T y k ) \begin{aligned} G_{k1} \, A^{-1}\frac{A^{-1}G_k^{-1}\delta_k\delta_k^{\mathrm{T}}G_k^{-1}A^{-1}}{\delta_k^{\mathrm{T}}G_k^{-1}\delta_k-\delta_k^{\mathrm{T}}G_k^{-1}A^{-1}G_k^{-1}\delta_{k}} \\ \, A^{-1}\frac{A^{-1}G_k^{-1}\delta_k\delta_k^{\mathrm{T}}G_k^{-1}A^{-1}}{\delta_k^{\mathrm{T}}G_k^{-1}\delta_k-\delta_k^{\mathrm{T}}G_k^{-1} \left( G_{k}-\frac{G_ky_ky_k^{\mathrm{T}}G_k} {y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k} \right) G_k^{-1}\delta_{k}} \\ \, A^{-1}\frac{A^{-1}G_k^{-1}\delta_k\delta_k^{\mathrm{T}}G_k^{-1}A^{-1}} {\frac{\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k}{y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k}} \\ \, A^{-1} \left( G_{k}-\frac{G_ky_ky_k^{\mathrm{T}}G_k} {y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k} \right) \left( \frac{G_k^{-1}\delta_k\delta_k^{\mathrm{T}}G_k^{-1}} {\frac{\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k}{y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k}} \right) \left( G_{k}-\frac{G_ky_ky_k^{\mathrm{T}}G_k} {y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k} \right) \\ \, A^{-1} \left( I-\frac{G_ky_ky_k^{\mathrm{T}}} {y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k} \right) \left( \frac{\delta_k\delta_k^{\mathrm{T}}} {\frac{\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k}{y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k}} \right) \left( I-\frac{y_ky_k^{\mathrm{T}}G_k} {y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k} \right) \\ \, A^{-1} \left( \frac{(\delta_k\delta_k^{\mathrm{T}})(y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k)} {\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k} \right) -\left( \frac{\delta_k\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}G_k}{\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k} \right) -\left( \frac{G_ky_ky_k^{\mathrm{T}}\delta_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k} \right) \left( \frac{G_ky_ky_k^{\mathrm{T}}\delta_k\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}G_k} {(\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k)(y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k)} \right) \\ \, G_{k}-\frac{G_ky_ky_k^{\mathrm{T}}G_k} {y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k} \\ \,\left( \frac{(\delta_k\delta_k^{\mathrm{T}})(y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k)} {\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k} \right) -\left( \frac{\delta_k\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}G_k}{\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k} \right) -\left( \frac{G_ky_ky_k^{\mathrm{T}}\delta_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k} \right) \left( \frac{G_ky_ky_k^{\mathrm{T}}G_k} {y_k^{\mathrm{T}}\delta_ky_k^{\mathrm{T}}G_ky_k} \right) \\ \, G_{k} \left( \frac{(\delta_k\delta_k^{\mathrm{T}})(y_k^{\mathrm{T}}\delta_k)} {\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k} \right) \left( \frac{(\delta_k\delta_k^{\mathrm{T}})(y_k^{\mathrm{T}}G_ky_k)} {\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k} \right) -\left( \frac{\delta_ky_k^{\mathrm{T}}G_k}{y_k^{\mathrm{T}}\delta_k} \right) -\left( \frac{G_ky_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k} \right) \\ \, G_{k} -\left( \frac{G_ky_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k} \right) -\left( \frac{\delta_ky_k^{\mathrm{T}}G_k}{y_k^{\mathrm{T}}\delta_k} \right) \left( \frac{\delta_k(y_k^{\mathrm{T}}G_ky_k)\delta_k^{\mathrm{T}}} {\delta_k^{\mathrm{T}}y_ky_k^{\mathrm{T}}\delta_k} \right) \left( \frac{\delta_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k} \right) \\ \, G_{k}\left( I- \frac{y_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k} \right) -\left( \frac{\delta_ky_k^{\mathrm{T}}G_k}{y_k^{\mathrm{T}}\delta_k} \right) \left( I-\frac{y_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k} \right) \left( \frac{\delta_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k} \right) \\ \, \left( I- \frac{\delta_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k}\right) G_k \left( I-\frac{y_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k} \right) \left( \frac{\delta_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k} \right) \\ \, \left( I- \frac{\delta_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k}\right) G_k \left( I- \frac{\delta_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k}\right)^\mathrm{T} \left( \frac{\delta_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k} \right) \\ \end{aligned} Gk1A−1δkTGk−1δk−δkTGk−1A−1Gk−1δkA−1Gk−1δkδkTGk−1A−1A−1δkTGk−1δk−δkTGk−1(Gk−ykTδkykTGkykGkykykTGk)Gk−1δkA−1Gk−1δkδkTGk−1A−1A−1ykTδkykTGkykδkTykykTδkA−1Gk−1δkδkTGk−1A−1A−1(Gk−ykTδkykTGkykGkykykTGk) ykTδkykTGkykδkTykykTδkGk−1δkδkTGk−1 (Gk−ykTδkykTGkykGkykykTGk)A−1(I−ykTδkykTGkykGkykykT) ykTδkykTGkykδkTykykTδkδkδkT (I−ykTδkykTGkykykykTGk)A−1(δkTykykTδk(δkδkT)(ykTδkykTGkyk))−(δkTykykTδkδkδkTykykTGk)−(δkTykykTδkGkykykTδkδkT)((δkTykykTδk)(ykTδkykTGkyk)GkykykTδkδkTykykTGk)Gk−ykTδkykTGkykGkykykTGk(δkTykykTδk(δkδkT)(ykTδkykTGkyk))−(δkTykykTδkδkδkTykykTGk)−(δkTykykTδkGkykykTδkδkT)(ykTδkykTGkykGkykykTGk)Gk(δkTykykTδk(δkδkT)(ykTδk))(δkTykykTδk(δkδkT)(ykTGkyk))−(ykTδkδkykTGk)−(δkTykGkykδkT)Gk−(δkTykGkykδkT)−(ykTδkδkykTGk)(δkTykykTδkδk(ykTGkyk)δkT)(δkTykδkδkT)Gk(I−δkTykykδkT)−(ykTδkδkykTGk)(I−δkTykykδkT)(δkTykδkδkT)(I−ykTδkδkykT)Gk(I−δkTykykδkT)(δkTykδkδkT)(I−ykTδkδkykT)Gk(I−ykTδkδkykT)T(δkTykδkδkT) 因此得到 BFGS 算法的 G k G_k Gk 的迭代公式 G k 1 BFGS ( I − δ k y k T y k T δ k ) G k BFGS ( I − δ k y k T y k T δ k ) T δ k δ k T δ k T y k G_{k1}^{\text{BFGS}} \left( I- \frac{\delta_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k}\right) G_k^{\text{BFGS}} \left( I- \frac{\delta_ky_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\delta_k}\right)^\mathrm{T} \frac{\delta_k\delta_k^{\mathrm{T}}}{\delta_k^{\mathrm{T}}y_k} Gk1BFGS(I−ykTδkδkykT)GkBFGS(I−ykTδkδkykT)TδkTykδkδkT 由 DFP 算法得到的 G k G_k Gk 记作 G k DFP G_k^{\text{DFP}} GkDFP 可知二者的线性组合也满足拟牛顿条件式而且是正定的 G k 1 α G k DFP ( 1 − α ) G k BFGS , 0 ≤ α ≤ 1 G_{k1}\alpha G_k^{\text{DFP}}(1-\alpha)G_k^{\text{BFGS}},\quad 0\leq\alpha\leq 1 Gk1αGkDFP(1−α)GkBFGS,0≤α≤1 这样就得到了一类拟牛顿算法称为 Broyden 类算法。
