非线性规划中的修正牛顿法（Modified Newton’s Method in Nonlinear Programming）
字数 3341 2025-12-15 00:15:41

非线性规划中的修正牛顿法（Modified Newton’s Method in Nonlinear Programming）

修正牛顿法是牛顿法（Newton’s Method）的一种改进变体，专门用于求解无约束非线性规划问题。针对牛顿法在实际应用中可能遇到的黑塞矩阵（Hessian Matrix）不正定、迭代点不收敛或收敛效率低等问题，修正牛顿法通过一系列技术调整，确保算法具有更好的鲁棒性和全局收敛性。下面我们分步深入讲解。

第一步：回顾牛顿法的基本思想与核心缺陷
牛顿法的目标是找到可微函数 \(f(x)\) 的极小值点。其基本思想是：在每一次迭代点 \(x_k\) 处，利用二阶泰勒展开来近似原函数：

\[f(x_k + d) \approx f(x_k) + \nabla f(x_k)^T d + \frac{1}{2} d^T \nabla^2 f(x_k) d \]

这里，\(\nabla f(x_k)\) 是梯度，\(\nabla^2 f(x_k)\) 是黑塞矩阵（Hessian Matrix）。通过最小化该二次模型，得到牛顿方向 \(d_k\) 满足：

\[\nabla^2 f(x_k) d_k = -\nabla f(x_k) \]

进而更新迭代点 \(x_{k+1} = x_k + d_k\)。

然而，牛顿法存在以下核心缺陷：

  1. 黑塞矩阵不正定：当 \(\nabla^2 f(x_k)\) 不是正定矩阵时，二次模型没有极小值，牛顿方向可能不是下降方向（即 \(\nabla f(x_k)^T d_k > 0\)），导致算法失效。
  2. 全局收敛性无法保证：即使黑塞矩阵正定，若初始点远离最优解，牛顿步长可能过大，导致迭代发散或陷入震荡。
  3. 计算成本高：每次迭代都需要计算黑塞矩阵及其逆（或求解线性系统），对于高维问题计算负担重。

正是这些缺陷催生了修正牛顿法，其核心任务是“修正”黑塞矩阵或牛顿方向，使之克服上述问题。

第二步：修正策略一：通过特征值修正保证矩阵正定性
最常见的修正是对黑塞矩阵进行特征值修正，确保修正后的矩阵正定且条件数良好。具体步骤如下：

  1. 计算黑塞矩阵 \(H_k = \nabla^2 f(x_k)\)。
  2. 对 \(H_k\) 进行特征值分解：\(H_k = Q \Lambda Q^T\)，其中 \(\Lambda = \text{diag}(\lambda_1, \dots, \lambda_n)\)。
  3. 设定一个小的正数 \(\delta > 0\)（例如 \(\delta = 10^{-6}\)），修正特征值：

\[ \tilde{\lambda}_i = \max(\lambda_i, \delta) \]

这保证了所有特征值都大于 \(\delta\)，从而 \(\tilde{H}_k = Q \tilde{\Lambda} Q^T\) 正定。
4. 用修正后的矩阵 \(\tilde{H}_k\) 替代原黑塞矩阵，求解修正牛顿方向：

\[ \tilde{H}_k d_k = -\nabla f(x_k) \]

此时，方向 \(d_k\) 必然是下降方向，因为 \(\nabla f(x_k)^T d_k = -\nabla f(x_k)^T \tilde{H}_k^{-1} \nabla f(x_k) < 0\)。

这种修正方法简单有效，但增加了特征值分解的计算量（\(O(n^3)\)），因此适合中低维问题。

第三步：修正策略二：信赖域框架下的截断牛顿步
另一种常见思路是将修正牛顿法与信赖域方法结合。在信赖域框架下，我们不仅考虑牛顿方向，还限制步长不超过一个信赖域半径 \(\Delta_k\)。子问题为：

\[\min_{d} \, m_k(d) = f(x_k) + \nabla f(x_k)^T d + \frac{1}{2} d^T B_k d \quad \text{s.t.} \ \|d\| \le \Delta_k \]

其中 \(B_k\) 可以是黑塞矩阵 \(\nabla^2 f(x_k)\) 或其近似（如拟牛顿法的BFGS矩阵）。即使 \(B_k\) 不正定，信赖域约束也能保证子问题有解。求解该子问题通常采用截断共轭梯度法（Steihaug-Toint方法）：

  • 在共轭梯度迭代中，若发现方向曲率 \(d^T B_k d \le 0\)（即矩阵不正定区域），则停止迭代，并沿当前方向走到信赖域边界。
  • 这样得到的步长自动满足下降性，且避免了直接分解不正定矩阵。

信赖域方法通过动态调整半径 \(\Delta_k\)（根据实际函数下降与模型预测下降的比值），能保证全局收敛性，特别适合非凸问题。

第四步：修正策略三：利用拟牛顿法避免黑塞矩阵计算
拟牛顿法（如BFGS、DFP）可以看作对牛顿法的另一种修正：它不直接计算黑塞矩阵，而是通过梯度信息迭代更新一个正定矩阵 \(B_k\) 来近似黑塞矩阵。其更新公式（以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} \]

