非线性规划中的信赖域反射牛顿法基础题
字数 3174 2025-10-29 11:31:55

非线性规划中的信赖域反射牛顿法基础题

题目描述
考虑非线性规划问题：

\[\min f(x) = (x_1 - 1)^2 + (x_2 - 2)^2 + x_1 x_2 \]

满足约束条件：

\[x_1 + x_2 \leq 3, \quad x_1 \geq 0, \quad x_2 \geq 0. \]

要求使用信赖域反射牛顿法（Trust-Region Reflective Newton Method）求解该问题，初始点为 \(x^{(0)} = (0, 0)\)，初始信赖域半径 \(\Delta_0 = 0.5\)，容忍误差 \(\epsilon = 10^{-6}\)。

解题步骤

信赖域反射牛顿法结合了信赖域法的全局收敛性和牛顿法的局部快速收敛性，并通过反射技巧处理边界约束。其核心思想是：在每次迭代中，用二次模型近似目标函数，在信赖域内求解子问题，并根据实际下降量与预测下降量的比值调整信赖域半径。

1. 问题重构与梯度、Hessian计算

目标函数梯度为：

\[\nabla f(x) = \begin{bmatrix} 2(x_1 - 1) + x_2 \\ 2(x_2 - 2) + x_1 \end{bmatrix} = \begin{bmatrix} 2x_1 + x_2 - 2 \\ x_1 + 2x_2 - 4 \end{bmatrix}. \]

Hessian矩阵为常数矩阵（因 \(f(x)\) 是二次函数）：

\[H(x) = \nabla^2 f(x) = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}. \]

约束条件定义可行域为多面体，需在迭代中通过反射操作将试探步映射回可行域。

2. 初始点验证

初始点 \(x^{(0)} = (0, 0)\) 满足约束 \(x_1 + x_2 = 0 \leq 3\)，位于可行域内。计算初始梯度：

\[\nabla f(0,0) = [-2, -4]^\top. \]

3. 信赖域子问题求解

在迭代点 \(x^{(k)}\) 处，构建二次模型：

\[m_k(p) = f(x^{(k)}) + \nabla f(x^{(k)})^\top p + \frac{1}{2} p^\top H_k p, \]

其中 \(H_k = H(x^{(k)})\)。子问题为：

\[\min_p m_k(p) \quad \text{s.t.} \quad \|p\| \leq \Delta_k, \quad x^{(k)} + p \in \Omega, \]

\(\Omega\) 为可行域。由于约束为线性，反射法将不可行试探步沿边界反射回可行域。

以第1次迭代为例（\(k=0\))：

  • 二次模型：

\[ m_0(p) = f(0,0) + [-2, -4] p + \frac{1}{2} p^\top \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} p. \]

其中 \(f(0,0) = (0-1)^2 + (0-2)^2 + 0 = 5\)。

  • 忽略边界约束，求解无约束子问题得牛顿步 \(p_N = -H^{-1} \nabla f = -\begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}^{-1} \begin{bmatrix} -2 \\ -4 \end{bmatrix}\)。
    计算逆矩阵：

\[ H^{-1} = \frac{1}{3} \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \implies p_N = \frac{1}{3} \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \begin{bmatrix} 2 \\ 4 \end{bmatrix} = \begin{bmatrix} 0 \\ 2 \end{bmatrix}. \]

  • 由于 \(\|p_N\| = 2 > \Delta_0 = 0.5\)，需缩放。采用狗腿法或截断牛顿步，得试探步 \(p_k\) 满足 \(\|p_k\| = \Delta_0\)。
    简单起见，这里取最速下降方向缩放： \(p_k = -\frac{\Delta_0}{\|\nabla f\|} \nabla f = -\frac{0.5}{\sqrt{20}} [-2, -4]^\top \approx [0.2236, 0.4472]^\top\)。

4. 反射处理边界约束

试探点 \(x^{(k)} + p_k = (0.2236, 0.4472)\) 满足所有约束（\(x_1 + x_2 \approx 0.6708 \leq 3\)），无需反射。若试探点越界，则沿边界反射至可行域。

5. 计算实际下降比并更新信赖域半径

实际下降量：

