非线性规划中的信赖域方法（Trust Region Methods in Nonlinear Programming）
字数 3742 2025-12-10 16:28:27

非线性规划中的信赖域方法（Trust Region Methods in Nonlinear Programming）

信赖域方法是一类重要的数值优化算法，用于求解无约束或带约束的非线性规划问题。与线搜索方法（如最速下降法、牛顿法）在给定方向上决定步长不同，信赖域方法的核心思想是：在当前迭代点 \(\mathbf{x}_k\) 附近，用一个简单的近似模型（通常是二次模型）来近似原目标函数，并且我们只在这个被认为“可信赖”的有限区域内相信这个近似模型的精度。然后，在此信赖域内求解这个近似模型的子问题，得到候选步。通过比较候选步带来的目标函数实际下降量与模型预测下降量，来判定这一步是否被接受，并动态调整信赖域半径的大小。

下面我将循序渐进地讲解其核心原理和步骤。

第一步：构建局部近似模型
假设我们要最小化一个光滑函数 \(f: \mathbb{R}^n \to \mathbb{R}\)。在当前迭代点 \(\mathbf{x}_k\) 处，我们用一个二次模型 \(m_k\) 来近似 \(f\)：

\[m_k(\mathbf{s}) = f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^T \mathbf{s} + \frac{1}{2} \mathbf{s}^T \mathbf{B}_k \mathbf{s} \]

其中：

  • \(\mathbf{s} = \mathbf{x} - \mathbf{x}_k\) 是待求的步长向量。
  • \(\nabla f(\mathbf{x}_k)\) 是 \(f\) 在 \(\mathbf{x}_k\) 处的梯度。
  • \(\mathbf{B}_k\) 是 \(f\) 在 \(\mathbf{x}_k\) 处的Hessian矩阵 \(\nabla^2 f(\mathbf{x}_k)\) 或其近似（如拟牛顿法中的BFGS更新矩阵）。这个二次模型是目标函数在 \(\mathbf{x}_k\) 处的二阶泰勒展开的近似。

第二步：定义信赖域子问题
我们不信任这个模型在任意远处都精确，因此限定步长 \(\mathbf{s}\) 必须位于一个以当前点为中心、半径为 \(\Delta_k > 0\) 的信赖域内。这个区域通常是一个球（使用2-范数）：

\[\min_{\mathbf{s} \in \mathbb{R}^n} m_k(\mathbf{s}) = f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^T \mathbf{s} + \frac{1}{2} \mathbf{s}^T \mathbf{B}_k \mathbf{s} \]

\[ \text{满足约束：} \|\mathbf{s}\| \le \Delta_k \]

这里 \(\|\cdot\|\) 通常指2-范数（欧几里得范数）。这个子问题是一个带球约束的二次规划问题。即使 \(\mathbf{B}_k\) 不定（非正定），由于约束集是紧的，这个子问题总有全局最优解。

第三步：求解信赖域子问题
精确求解这个子问题计算量较大。实际上，信赖域方法通常采用高效的近似求解策略，最著名的是柯西点（Cauchy Point） 和狗腿法（Dogleg Method）。

  1. 柯西点：这是最速下降方向（负梯度方向）在信赖域约束下的最优步长点。它提供了目标函数值的保证下降，是理论分析的基础。
  2. 狗腿法：当 \(\mathbf{B}_k\) 正定时，最优无约束步是牛顿步 \(\mathbf{s}_k^N = -\mathbf{B}_k^{-1} \nabla f(\mathbf{x}_k)\)。狗腿路径由两段组成：从原点沿最速下降方向到梯度方向与模型极小值点方向的交点（柯西点所在的“拐点”），再沿此拐点到牛顿步的直线段。信赖域内的解就在这条折线上。通过判断信赖域半径与这条路径的交点，可以非常高效地得到近似解。

第四步：评估候选步与更新信赖域半径
计算候选步 \(\mathbf{s}_k\) 后，需要评估这个步长的质量。定义实际下降量（actual reduction）和预测下降量（predicted reduction）：

\[\text{实际下降：} \quad \text{ared}_k = f(\mathbf{x}_k) - f(\mathbf{x}_k + \mathbf{s}_k) \]

