自适应信赖域序列二次规划(TR-SQP)算法进阶题
字数 3891 2025-12-12 20:55:17

自适应信赖域序列二次规划(TR-SQP)算法进阶题

题目描述
考虑以下带非线性不等式约束的优化问题：

\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) = e^{x_1 + 2x_2} + x_1^2 + 3x_1 x_2 + x_2^4 \\ \text{s.t.} \quad & c_1(x) = x_1^2 + x_2^2 - 4 \le 0, \\ & c_2(x) = -\sin(x_1 x_2) + 0.5 \le 0, \\ & -3 \le x_1, x_2 \le 3. \end{aligned} \]

其中目标函数 \(f(x)\) 非凸且非线性程度高，约束 \(c_1(x)\) 为凸二次不等式，\(c_2(x)\) 为非线性非凸约束。变量边界构成闭箱约束。要求使用自适应信赖域序列二次规划（Adaptive Trust Region SQP, TR-SQP） 算法求解该问题，重点在于信赖域半径的自动调整策略、子问题的构造与求解，以及如何处理非凸约束带来的收敛性挑战。

解题过程循序渐进讲解

步骤1：算法框架理解
自适应TR-SQP是序列二次规划（SQP）与信赖域（Trust Region）结合的方法，在每一步迭代中：

  1. 在当前点 \(x_k\) 构造目标函数和约束的局部二次/线性近似模型。
  2. 在信赖域内求解该近似子问题，得到试探步 \(p_k\)。
  3. 根据实际目标下降与预测下降的比值，自适应调整信赖域半径 \(\Delta_k\)，并决定是否接受该步。
    核心优势：信赖域机制保证全局收敛，自适应调整提升效率，适用于非凸问题。

步骤2：构建拉格朗日函数与近似子问题
首先，定义拉格朗日函数：

\[L(x, \lambda) = f(x) + \lambda_1 c_1(x) + \lambda_2 c_2(x), \]

其中 \(\lambda = (\lambda_1, \lambda_2) \ge 0\) 为不等式约束的拉格朗日乘子。

在第 \(k\) 次迭代点 \(x_k\)，构造二次规划（QP）子问题：

\[\begin{aligned} \min_{p \in \mathbb{R}^2} \quad & f_k + \nabla f_k^\top p + \frac{1}{2} p^\top B_k p \\ \text{s.t.} \quad & c_{1,k} + \nabla c_{1,k}^\top p \le 0, \\ & c_{2,k} + \nabla c_{2,k}^\top p \le 0, \\ & -3 \le x_k + p \le 3, \\ & \|p\| \le \Delta_k. \end{aligned} \]

其中：

  • \(f_k = f(x_k)\), \(c_{i,k} = c_i(x_k)\), \(\nabla f_k, \nabla c_{i,k}\) 为对应梯度。
  • \(B_k\) 是拉格朗日函数海森矩阵的近似（常用BFGS等拟牛顿法更新）。
  • \(\| \cdot \|\) 通常取2-范数，\(\Delta_k > 0\) 是当前信赖域半径。

步骤3：计算梯度与海森近似
本题中 \(x = (x_1, x_2)^\top\)，具体表达式：

  • \(\nabla f(x) = \begin{bmatrix} e^{x_1+2x_2} + 2x_1 + 3x_2 \\ 2e^{x_1+2x_2} + 3x_1 + 4x_2^3 \end{bmatrix}\)
  • \(\nabla c_1(x) = \begin{bmatrix} 2x_1 \\ 2x_2 \end{bmatrix}\)
  • \(\nabla c_2(x) = \begin{bmatrix} -x_2 \cos(x_1 x_2) \\ -x_1 \cos(x_1 x_2) \end{bmatrix}\)

海森近似 \(B_k\) 可通过BFGS公式更新：

\[B_{k+1} = B_k + \frac{y_k y_k^\top}{y_k^\top s_k} - \frac{B_k s_k s_k^\top B_k}{s_k^\top B_k s_k}, \]

其中 \(s_k = x_{k+1} - x_k\), \(y_k = \nabla_x L(x_{k+1}, \lambda_{k+1}) - \nabla_x L(x_k, \lambda_{k+1})\)，初始 \(B_0 = I\)（单位阵）。

