信赖域方法
字数 3291 2025-10-29 11:32:30

信赖域方法

信赖域方法是求解非线性优化问题的一类重要数值算法。其核心思想是：在每次迭代中，在一个给定的局部“信赖域”内，构建一个简单的模型（通常是二次模型）来近似复杂的目标函数，并通过求解该简单模型的子问题来确定迭代步长。

第一步：基本思想与动机

考虑无约束非线性优化问题：

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

其中 \(f(x)\) 是一个光滑但可能非常复杂的函数（例如非凸、高阶非线性）。

许多优化算法（如最速下降法、牛顿法）可以理解为：在当前迭代点 \(x_k\) 处，我们用一个简单的模型函数 \(m_k(p)\) 来近似目标函数在位移 \(p\) 处的值 \(f(x_k + p)\)。这个模型通常是基于泰勒展开的：

  • 线性模型（一阶）：\(m_k(p) = f(x_k) + \nabla f(x_k)^T p\)
  • 二次模型（二阶）：\(m_k(p) = f(x_k) + \nabla f(x_k)^T p + \frac{1}{2} p^T B_k p\)
    其中 \(B_k\) 是Hessian矩阵 \(\nabla^2 f(x_k)\) 或其某个近似。

关键问题是：我们能在多大范围内信赖这个模型？如果模型在离 \(x_k\) 很远的地方与真实函数差异巨大，那么根据模型找到的“最优”位移 \(p\) 可能实际上会使真实函数值 \(f(x_k + p)\) 变得很差。

信赖域方法的核心策略是：明确地定义一个区域，在这个区域内我们相信模型 \(m_k(p)\) 是原始函数 \(f(x)\) 的一个合理近似。 这个区域就是“信赖域”，通常定义为一个球体：

\[ \Omega_k = \{ p \in \mathbb{R}^n : \| p \| \le \Delta_k \} \]

其中 \(\Delta_k > 0\) 称为信赖域半径。算法在每次迭代中，都在这个半径为 \(\Delta_k\) 的球内寻找能使模型 \(m_k(p)\) 最小的位移 \(p_k\)。

第二步：算法框架与关键步骤

一个标准的信赖域方法的迭代过程如下：

  1. 初始化：给定初始点 \(x_0\)，初始信赖域半径 \(\Delta_0 > 0\)，以及常数 \(\eta \in [0, \frac{1}{4})\)（用于判断接受迭代步的阈值），\(\gamma_1 \in (0, 1)\)，\(\gamma_2 > 1\)（用于调整半径的因子）。

  2. 对于 k = 0, 1, 2, ... 直到收敛：
    a. 模型构建：在当前点 \(x_k\) 处，构建局部模型 \(m_k(p)\)。最常用的是二次模型，其中 \(B_k\) 可以是精确的Hessian、拟牛顿法得到的近似Hessian（如BFGS公式），或者当Hessian计算成本高时，甚至可以是简单的单位矩阵缩放（此时退化为最速下降法的思想）。
    b. 子问题求解：在信赖域 \(\| p \| \le \Delta_k\) 内求解子问题，寻找试探步 \(p_k\)：

\[ p_k = \arg \min_{\| p \| \le \Delta_k} m_k(p) \]

    这个子问题是一个带球约束的（可能是非凸的）二次规划问题。其精确求解有专门方法（如柯西点、狗腿法、Steihaug-Toint共轭梯度法），目标是高效地找到一个足够好的近似解。

c. 实际下降量与预测下降量：计算试探点 \(x_k + p_k\) 处的真实函数值。定义两个关键量：

  • 实际下降量 (Actual Reduction)：\(\text{ared}_k = f(x_k) - f(x_k + p_k)\)。这是目标函数真实的改进量。
  • 预测下降量 (Predicted Reduction)：\(\text{pred}_k = m_k(0) - m_k(p_k) = f(x_k) - m_k(p_k)\)。这是模型所预测的函数改进量。
    d. 比率计算与步长接受：计算比率 \(\rho_k\)：

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

这个比率衡量了模型 \(m_k\) 在当前迭代中的预测准确度。

  • 如果 \(\rho_k > \eta\)（例如 \(\eta = 0.1\) 或 0.25），说明模型预测是相当可靠的，真实下降接近或优于预测下降。接受该步：令 \(x_{k+1} = x_k + p_k\)。
  • 否则，说明模型在半径为 \(\Delta_k\) 的区域内并不可靠，真实下降远小于预测下降。拒绝该步：令 \(x_{k+1} = x_k\)（保持原地不动）。
    e. 信赖域半径更新：根据比率 \(\rho_k\) 调整下一次迭代的信赖域半径 \(\Delta_{k+1}\)。
  • 如果 \(\rho_k\) 非常小（例如 \(\rho_k < 0.25\)），说明模型在当前区域内不可信。收缩信赖域：\(\Delta_{k+1} = \gamma_1 \Delta_k\)（例如 \(\gamma_1 = 0.25\)），以便在下一次迭代中构建一个更局部的、更可靠的模型。
  • 如果 \(\rho_k\) 很大（例如 \(\rho_k > 0.75\)），并且试探步 \(p_k\) 已经“碰”到了信赖域的边界（即 \(\| p_k \| = \Delta_k\)），说明模型非常可靠，我们可能过于保守了。扩张信赖域：\(\Delta_{k+1} = \gamma_2 \Delta_k\)（例如 \(\gamma_2 = 2\)），允许下一次迭代探索更大的范围，可能获得更快的进展。
  • 其他情况，保持半径不变：\(\Delta_{k+1} = \Delta_k\)。