\[ \text{预测下降：} \quad \text{pred}_k = m_k(\mathbf{0}) - m_k(\mathbf{s}_k) = -[\nabla f(\mathbf{x}_k)^T \mathbf{s}_k + \frac{1}{2} \mathbf{s}_k^T \mathbf{B}_k \mathbf{s}_k] \]

然后计算它们的比值：

\[\rho_k = \frac{\text{ared}_k}{\text{pred}_k} \]

这个比值 \(\rho_k\) 是衡量模型 \(m_k\) 在步长 \(\mathbf{s}_k\) 上预测精度的关键指标。

第五步：根据比值 \(\rho_k\) 决定是否接受步长并调整半径
信赖域算法的迭代逻辑基于 \(\rho_k\)：

  • 接受步长：如果 \(\rho_k > \eta_1\)（例如 \(\eta_1 = 0.01\)，一个很小的正数），说明实际下降与预测下降匹配得尚可，我们接受这一步：\(\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_k\)。否则，拒绝这一步：\(\mathbf{x}_{k+1} = \mathbf{x}_k\)。
  • 调整半径：根据 \(\rho_k\) 更新信赖域半径 \(\Delta_{k+1}\)。
    1. 如果 \(\rho_k < \eta_1\)，说明模型在该半径下预测非常不准确，我们需要大幅缩小信赖域半径（例如 \(\Delta_{k+1} = \alpha_1 \Delta_k, \alpha_1 < 1\)），以便在更小的、模型更可信的区域内重新寻找合适的步长。
    2. 如果 \(\rho_k > \eta_2\)（例如 \(\eta_2 = 0.9\)）且步长 \(\mathbf{s}_k\) 达到了信赖域的边界（即 \(\|\mathbf{s}_k\| = \Delta_k\)），说明模型在当前区域内非常精确，我们可能过于保守，可以尝试扩大信赖域半径以允许更大的步长，加速收敛（例如 \(\Delta_{k+1} = \alpha_2 \Delta_k, \alpha_2 > 1\)）。
    3. 其他情况，保持半径不变或微调。

第六步：算法框架与收敛性
将以上步骤整合进一个迭代循环：

  1. 给定初始点 \(\mathbf{x}_0\)，初始信赖域半径 \(\Delta_0 > 0\)，常数 \(0 < \eta_1 < \eta_2 < 1\) 和 \(0 < \alpha_1 < 1 < \alpha_2\)。
  2. For \(k = 0, 1, 2, \dots\) until 收敛：
    a. 构建或更新模型 \(m_k(\mathbf{s})\)（计算梯度 \(\nabla f(\mathbf{x}_k)\) 和Hessian近似 \(\mathbf{B}_k\)）。
    b. 求解信赖域子问题，得到候选步 \(\mathbf{s}_k\)。
    c. 计算比值 \(\rho_k = \text{ared}_k / \text{pred}_k\)。
    d. 更新迭代点：如果 \(\rho_k > \eta_1\)，则 \(\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_k\)；否则 \(\mathbf{x}_{k+1} = \mathbf{x}_k\)。
    e. 更新信赖域半径 \(\Delta_{k+1}\) 根据上述第五步规则。
  3. 收敛判断：当梯度 \(\nabla f(\mathbf{x}_k)\) 的范数小于预设容差，或信赖域半径变得非常小，算法终止。

信赖域方法的强大之处在于其对模型曲率信息的鲁棒性。即使Hessian近似 \(\mathbf{B}_k\) 不是正定的，信赖域约束也能保证子问题有解，并且通过半径控制保证了全局收敛性（在适当条件下，算法能收敛到稳定点）。相比之下，牛顿法在Hessian非正定时可能失效，而线搜索方法在处理不定曲率时需要复杂的修正。因此，信赖域方法在处理非凸、曲率变化剧烈的问题时非常可靠，是现代优化软件包（如MATLAB的fminunc， SciPy的优化库）中非线性最小二乘和一般无约束优化的核心算法之一。

