非线性规划中的信赖域子问题与信赖域步求解
字数 3123 2025-12-08 19:07:38

非线性规划中的信赖域子问题与信赖域步求解

我将为你详细讲解信赖域方法中的核心子问题，即如何构造并求解信赖域子问题，从而获得每次迭代的试探步。这个过程分为以下几个步骤：

1. 基本思想：用局部模型近似原问题

在非线性规划中，我们常面对无约束优化问题：

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

信赖域方法在每次迭代点 \(x_k\) 处，构造一个局部近似模型 \(m_k(p)\) 来近似目标函数在步长 \(p\) 下的变化：

\[f(x_k + p) \approx m_k(p) = f(x_k) + \nabla f(x_k)^\top p + \frac{1}{2} p^\top B_k p \]

其中：

  • \(p\) 是试探步（从当前点 \(x_k\) 出发的位移）；
  • \(B_k\) 是 Hessian 矩阵或其近似（若使用牛顿法则 \(B_k = \nabla^2 f(x_k)\)，若使用拟牛顿法则为近似 Hessian）；
  • 模型 \(m_k(p)\) 通常是二次函数（但也可以是一阶线性模型）。

为了保证模型在 \(p\) 较小时足够精确，我们限制 \(p\) 的范数不超过一个信赖域半径 \(\Delta_k > 0\)，即：

\[\|p\| \le \Delta_k \]

这里范数常用 \(\ell_2\) 范数（欧几里得范数）。

2. 信赖域子问题的数学形式

在迭代点 \(x_k\)，信赖域子问题为：

\[\min_{p \in \mathbb{R}^n} \; m_k(p) = f_k + g_k^\top p + \frac{1}{2} p^\top B_k p \]

\[\text{s.t.} \; \|p\| \le \Delta_k \]

其中 \(f_k = f(x_k)\), \(g_k = \nabla f(x_k)\)。

这是一个带球约束的二次规划问题。注意：

  • 如果 \(B_k\) 半正定，子问题是凸的，容易求解；
  • 如果 \(B_k\) 不定，子问题可能非凸，但球约束保证了全局解的存在。

3. 子问题的求解思路

3.1 一维情形（直观理解）

若 \(n=1\)，子问题是在区间 \([-\Delta_k, \Delta_k]\) 上最小化二次函数 \(q(p) = a p^2 + b p + c\)。

  • 若 \(a>0\)，无约束极小点 \(p^* = -b/(2a)\)，若 \(|p^*| \le \Delta_k\) 则取 \(p^*\)，否则取边界点中使 \(q(p)\) 较小的点。
  • 若 \(a \le 0\)，极小点必在边界处取得。

3.2 高维情形：利用最优性条件

通过拉格朗日函数推导，子问题的解 \(p^*\) 满足：

\[(B_k + \lambda I) p^* = -g_k \]

\[\lambda \ge 0, \quad \|p^*\| \le \Delta_k, \quad \lambda (\|p^*\| - \Delta_k) = 0 \]

这里 \(\lambda\) 是拉格朗日乘子，对应球约束的互补松弛条件。

解释：

  • 如果无约束牛顿步 \(p_N = -B_k^{-1} g_k\)（假设 \(B_k\) 可逆）满足 \(\|p_N\| \le \Delta_k\)，且 \(B_k\) 正定，则取 \(p^* = p_N, \lambda=0\)。
  • 否则，需要增大 \(\lambda\) 使得 \((B_k + \lambda I)\) 正定，并求解上述线性系统得到 \(p(\lambda)\)，再调整 \(\lambda\) 使得 \(\|p(\lambda)\| = \Delta_k\)（此时约束积极）。

4. 实际求解算法：截断共轭梯度法（Steihaug 方法）

由于精确求解上述系统需要特征值分解（代价高），常用截断共轭梯度法（Truncated CG）近似求解子问题，步骤如下：

  1. 初始化 \(p_0 = 0\), \(r_0 = g_k\), \(d_0 = -r_0\)。
  2. 对 \(j=0,1,\dots\) 迭代：
    • 若 \(d_j^\top B_k d_j \le 0\)，说明沿方向 \(d_j\) 模型无下界，则沿负曲率方向走到边界：计算 \(\tau\) 使 \(\|p_j + \tau d_j\| = \Delta_k\)，取 \(p = p_j + \tau d_j\) 并终止。
    • 否则，计算步长 \(\alpha_j = r_j^\top r_j / (d_j^\top B_k d_j)\)，更新 \(p_{j+1} = p_j + \alpha_j d_j\)。
    • 若 \(\|p_{j+1}\| \ge \Delta_k\)，则类似走到边界：计算 \(\tau\) 使 \(\|p_j + \tau d_j\| = \Delta_k\)，取 \(p = p_j + \tau d_j\) 并终止。
    • 更新残差 \(r_{j+1} = r_j + \alpha_j B_k d_j\)，若 \(\|r_{j+1}\|\) 足够小，则终止并返回 \(p_{j+1}\)。
    • 计算 \(\beta_j = r_{j+1}^\top r_{j+1} / (r_j^\top r_j)\)，更新方向 \(d_{j+1} = -r_{j+1} + \beta_j d_j\)。

