非线性规划中的序列二次规划-近似Hessian-积极集-信赖域-乘子法混合算法基础题
字数 4721 2025-12-22 17:00:04

非线性规划中的序列二次规划-近似Hessian-积极集-信赖域-乘子法混合算法基础题

题目描述

考虑如下带非线性等式与不等式约束的优化问题：

\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & c_i(x) = 0, \quad i \in \mathcal{E}, \\ & c_i(x) \le 0, \quad i \in \mathcal{I}, \end{aligned} \]

其中目标函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 二阶连续可微，等式约束索引集 \(\mathcal{E}\) 和不等式约束索引集 \(\mathcal{I}\) 均为有限集，所有约束函数 \(c_i\) 也二阶连续可微。我们采用一种序列二次规划（SQP）框架，但为了避免计算精确Hessian矩阵的高代价，使用拟牛顿法（BFGS）更新近似Hessian，并嵌入积极集策略识别有效约束，结合信赖域控制步长可行性，同时用乘子法处理约束违反。该混合算法在保证收敛的同时兼顾计算效率，适合中小规模非凸问题。

本题要求：

  1. 推导该混合算法的完整迭代格式。
  2. 解释如何协调积极集更新、信赖域调整和乘子更新。
  3. 给出一个简单算例（如二维Rosenbrock函数加一个圆不等式约束）的迭代步骤演示。

第一步：建立SQP子问题并引入近似Hessian

在SQP中，每一步迭代求解一个二次规划（QP）子问题。在第 \(k\) 步，给定当前点 \(x_k\)、拉格朗日乘子估计 \(\lambda_k\) 和Hessian近似 \(B_k\)，子问题为：

\[\begin{aligned} \min_{d \in \mathbb{R}^n} \quad & \nabla f(x_k)^\top d + \frac{1}{2} d^\top B_k d \\ \text{s.t.} \quad & c_i(x_k) + \nabla c_i(x_k)^\top d = 0, \quad i \in \mathcal{E}, \\ & c_i(x_k) + \nabla c_i(x_k)^\top d \le 0, \quad i \in \mathcal{I}. \end{aligned} \]

  • 为何用 \(B_k\) 代替 \(\nabla^2_{xx} L(x_k, \lambda_k)\)：
    精确Hessian计算成本高，尤其当 \(n\) 较大时。BFGS拟牛顿法通过梯度信息更新 \(B_k\)，使其逐步逼近拉格朗日函数 \(L(x, \lambda) = f(x) + \sum \lambda_i c_i(x)\) 的Hessian。
  • BFGS更新公式（ damped BFGS 保证正定性）：

\[ s_k = x_{k+1} - x_k, \quad y_k = \nabla_x L(x_{k+1}, \lambda_k) - \nabla_x L(x_k, \lambda_k), \]

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

第二步：积极集策略识别有效约束

在求解QP子问题时，不等式约束可能不都起作用。积极集 \(\mathcal{A}_k \subseteq \mathcal{I}\) 包含在当前点“活动”的不等式约束（即 \(c_i(x_k) = 0\) 或虽 \(c_i(x_k) < 0\) 但在QP子问题中会阻碍步长 \(d\) 的约束）。

  • 识别规则：
    初始积极集可设为 \(\mathcal{A}_k = \{ i \in \mathcal{I} \mid c_i(x_k) \ge -\epsilon \}\)，\(\epsilon > 0\) 为容忍度。
    求解QP子问题时，只将积极集中的不等式约束作为等式约束处理，其余忽略，从而降低QP规模。
  • 更新时机：
    每步迭代后，检查新点 \(x_{k+1}\) 的约束违反情况，若某个 \(i \notin \mathcal{A}_k\) 在新点处 \(c_i(x_{k+1}) > 0\)，则将其加入积极集；若 \(i \in \mathcal{A}_k\) 但对应的乘子 \(\lambda_i \le 0\)（说明约束不再积极），则将其移除。

第三步：信赖域控制步长可行性

