信赖域方法的子问题求解算法 (Trust Region Subproblem Solving Algorithms)
字数 3714 2025-12-21 22:06:27

好的，我注意到您已列出了详尽的已讲词条。我将为您讲解一个尚未出现的、在优化理论和算法设计中具有基础性地位的词条。

信赖域方法的子问题求解算法 (Trust Region Subproblem Solving Algorithms)

我将为您循序渐进地讲解这个概念。

第一步：理解“信赖域方法”的总体框架

  • 核心思想：在每一次迭代中，我们都在当前迭代点 \(x_k\) 附近，用一个简单的“模型函数” \(m_k(p)\) 来近似复杂的目标函数 \(f(x)\)。这个近似只在以 \(x_k\) 为中心、半径为 \(\Delta_k\) 的一个“球”（信赖域）内被认为是可靠的。
  • 迭代步骤：
  1. 构建模型：在当前点 \(x_k\)，构建一个简单的局部模型 \(m_k(p)\)，通常是一个二次模型：\(m_k(p) = f(x_k) + \nabla f(x_k)^T p + \frac{1}{2} p^T B_k p\)。其中 \(p\) 是待求的移动步长，\(B_k\) 是 Hessian 矩阵或其近似（如拟牛顿法的 BFGS 矩阵）。
  2. 求解子问题：在信赖域 \(\|p\| \le \Delta_k\) 内，求解模型的最优步长 \(p_k\)： \(\min_{p \in \mathbb{R}^n} m_k(p) \quad \text{s.t.} \quad \|p\| \le \Delta_k\)。
  3. 评估与更新：计算实际下降 \(f(x_k) - f(x_k + p_k)\) 与模型预测下降 \(m_k(0) - m_k(p_k)\) 的比值 \(\rho_k\)。
  • 如果 \(\rho_k\) 接近1，说明模型近似得很好，接受这一步，并可能扩大信赖域半径 \(\Delta_{k+1} > \Delta_k\)。
  • 如果 \(\rho_k\) 很小甚至为负，说明模型近似得很差，拒绝这一步（ \(x_{k+1} = x_k\) ），并缩小信赖域半径 \(\Delta_{k+1} < \Delta_k\) 以获取更精确的模型。
    4. 迭代：重复以上步骤，直到满足收敛条件。

第二步：聚焦核心——信赖域子问题 (Trust Region Subproblem, TRS)

  • 标准形式：在第二步中，我们需要精确求解的子优化问题，通常写作：

\[ \min_{p \in \mathbb{R}^n} \quad g^T p + \frac{1}{2} p^T B p \quad \text{s.t.} \quad \|p\| \le \Delta \]

这里为了简洁，省略了下标 \(k\)，其中 \(g = \nabla f(x_k)\), \(B = B_k\)，信赖域约束 \(\|p\|\) 通常是2-范数（欧几里得范数）。

  • 问题特性：这是一个具有球形约束的（可能非凸）二次优化问题。其挑战在于：
  1. 非凸性：矩阵 \(B\) 可能不定（即存在负特征值），导致目标函数非凸。传统的无约束优化方法（如牛顿法）会失效。
  2. 约束性：球形约束使得最优解可能落在边界上（ \(\|p\| = \Delta\) ），也可能落在内部（ \(\|p\| < \Delta\) ）。内部解等价于无约束极小点，但当无约束极小点在信赖域外时，最优解必然落在边界上。

第三步：最优性条件与求解思路

  • KKT条件：对于子问题，其拉格朗日函数为 \(L(p, \lambda) = g^T p + \frac{1}{2} p^T B p + \frac{\lambda}{2} (p^T p - \Delta^2)\)。最优解 \(p^*\) 和对应的拉格朗日乘子 \(\lambda^*\) 满足：
  1. 平稳性条件：\((B + \lambda^* I) p^* = -g\)
  2. 互补松弛条件：\(\lambda^* (\|p^*\| - \Delta) = 0\)
  3. 可行性：\(\|p^*\| \le \Delta\)
  4. 对偶可行性：\(\lambda^* \ge 0\)
  5. 二阶充分条件：矩阵 \((B + \lambda^* I)\) 半正定。
  • 核心洞见：从平稳性条件 \((B + \lambda I) p = -g\) 可以看出，最优解 \(p^*\) 是参数 \(\lambda\) 的函数：\(p(\lambda) = -(B + \lambda I)^{-1} g\)。我们需要找到一个 \(\lambda^* \ge 0\)，使得对应的 \(p(\lambda^*)\) 满足：
  • 如果 \(\lambda^* = 0\)，则 \(B\) 需半正定且 \(\|p(0)\| \le \Delta\)（内部解）。
  • 如果 \(\lambda^* > 0\)，则必有 \(\|p(\lambda^*)\| = \Delta\)（边界解），且 \(B + \lambda^* I\) 正定。