该方法能在有限步内返回一个满足充分下降条件的近似解，且计算量较小。

5. 信赖域半径的更新

得到试探步 \(p_k\) 后，比较模型预测下降量与实际下降量：

\[\rho_k = \frac{f(x_k) - f(x_k + p_k)}{m_k(0) - m_k(p_k)} \]

其中分母是预测下降量（恒正）。

  • 若 \(\rho_k\) 接近 1，说明模型拟合好，可增大信赖域半径 \(\Delta_{k+1} = 2\Delta_k\) 或保持。
  • 若 \(\rho_k\) 很小（如 <0.1），说明模型拟合差，应缩小半径 \(\Delta_{k+1} = 0.5\Delta_k\)。
  • 若 \(\rho_k > 0.75\) 且步长触及边界，则可扩大半径；若 \(\rho_k < 0.1\) 则缩小半径；否则保持。

半径调整策略保证了方法在局部收敛到牛顿速度，在远处稳健下降。

6. 全局收敛性保证

在适当条件下（如 \(B_k\) 一致有界，梯度 Lipschitz 连续），信赖域方法能保证：

\[\liminf_{k \to \infty} \|\nabla f(x_k)\| = 0 \]

即迭代点列至少有一个聚点是稳定点。这是因为当梯度不可忽略时，即使子问题非精确求解，试探步也能带来足够的实际下降。

7. 与线搜索方法的对比

  • 线搜索先定方向，再沿方向定步长；
  • 信赖域先定步长范围（半径），再在球内找最优步。
    信赖域尤其适用于 Hessian 不正定或模型近似较差的情形，因为它通过半径直接控制步长，避免无效迭代。

通过以上步骤，信赖域子问题的构造与求解构成了信赖域方法的核心，它平衡了局部模型的精度与全局收敛的鲁棒性。

