最优化方法复习笔记(四)拟牛顿法与SR1,DFP,BFGS三种拟牛顿算法的推导与...
上一章传送门：已提供
经过一周的忙碌，我终于迎来了轻松的生活，可以尽情享受咸鱼般的悠闲时光。
拟牛顿法概述：在上一节中，我们讨论了牛顿法的局限性，特别是Hessian矩阵的计算和存储需求。为解决这一问题，拟牛顿法提出了一种近似Hessian矩阵的方法，仅使用迭代点的梯度信息进行迭代。
关键概念：我们通过近似求得迭代点处的Hessian矩阵近似值，记为\(B_k\)，目标是使其能较好地近似第\(k\)步的Hessian矩阵。这使得迭代形式为\(x_{k+1} = x_k - B_k^{-1}g_k\)，其中\(g_k\)表示梯度。
迭代过程：通过某种映射更新\(B_k\)，使得\(B_k\)能近似第\(k\)步的Hessian矩阵。此外，考虑到计算Hessian矩阵和其逆矩阵的困难，我们直接近似Hessian矩阵的逆矩阵，记为\(B_k\)。
拟牛顿法框架：在确定\(B_k\)的更新规则后，可大致写出拟牛顿法的算法流程。为避免复杂度，可以引入步长因子，形成阻尼拟牛顿法。
最速下降法解释：从另一个角度看问题，拟牛顿法本质上是寻找在某个特定方向上的最速下降路径。通过Taylor展开和约束条件，我们可以推导出拟牛顿法的迭代方向。
SR1算法：SR1（Symmetric Rank-One）算法是William C. Davidon于1956年提出的一种拟牛顿法。其迭代更新式为\(B_k = B_{k-1} + \frac{y_ky_k^T}{y_k^Ty_k} - \frac{B_{k-1}x_kx_k^T}{x_k^TB_{k-1}x_k}\)，其中\(y_k = g_k - B_{k-1}x_k\)。
DFP算法：DFP（Davidon-Fletcher-Powell）算法是第一个公认的拟牛顿法，其迭代更新式为\(B_k = (I - \alpha_ky_kx_k^T)B_{k-1}(I - \alpha_kx_ky_k^T) + \alpha_kx_kx_k^T\)，其中\(y_k = g_k - B_{k-1}x_k\)。
BFGS算法：BFGS算法在迭代更新式上与DFP类似，但通过逆矩阵的更新实现了更高效的操作，更新式为\(B_k = B_{k-1} + \frac{y_ky_k^T - B_{k-1}x_kx_k^TB_{k-1}}{x_k^TB_{k-1}x_k}\)。
SR1、DFP、BFGS之间的关系：通过求解特定优化问题，可以发现这三个算法在迭代更新式上存在对称性，且存在互为对偶的关系。
实现拟牛顿法（Python）：利用scipy.optimize子库实现SR1、DFP、BFGS算法，通过观察迭代点下降情况和可视化结果，验证算法的有效性。
总结：本文详细介绍了拟牛顿法的基本原理、具体算法（SR1、DFP、BFGS）以及代码实现，旨在提供一种高效求解优化问题的替代方法，适用于高维数据的优化场景。
继续阅读：最优化方法复习笔记(四)拟牛顿法与SR1,DFP,BFGS三种拟牛顿算法的推导与...经过一周的忙碌，我终于迎来了轻松的生活，可以尽情享受咸鱼般的悠闲时光。
拟牛顿法概述：在上一节中，我们讨论了牛顿法的局限性，特别是Hessian矩阵的计算和存储需求。为解决这一问题，拟牛顿法提出了一种近似Hessian矩阵的方法，仅使用迭代点的梯度信息进行迭代。
关键概念：我们通过近似求得迭代点处的Hessian矩阵近似值，记为\(B_k\)，目标是使其能较好地近似第\(k\)步的Hessian矩阵。这使得迭代形式为\(x_{k+1} = x_k - B_k^{-1}g_k\)，其中\(g_k\)表示梯度。
迭代过程：通过某种映射更新\(B_k\)，使得\(B_k\)能近似第\(k\)步的Hessian矩阵。此外，考虑到计算Hessian矩阵和其逆矩阵的困难，我们直接近似Hessian矩阵的逆矩阵，记为\(B_k\)。
拟牛顿法框架：在确定\(B_k\)的更新规则后，可大致写出拟牛顿法的算法流程。为避免复杂度，可以引入步长因子，形成阻尼拟牛顿法。
最速下降法解释：从另一个角度看问题，拟牛顿法本质上是寻找在某个特定方向上的最速下降路径。通过Taylor展开和约束条件，我们可以推导出拟牛顿法的迭代方向。
SR1算法：SR1（Symmetric Rank-One）算法是William C. Davidon于1956年提出的一种拟牛顿法。其迭代更新式为\(B_k = B_{k-1} + \frac{y_ky_k^T}{y_k^Ty_k} - \frac{B_{k-1}x_kx_k^T}{x_k^TB_{k-1}x_k}\)，其中\(y_k = g_k - B_{k-1}x_k\)。
DFP算法：DFP（Davidon-Fletcher-Powell）算法是第一个公认的拟牛顿法，其迭代更新式为\(B_k = (I - \alpha_ky_kx_k^T)B_{k-1}(I - \alpha_kx_ky_k^T) + \alpha_kx_kx_k^T\)，其中\(y_k = g_k - B_{k-1}x_k\)。
BFGS算法：BFGS算法在迭代更新式上与DFP类似，但通过逆矩阵的更新实现了更高效的操作，更新式为\(B_k = B_{k-1} + \frac{y_ky_k^T - B_{k-1}x_kx_k^TB_{k-1}}{x_k^TB_{k-1}x_k}\)。
SR1、DFP、BFGS之间的关系：通过求解特定优化问题，可以发现这三个算法在迭代更新式上存在对称性，且存在互为对偶的关系。
实现拟牛顿法（Python）：利用scipy.optimize子库实现SR1、DFP、BFGS算法，通过观察迭代点下降情况和可视化结果，验证算法的有效性。
总结：本文详细介绍了拟牛顿法的基本原理、具体算法（SR1、DFP、BFGS）以及代码实现，旨在提供一种高效求解优化问题的替代方法，适用于高维数据的优化场景。