其中 \(s_k = x_{k+1} - x_k\)，\(y_k = \nabla f(x_{k+1}) - \nabla f(x_k)\)。只要初始矩阵 \(B_0\) 正定且 \(y_k^T s_k > 0\)（通过线搜索保证），则 \(B_k\) 始终保持正定。因此，拟牛顿法天然避免了黑塞矩阵不正定的问题，同时减少了计算量。

第五步：修正策略四：结合线搜索保证全局收敛
纯牛顿法使用固定步长1，可能造成发散。修正牛顿法通常引入线搜索（如Armijo、Wolfe条件）来确定步长 \(\alpha_k\)，更新为：

\[x_{k+1} = x_k + \alpha_k d_k \]

其中 \(d_k\) 是修正后的牛顿方向。线搜索能确保每次迭代函数值充分下降，从而在较温和条件下实现全局收敛（即从任意初始点出发收敛到稳定点）。

第六步：算法流程与总结
综合以上策略，一个典型的修正牛顿法步骤如下：

  1. 初始化：选择初始点 \(x_0\)，设置参数 \(\epsilon > 0\)，\(k=0\)。
  2. 循环直至收敛（如 \(\|\nabla f(x_k)\| < \epsilon\)）：
    a. 计算梯度 \(g_k = \nabla f(x_k)\) 和黑塞矩阵 \(H_k = \nabla^2 f(x_k)\)（或拟牛顿近似 \(B_k\)）。
    b. 修正黑塞矩阵：若 \(H_k\) 不正定，进行特征值修正得到 \(\tilde{H}_k\)，或切换到信赖域子问题求解。
    c. 求解方向：解方程 \(\tilde{H}_k d_k = -g_k\)（或信赖域子问题）得到下降方向 \(d_k\)。
    d. 线搜索：沿 \(d_k\) 执行线搜索确定步长 \(\alpha_k\)。
    e. 更新：\(x_{k+1} = x_k + \alpha_k d_k\)，\(k = k+1\)。
  3. 输出：近似最优解 \(x_k\)。

修正牛顿法通过矩阵正定性修正、信赖域约束、拟牛顿近似和线搜索等技术，在保留牛顿法快速局部收敛（二阶收敛速率）优点的同时，增强了鲁棒性和全局收敛性。它特别适用于中小规模、光滑的非线性优化问题，是许多优化软件包（如MATLAB的fminunc）的核心算法之一。