非线性规划中的信赖域方法（Trust Region Methods in Nonlinear Programming） 信赖域方法是一类重要的数值优化算法，用于求解无约束或带约束的非线性规划问题。与线搜索方法（如最速下降法、牛顿法）在给定方向上决定步长不同，信赖域方法的核心思想是：在当前迭代点 \(\mathbf{x}_ k\) 附近，用一个简单的近似模型（通常是二次模型）来近似原目标函数，并且我们只在这个被认为“可信赖”的有限区域内相信这个近似模型的精度。然后，在此信赖域内求解这个近似模型的子问题，得到候选步。通过比较候选步带来的目标函数实际下降量与模型预测下降量，来判定这一步是否被接受，并动态调整信赖域半径的大小。 下面我将循序渐进地讲解其核心原理和步骤。 第一步：构建局部近似模型 假设我们要最小化一个光滑函数 \(f: \mathbb{R}^n \to \mathbb{R}\)。在当前迭代点 \(\mathbf{x}_ k\) 处，我们用一个二次模型 \(m_ k\) 来近似 \(f\)： \[ m_ k(\mathbf{s}) = f(\mathbf{x}_ k) + \nabla f(\mathbf{x}_ k)^T \mathbf{s} + \frac{1}{2} \mathbf{s}^T \mathbf{B}_ k \mathbf{s} \] 其中： \(\mathbf{s} = \mathbf{x} - \mathbf{x}_ k\) 是待求的步长向量。 \(\nabla f(\mathbf{x}_ k)\) 是 \(f\) 在 \(\mathbf{x}_ k\) 处的梯度。 \(\mathbf{B}_ k\) 是 \(f\) 在 \(\mathbf{x}_ k\) 处的Hessian矩阵 \(\nabla^2 f(\mathbf{x}_ k)\) 或其近似（如拟牛顿法中的BFGS更新矩阵）。这个二次模型是目标函数在 \(\mathbf{x}_ k\) 处的二阶泰勒展开的近似。 第二步：定义信赖域子问题 我们不信任这个模型在任意远处都精确，因此限定步长 \(\mathbf{s}\) 必须位于一个以当前点为中心、半径为 \(\Delta_ k > 0\) 的信赖域内。这个区域通常是一个球（使用2-范数）： \[ \min_ {\mathbf{s} \in \mathbb{R}^n} m_ k(\mathbf{s}) = f(\mathbf{x}_ k) + \nabla f(\mathbf{x}_ k)^T \mathbf{s} + \frac{1}{2} \mathbf{s}^T \mathbf{B}_ k \mathbf{s} \] \[ \text{满足约束：} \|\mathbf{s}\| \le \Delta_ k \] 这里 \(\|\cdot\|\) 通常指2-范数（欧几里得范数）。这个子问题是一个带球约束的二次规划问题。即使 \(\mathbf{B}_ k\) 不定（非正定），由于约束集是紧的，这个子问题总有全局最优解。 第三步：求解信赖域子问题 精确求解这个子问题计算量较大。实际上，信赖域方法通常采用高效的近似求解策略，最著名的是 柯西点（Cauchy Point） 和 狗腿法（Dogleg Method） 。 柯西点 ：这是最速下降方向（负梯度方向）在信赖域约束下的最优步长点。它提供了目标函数值的保证下降，是理论分析的基础。 狗腿法 ：当 \(\mathbf{B}_ k\) 正定时，最优无约束步是牛顿步 \(\mathbf{s}_ k^N = -\mathbf{B}_ k^{-1} \nabla f(\mathbf{x}_ k)\)。狗腿路径由两段组成：从原点沿最速下降方向到梯度方向与模型极小值点方向的交点（柯西点所在的“拐点”），再沿此拐点到牛顿步的直线段。信赖域内的解就在这条折线上。通过判断信赖域半径与这条路径的交点，可以非常高效地得到近似解。 第四步：评估候选步与更新信赖域半径 计算候选步 \(\mathbf{s}_ k\) 后，需要评估这个步长的质量。定义实际下降量（actual reduction）和预测下降量（predicted reduction）： \[ \text{实际下降：} \quad \text{ared}_ k = f(\mathbf{x}_ k) - f(\mathbf{x}_ k + \mathbf{s}_ k) \] \[ \text{预测下降：} \quad \text{pred}_ k = m_ k(\mathbf{0}) - m_ k(\mathbf{s}_ k) = -[ \nabla f(\mathbf{x}_ k)^T \mathbf{s}_ k + \frac{1}{2} \mathbf{s}_ k^T \mathbf{B}_ k \mathbf{s}_ k ] \] 然后计算它们的比值： \[ \rho_ k = \frac{\text{ared}_ k}{\text{pred}_ k} \] 这个比值 \(\rho_ k\) 是衡量模型 \(m_ k\) 在步长 \(\mathbf{s}_ k\) 上预测精度的关键指标。 第五步：根据比值 \(\rho_ k\) 决定是否接受步长并调整半径 信赖域算法的迭代逻辑基于 \(\rho_ k\)： 接受步长 ：如果 \(\rho_ k > \eta_ 1\)（例如 \(\eta_ 1 = 0.01\)，一个很小的正数），说明实际下降与预测下降匹配得尚可，我们接受这一步：\(\mathbf{x}_ {k+1} = \mathbf{x}_ k + \mathbf{s} k\)。否则，拒绝这一步：\(\mathbf{x} {k+1} = \mathbf{x}_ k\)。 调整半径 ：根据 \(\rho_ k\) 更新信赖域半径 \(\Delta_ {k+1}\)。 如果 \(\rho_ k < \eta_ 1\)，说明模型在该半径下预测非常不准确，我们需要大幅缩小信赖域半径（例如 \(\Delta_ {k+1} = \alpha_ 1 \Delta_ k, \alpha_ 1 < 1\)），以便在更小的、模型更可信的区域内重新寻找合适的步长。 如果 \(\rho_ k > \eta_ 2\)（例如 \(\eta_ 2 = 0.9\)）且步长 \(\mathbf{s}_ k\) 达到了信赖域的边界（即 \(\|\mathbf{s} k\| = \Delta_ k\)），说明模型在当前区域内非常精确，我们可能过于保守，可以尝试扩大信赖域半径以允许更大的步长，加速收敛（例如 \(\Delta {k+1} = \alpha_ 2 \Delta_ k, \alpha_ 2 > 1\)）。 其他情况，保持半径不变或微调。 第六步：算法框架与收敛性 将以上步骤整合进一个迭代循环： 给定初始点 \(\mathbf{x}_ 0\)，初始信赖域半径 \(\Delta_ 0 > 0\)，常数 \(0 < \eta_ 1 < \eta_ 2 < 1\) 和 \(0 < \alpha_ 1 < 1 < \alpha_ 2\)。 For \(k = 0, 1, 2, \dots\) until 收敛： a. 构建或更新模型 \(m_ k(\mathbf{s})\)（计算梯度 \(\nabla f(\mathbf{x}_ k)\) 和Hessian近似 \(\mathbf{B}_ k\)）。 b. 求解信赖域子问题，得到候选步 \(\mathbf{s}_ k\)。 c. 计算比值 \(\rho_ k = \text{ared}_ k / \text{pred} k\)。 d. 更新迭代点 ：如果 \(\rho_ k > \eta_ 1\)，则 \(\mathbf{x} {k+1} = \mathbf{x}_ k + \mathbf{s} k\)；否则 \(\mathbf{x} {k+1} = \mathbf{x} k\)。 e. 更新信赖域半径 \(\Delta {k+1}\) 根据上述第五步规则。 收敛判断 ：当梯度 \(\nabla f(\mathbf{x}_ k)\) 的范数小于预设容差，或信赖域半径变得非常小，算法终止。 信赖域方法的强大之处在于其 对模型曲率信息的鲁棒性 。即使Hessian近似 \(\mathbf{B}_ k\) 不是正定的，信赖域约束也能保证子问题有解，并且通过半径控制保证了全局收敛性（在适当条件下，算法能收敛到稳定点）。相比之下，牛顿法在Hessian非正定时可能失效，而线搜索方法在处理不定曲率时需要复杂的修正。因此，信赖域方法在处理非凸、曲率变化剧烈的问题时非常可靠，是现代优化软件包（如MATLAB的 fminunc ， SciPy的优化库）中非线性最小二乘和一般无约束优化的核心算法之一。