非线性规划中的拟牛顿法（Quasi-Newton Methods in Nonlinear Programming）
字数 4122 2025-12-20 05:35:03

非线性规划中的拟牛顿法（Quasi-Newton Methods in Nonlinear Programming）

好的，我们开始学习非线性规划中的“拟牛顿法”。我会从最基础的概念开始，循序渐进地为你构建完整的知识体系。

步骤1：核心问题与牛顿法的困境

我们考虑一个无约束非线性优化问题：

\[ \min_{x \in \mathbb{R}^n} f(x) \]

其中，目标函数 \(f(x)\) 是二次连续可微的。

寻找最优解的关键是找到驻点，即满足一阶必要条件 \(\nabla f(x) = 0\) 的点。牛顿法是求解此方程的经典方法。其核心迭代公式为：

\[ x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k) \]

这里，\(\nabla^2 f(x_k)\) 是函数在 \(x_k\) 点的Hessian矩阵（二阶导数矩阵）。

牛顿法的优势与致命缺点：

  • 优势：如果初始点靠近最优解，且Hessian矩阵正定，牛顿法具有二次收敛速率，收敛速度极快。
  • 致命缺点：
  1. 计算负担：每次迭代都需要计算完整的n×n维Hessian矩阵及其逆矩阵，当变量维度n很大时，计算成本（\(O(n^3)\)）和存储成本（\(O(n^2)\)）极高。
    2. 可行性问题：计算出的Hessian矩阵可能不正定，导致搜索方向不是下降方向，算法可能失效。

拟牛顿法就是为了解决这些缺点而诞生的。

步骤2：拟牛顿法的基本思想

拟牛顿法的核心思想是：不使用精确的Hessian矩阵，而是用一个构造出来的、正定的矩阵 \(B_k\) 来近似它。 这个近似矩阵会随着迭代不断更新，变得越来越接近真实的Hessian矩阵。

为什么这个想法可行？

  1. 计算效率：构造和更新 \(B_k\) 的代价远低于计算精确的Hessian矩阵。
  2. 保证正定性：我们可以设计更新规则，确保 \(B_k\) 始终保持正定，从而保证产生的搜索方向 \(d_k = -B_k^{-1} \nabla f(x_k)\) 是下降方向。
  3. 超线性收敛：在适当的条件下，拟牛顿法能达到超线性收敛速率，虽然略慢于牛顿法的二次收敛，但比最速下降法的线性收敛快得多。

步骤3：拟牛顿条件（割线方程）

这是拟牛顿法的理论基础。如何构造一个好的近似矩阵 \(B_{k+1}\)？

考虑梯度函数 \(\nabla f(x)\) 在相邻两点 \(x_k\) 和 \(x_{k+1}\) 处的变化。根据中值定理，存在一点 \(\xi\) 使得：

\[ \nabla f(x_{k+1}) - \nabla f(x_k) \approx \nabla^2 f(\xi)(x_{k+1} - x_k) \]

这个关系提示我们，好的近似矩阵 \(B_{k+1}\) 应该满足：

\[ B_{k+1} (x_{k+1} - x_k) = \nabla f(x_{k+1}) - \nabla f(x_k) \]

这就是著名的拟牛顿条件或割线方程。

我们定义：

  • 位移向量 \(s_k = x_{k+1} - x_k\)
  • 梯度差向量 \(y_k = \nabla f(x_{k+1}) - \nabla f(x_k)\)

那么，拟牛顿条件可以简洁地写为：

\[ \boxed{ B_{k+1} s_k = y_k } \]

这个方程的含义是：用近似矩阵 \(B_{k+1}\) 乘以位移向量，应等于梯度的实际变化量。它是连接相邻两次迭代信息的关键桥梁。

有时，我们更愿意直接近似Hessian矩阵的逆 \(H_k = B_k^{-1}\)，这样搜索方向可以直接计算为 \(d_k = -H_k \nabla f(x_k)\)，省去了求解线性方程组的步骤。此时拟牛顿条件变为：

\[ \boxed{ H_{k+1} y_k = s_k } \]

步骤4：BFGS更新公式（最经典、最有效的公式）

有许多满足拟牛顿条件的更新公式，其中最著名、应用最广的是Broyden-Fletcher-Goldfarb-Shanno (BFGS) 公式。它被认为在数值稳定性、收敛速度和适用性方面综合表现最佳。

BFGS公式（直接更新Hessian近似矩阵 \(B_k\)）：
给定正定矩阵 \(B_k\)，位移 \(s_k\)，梯度差 \(y_k\)，且要求满足曲率条件 \(y_k^T s_k > 0\)（这在下凸函数中自然满足，或可通过线搜索保证）。BFGS更新公式为：

\[B_{k+1} = B_k - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} + \frac{y_k y_k^T}{y_k^T s_k} \]