为防止二次模型在不稳定时步长过大，添加信赖域约束 \(\|d\| \le \Delta_k\) 到QP子问题中，其中 \(\Delta_k > 0\) 是信赖域半径。此时子问题变为：

\[\begin{aligned} \min_{d} \quad & \nabla f_k^\top d + \frac{1}{2} d^\top B_k d \\ \text{s.t.} \quad & c_i(x_k) + \nabla c_i(x_k)^\top d = 0, \; i \in \mathcal{E}, \\ & c_i(x_k) + \nabla c_i(x_k)^\top d \le 0, \; i \in \mathcal{A}_k, \\ & \|d\| \le \Delta_k. \end{aligned} \]

  • 实际比值 \(\rho_k = \frac{\text{实际下降量}}{\text{预测下降量}}\)，其中
    实际下降量 \(= f(x_k) - f(x_k + d_k)\)，
    预测下降量 \(= -\big( \nabla f_k^\top d_k + \frac{1}{2} d_k^\top B_k d_k \big)\)。
  • 调整规则：
    • 若 \(\rho_k\) 接近1（模型拟合好），扩大 \(\Delta_{k+1} = 2\Delta_k\)；
    • 若 \(\rho_k\) 过小（模型差），缩小 \(\Delta_{k+1} = 0.5\Delta_k\)；
    • 若 \(\rho_k\) 中等，保持 \(\Delta_{k+1} = \Delta_k\)。

第四步：乘子法处理约束违反

拉格朗日乘子 \(\lambda\) 的更新采用乘子法（Augmented Lagrangian风格），在每次迭代后更新：

\[\lambda_i^{k+1} = \lambda_i^k + \mu \, c_i(x_{k+1}), \quad \forall i \in \mathcal{E} \cup \mathcal{A}_k, \]

其中 \(\mu > 0\) 为惩罚参数。对于不等式约束，乘子被截断为非负：
\(\lambda_i^{k+1} = \max(0, \; \lambda_i^k + \mu \, c_i(x_{k+1}))\)，\(i \in \mathcal{I}\)。

乘子更新可看作对约束违反的惩罚加强，促使后续迭代更可行。

第五步：整体算法流程

  1. 初始化：选取初始点 \(x_0\)、初始乘子 \(\lambda_0\)、初始Hessian近似 \(B_0 = I\)、信赖域半径 \(\Delta_0\)、容忍度 \(\epsilon\)、惩罚参数 \(\mu\)。
  2. 循环直到收敛（如 \(\|\nabla_x L(x_k, \lambda_k)\| < \epsilon\) 且约束违反足够小）：
    a. 确定当前积极集 \(\mathcal{A}_k\)。
    b. 构建并求解带信赖域的QP子问题，得到步长 \(d_k\)。
    c. 计算实际比值 \(\rho_k\)，按规则更新 \(\Delta_{k+1}\)。
    d. 若 \(\rho_k > 0.1\)，接受步长：\(x_{k+1} = x_k + d_k\)；否则拒绝步长，保持 \(x_{k+1} = x_k\)。
    e. 用BFGS更新 \(B_{k+1}\)。
    f. 更新乘子 \(\lambda^{k+1}\)。
    g. 更新积极集 \(\mathcal{A}_{k+1}\)。
  3. 输出解 \(x^*\) 和乘子 \(\lambda^*\)。

第六步：算例演示（二维Rosenbrock函数加圆约束）

问题：

\[\min_{x_1, x_2} \; 100(x_2 - x_1^2)^2 + (1 - x_1)^2 \quad \text{s.t.} \quad x_1^2 + x_2^2 \le 2. \]

  • 初始化：\(x_0 = (-1, 1)\)，\(\lambda_0 = 0\)，\(B_0 = I\)，\(\Delta_0 = 1\)，\(\mu = 1\)，\(\epsilon = 10^{-3}\)。
  • 迭代1：
    • 约束值 \(c = x_1^2 + x_2^2 - 2 = 0\)，故 \(\mathcal{A}_0 = \{1\}\)（仅一个不等式约束）。
    • 梯度 \(\nabla f = (-400x_1(x_2 - x_1^2) - 2(1 - x_1), \; 200(x_2 - x_1^2))^\top = (402, 0)^\top\)。
    • 约束梯度 \(\nabla c = (2x_1, 2x_2)^\top = (-2, 2)^\top\)。
    • QP子问题：