第三步：深入理解与特性

  1. 与线搜索方法的对比：线搜索方法（如最速下降法、牛顿法）是先确定一个搜索方向（如负梯度方向），然后沿着这个方向寻找一个合适的步长，使函数值充分下降。而信赖域方法是先确定一个步长的最大可能范围（信赖域半径），然后在这个范围内同时确定方向和步长。这使得它在处理病态问题（如Hessian矩阵病态或非正定）时通常更稳定。

  2. 子问题的求解：精确求解带约束的二次子问题可能计算量很大。实践中广泛使用截断共轭梯度法（如Steihaug-Toint方法）。该方法在共轭梯度迭代过程中，如果迭代点到达了信赖域边界，或者遇到了负曲率方向（当 \(B_k\) 非正定时），就提前终止。这提供了一个高效且数值稳定的近似解。

  3. 全局收敛性：信赖域方法一个非常重要的优点是，在相对温和的条件下（如函数 \(f\) 有下界且 Lipschitz 连续），算法能保证全局收敛，即 \(\lim_{k \to \infty} \nabla f(x_k) = 0\)，收敛到一个稳定点（一阶临界点）。这种稳健性使其非常受欢迎。

  4. 处理约束：信赖域方法的思想可以自然推广到约束优化问题。此时，信赖域子问题会变得更加复杂，可能包含线性或非线性约束，但核心思想不变：在一個局部可信的区域内，用简化模型逼近原问题。

总结来说，信赖域方法通过动态调整一个局部区域的大小，并在该区域内求解一个简化的子问题，巧妙地平衡了“利用模型快速收敛”和“保证算法全局稳健”这两个目标，是解决中大规模非线性优化问题的一类强大而可靠的算法。