\[\text{ared} = f(x^{(k)}) - f(x^{(k)} + p_k) = 5 - f(0.2236, 0.4472). \]

计算 \(f(0.2236, 0.4472) \approx (0.2236-1)^2 + (0.4472-2)^2 + 0.2236 \times 0.4472 \approx 3.618\)。
预测下降量：

\[\text{pred} = m_k(0) - m_k(p_k) = 0 - \left( [-2, -4] p_k + \frac{1}{2} p_k^\top H p_k \right) \approx 2.236 - 0.5 \approx 1.736. \]

比值：

\[\rho_k = \frac{\text{ared}}{\text{pred}} \approx \frac{5 - 3.618}{1.736} \approx 0.796. \]

阈值通常设为 \(\eta_1 = 0.25, \eta_2 = 0.75\)。

  • 若 \(\rho_k < \eta_1\)，拒绝步长，缩小信赖域： \(\Delta_{k+1} = 0.25 \Delta_k\)。
  • 若 \(\rho_k > \eta_2\) 且 \(\|p_k\| = \Delta_k\)，扩大信赖域： \(\Delta_{k+1} = 2 \Delta_k\)。
  • 否则保持半径不变。
    此处 \(\rho_k \approx 0.796 > 0.75\)，且 \(\|p_k\| = \Delta_0\)，故扩大半径： \(\Delta_1 = 1.0\)。

6. 迭代直至收敛

重复步骤3-5，更新 \(x^{(k+1)} = x^{(k)} + p_k\)，直到梯度范数 \(\|\nabla f(x^{(k)})\| < \epsilon\)。
对于本例，最优解为 \(x^* = (0, 2)\)（通过解析法验证：拉格朗日函数得边界解），梯度为 \(\nabla f(0,2) = [0, 0]^\top\)。

关键点总结

  • 反射操作确保迭代点始终可行。
  • 信赖域半径根据实际/预测下降比动态调整，平衡收敛速度与稳定性。
  • 对于二次函数，Hessian矩阵恒定，牛顿步只需计算一次逆矩阵。