非线性规划中的修正牛顿法（Modified Newton’s Method in Nonlinear Programming） 修正牛顿法是牛顿法（Newton’s Method）的一种改进变体，专门用于求解无约束非线性规划问题。针对牛顿法在实际应用中可能遇到的黑塞矩阵（Hessian Matrix）不正定、迭代点不收敛或收敛效率低等问题，修正牛顿法通过一系列技术调整，确保算法具有更好的鲁棒性和全局收敛性。下面我们分步深入讲解。 第一步：回顾牛顿法的基本思想与核心缺陷 牛顿法的目标是找到可微函数 \( f(x) \) 的极小值点。其基本思想是：在每一次迭代点 \( x_ k \) 处，利用二阶泰勒展开来近似原函数： \[ f(x_ k + d) \approx f(x_ k) + \nabla f(x_ k)^T d + \frac{1}{2} d^T \nabla^2 f(x_ k) d \] 这里，\( \nabla f(x_ k) \) 是梯度，\( \nabla^2 f(x_ k) \) 是黑塞矩阵（Hessian Matrix）。通过最小化该二次模型，得到牛顿方向 \( d_ k \) 满足： \[ \nabla^2 f(x_ k) d_ k = -\nabla f(x_ k) \] 进而更新迭代点 \( x_ {k+1} = x_ k + d_ k \)。 然而，牛顿法存在以下 核心缺陷 ： 黑塞矩阵不正定 ：当 \( \nabla^2 f(x_ k) \) 不是正定矩阵时，二次模型没有极小值，牛顿方向可能不是下降方向（即 \( \nabla f(x_ k)^T d_ k > 0 \)），导致算法失效。 全局收敛性无法保证 ：即使黑塞矩阵正定，若初始点远离最优解，牛顿步长可能过大，导致迭代发散或陷入震荡。 计算成本高 ：每次迭代都需要计算黑塞矩阵及其逆（或求解线性系统），对于高维问题计算负担重。 正是这些缺陷催生了 修正牛顿法 ，其核心任务是“修正”黑塞矩阵或牛顿方向，使之克服上述问题。 第二步：修正策略一：通过特征值修正保证矩阵正定性 最常见的修正是对黑塞矩阵进行 特征值修正 ，确保修正后的矩阵正定且条件数良好。具体步骤如下： 计算黑塞矩阵 \( H_ k = \nabla^2 f(x_ k) \)。 对 \( H_ k \) 进行特征值分解：\( H_ k = Q \Lambda Q^T \)，其中 \( \Lambda = \text{diag}(\lambda_ 1, \dots, \lambda_ n) \)。 设定一个小的正数 \( \delta > 0 \)（例如 \( \delta = 10^{-6} \)），修正特征值： \[ \tilde{\lambda}_ i = \max(\lambda_ i, \delta) \] 这保证了所有特征值都大于 \( \delta \)，从而 \( \tilde{H}_ k = Q \tilde{\Lambda} Q^T \) 正定。 用修正后的矩阵 \( \tilde{H}_ k \) 替代原黑塞矩阵，求解修正牛顿方向： \[ \tilde{H}_ k d_ k = -\nabla f(x_ k) \] 此时，方向 \( d_ k \) 必然是下降方向，因为 \( \nabla f(x_ k)^T d_ k = -\nabla f(x_ k)^T \tilde{H}_ k^{-1} \nabla f(x_ k) < 0 \)。 这种修正方法简单有效，但增加了特征值分解的计算量（\( O(n^3) \)），因此适合中低维问题。 第三步：修正策略二：信赖域框架下的截断牛顿步 另一种常见思路是将修正牛顿法与 信赖域方法 结合。在信赖域框架下，我们不仅考虑牛顿方向，还限制步长不超过一个信赖域半径 \( \Delta_ k \)。子问题为： \[ \min_ {d} \, m_ k(d) = f(x_ k) + \nabla f(x_ k)^T d + \frac{1}{2} d^T B_ k d \quad \text{s.t.} \ \|d\| \le \Delta_ k \] 其中 \( B_ k \) 可以是黑塞矩阵 \( \nabla^2 f(x_ k) \) 或其近似（如拟牛顿法的BFGS矩阵）。即使 \( B_ k \) 不正定，信赖域约束也能保证子问题有解。求解该子问题通常采用 截断共轭梯度法 （Steihaug-Toint方法）： 在共轭梯度迭代中，若发现方向曲率 \( d^T B_ k d \le 0 \)（即矩阵不正定区域），则停止迭代，并沿当前方向走到信赖域边界。 这样得到的步长自动满足下降性，且避免了直接分解不正定矩阵。 信赖域方法通过动态调整半径 \( \Delta_ k \)（根据实际函数下降与模型预测下降的比值），能保证全局收敛性，特别适合非凸问题。 第四步：修正策略三：利用拟牛顿法避免黑塞矩阵计算 拟牛顿法（如BFGS、DFP）可以看作对牛顿法的另一种修正：它不直接计算黑塞矩阵，而是通过梯度信息迭代更新一个正定矩阵 \( B_ k \) 来近似黑塞矩阵。其更新公式（以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} \] 其中 \( s_ k = x_ {k+1} - x_ k \)，\( y_ k = \nabla f(x_ {k+1}) - \nabla f(x_ k) \)。只要初始矩阵 \( B_ 0 \) 正定且 \( y_ k^T s_ k > 0 \)（通过线搜索保证），则 \( B_ k \) 始终保持正定。因此，拟牛顿法天然避免了黑塞矩阵不正定的问题，同时减少了计算量。 第五步：修正策略四：结合线搜索保证全局收敛 纯牛顿法使用固定步长1，可能造成发散。修正牛顿法通常引入 线搜索 （如Armijo、Wolfe条件）来确定步长 \( \alpha_ k \)，更新为： \[ x_ {k+1} = x_ k + \alpha_ k d_ k \] 其中 \( d_ k \) 是修正后的牛顿方向。线搜索能确保每次迭代函数值充分下降，从而在较温和条件下实现全局收敛（即从任意初始点出发收敛到稳定点）。 第六步：算法流程与总结 综合以上策略，一个典型的修正牛顿法步骤如下： 初始化 ：选择初始点 \( x_ 0 \)，设置参数 \( \epsilon > 0 \)，\( k=0 \)。 循环直至收敛 （如 \( \|\nabla f(x_ k)\| < \epsilon \)）： a. 计算梯度 \( g_ k = \nabla f(x_ k) \) 和黑塞矩阵 \( H_ k = \nabla^2 f(x_ k) \)（或拟牛顿近似 \( B_ k \)）。 b. 修正黑塞矩阵 ：若 \( H_ k \) 不正定，进行特征值修正得到 \( \tilde{H}_ k \)，或切换到信赖域子问题求解。 c. 求解方向 ：解方程 \( \tilde{H} k d_ k = -g_ k \)（或信赖域子问题）得到下降方向 \( d_ k \)。 d. 线搜索 ：沿 \( d_ k \) 执行线搜索确定步长 \( \alpha_ k \)。 e. 更新 ：\( x {k+1} = x_ k + \alpha_ k d_ k \)，\( k = k+1 \)。 输出 ：近似最优解 \( x_ k \)。 修正牛顿法通过 矩阵正定性修正 、 信赖域约束 、 拟牛顿近似 和 线搜索 等技术，在保留牛顿法快速局部收敛（二阶收敛速率）优点的同时，增强了鲁棒性和全局收敛性。它特别适用于中小规模、光滑的非线性优化问题，是许多优化软件包（如MATLAB的 fminunc ）的核心算法之一。