61-理论方法-拟牛顿法

知识点：拟牛顿法

知识点概述

拟牛顿法是一类介于梯度下降和牛顿法之间的方法。它通过迭代地近似海瑟矩阵的逆矩阵，来模拟牛顿法的快速收敛特性，同时又避免了直接计算、存储和求逆海瑟矩阵的高昂成本，在实践中应用非常广泛。

详细解释

• 动机: 牛顿法收敛快但成本高，梯度法成本低但收敛慢。拟牛顿法旨在取得二者的平衡。
• 核心思想:
  1. 用一个矩阵 $B_k$ 来近似海瑟矩阵 $abl{a}^{2}f(x_k)$，或用 $H_k$ 来近似其逆矩阵 $[abl{a}^{2}f(x_k){]}^{-1}$。
  2. 这个近似矩阵 $B_k$ (或 $H_k$) 必须满足割线方程 (Secant Equation): $B_{k+1}{s}_k=y_k$ (或 $H_{k+1}{y}_k=s_k$)，其中 $s_k=x_{k+1}-x_k$, $y_k=ablaf(x_{k+1})-ablaf(x_k)$。这个方程保证了近似矩阵在最新迭代方向上的行为与真实海瑟矩阵一致。
  3. 通过一个低秩矩阵对当前近似矩阵进行更新，得到新的近似矩阵：$B_{k+1}=B_k+\text{update}$。
• 著名算法:
  • BFGS (Broyden-Fletcher-Goldfarb-Shanno): 最流行的拟牛顿算法之一。它直接更新海瑟矩阵的逆 $H_k$，更新公式保证了 $H_{k+1}$ 的对称正定性。
  • L-BFGS (Limited-memory BFGS): BFGS的低内存消耗版本。它不存储完整的近似矩阵 $H_k$，而是只存储最近的 $m$ 组向量 $(s_i,y_i)$ 来隐式地计算更新方向。这使得它能应用于高维问题（如深度学习）。
• 收敛速度: 对于凸问题，通常具有Q-超线性收敛速度。

学习要点

• 理解拟牛顿法的定位：在计算成本和收敛速度之间取得平衡。
• 掌握割线方程是拟牛顿法的核心。
• 了解BFGS是最经典的拟牛顿算法，L-BFGS是其适用于大规模问题的变体。

实践应用

• 是求解中等规模无约束优化问题的默认首选方法。
• L-BFGS在机器学习中被广泛使用，例如用于训练逻辑回归、SVM等模型。

关联知识点

• 前置知识: 60-理论方法-牛顿法, 57-理论方法-梯度下降法
• 后续知识: 58-理论方法-Barzilar-Borwein方法
• 相关知识: 无