步骤4：求解QP子问题
子问题是带线性约束的二次规划，变量为 \(p = (p_1, p_2)^\top\)。由于规模小，可用积极集法或内点法精确解出 \(p_k\) 及对应的乘子估计 \(\lambda_{k+1}\)。注意：

  • 边界约束 \(-3 \le x_k + p \le 3\) 也需线性化。
  • 信赖域约束 \(\|p\| \le \Delta_k\) 是凸二次约束，可等价转化为二阶锥约束或直接作为球约束处理。

步骤5：自适应信赖域调整策略
计算实际下降量 \(\text{ared}_k = f(x_k) - f(x_k + p_k)\) 和预测下降量 \(\text{pred}_k = -\left( \nabla f_k^\top p_k + \frac{1}{2} p_k^\top B_k p_k \right)\)。
定义比值：

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

根据 \(\rho_k\) 调整信赖域半径：

  • 若 \(\rho_k < 0.1\)：拒绝步长，缩小半径 \(\Delta_{k+1} = 0.5 \Delta_k\)，不更新 \(x_k\)。
  • 若 \(0.1 \le \rho_k < 0.75\)：接受步长 \(x_{k+1} = x_k + p_k\)，保持半径 \(\Delta_{k+1} = \Delta_k\)。
  • 若 \(\rho_k \ge 0.75\)：接受步长，扩大半径 \(\Delta_{k+1} = \min(2\Delta_k, \Delta_{\max})\)，其中 \(\Delta_{\max}\) 为预设上限（例如5.0）。

步骤6：处理非凸约束 \(c_2(x)\) 的挑战
由于 \(c_2(x)\) 非凸，其线性化可能不可行。策略：

  • 在QP子问题求解时，若检测到不可行，可引入松弛变量或采用弹性模式（elastic mode），暂时放宽约束保证子问题有解，并在后续迭代中收紧。
  • 另一种做法是使用滤子（filter）结合信赖域，避免Maratos效应（即目标下降但约束违反增加导致拒绝步长）。

步骤7：迭代终止条件
当满足以下条件之一时停止：

  1. 步长范数 \(\|p_k\| < \epsilon_1\)（例如 \(10^{-6}\)）。
  2. 约束违反度 \(\max(0, c_1(x_k), c_2(x_k)) < \epsilon_2\)（例如 \(10^{-6}\)）。
  3. 一阶最优性条件（KKT条件）残差小于容差。

步骤8：算法流程总结

  1. 初始化：给定 \(x_0, \Delta_0 > 0, B_0 = I\)，设定 \(\lambda_0 = 0\)，容许误差 \(\epsilon_1, \epsilon_2\)。
  2. 对 \(k=0,1,2,\dots\)：
    a. 计算 \(f_k, \nabla f_k, c_{i,k}, \nabla c_{i,k}\)。
    b. 求解QP子问题得 \(p_k, \lambda_{k+1}\)。
    c. 若子问题不可行，进入弹性模式或缩减 \(\Delta_k\) 后重解。
    d. 计算 \(\rho_k\)，按上述策略更新 \(\Delta_{k+1}\) 和 \(x_{k+1}\)。
    e. 用BFGS更新 \(B_{k+1}\)。
    f. 检查终止条件，满足则输出 \(x_{k+1}\) 为近似最优解。

步骤9：实例数值演示（简要）
假设从初始点 \(x_0 = (1, 1)\) 开始，\(\Delta_0 = 1\)：

  • 计算得 \(f_0 \approx 33.6\), \(c_1(1,1) = -2 \le 0\)（可行），\(c_2(1,1) \approx 0.16 \le 0\)（临界）。
  • 子问题求解得 \(p_0 \approx (-0.3, -0.4)\)，\(\rho_0 > 0.75\)，接受并扩大信赖域。
  • 几次迭代后趋近局部最优解 \(x^* \approx (0.5, -1.2)\)，\(f^* \approx 1.85\)，约束满足。

该算法通过自适应信赖域控制步长可靠性，结合SQP的快速局部收敛，有效处理非凸约束，适合中低维复杂非线性规划。

