非线性规划中的信赖域反射算法基础题
字数 2299 2025-10-27 17:41:11

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

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

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

\[\text{s.t. } x_1 + x_2 \leq 2 \]

\[-x_1 + x_2 \leq 1 \]

\[x_1, x_2 \geq 0 \]

初始点取为 \(x^{(0)} = (0, 0)\)，信赖域半径初始值 \(\Delta_0 = 0.5\)。要求用信赖域反射算法（Trust Region Reflective Algorithm）求解该问题，重点说明子问题构造、反射步骤和收敛判断。

解题过程

  1. 算法原理概述
    信赖域反射算法结合了信赖域法和反射技巧，用于处理带边界约束的优化问题。其核心步骤包括：

    • 在每次迭代中，用二次模型近似目标函数，在信赖域内求解子问题。
    • 若试探步超出可行域，通过反射操作将其映射回可行域。
    • 根据实际目标函数下降量与预测下降量的比值，调整信赖域半径。

  2. 初始化
    初始点 \(x^{(0)} = (0, 0)\)，目标函数值 \(f(x^{(0)}) = (0-2)^2 + (0-1)^2 = 5\)。初始信赖域半径 \(\Delta_0 = 0.5\)，容忍误差 \(\epsilon = 10^{-6}\)。

  3. 第一次迭代（k=0）

    • 构建二次模型：
      在 \(x^{(0)}\) 处计算梯度 \(\nabla f(x) = [2(x_1-2), 2(x_2-1)]^T = [-4, -2]^T\)，Hessian矩阵 \(H = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\)。
      二次模型为：

\[ m_k(p) = f(x^{(k)}) + \nabla f(x^{(k)})^T p + \frac{1}{2} p^T H p = 5 + [-4, -2] p + \frac{1}{2} p^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} p. \]

  • 求解信赖域子问题：
    约束为 \(\|p\| \leq \Delta_0 = 0.5\)。由于梯度方向为 \([-4, -2]^T\)，最优步长沿负梯度方向取边界值：

\[ p^{(0)} = -\frac{\Delta_0}{\|\nabla f\|} \nabla f = -\frac{0.5}{\sqrt{20}} [-4, -2]^T \approx [0.2236, 0.1118]^T. \]

  • 反射检查：
    试探点 \(x^{(0)} + p^{(0)} \approx (0.2236, 0.1118)\) 满足所有约束（验证：\(0.2236+0.1118=0.3354 \leq 2\)，其他约束均满足），无需反射。
  • 计算实际下降比：
    实际函数值 \(f(x^{(0)}+p^{(0)}) \approx (0.2236-2)^2 + (0.1118-1)^2 \approx 4.277\)，
    预测下降量 \(\Delta m = m(0) - m(p^{(0)}) \approx 5 - 4.277 = 0.723\)，
    实际下降量 \(\Delta f = f(x^{(0)}) - f(x^{(0)}+p^{(0)}) \approx 5 - 4.277 = 0.723\)，
    比值 \(\rho = \frac{\Delta f}{\Delta m} = 1 > 0.75\)，接受试探点，并扩大信赖域半径 \(\Delta_1 = 1.5 \Delta_0 = 0.75\)。
    更新 \(x^{(1)} = (0.2236, 0.1118)\)。

  1. 第二次迭代（k=1）

    • 构建二次模型：
      梯度 \(\nabla f(x^{(1)}) \approx [-3.5528, -1.7764]^T\)，Hessian 不变。
    • 求解子问题：
      沿负梯度方向取步长 \(p^{(1)} \approx [0.3354, 0.1677]^T\)（满足 \(\|p\| \leq 0.75\)）。
    • 反射检查：
      试探点 \(x^{(1)}+p^{(1)} \approx (0.5590, 0.2795)\) 仍满足约束，无需反射。
    • 计算实际下降比：
      \(f(x^{(1)}+p^{(1)}) \approx 3.625\)，\(\rho \approx \frac{4.277-3.625}{4.277-3.625} = 1\)，接受点并扩大信赖域至 \(\Delta_2 = 1.125\)。
      更新 \(x^{(2)} = (0.5590, 0.2795)\)。

  2. 后续迭代与收敛
    重复上述过程，迭代点向约束边界 \(x_1 + x_2 = 2\) 靠近。当梯度在可行域内的投影很小时停止。最终解接近最优解 \(x^* = (1.5, 0.5)\)，对应 \(f(x^*) = 0.5\)。

  3. 关键点总结

    • 反射步骤仅在试探步违反边界约束时触发，将点映射回可行域。
    • 比值 \(\rho\) 决定是否接受试探步和调整信赖域半径：
      • \(\rho > 0.75\)：扩大半径；
      • \(\rho < 0.25\)：缩小半径；
      • 中间值：保持半径。
    • 收敛条件为梯度范数小于容忍误差或信赖域半径过小。

通过以上步骤，信赖域反射算法在保证可行性的同时逐步逼近最优解。