非线性规划中的信赖域反射牛顿法基础题 题目描述 考虑非线性规划问题： \[ \min f(x) = (x_ 1 - 1)^2 + (x_ 2 - 2)^2 + x_ 1 x_ 2 \] 满足约束条件： \[ x_ 1 + x_ 2 \leq 3, \quad x_ 1 \geq 0, \quad x_ 2 \geq 0. \] 要求使用信赖域反射牛顿法（Trust-Region Reflective Newton Method）求解该问题，初始点为 \( x^{(0)} = (0, 0) \)，初始信赖域半径 \(\Delta_ 0 = 0.5\)，容忍误差 \(\epsilon = 10^{-6}\)。 解题步骤 信赖域反射牛顿法结合了信赖域法的全局收敛性和牛顿法的局部快速收敛性，并通过反射技巧处理边界约束。其核心思想是：在每次迭代中，用二次模型近似目标函数，在信赖域内求解子问题，并根据实际下降量与预测下降量的比值调整信赖域半径。 1. 问题重构与梯度、Hessian计算 目标函数梯度为： \[ \nabla f(x) = \begin{bmatrix} 2(x_ 1 - 1) + x_ 2 \\ 2(x_ 2 - 2) + x_ 1 \end{bmatrix} = \begin{bmatrix} 2x_ 1 + x_ 2 - 2 \\ x_ 1 + 2x_ 2 - 4 \end{bmatrix}. \] Hessian矩阵为常数矩阵（因 \( f(x) \) 是二次函数）： \[ H(x) = \nabla^2 f(x) = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}. \] 约束条件定义可行域为多面体，需在迭代中通过反射操作将试探步映射回可行域。 2. 初始点验证 初始点 \( x^{(0)} = (0, 0) \) 满足约束 \( x_ 1 + x_ 2 = 0 \leq 3 \)，位于可行域内。计算初始梯度： \[ \nabla f(0,0) = [ -2, -4 ]^\top. \] 3. 信赖域子问题求解 在迭代点 \( x^{(k)} \) 处，构建二次模型： \[ m_ k(p) = f(x^{(k)}) + \nabla f(x^{(k)})^\top p + \frac{1}{2} p^\top H_ k p, \] 其中 \( H_ k = H(x^{(k)}) \)。子问题为： \[ \min_ p m_ k(p) \quad \text{s.t.} \quad \|p\| \leq \Delta_ k, \quad x^{(k)} + p \in \Omega, \] \(\Omega\) 为可行域。由于约束为线性，反射法将不可行试探步沿边界反射回可行域。 以第1次迭代为例（\( k=0 \))： 二次模型： \[ m_ 0(p) = f(0,0) + [ -2, -4 ] p + \frac{1}{2} p^\top \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} p. \] 其中 \( f(0,0) = (0-1)^2 + (0-2)^2 + 0 = 5 \)。 忽略边界约束，求解无约束子问题得牛顿步 \( p_ N = -H^{-1} \nabla f = -\begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}^{-1} \begin{bmatrix} -2 \\ -4 \end{bmatrix} \)。 计算逆矩阵： \[ H^{-1} = \frac{1}{3} \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \implies p_ N = \frac{1}{3} \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \begin{bmatrix} 2 \\ 4 \end{bmatrix} = \begin{bmatrix} 0 \\ 2 \end{bmatrix}. \] 由于 \( \|p_ N\| = 2 > \Delta_ 0 = 0.5 \)，需缩放。采用狗腿法或截断牛顿步，得试探步 \( p_ k \) 满足 \( \|p_ k\| = \Delta_ 0 \)。 简单起见，这里取最速下降方向缩放： \( p_ k = -\frac{\Delta_ 0}{\|\nabla f\|} \nabla f = -\frac{0.5}{\sqrt{20}} [ -2, -4]^\top \approx [ 0.2236, 0.4472 ]^\top \)。 4. 反射处理边界约束 试探点 \( x^{(k)} + p_ k = (0.2236, 0.4472) \) 满足所有约束（\( x_ 1 + x_ 2 \approx 0.6708 \leq 3 \)），无需反射。若试探点越界，则沿边界反射至可行域。 5. 计算实际下降比并更新信赖域半径 实际下降量： \[ \text{ared} = f(x^{(k)}) - f(x^{(k)} + p_ k) = 5 - f(0.2236, 0.4472). \] 计算 \( f(0.2236, 0.4472) \approx (0.2236-1)^2 + (0.4472-2)^2 + 0.2236 \times 0.4472 \approx 3.618 \)。 预测下降量： \[ \text{pred} = m_ k(0) - m_ k(p_ k) = 0 - \left( [ -2, -4] p_ k + \frac{1}{2} p_ k^\top H p_ k \right) \approx 2.236 - 0.5 \approx 1.736. \] 比值： \[ \rho_ k = \frac{\text{ared}}{\text{pred}} \approx \frac{5 - 3.618}{1.736} \approx 0.796. \] 阈值通常设为 \( \eta_ 1 = 0.25, \eta_ 2 = 0.75 \)。 若 \( \rho_ k < \eta_ 1 \)，拒绝步长，缩小信赖域： \( \Delta_ {k+1} = 0.25 \Delta_ k \)。 若 \( \rho_ k > \eta_ 2 \) 且 \( \|p_ k\| = \Delta_ k \)，扩大信赖域： \( \Delta_ {k+1} = 2 \Delta_ k \)。 否则保持半径不变。 此处 \( \rho_ k \approx 0.796 > 0.75 \)，且 \( \|p_ k\| = \Delta_ 0 \)，故扩大半径： \( \Delta_ 1 = 1.0 \)。 6. 迭代直至收敛 重复步骤3-5，更新 \( x^{(k+1)} = x^{(k)} + p_ k \)，直到梯度范数 \( \|\nabla f(x^{(k)})\| < \epsilon \)。 对于本例，最优解为 \( x^* = (0, 2) \)（通过解析法验证：拉格朗日函数得边界解），梯度为 \( \nabla f(0,2) = [ 0, 0 ]^\top \)。 关键点总结 反射操作确保迭代点始终可行。 信赖域半径根据实际/预测下降比动态调整，平衡收敛速度与稳定性。 对于二次函数，Hessian矩阵恒定，牛顿步只需计算一次逆矩阵。