第四步：经典求解算法——柯西点法与精确求解法

  1. 柯西点 (Cauchy Point) 法：
  • 思想：这是一种快速、廉价的近似求解法。它先沿最速下降方向（负梯度方向 \(-g\) ）走到信赖域边界，得到点 \(p^C_s\)。然后在连接原点、最速下降方向和 \(p^C_s\) 的二维子空间内，极小化二次模型。这个二维子空间极小化有解析解。
    • 优点：计算量极小（主要是一次梯度计算和一个低维最小化），能保证全局收敛。
    • 缺点：解的质量是“一阶”的，收敛速度较慢。通常作为复杂算法的安全备用步骤或初始化步骤。
  1. 精确求解法：根搜索（牛顿迭代或特征值分解）：
  • 思想：既然最优解满足 \(\|p(\lambda)\| = \Delta\) (当 \(\lambda > 0\))，我们可以将问题转化为求解关于 \(\lambda\) 的非线性方程：

\[ \phi(\lambda) = \|p(\lambda)\| - \Delta = \|-(B + \lambda I)^{-1} g\| - \Delta = 0, \quad \lambda > 0, \quad B + \lambda I \succ 0 \]

*   **求解方法**：
  • 特征值分解法：对矩阵 \(B\) 进行特征值分解 \(B = Q \Lambda Q^T\)，则 \(p(\lambda) = -Q (\Lambda + \lambda I)^{-1} Q^T g\)。函数 \(\phi(\lambda)\) 可以显式写出，其求解转化为一个关于 \(\lambda\) 的单变量单调递减方程的求根问题，可以用牛顿法高效求解。这是最经典和稳健的精确求解方法。
  • 截断共轭梯度法 (Steihaug-Toint CG)：这是一种迭代法。它运行标准共轭梯度法来求解方程 \(B p = -g\)，但在迭代过程中：
    a) 如果得到的解在信赖域内部且共轭梯度法正常收敛，则返回内部解。
    b) 如果迭代路径首次触及信赖域边界（ \(\|p\| = \Delta\) ），则返回这个边界点作为近似解。
    c) 如果检测到曲率为负（ \(p^T B p \le 0\) ），意味着模型在边界上可能下降更多，此时算法沿着当前负曲率方向走到边界，并返回该点。
    * 优点：截断共轭梯度法特别适合大规模稀疏问题，因为它只需矩阵-向量乘积，无需矩阵求逆或分解。

第五步：算法选择与比较

  • 柯西点法：适用于对子问题精度要求不高、或作为复杂算法（如截断共轭梯度法）失效时的安全步。是保证理论收敛性的基石。
  • 特征值分解/根搜索法：精度最高，能得到数学上“精确”的全局解。但需要对矩阵 \(B\) 进行分解，计算复杂度为 \(O(n^3)\)，适合中小规模稠密问题。
  • 截断共轭梯度法：是大规模优化问题的首选。它牺牲了一点精度（返回的通常是边界点，但不一定是边界上全局最优的点），但换来了处理海量变量（\(n\) 很大）的能力，因为它具有迭代法的良好尺度特性。

总结：
信赖域方法的子问题求解算法 是信赖域框架中的核心计算引擎。其目标是在一个球型约束下最小化一个（可能非凸的）二次函数。我们首先通过KKT条件将其转化为一个关于对偶变量 \(\lambda\) 的方程。在实践中，根据问题规模和精度需求，我们有多样化的选择：计算简单但粗糙的柯西点法、精度最高但计算量大的基于特征值分解的精确根搜索法，以及兼顾大规模计算和实用精度的截断共轭梯度法。高效稳健地求解这个子问题，是整个信赖域方法快速、可靠收敛的关键。