非线性规划中的信赖域反射算法基础题 题目描述 考虑非线性规划问题： \[\min f(x) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2\] \[\text{s.t. } x_ 1 + x_ 2 \leq 2\] \[-x_ 1 + x_ 2 \leq 1\] \[x_ 1, x_ 2 \geq 0\] 初始点取为 \(x^{(0)} = (0, 0)\)，信赖域半径初始值 \(\Delta_ 0 = 0.5\)。要求用信赖域反射算法（Trust Region Reflective Algorithm）求解该问题，重点说明子问题构造、反射步骤和收敛判断。 解题过程 算法原理概述 信赖域反射算法结合了信赖域法和反射技巧，用于处理带边界约束的优化问题。其核心步骤包括： 在每次迭代中，用二次模型近似目标函数，在信赖域内求解子问题。 若试探步超出可行域，通过反射操作将其映射回可行域。 根据实际目标函数下降量与预测下降量的比值，调整信赖域半径。 初始化 初始点 \(x^{(0)} = (0, 0)\)，目标函数值 \(f(x^{(0)}) = (0-2)^2 + (0-1)^2 = 5\)。初始信赖域半径 \(\Delta_ 0 = 0.5\)，容忍误差 \(\epsilon = 10^{-6}\)。 第一次迭代（k=0） 构建二次模型 ： 在 \(x^{(0)}\) 处计算梯度 \(\nabla f(x) = [ 2(x_ 1-2), 2(x_ 2-1)]^T = [ -4, -2 ]^T\)，Hessian矩阵 \(H = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}\)。 二次模型为： \[ m_ k(p) = f(x^{(k)}) + \nabla f(x^{(k)})^T p + \frac{1}{2} p^T H p = 5 + [ -4, -2 ] p + \frac{1}{2} p^T \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} p. \] 求解信赖域子问题 ： 约束为 \(\|p\| \leq \Delta_ 0 = 0.5\)。由于梯度方向为 \([ -4, -2 ]^T\)，最优步长沿负梯度方向取边界值： \[ p^{(0)} = -\frac{\Delta_ 0}{\|\nabla f\|} \nabla f = -\frac{0.5}{\sqrt{20}} [ -4, -2]^T \approx [ 0.2236, 0.1118 ]^T. \] 反射检查 ： 试探点 \(x^{(0)} + p^{(0)} \approx (0.2236, 0.1118)\) 满足所有约束（验证：\(0.2236+0.1118=0.3354 \leq 2\)，其他约束均满足），无需反射。 计算实际下降比 ： 实际函数值 \(f(x^{(0)}+p^{(0)}) \approx (0.2236-2)^2 + (0.1118-1)^2 \approx 4.277\)， 预测下降量 \(\Delta m = m(0) - m(p^{(0)}) \approx 5 - 4.277 = 0.723\)， 实际下降量 \(\Delta f = f(x^{(0)}) - f(x^{(0)}+p^{(0)}) \approx 5 - 4.277 = 0.723\)， 比值 \(\rho = \frac{\Delta f}{\Delta m} = 1 > 0.75\)，接受试探点，并扩大信赖域半径 \(\Delta_ 1 = 1.5 \Delta_ 0 = 0.75\)。 更新 \(x^{(1)} = (0.2236, 0.1118)\)。 第二次迭代（k=1） 构建二次模型 ： 梯度 \(\nabla f(x^{(1)}) \approx [ -3.5528, -1.7764 ]^T\)，Hessian 不变。 求解子问题 ： 沿负梯度方向取步长 \(p^{(1)} \approx [ 0.3354, 0.1677 ]^T\)（满足 \(\|p\| \leq 0.75\)）。 反射检查 ： 试探点 \(x^{(1)}+p^{(1)} \approx (0.5590, 0.2795)\) 仍满足约束，无需反射。 计算实际下降比 ： \(f(x^{(1)}+p^{(1)}) \approx 3.625\)，\(\rho \approx \frac{4.277-3.625}{4.277-3.625} = 1\)，接受点并扩大信赖域至 \(\Delta_ 2 = 1.125\)。 更新 \(x^{(2)} = (0.5590, 0.2795)\)。 后续迭代与收敛 重复上述过程，迭代点向约束边界 \(x_ 1 + x_ 2 = 2\) 靠近。当梯度在可行域内的投影很小时停止。最终解接近最优解 \(x^* = (1.5, 0.5)\)，对应 \(f(x^* ) = 0.5\)。 关键点总结 反射步骤仅在试探步违反边界约束时触发，将点映射回可行域。 比值 \(\rho\) 决定是否接受试探步和调整信赖域半径： \(\rho > 0.75\)：扩大半径； \(\rho < 0.25\)：缩小半径； 中间值：保持半径。 收敛条件为梯度范数小于容忍误差或信赖域半径过小。 通过以上步骤，信赖域反射算法在保证可行性的同时逐步逼近最优解。