\[ \min_d \; 402 d_1 + \frac{1}{2}(d_1^2 + d_2^2) \quad \text{s.t.} \; 0 + (-2, 2)^\top d \le 0, \; \|d\| \le 1. \]

解得 $d \approx (-0.707, -0.707)^\top$（向圆内移动）。
  • 计算 \(\rho_k \approx 0.8 > 0.1\)，接受步长，更新 \(x_1 = (-1.707, 0.293)^\top\)。
  • 更新乘子：\(\lambda_1 = \max(0, 0 + 1 \times c(x_1)) = 0\)（仍在边界内）。
  • BFGS更新 \(B_1\)。
  • 迭代2及之后：重复类似步骤，直至梯度与约束违反均小于 \(\epsilon\)。最终解接近约束边界上的最优点（约为 \(x^* \approx (0.786, 0.618)^\top\)，对应目标值约 \(0.046\)）。

第七步：关键点总结

  • 近似Hessian 降低计算量，BFGS保证正定且逐步逼近。
  • 积极集 缩减QP规模，动态调整提高效率。
  • 信赖域 控制步长，增强稳定性。
  • 乘子法 隐式处理约束违反，促进可行性。

此混合算法平衡了精度、稳定性和计算负担，适合求解中小规模非凸约束问题。实际实现中还需处理QP子问题不可行、BFGS修正条件等技术细节。