自适应信赖域序列二次规划(TR-SQP)算法进阶题 题目描述 考虑以下带非线性不等式约束的优化问题： \[ \begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & f(x) = e^{x_ 1 + 2x_ 2} + x_ 1^2 + 3x_ 1 x_ 2 + x_ 2^4 \\ \text{s.t.} \quad & c_ 1(x) = x_ 1^2 + x_ 2^2 - 4 \le 0, \\ & c_ 2(x) = -\sin(x_ 1 x_ 2) + 0.5 \le 0, \\ & -3 \le x_ 1, x_ 2 \le 3. \end{aligned} \] 其中目标函数 \(f(x)\) 非凸且非线性程度高，约束 \(c_ 1(x)\) 为凸二次不等式，\(c_ 2(x)\) 为非线性非凸约束。变量边界构成闭箱约束。要求使用 自适应信赖域序列二次规划（Adaptive Trust Region SQP, TR-SQP） 算法求解该问题，重点在于信赖域半径的自动调整策略、子问题的构造与求解，以及如何处理非凸约束带来的收敛性挑战。 解题过程循序渐进讲解 步骤1：算法框架理解 自适应TR-SQP是序列二次规划（SQP）与信赖域（Trust Region）结合的方法，在每一步迭代中： 在当前点 \(x_ k\) 构造目标函数和约束的局部二次/线性近似模型。 在信赖域内求解该近似子问题，得到试探步 \(p_ k\)。 根据实际目标下降与预测下降的比值，自适应调整信赖域半径 \(\Delta_ k\)，并决定是否接受该步。 核心优势：信赖域机制保证全局收敛，自适应调整提升效率，适用于非凸问题。 步骤2：构建拉格朗日函数与近似子问题 首先，定义拉格朗日函数： \[ L(x, \lambda) = f(x) + \lambda_ 1 c_ 1(x) + \lambda_ 2 c_ 2(x), \] 其中 \(\lambda = (\lambda_ 1, \lambda_ 2) \ge 0\) 为不等式约束的拉格朗日乘子。 在第 \(k\) 次迭代点 \(x_ k\)，构造二次规划（QP）子问题： \[ \begin{aligned} \min_ {p \in \mathbb{R}^2} \quad & f_ k + \nabla f_ k^\top p + \frac{1}{2} p^\top B_ k p \\ \text{s.t.} \quad & c_ {1,k} + \nabla c_ {1,k}^\top p \le 0, \\ & c_ {2,k} + \nabla c_ {2,k}^\top p \le 0, \\ & -3 \le x_ k + p \le 3, \\ & \|p\| \le \Delta_ k. \end{aligned} \] 其中： \(f_ k = f(x_ k)\), \(c_ {i,k} = c_ i(x_ k)\), \(\nabla f_ k, \nabla c_ {i,k}\) 为对应梯度。 \(B_ k\) 是拉格朗日函数海森矩阵的近似（常用BFGS等拟牛顿法更新）。 \(\| \cdot \|\) 通常取2-范数，\(\Delta_ k > 0\) 是当前信赖域半径。 步骤3：计算梯度与海森近似 本题中 \(x = (x_ 1, x_ 2)^\top\)，具体表达式： \(\nabla f(x) = \begin{bmatrix} e^{x_ 1+2x_ 2} + 2x_ 1 + 3x_ 2 \\ 2e^{x_ 1+2x_ 2} + 3x_ 1 + 4x_ 2^3 \end{bmatrix}\) \(\nabla c_ 1(x) = \begin{bmatrix} 2x_ 1 \\ 2x_ 2 \end{bmatrix}\) \(\nabla c_ 2(x) = \begin{bmatrix} -x_ 2 \cos(x_ 1 x_ 2) \\ -x_ 1 \cos(x_ 1 x_ 2) \end{bmatrix}\) 海森近似 \(B_ k\) 可通过BFGS公式更新： \[ B_ {k+1} = B_ k + \frac{y_ k y_ k^\top}{y_ k^\top s_ k} - \frac{B_ k s_ k s_ k^\top B_ k}{s_ k^\top B_ k s_ k}, \] 其中 \(s_ k = x_ {k+1} - x_ k\), \(y_ k = \nabla_ x L(x_ {k+1}, \lambda_ {k+1}) - \nabla_ x L(x_ k, \lambda_ {k+1})\)，初始 \(B_ 0 = I\)（单位阵）。 步骤4：求解QP子问题 子问题是带线性约束的二次规划，变量为 \(p = (p_ 1, p_ 2)^\top\)。由于规模小，可用积极集法或内点法精确解出 \(p_ k\) 及对应的乘子估计 \(\lambda_ {k+1}\)。注意： 边界约束 \(-3 \le x_ k + p \le 3\) 也需线性化。 信赖域约束 \(\|p\| \le \Delta_ k\) 是凸二次约束，可等价转化为二阶锥约束或直接作为球约束处理。 步骤5：自适应信赖域调整策略 计算实际下降量 \(\text{ared}_ k = f(x_ k) - f(x_ k + p_ k)\) 和预测下降量 \(\text{pred}_ k = -\left( \nabla f_ k^\top p_ k + \frac{1}{2} p_ k^\top B_ k p_ k \right)\)。 定义比值： \[ \rho_ k = \frac{\text{ared}_ k}{\text{pred}_ k}. \] 根据 \(\rho_ k\) 调整信赖域半径： 若 \(\rho_ k < 0.1\)：拒绝步长，缩小半径 \(\Delta_ {k+1} = 0.5 \Delta_ k\)，不更新 \(x_ k\)。 若 \(0.1 \le \rho_ k < 0.75\)：接受步长 \(x_ {k+1} = x_ k + p_ k\)，保持半径 \(\Delta_ {k+1} = \Delta_ k\)。 若 \(\rho_ k \ge 0.75\)：接受步长，扩大半径 \(\Delta_ {k+1} = \min(2\Delta_ k, \Delta_ {\max})\)，其中 \(\Delta_ {\max}\) 为预设上限（例如5.0）。 步骤6：处理非凸约束 \(c_ 2(x)\) 的挑战 由于 \(c_ 2(x)\) 非凸，其线性化可能不可行。策略： 在QP子问题求解时，若检测到不可行，可引入松弛变量或采用弹性模式（elastic mode），暂时放宽约束保证子问题有解，并在后续迭代中收紧。 另一种做法是使用滤子（filter）结合信赖域，避免Maratos效应（即目标下降但约束违反增加导致拒绝步长）。 步骤7：迭代终止条件 当满足以下条件之一时停止： 步长范数 \(\|p_ k\| < \epsilon_ 1\)（例如 \(10^{-6}\)）。 约束违反度 \(\max(0, c_ 1(x_ k), c_ 2(x_ k)) < \epsilon_ 2\)（例如 \(10^{-6}\)）。 一阶最优性条件（KKT条件）残差小于容差。 步骤8：算法流程总结 初始化：给定 \(x_ 0, \Delta_ 0 > 0, B_ 0 = I\)，设定 \(\lambda_ 0 = 0\)，容许误差 \(\epsilon_ 1, \epsilon_ 2\)。 对 \(k=0,1,2,\dots\)： a. 计算 \(f_ k, \nabla f_ k, c_ {i,k}, \nabla c_ {i,k}\)。 b. 求解QP子问题得 \(p_ k, \lambda_ {k+1}\)。 c. 若子问题不可行，进入弹性模式或缩减 \(\Delta_ k\) 后重解。 d. 计算 \(\rho_ k\)，按上述策略更新 \(\Delta_ {k+1}\) 和 \(x_ {k+1}\)。 e. 用BFGS更新 \(B_ {k+1}\)。 f. 检查终止条件，满足则输出 \(x_ {k+1}\) 为近似最优解。 步骤9：实例数值演示（简要） 假设从初始点 \(x_ 0 = (1, 1)\) 开始，\(\Delta_ 0 = 1\)： 计算得 \(f_ 0 \approx 33.6\), \(c_ 1(1,1) = -2 \le 0\)（可行），\(c_ 2(1,1) \approx 0.16 \le 0\)（临界）。 子问题求解得 \(p_ 0 \approx (-0.3, -0.4)\)，\(\rho_ 0 > 0.75\)，接受并扩大信赖域。 几次迭代后趋近局部最优解 \(x^* \approx (0.5, -1.2)\)，\(f^* \approx 1.85\)，约束满足。 该算法通过自适应信赖域控制步长可靠性，结合SQP的快速局部收敛，有效处理非凸约束，适合中低维复杂非线性规划。