非线性规划中的信赖域子问题与信赖域步求解 我将为你详细讲解信赖域方法中的核心子问题，即如何构造并求解信赖域子问题，从而获得每次迭代的试探步。这个过程分为以下几个步骤： 1. 基本思想：用局部模型近似原问题 在非线性规划中，我们常面对无约束优化问题： \[ \min_ {x \in \mathbb{R}^n} f(x) \] 信赖域方法在每次迭代点 \(x_ k\) 处，构造一个 局部近似模型 \(m_ k(p)\) 来近似目标函数在步长 \(p\) 下的变化： \[ f(x_ k + p) \approx m_ k(p) = f(x_ k) + \nabla f(x_ k)^\top p + \frac{1}{2} p^\top B_ k p \] 其中： \(p\) 是试探步（从当前点 \(x_ k\) 出发的位移）； \(B_ k\) 是 Hessian 矩阵或其近似（若使用牛顿法则 \(B_ k = \nabla^2 f(x_ k)\)，若使用拟牛顿法则为近似 Hessian）； 模型 \(m_ k(p)\) 通常是二次函数（但也可以是一阶线性模型）。 为了保证模型在 \(p\) 较小时足够精确，我们限制 \(p\) 的范数不超过一个 信赖域半径 \(\Delta_ k > 0\)，即： \[ \|p\| \le \Delta_ k \] 这里范数常用 \(\ell_ 2\) 范数（欧几里得范数）。 2. 信赖域子问题的数学形式 在迭代点 \(x_ k\)，信赖域子问题为： \[ \min_ {p \in \mathbb{R}^n} \; m_ k(p) = f_ k + g_ k^\top p + \frac{1}{2} p^\top B_ k p \] \[ \text{s.t.} \; \|p\| \le \Delta_ k \] 其中 \(f_ k = f(x_ k)\), \(g_ k = \nabla f(x_ k)\)。 这是一个 带球约束的二次规划问题 。注意： 如果 \(B_ k\) 半正定，子问题是凸的，容易求解； 如果 \(B_ k\) 不定，子问题可能非凸，但球约束保证了全局解的存在。 3. 子问题的求解思路 3.1 一维情形（直观理解） 若 \(n=1\)，子问题是在区间 \([ -\Delta_ k, \Delta_ k ]\) 上最小化二次函数 \(q(p) = a p^2 + b p + c\)。 若 \(a>0\)，无约束极小点 \(p^* = -b/(2a)\)，若 \(|p^ | \le \Delta_ k\) 则取 \(p^ \)，否则取边界点中使 \(q(p)\) 较小的点。 若 \(a \le 0\)，极小点必在边界处取得。 3.2 高维情形：利用最优性条件 通过拉格朗日函数推导，子问题的解 \(p^ \) 满足： \[ (B_ k + \lambda I) p^ = -g_ k \] \[ \lambda \ge 0, \quad \|p^ \| \le \Delta_ k, \quad \lambda (\|p^ \| - \Delta_ k) = 0 \] 这里 \(\lambda\) 是拉格朗日乘子，对应球约束的互补松弛条件。 解释 ： 如果无约束牛顿步 \(p_ N = -B_ k^{-1} g_ k\)（假设 \(B_ k\) 可逆）满足 \(\|p_ N\| \le \Delta_ k\)，且 \(B_ k\) 正定，则取 \(p^* = p_ N, \lambda=0\)。 否则，需要增大 \(\lambda\) 使得 \((B_ k + \lambda I)\) 正定，并求解上述线性系统得到 \(p(\lambda)\)，再调整 \(\lambda\) 使得 \(\|p(\lambda)\| = \Delta_ k\)（此时约束积极）。 4. 实际求解算法：截断共轭梯度法（Steihaug 方法） 由于精确求解上述系统需要特征值分解（代价高），常用 截断共轭梯度法 （Truncated CG）近似求解子问题，步骤如下： 初始化 \(p_ 0 = 0\), \(r_ 0 = g_ k\), \(d_ 0 = -r_ 0\)。 对 \(j=0,1,\dots\) 迭代： 若 \(d_ j^\top B_ k d_ j \le 0\)，说明沿方向 \(d_ j\) 模型无下界，则沿负曲率方向走到边界：计算 \(\tau\) 使 \(\|p_ j + \tau d_ j\| = \Delta_ k\)，取 \(p = p_ j + \tau d_ j\) 并终止。 否则，计算步长 \(\alpha_ j = r_ j^\top r_ j / (d_ j^\top B_ k d_ j)\)，更新 \(p_ {j+1} = p_ j + \alpha_ j d_ j\)。 若 \(\|p_ {j+1}\| \ge \Delta_ k\)，则类似走到边界：计算 \(\tau\) 使 \(\|p_ j + \tau d_ j\| = \Delta_ k\)，取 \(p = p_ j + \tau d_ j\) 并终止。 更新残差 \(r_ {j+1} = r_ j + \alpha_ j B_ k d_ j\)，若 \(\|r_ {j+1}\|\) 足够小，则终止并返回 \(p_ {j+1}\)。 计算 \(\beta_ j = r_ {j+1}^\top r_ {j+1} / (r_ j^\top r_ j)\)，更新方向 \(d_ {j+1} = -r_ {j+1} + \beta_ j d_ j\)。 该方法能在有限步内返回一个满足 充分下降条件 的近似解，且计算量较小。 5. 信赖域半径的更新 得到试探步 \(p_ k\) 后，比较模型预测下降量与实际下降量： \[ \rho_ k = \frac{f(x_ k) - f(x_ k + p_ k)}{m_ k(0) - m_ k(p_ k)} \] 其中分母是预测下降量（恒正）。 若 \(\rho_ k\) 接近 1，说明模型拟合好，可增大信赖域半径 \(\Delta_ {k+1} = 2\Delta_ k\) 或保持。 若 \(\rho_ k\) 很小（如 <0.1），说明模型拟合差，应缩小半径 \(\Delta_ {k+1} = 0.5\Delta_ k\)。 若 \(\rho_ k > 0.75\) 且步长触及边界，则可扩大半径；若 \(\rho_ k < 0.1\) 则缩小半径；否则保持。 半径调整策略保证了方法在局部收敛到牛顿速度，在远处稳健下降。 6. 全局收敛性保证 在适当条件下（如 \(B_ k\) 一致有界，梯度 Lipschitz 连续），信赖域方法能保证： \[ \liminf_ {k \to \infty} \|\nabla f(x_ k)\| = 0 \] 即迭代点列至少有一个聚点是稳定点。这是因为当梯度不可忽略时，即使子问题非精确求解，试探步也能带来足够的实际下降。 7. 与线搜索方法的对比 线搜索先定方向，再沿方向定步长； 信赖域先定步长范围（半径），再在球内找最优步。 信赖域尤其适用于 Hessian 不正定或模型近似较差的情形，因为它通过半径直接控制步长，避免无效迭代。 通过以上步骤，信赖域子问题的构造与求解构成了信赖域方法的核心，它平衡了局部模型的精度与全局收敛的鲁棒性。