这个公式通过秩-2修正（两个外积项）来更新 \(B_k\)，保证了如果 \(B_k\) 正定且 \(y_k^T s_k > 0\)，则 \(B_{k+1}\) 也正定。

BFGS公式（更新Hessian逆近似矩阵 \(H_k\)）：
更常用的形式是直接更新 \(H_k\)：

\[\boxed{ H_{k+1} = \left( I - \frac{s_k y_k^T}{y_k^T s_k} \right) H_k \left( I - \frac{y_k s_k^T}{y_k^T s_k} \right) + \frac{s_k s_k^T}{y_k^T s_k} } \]

这个公式就是拟牛顿法迭代中的核心计算步骤。更新 \(H_k\) 只需要几次矩阵向量乘法和外积运算，计算复杂度为 \(O(n^2)\)，远低于求逆的 \(O(n^3)\)。

步骤5：完整的拟牛顿法（BFGS）算法框架

结合上述思想，一个标准的（无约束）BFGS拟牛顿算法流程如下：

  1. 初始化：选择初始点 \(x_0\)，初始正定矩阵 \(H_0\)（通常取为单位矩阵 \(I\)），设定收敛容差 \(\epsilon > 0\)。令 \(k = 0\)。
  2. 检查终止：计算梯度 \(g_k = \nabla f(x_k)\)。如果 \(\| g_k \| \le \epsilon\)，则算法终止，\(x_k\) 作为近似最优解。
  3. 计算搜索方向：\(d_k = -H_k g_k\)。
  4. 执行线搜索：沿方向 \(d_k\) 进行（通常是满足Wolfe条件的）非精确线搜索，确定步长 \(\alpha_k > 0\)，使得函数值充分下降。这是一个关键步骤，它保证了 \(y_k^T s_k > 0\)。
  5. 更新迭代点：\(x_{k+1} = x_k + \alpha_k d_k\)。
  6. 计算位移与梯度差：\(s_k = x_{k+1} - x_k = \alpha_k d_k\)，\(y_k = \nabla f(x_{k+1}) - \nabla f(x_k)\)。
  7. 更新Hessian逆近似：使用BFGS公式计算 \(H_{k+1}\)。
  8. 循环：令 \(k = k+1\)，返回步骤2。

步骤6：收敛性分析与特性总结

  • 全局收敛性：对于凸函数，结合Wolfe线搜索，标准BFGS算法具有全局收敛性（即从任意初始点出发都能收敛到最优解）。
  • 收敛速率：在目标函数二阶连续可微且Hessian矩阵在解处正定的条件下，BFGS算法具有超线性收敛速率。即：

\[ \lim_{k \to \infty} \frac{\| x_{k+1} - x^* \|}{\| x_k - x^* \|} = 0 \]

这比最速下降法的线性收敛快，比牛顿法的二次收敛慢，但在实际中是非常理想的权衡。
  • 自校正特性：BFGS更新具有“记忆”梯度和位移历史信息的能力，能自动调整近似矩阵以适应目标函数的局部曲率。
  • 局限性：
  • 仍需要存储稠密的 \(n \times n\) 矩阵 \(H_k\)，对于超大规模问题（n极大）内存可能成为瓶颈。为此，发展出了有限内存BFGS (L-BFGS) 方法，它只保存最近m次的 \(s_k, y_k\) 向量对，来隐式地表示 \(H_k\)，将存储开销降至 \(O(mn)\)。
    • 对于高度非凸或病态问题，性能可能下降。

步骤7：L-BFGS算法简介（对大规模问题的扩展）

L-BFGS（Limited-memory BFGS）是解决BFGS内存问题的核心变种。

  • 思想：不显式存储和操作矩阵 \(H_k\)，而是存储最近 \(m\)（通常5到20）组向量对 \(\{s_i, y_i\}\)。当需要计算搜索方向 \(d_k = -H_k g_k\) 时，使用一个巧妙的双循环递归算法，仅利用这些向量对和初始矩阵 \(H_k^0\)（通常为标量矩阵）来递推计算出乘积 \(H_k g_k\)。
  • 优势：存储需求从 \(O(n^2)\) 降为 \(O(mn)\)，计算复杂度也维持在线性水平，使得它能处理变量数上万甚至百万级别的大规模优化问题。L-BFGS已成为当今大规模无约束/带简单约束优化问题的事实标准算法之一。

总而言之，拟牛顿法（特别是BFGS及其变种L-BFGS）通过巧妙地近似二阶信息，在收敛速度和计算成本之间取得了卓越的平衡，是非线性规划乃至机器学习等领域求解无约束优化问题的基石性算法。