非线性规划中的序列二次规划-近似Hessian-积极集-信赖域-乘子法混合算法基础题 题目描述 考虑如下带非线性等式与不等式约束的优化问题： \[ \begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & c_ i(x) = 0, \quad i \in \mathcal{E}, \\ & c_ i(x) \le 0, \quad i \in \mathcal{I}, \end{aligned} \] 其中目标函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 二阶连续可微，等式约束索引集 \(\mathcal{E}\) 和不等式约束索引集 \(\mathcal{I}\) 均为有限集，所有约束函数 \(c_ i\) 也二阶连续可微。我们采用一种 序列二次规划（SQP）框架 ，但为了避免计算精确Hessian矩阵的高代价，使用 拟牛顿法（BFGS）更新近似Hessian ，并嵌入 积极集策略 识别有效约束，结合 信赖域 控制步长可行性，同时用 乘子法 处理约束违反。该混合算法在保证收敛的同时兼顾计算效率，适合中小规模非凸问题。 本题要求： 推导该混合算法的完整迭代格式。 解释如何协调积极集更新、信赖域调整和乘子更新。 给出一个简单算例（如二维Rosenbrock函数加一个圆不等式约束）的迭代步骤演示。 第一步：建立SQP子问题并引入近似Hessian 在SQP中，每一步迭代求解一个二次规划（QP）子问题。在第 \(k\) 步，给定当前点 \(x_ k\)、拉格朗日乘子估计 \(\lambda_ k\) 和Hessian近似 \(B_ k\)，子问题为： \[ \begin{aligned} \min_ {d \in \mathbb{R}^n} \quad & \nabla f(x_ k)^\top d + \frac{1}{2} d^\top B_ k d \\ \text{s.t.} \quad & c_ i(x_ k) + \nabla c_ i(x_ k)^\top d = 0, \quad i \in \mathcal{E}, \\ & c_ i(x_ k) + \nabla c_ i(x_ k)^\top d \le 0, \quad i \in \mathcal{I}. \end{aligned} \] 为何用 \(B_ k\) 代替 \(\nabla^2_ {xx} L(x_ k, \lambda_ k)\) ： 精确Hessian计算成本高，尤其当 \(n\) 较大时。BFGS拟牛顿法通过梯度信息更新 \(B_ k\)，使其逐步逼近拉格朗日函数 \(L(x, \lambda) = f(x) + \sum \lambda_ i c_ i(x)\) 的Hessian。 BFGS更新公式 （ damped BFGS 保证正定性）： \[ s_ k = x_ {k+1} - x_ k, \quad y_ k = \nabla_ x L(x_ {k+1}, \lambda_ k) - \nabla_ x L(x_ k, \lambda_ k), \] \[ B_ {k+1} = B_ k - \frac{B_ k s_ k s_ k^\top B_ k}{s_ k^\top B_ k s_ k} + \frac{y_ k y_ k^\top}{y_ k^\top s_ k}. \] 第二步：积极集策略识别有效约束 在求解QP子问题时，不等式约束可能不都起作用。 积极集 \(\mathcal{A}_ k \subseteq \mathcal{I}\) 包含在当前点“活动”的不等式约束（即 \(c_ i(x_ k) = 0\) 或虽 \(c_ i(x_ k) < 0\) 但在QP子问题中会阻碍步长 \(d\) 的约束）。 识别规则 ： 初始积极集可设为 \(\mathcal{A}_ k = \{ i \in \mathcal{I} \mid c_ i(x_ k) \ge -\epsilon \}\)，\(\epsilon > 0\) 为容忍度。 求解QP子问题时，只将积极集中的不等式约束作为等式约束处理，其余忽略，从而降低QP规模。 更新时机 ： 每步迭代后，检查新点 \(x_ {k+1}\) 的约束违反情况，若某个 \(i \notin \mathcal{A} k\) 在新点处 \(c_ i(x {k+1}) > 0\)，则将其加入积极集；若 \(i \in \mathcal{A}_ k\) 但对应的乘子 \(\lambda_ i \le 0\)（说明约束不再积极），则将其移除。 第三步：信赖域控制步长可行性 为防止二次模型在不稳定时步长过大，添加信赖域约束 \(\|d\| \le \Delta_ k\) 到QP子问题中，其中 \(\Delta_ k > 0\) 是信赖域半径。此时子问题变为： \[ \begin{aligned} \min_ {d} \quad & \nabla f_ k^\top d + \frac{1}{2} d^\top B_ k d \\ \text{s.t.} \quad & c_ i(x_ k) + \nabla c_ i(x_ k)^\top d = 0, \; i \in \mathcal{E}, \\ & c_ i(x_ k) + \nabla c_ i(x_ k)^\top d \le 0, \; i \in \mathcal{A}_ k, \\ & \|d\| \le \Delta_ k. \end{aligned} \] 实际比值 \(\rho_ k = \frac{\text{实际下降量}}{\text{预测下降量}}\)，其中 实际下降量 \(= f(x_ k) - f(x_ k + d_ k)\)， 预测下降量 \(= -\big( \nabla f_ k^\top d_ k + \frac{1}{2} d_ k^\top B_ k d_ k \big)\)。 调整规则 ： 若 \(\rho_ k\) 接近1（模型拟合好），扩大 \(\Delta_ {k+1} = 2\Delta_ k\)； 若 \(\rho_ k\) 过小（模型差），缩小 \(\Delta_ {k+1} = 0.5\Delta_ k\)； 若 \(\rho_ k\) 中等，保持 \(\Delta_ {k+1} = \Delta_ k\)。 第四步：乘子法处理约束违反 拉格朗日乘子 \(\lambda\) 的更新采用 乘子法（Augmented Lagrangian风格） ，在每次迭代后更新： \[ \lambda_ i^{k+1} = \lambda_ i^k + \mu \, c_ i(x_ {k+1}), \quad \forall i \in \mathcal{E} \cup \mathcal{A}_ k, \] 其中 \(\mu > 0\) 为惩罚参数。对于不等式约束，乘子被截断为非负： \(\lambda_ i^{k+1} = \max(0, \; \lambda_ i^k + \mu \, c_ i(x_ {k+1}))\)，\(i \in \mathcal{I}\)。 乘子更新可看作对约束违反的惩罚加强，促使后续迭代更可行。 第五步：整体算法流程 初始化 ：选取初始点 \(x_ 0\)、初始乘子 \(\lambda_ 0\)、初始Hessian近似 \(B_ 0 = I\)、信赖域半径 \(\Delta_ 0\)、容忍度 \(\epsilon\)、惩罚参数 \(\mu\)。 循环 直到收敛（如 \(\|\nabla_ x L(x_ k, \lambda_ k)\| < \epsilon\) 且约束违反足够小）： a. 确定当前积极集 \(\mathcal{A} k\)。 b. 构建并求解带信赖域的QP子问题，得到步长 \(d_ k\)。 c. 计算实际比值 \(\rho_ k\)，按规则更新 \(\Delta {k+1}\)。 d. 若 \(\rho_ k > 0.1\)，接受步长：\(x_ {k+1} = x_ k + d_ k\)；否则拒绝步长，保持 \(x_ {k+1} = x_ k\)。 e. 用BFGS更新 \(B_ {k+1}\)。 f. 更新乘子 \(\lambda^{k+1}\)。 g. 更新积极集 \(\mathcal{A}_ {k+1}\)。 输出解 \(x^ \) 和乘子 \(\lambda^ \)。 第六步：算例演示（二维Rosenbrock函数加圆约束） 问题 ： \[ \min_ {x_ 1, x_ 2} \; 100(x_ 2 - x_ 1^2)^2 + (1 - x_ 1)^2 \quad \text{s.t.} \quad x_ 1^2 + x_ 2^2 \le 2. \] 初始化 ：\(x_ 0 = (-1, 1)\)，\(\lambda_ 0 = 0\)，\(B_ 0 = I\)，\(\Delta_ 0 = 1\)，\(\mu = 1\)，\(\epsilon = 10^{-3}\)。 迭代1 ： 约束值 \(c = x_ 1^2 + x_ 2^2 - 2 = 0\)，故 \(\mathcal{A}_ 0 = \{1\}\)（仅一个不等式约束）。 梯度 \(\nabla f = (-400x_ 1(x_ 2 - x_ 1^2) - 2(1 - x_ 1), \; 200(x_ 2 - x_ 1^2))^\top = (402, 0)^\top\)。 约束梯度 \(\nabla c = (2x_ 1, 2x_ 2)^\top = (-2, 2)^\top\)。 QP子问题： \[ \min_ d \; 402 d_ 1 + \frac{1}{2}(d_ 1^2 + d_ 2^2) \quad \text{s.t.} \; 0 + (-2, 2)^\top d \le 0, \; \|d\| \le 1. \] 解得 \(d \approx (-0.707, -0.707)^\top\)（向圆内移动）。 计算 \(\rho_ k \approx 0.8 > 0.1\)，接受步长，更新 \(x_ 1 = (-1.707, 0.293)^\top\)。 更新乘子：\(\lambda_ 1 = \max(0, 0 + 1 \times c(x_ 1)) = 0\)（仍在边界内）。 BFGS更新 \(B_ 1\)。 迭代2及之后 ：重复类似步骤，直至梯度与约束违反均小于 \(\epsilon\)。最终解接近约束边界上的最优点（约为 \(x^* \approx (0.786, 0.618)^\top\)，对应目标值约 \(0.046\)）。 第七步：关键点总结 近似Hessian 降低计算量，BFGS保证正定且逐步逼近。 积极集 缩减QP规模，动态调整提高效率。 信赖域 控制步长，增强稳定性。 乘子法 隐式处理约束违反，促进可行性。 此混合算法平衡了精度、稳定性和计算负担，适合求解中小规模非凸约束问题。实际实现中还需处理QP子问题不可行、BFGS修正条件等技术细节。