信赖域方法 信赖域方法是求解非线性优化问题的一类重要数值算法。其核心思想是：在每次迭代中，在一个给定的局部“信赖域”内，构建一个简单的模型（通常是二次模型）来近似复杂的目标函数，并通过求解该简单模型的子问题来确定迭代步长。 第一步：基本思想与动机 考虑无约束非线性优化问题： \[ \min_ {x \in \mathbb{R}^n} f(x) \] 其中 \( f(x) \) 是一个光滑但可能非常复杂的函数（例如非凸、高阶非线性）。 许多优化算法（如最速下降法、牛顿法）可以理解为：在当前迭代点 \( x_ k \) 处，我们用一个简单的模型函数 \( m_ k(p) \) 来近似目标函数在位移 \( p \) 处的值 \( f(x_ k + p) \)。这个模型通常是基于泰勒展开的： 线性模型（一阶） ：\( m_ k(p) = f(x_ k) + \nabla f(x_ k)^T p \) 二次模型（二阶） ：\( m_ k(p) = f(x_ k) + \nabla f(x_ k)^T p + \frac{1}{2} p^T B_ k p \) 其中 \( B_ k \) 是Hessian矩阵 \( \nabla^2 f(x_ k) \) 或其某个近似。 关键问题是：我们能在多大范围内信赖这个模型？如果模型在离 \( x_ k \) 很远的地方与真实函数差异巨大，那么根据模型找到的“最优”位移 \( p \) 可能实际上会使真实函数值 \( f(x_ k + p) \) 变得很差。 信赖域方法的核心策略是： 明确地定义一个区域，在这个区域内我们相信模型 \( m_ k(p) \) 是原始函数 \( f(x) \) 的一个合理近似。 这个区域就是“信赖域”，通常定义为一个球体： \[ \Omega_ k = \{ p \in \mathbb{R}^n : \| p \| \le \Delta_ k \} \] 其中 \( \Delta_ k > 0 \) 称为信赖域半径。算法在每次迭代中，都在这个半径为 \( \Delta_ k \) 的球内寻找能使模型 \( m_ k(p) \) 最小的位移 \( p_ k \)。 第二步：算法框架与关键步骤 一个标准的信赖域方法的迭代过程如下： 初始化 ：给定初始点 \( x_ 0 \)，初始信赖域半径 \( \Delta_ 0 > 0 \)，以及常数 \( \eta \in [ 0, \frac{1}{4}) \)（用于判断接受迭代步的阈值），\( \gamma_ 1 \in (0, 1) \)，\( \gamma_ 2 > 1 \)（用于调整半径的因子）。 对于 k = 0, 1, 2, ... 直到收敛 ： a. 模型构建 ：在当前点 \( x_ k \) 处，构建局部模型 \( m_ k(p) \)。最常用的是二次模型，其中 \( B_ k \) 可以是精确的Hessian、拟牛顿法得到的近似Hessian（如BFGS公式），或者当Hessian计算成本高时，甚至可以是简单的单位矩阵缩放（此时退化为最速下降法的思想）。 b. 子问题求解 ：在信赖域 \( \| p \| \le \Delta_ k \) 内求解子问题，寻找试探步 \( p_ k \)： \[ p_ k = \arg \min_ {\| p \| \le \Delta_ k} m_ k(p) \] 这个子问题是一个带球约束的（可能是非凸的）二次规划问题。其精确求解有专门方法（如柯西点、狗腿法、Steihaug-Toint共轭梯度法），目标是高效地找到一个足够好的近似解。 c. 实际下降量与预测下降量 ：计算试探点 \( x_ k + p_ k \) 处的真实函数值。定义两个关键量： - 实际下降量 (Actual Reduction) ：\( \text{ared} k = f(x_ k) - f(x_ k + p_ k) \)。这是目标函数真实的改进量。 - 预测下降量 (Predicted Reduction) ：\( \text{pred} k = m_ k(0) - m_ k(p_ k) = f(x_ k) - m_ k(p_ k) \)。这是模型所预测的函数改进量。 d. 比率计算与步长接受 ：计算比率 \( \rho_ k \)： \[ \rho_ k = \frac{\text{ared} k}{\text{pred} k} \] 这个比率衡量了模型 \( m_ k \) 在当前迭代中的预测准确度。 - 如果 \( \rho_ k > \eta \)（例如 \( \eta = 0.1 \) 或 0.25），说明模型预测是相当可靠的，真实下降接近或优于预测下降。 接受该步 ：令 \( x {k+1} = x_ k + p_ k \)。 - 否则，说明模型在半径为 \( \Delta_ k \) 的区域内并不可靠，真实下降远小于预测下降。 拒绝该步 ：令 \( x {k+1} = x_ k \)（保持原地不动）。 e. 信赖域半径更新 ：根据比率 \( \rho_ k \) 调整下一次迭代的信赖域半径 \( \Delta {k+1} \)。 - 如果 \( \rho_ k \) 非常小（例如 \( \rho_ k < 0.25 \)），说明模型在当前区域内不可信。 收缩信赖域 ：\( \Delta {k+1} = \gamma_ 1 \Delta_ k \)（例如 \( \gamma_ 1 = 0.25 \)），以便在下一次迭代中构建一个更局部的、更可靠的模型。 - 如果 \( \rho_ k \) 很大（例如 \( \rho_ k > 0.75 \)），并且试探步 \( p_ k \) 已经“碰”到了信赖域的边界（即 \( \| p_ k \| = \Delta_ k \)），说明模型非常可靠，我们可能过于保守了。 扩张信赖域 ：\( \Delta_ {k+1} = \gamma_ 2 \Delta_ k \)（例如 \( \gamma_ 2 = 2 \)），允许下一次迭代探索更大的范围，可能获得更快的进展。 - 其他情况， 保持半径不变 ：\( \Delta_ {k+1} = \Delta_ k \)。 第三步：深入理解与特性 与线搜索方法的对比 ：线搜索方法（如最速下降法、牛顿法）是先确定一个搜索方向（如负梯度方向），然后沿着这个方向寻找一个合适的步长，使函数值充分下降。而信赖域方法是先确定一个步长的最大可能范围（信赖域半径），然后在这个范围内同时确定方向和步长。这使得它在处理病态问题（如Hessian矩阵病态或非正定）时通常更稳定。 子问题的求解 ：精确求解带约束的二次子问题可能计算量很大。实践中广泛使用 截断共轭梯度法 （如Steihaug-Toint方法）。该方法在共轭梯度迭代过程中，如果迭代点到达了信赖域边界，或者遇到了负曲率方向（当 \( B_ k \) 非正定时），就提前终止。这提供了一个高效且数值稳定的近似解。 全局收敛性 ：信赖域方法一个非常重要的优点是，在相对温和的条件下（如函数 \( f \) 有下界且 Lipschitz 连续），算法能保证全局收敛，即 \( \lim_ {k \to \infty} \nabla f(x_ k) = 0 \)，收敛到一个稳定点（一阶临界点）。这种稳健性使其非常受欢迎。 处理约束 ：信赖域方法的思想可以自然推广到约束优化问题。此时，信赖域子问题会变得更加复杂，可能包含线性或非线性约束，但核心思想不变：在一個局部可信的区域内，用简化模型逼近原问题。 总结来说，信赖域方法通过动态调整一个局部区域的大小，并在该区域内求解一个简化的子问题，巧妙地平衡了“利用模型快速收敛”和“保证算法全局稳健”这两个目标，是解决中大规模非线性优化问题的一类强大而可靠的算法。