非线性规划中的拟牛顿法（Quasi-Newton Methods in Nonlinear Programming） 好的，我们开始学习非线性规划中的“拟牛顿法”。我会从最基础的概念开始，循序渐进地为你构建完整的知识体系。 步骤1：核心问题与牛顿法的困境 我们考虑一个 无约束非线性优化问题 ： \[ \min_ {x \in \mathbb{R}^n} f(x) \] 其中，目标函数 \( f(x) \) 是 二次连续可微 的。 寻找最优解的关键是找到 驻点 ，即满足一阶必要条件 \( \nabla f(x) = 0 \) 的点。牛顿法是求解此方程的经典方法。其核心迭代公式为： \[ x_ {k+1} = x_ k - [ \nabla^2 f(x_ k)]^{-1} \nabla f(x_ k) \] 这里，\( \nabla^2 f(x_ k) \) 是函数在 \( x_ k \) 点的 Hessian矩阵 （二阶导数矩阵）。 牛顿法的优势与致命缺点： 优势 ：如果初始点靠近最优解，且Hessian矩阵正定，牛顿法具有 二次收敛速率 ，收敛速度极快。 致命缺点 ： 计算负担 ：每次迭代都需要计算 完整的n×n维Hessian矩阵 及其 逆矩阵 ，当变量维度n很大时，计算成本（\( O(n^3) \)）和存储成本（\( O(n^2) \)）极高。 可行性问题 ：计算出的Hessian矩阵可能 不正定 ，导致搜索方向不是下降方向，算法可能失效。 拟牛顿法就是为了解决这些缺点而诞生的。 步骤2：拟牛顿法的基本思想 拟牛顿法的核心思想是： 不使用精确的Hessian矩阵，而是用一个构造出来的、正定的矩阵 \( B_ k \) 来近似它。 这个近似矩阵会随着迭代不断更新，变得越来越接近真实的Hessian矩阵。 为什么这个想法可行？ 计算效率 ：构造和更新 \( B_ k \) 的代价远低于计算精确的Hessian矩阵。 保证正定性 ：我们可以设计更新规则，确保 \( B_ k \) 始终保持正定，从而保证产生的搜索方向 \( d_ k = -B_ k^{-1} \nabla f(x_ k) \) 是下降方向。 超线性收敛 ：在适当的条件下，拟牛顿法能达到 超线性收敛速率 ，虽然略慢于牛顿法的二次收敛，但比最速下降法的线性收敛快得多。 步骤3：拟牛顿条件（割线方程） 这是拟牛顿法的理论基础。如何构造一个好的近似矩阵 \( B_ {k+1} \)？ 考虑梯度函数 \( \nabla f(x) \) 在相邻两点 \( x_ k \) 和 \( x_ {k+1} \) 处的变化。根据中值定理，存在一点 \( \xi \) 使得： \[ \nabla f(x_ {k+1}) - \nabla f(x_ k) \approx \nabla^2 f(\xi)(x_ {k+1} - x_ k) \] 这个关系提示我们，好的近似矩阵 \( B_ {k+1} \) 应该满足： \[ B_ {k+1} (x_ {k+1} - x_ k) = \nabla f(x_ {k+1}) - \nabla f(x_ k) \] 这就是著名的 拟牛顿条件 或 割线方程 。 我们定义： 位移向量 \( s_ k = x_ {k+1} - x_ k \) 梯度差向量 \( y_ k = \nabla f(x_ {k+1}) - \nabla f(x_ k) \) 那么，拟牛顿条件可以简洁地写为： \[ \boxed{ B_ {k+1} s_ k = y_ k } \] 这个方程的含义是：用近似矩阵 \( B_ {k+1} \) 乘以位移向量，应等于梯度的实际变化量。它是连接相邻两次迭代信息的关键桥梁。 有时，我们更愿意直接近似Hessian矩阵的 逆 \( H_ k = B_ k^{-1} \)，这样搜索方向可以直接计算为 \( d_ k = -H_ k \nabla f(x_ k) \)，省去了求解线性方程组的步骤。此时拟牛顿条件变为： \[ \boxed{ H_ {k+1} y_ k = s_ k } \] 步骤4：BFGS更新公式（最经典、最有效的公式） 有许多满足拟牛顿条件的更新公式，其中最著名、应用最广的是 Broyden-Fletcher-Goldfarb-Shanno (BFGS) 公式。它被认为在数值稳定性、收敛速度和适用性方面综合表现最佳。 BFGS公式（直接更新Hessian近似矩阵 \( B_ k \)）： 给定正定矩阵 \( B_ k \)，位移 \( s_ k \)，梯度差 \( y_ k \)，且要求满足 曲率条件 \( y_ k^T s_ k > 0 \)（这在下凸函数中自然满足，或可通过线搜索保证）。BFGS更新公式为： \[ B_ {k+1} = B_ k - \frac{B_ k s_ k s_ k^T B_ k}{s_ k^T B_ k s_ k} + \frac{y_ k y_ k^T}{y_ k^T s_ k} \] 这个公式通过秩-2修正（两个外积项）来更新 \( B_ k \)，保证了如果 \( B_ k \) 正定且 \( y_ k^T s_ k > 0 \)，则 \( B_ {k+1} \) 也正定。 BFGS公式（更新Hessian逆近似矩阵 \( H_ k \)）： 更常用的形式是直接更新 \( H_ k \)： \[ \boxed{ H_ {k+1} = \left( I - \frac{s_ k y_ k^T}{y_ k^T s_ k} \right) H_ k \left( I - \frac{y_ k s_ k^T}{y_ k^T s_ k} \right) + \frac{s_ k s_ k^T}{y_ k^T s_ k} } \] 这个公式就是拟牛顿法迭代中的核心计算步骤。更新 \( H_ k \) 只需要几次矩阵向量乘法和外积运算，计算复杂度为 \( O(n^2) \)，远低于求逆的 \( O(n^3) \)。 步骤5：完整的拟牛顿法（BFGS）算法框架 结合上述思想，一个标准的（无约束）BFGS拟牛顿算法流程如下： 初始化 ：选择初始点 \( x_ 0 \)，初始正定矩阵 \( H_ 0 \)（通常取为单位矩阵 \( I \)），设定收敛容差 \( \epsilon > 0 \)。令 \( k = 0 \)。 检查终止 ：计算梯度 \( g_ k = \nabla f(x_ k) \)。如果 \( \| g_ k \| \le \epsilon \)，则算法终止，\( x_ k \) 作为近似最优解。 计算搜索方向 ：\( d_ k = -H_ k g_ k \)。 执行线搜索 ：沿方向 \( d_ k \) 进行（通常是满足Wolfe条件的） 非精确线搜索 ，确定步长 \( \alpha_ k > 0 \)，使得函数值充分下降。这是一个关键步骤，它保证了 \( y_ k^T s_ k > 0 \)。 更新迭代点 ：\( x_ {k+1} = x_ k + \alpha_ k d_ k \)。 计算位移与梯度差 ：\( s_ k = x_ {k+1} - x_ k = \alpha_ k d_ k \)，\( y_ k = \nabla f(x_ {k+1}) - \nabla f(x_ k) \)。 更新Hessian逆近似 ：使用BFGS公式计算 \( H_ {k+1} \)。 循环 ：令 \( k = k+1 \)，返回步骤2。 步骤6：收敛性分析与特性总结 全局收敛性 ：对于凸函数，结合Wolfe线搜索，标准BFGS算法具有 全局收敛性 （即从任意初始点出发都能收敛到最优解）。 收敛速率 ：在目标函数二阶连续可微且Hessian矩阵在解处正定的条件下，BFGS算法具有 超线性收敛速率 。即： \[ \lim_ {k \to \infty} \frac{\| x_ {k+1} - x^* \|}{\| x_ k - x^* \|} = 0 \] 这比最速下降法的线性收敛快，比牛顿法的二次收敛慢，但在实际中是非常理想的权衡。 自校正特性 ：BFGS更新具有“记忆”梯度和位移历史信息的能力，能自动调整近似矩阵以适应目标函数的局部曲率。 局限性 ： 仍需要存储稠密的 \( n \times n \) 矩阵 \( H_ k \)，对于 超大规模问题 （n极大）内存可能成为瓶颈。为此，发展出了 有限内存BFGS (L-BFGS) 方法，它只保存最近m次的 \( s_ k, y_ k \) 向量对，来隐式地表示 \( H_ k \)，将存储开销降至 \( O(mn) \)。 对于高度非凸或病态问题，性能可能下降。 步骤7：L-BFGS算法简介（对大规模问题的扩展） L-BFGS（Limited-memory BFGS）是解决BFGS内存问题的核心变种。 思想 ：不显式存储和操作矩阵 \( H_ k \)，而是存储最近 \( m \)（通常5到20）组向量对 \( \{s_ i, y_ i\} \)。当需要计算搜索方向 \( d_ k = -H_ k g_ k \) 时，使用一个巧妙的 双循环递归算法 ，仅利用这些向量对和初始矩阵 \( H_ k^0 \)（通常为标量矩阵）来递推计算出乘积 \( H_ k g_ k \)。 优势 ：存储需求从 \( O(n^2) \) 降为 \( O(mn) \)，计算复杂度也维持在线性水平，使得它能处理变量数上万甚至百万级别的大规模优化问题。L-BFGS已成为当今大规模无约束/带简单约束优化问题的 事实标准算法 之一。 总而言之，拟牛顿法（特别是BFGS及其变种L-BFGS）通过巧妙地近似二阶信息，在 收敛速度 和 计算成本 之间取得了卓越的平衡，是非线性规划乃至机器学习等领域求解无约束优化问题的基石性算法。