好的，我注意到您已列出了详尽的已讲词条。我将为您讲解一个尚未出现的、在优化理论和算法设计中具有基础性地位的词条。 信赖域方法的子问题求解算法 (Trust Region Subproblem Solving Algorithms) 我将为您循序渐进地讲解这个概念。 第一步：理解“信赖域方法”的总体框架 核心思想 ：在每一次迭代中，我们都在当前迭代点 \( x_ k \) 附近，用一个简单的“模型函数” \( m_ k(p) \) 来近似复杂的目标函数 \( f(x) \)。这个近似只在以 \( x_ k \) 为中心、半径为 \( \Delta_ k \) 的一个“球”（信赖域）内被认为是可靠的。 迭代步骤 ： 构建模型 ：在当前点 \( x_ k \)，构建一个简单的局部模型 \( m_ k(p) \)，通常是一个二次模型：\( m_ k(p) = f(x_ k) + \nabla f(x_ k)^T p + \frac{1}{2} p^T B_ k p \)。其中 \( p \) 是待求的移动步长，\( B_ k \) 是 Hessian 矩阵或其近似（如拟牛顿法的 BFGS 矩阵）。 求解子问题 ：在信赖域 \( \|p\| \le \Delta_ k \) 内，求解模型的最优步长 \( p_ k \)： \( \min_ {p \in \mathbb{R}^n} m_ k(p) \quad \text{s.t.} \quad \|p\| \le \Delta_ k \)。 评估与更新 ：计算实际下降 \( f(x_ k) - f(x_ k + p_ k) \) 与模型预测下降 \( m_ k(0) - m_ k(p_ k) \) 的比值 \( \rho_ k \)。 如果 \( \rho_ k \) 接近1，说明模型近似得很好，接受这一步，并可能扩大信赖域半径 \( \Delta_ {k+1} > \Delta_ k \)。 如果 \( \rho_ k \) 很小甚至为负，说明模型近似得很差，拒绝这一步（ \( x_ {k+1} = x_ k \) ），并缩小信赖域半径 \( \Delta_ {k+1} < \Delta_ k \) 以获取更精确的模型。 迭代 ：重复以上步骤，直到满足收敛条件。 第二步：聚焦核心——信赖域子问题 (Trust Region Subproblem, TRS) 标准形式 ：在第二步中，我们需要精确求解的子优化问题，通常写作： \[ \min_ {p \in \mathbb{R}^n} \quad g^T p + \frac{1}{2} p^T B p \quad \text{s.t.} \quad \|p\| \le \Delta \] 这里为了简洁，省略了下标 \( k \)，其中 \( g = \nabla f(x_ k) \), \( B = B_ k \)，信赖域约束 \( \|p\| \) 通常是2-范数（欧几里得范数）。 问题特性 ：这是一个 具有球形约束的（可能非凸）二次优化问题 。其挑战在于： 非凸性 ：矩阵 \( B \) 可能不定（即存在负特征值），导致目标函数非凸。传统的无约束优化方法（如牛顿法）会失效。 约束性 ：球形约束使得最优解可能落在边界上（ \( \|p\| = \Delta \) ），也可能落在内部（ \( \|p\| < \Delta \) ）。内部解等价于无约束极小点，但当无约束极小点在信赖域外时，最优解必然落在边界上。 第三步：最优性条件与求解思路 KKT条件 ：对于子问题，其拉格朗日函数为 \( L(p, \lambda) = g^T p + \frac{1}{2} p^T B p + \frac{\lambda}{2} (p^T p - \Delta^2) \)。最优解 \( p^* \) 和对应的拉格朗日乘子 \( \lambda^* \) 满足： 平稳性条件 ：\( (B + \lambda^* I) p^* = -g \) 互补松弛条件 ：\( \lambda^* (\|p^* \| - \Delta) = 0 \) 可行性 ：\( \|p^* \| \le \Delta \) 对偶可行性 ：\( \lambda^* \ge 0 \) 二阶充分条件 ：矩阵 \( (B + \lambda^* I) \) 半正定。 核心洞见 ：从平稳性条件 \( (B + \lambda I) p = -g \) 可以看出，最优解 \( p^* \) 是参数 \( \lambda \) 的函数：\( p(\lambda) = -(B + \lambda I)^{-1} g \)。我们需要找到一个 \( \lambda^* \ge 0 \)，使得对应的 \( p(\lambda^* ) \) 满足： 如果 \( \lambda^* = 0 \)，则 \( B \) 需半正定且 \( \|p(0)\| \le \Delta \)（内部解）。 如果 \( \lambda^* > 0 \)，则必有 \( \|p(\lambda^ )\| = \Delta \)（边界解），且 \( B + \lambda^ I \) 正定。 第四步：经典求解算法——柯西点法与精确求解法 柯西点 (Cauchy Point) 法 ： 思想 ：这是一种快速、廉价的近似求解法。它先沿最速下降方向（负梯度方向 \( -g \) ）走到信赖域边界，得到点 \( p^C_ s \)。然后在连接原点、最速下降方向和 \( p^C_ s \) 的二维子空间内，极小化二次模型。这个二维子空间极小化有解析解。 优点 ：计算量极小（主要是一次梯度计算和一个低维最小化），能保证全局收敛。 缺点 ：解的质量是“一阶”的，收敛速度较慢。通常作为复杂算法的安全备用步骤或初始化步骤。 精确求解法：根搜索（牛顿迭代或特征值分解） ： 思想 ：既然最优解满足 \( \|p(\lambda)\| = \Delta \) (当 \( \lambda > 0 \))，我们可以将问题转化为求解关于 \( \lambda \) 的非线性方程： \[ \phi(\lambda) = \|p(\lambda)\| - \Delta = \|-(B + \lambda I)^{-1} g\| - \Delta = 0, \quad \lambda > 0, \quad B + \lambda I \succ 0 \] 求解方法 ： 特征值分解法 ：对矩阵 \( B \) 进行特征值分解 \( B = Q \Lambda Q^T \)，则 \( p(\lambda) = -Q (\Lambda + \lambda I)^{-1} Q^T g \)。函数 \( \phi(\lambda) \) 可以显式写出，其求解转化为一个关于 \( \lambda \) 的单变量单调递减方程的求根问题，可以用牛顿法高效求解。这是最经典和稳健的精确求解方法。 截断共轭梯度法 (Steihaug-Toint CG) ：这是一种迭代法。它运行标准共轭梯度法来求解方程 \( B p = -g \)，但在迭代过程中： a) 如果得到的解在信赖域内部且共轭梯度法正常收敛，则返回内部解。 b) 如果迭代路径首次触及信赖域边界（ \( \|p\| = \Delta \) ），则返回这个边界点作为近似解。 c) 如果检测到曲率为负（ \( p^T B p \le 0 \) ），意味着模型在边界上可能下降更多，此时算法沿着当前负曲率方向走到边界，并返回该点。 优点 ：截断共轭梯度法特别适合大规模稀疏问题，因为它只需矩阵-向量乘积，无需矩阵求逆或分解。 第五步：算法选择与比较 柯西点法 ：适用于对子问题精度要求不高、或作为复杂算法（如截断共轭梯度法）失效时的安全步。是保证理论收敛性的基石。 特征值分解/根搜索法 ：精度最高，能得到数学上“精确”的全局解。但需要对矩阵 \( B \) 进行分解，计算复杂度为 \( O(n^3) \)，适合中小规模稠密问题。 截断共轭梯度法 ：是大规模优化问题的首选。它牺牲了一点精度（返回的通常是边界点，但不一定是边界上全局最优的点），但换来了处理海量变量（\( n \) 很大）的能力，因为它具有迭代法的良好尺度特性。 总结 ： 信赖域方法的子问题求解算法 是信赖域框架中的核心计算引擎。其目标是在一个球型约束下最小化一个（可能非凸的）二次函数。我们首先通过KKT条件将其转化为一个关于对偶变量 \( \lambda \) 的方程。在实践中，根据问题规模和精度需求，我们有多样化的选择：计算简单但粗糙的 柯西点法 、精度最高但计算量大的基于特征值分解的 精确根搜索法 ，以及兼顾大规模计算和实用精度的 截断共轭梯度法 。高效稳健地求解这个子问题，是整个信赖域方法快速、可靠收敛的关键。