非线性规划中的序列二次规划-乘子法-积极集-过滤器混合算法基础题

字数 2494 2025-11-06 12:40:15

非线性规划中的序列二次规划-乘子法-积极集-过滤器混合算法基础题

题目描述
考虑非线性约束优化问题：
最小化 \(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
约束条件：
\(g_1(x) = x_1 + x_2 - 2 \leq 0\)
\(g_2(x) = x_1^2 - x_2 \leq 0\)
初始点 \(x^{(0)} = (0, 0)\)，要求使用序列二次规划（SQP）框架，结合乘子法处理约束、积极集策略识别有效约束、过滤器机制避免试探点因约束违反或目标值退化而被拒绝。请详细说明迭代步骤。

解题过程

算法框架概述
- SQP将原问题转化为一系列二次规划子问题，通过迭代逼近解。
- 乘子法将约束罚函数与拉格朗日乘子结合，改善收敛性。
- 积极集策略仅对当前有效的约束（等式或活跃不等式）进行优化。
- 过滤器记录历史点的目标值 \(f\) 和约束违反度 \(\theta = \| \max(0, g_1, g_2) \|\)，新点需优于过滤器内所有点（即 \(f\) 或 \(\theta\) 至少一方更优）。
初始化
- 设当前点 \(x^{(0)} = (0, 0)\)，乘子 \(\lambda_1^{(0)} = 0, \lambda_2^{(0)} = 0\)，罚参数 \(\mu = 10\)。
- 过滤器初始为空。
第一轮迭代（k=0）
- 步骤1：计算约束违反度与梯度
  \(\theta(x^{(0)}) = \max(0, g_1, g_2) = \max(0, -2, 0) = 0\)（无违反）。
  \(\nabla f = (2(x_1-2), 2(x_2-1)) = (-4, -2)\)，\(\nabla g_1 = (1, 1)\)，\(\nabla g_2 = (2x_1, -1) = (0, -1)\)。
- 步骤2：构建二次规划子问题
  目标函数：
  \(\min_d \frac{1}{2} d^T \nabla^2 L d + \nabla f^T d\)，其中 \(\nabla^2 L\) 用单位矩阵近似（简化计算）。
  约束：仅考虑积极集（当前 \(g_1, g_2\) 均非严格活跃，但 \(g_2\) 在边界 \(g_2=0\)）。子问题为：
  \(\min_d \frac{1}{2} d^T I d + (-4, -2)^T d\)
  受限于 \(\nabla g_1^T d + g_1 \leq 0 \rightarrow d_1 + d_2 - 2 \leq 0\)
  \(\nabla g_2^T d + g_2 \leq 0 \rightarrow -d_2 \leq 0\)（因 \(g_2=0\)）。
  解得 \(d = (1, 0)\)（通过拉格朗日法或求解器），新试探点 \(x_{\text{trial}} = (1, 0)\)。
- 步骤3：过滤器判断
  计算 \(f_{\text{trial}} = (1-2)^2 + (0-1)^2 = 2\)，\(\theta_{\text{trial}} = \max(0, 1+0-2, 1-0) = \max(0, -1, 1) = 1\)。
  与过滤器内点比较（当前为空），接受该点，更新过滤器为 \(\{ (f=2, \theta=1) \}\)。
- 步骤4：更新乘子与罚参数
  乘子更新规则：\(\lambda_i^{(1)} = \max(0, \lambda_i^{(0)} + \mu g_i(x_{\text{trial}}))\)。
  \(\lambda_1^{(1)} = \max(0, 0 + 10 \cdot (-1)) = 0\)，\(\lambda_2^{(1)} = \max(0, 0 + 10 \cdot 1) = 10\)。
  罚参数 \(\mu\) 保持不变（因收敛良好）。
第二轮迭代（k=1）
- 当前点 \(x^{(1)} = (1, 0)\)，\(\nabla f = (-2, -2)\)，\(\nabla g_2 = (2, -1)\)。
- 子问题约束：积极集为 \(g_2\)（因 \(\lambda_2>0\)），子问题：
  \(\min_d \frac{1}{2} d^T I d + (-2, -2)^T d\)
  受限于 \(\nabla g_2^T d + g_2 \leq 0 \rightarrow 2d_1 - d_2 + 1 \leq 0\)。
  解得 \(d = (0.2, 1.4)\)，\(x_{\text{trial}} = (1.2, 1.4)\)。
- 过滤器检查：\(f_{\text{trial}} = 0.8\)，\(\theta_{\text{trial}} = \max(0, 1.2+1.4-2, 1.44-1.4) = 0.04\)。
  优于过滤器点 \((f=2, \theta=1)\)（目标值更小），接受，更新过滤器。
- 乘子更新：\(\lambda_1^{(2)} = 0\)，\(\lambda_2^{(2)} = \max(0, 10 + 10 \cdot 0.04) = 10.4\)。
收敛判断
- 后续迭代继续逼近解 \(x^* \approx (1, 1)\)（满足 \(g_1=0, g_2=0\)），当 \(\|d\|\) 和约束违反度小于阈值（如 \(10^{-6}\)）时停止。

关键点总结

乘子法避免罚参数无限增大，提升数值稳定性。
积极集减少子问题规模，过滤器平衡目标值与可行性。
实际应用中需处理海森矩阵近似（如BFGS更新）和约束线性化误差。

非线性规划中的序列二次规划-乘子法-积极集-过滤器混合算法基础题题目描述考虑非线性约束优化问题：最小化 \( f(x) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \) 约束条件： \( g_ 1(x) = x_ 1 + x_ 2 - 2 \leq 0 \) \( g_ 2(x) = x_ 1^2 - x_ 2 \leq 0 \) 初始点 \( x^{(0)} = (0, 0) \)，要求使用序列二次规划（SQP）框架，结合乘子法处理约束、积极集策略识别有效约束、过滤器机制避免试探点因约束违反或目标值退化而被拒绝。请详细说明迭代步骤。解题过程算法框架概述 SQP将原问题转化为一系列二次规划子问题，通过迭代逼近解。乘子法将约束罚函数与拉格朗日乘子结合，改善收敛性。积极集策略仅对当前有效的约束（等式或活跃不等式）进行优化。过滤器记录历史点的目标值 \( f \) 和约束违反度 \( \theta = \| \max(0, g_ 1, g_ 2) \| \)，新点需优于过滤器内所有点（即 \( f \) 或 \( \theta \) 至少一方更优）。初始化设当前点 \( x^{(0)} = (0, 0) \)，乘子 \( \lambda_ 1^{(0)} = 0, \lambda_ 2^{(0)} = 0 \)，罚参数 \( \mu = 10 \)。过滤器初始为空。第一轮迭代（k=0）步骤1：计算约束违反度与梯度 \( \theta(x^{(0)}) = \max(0, g_ 1, g_ 2) = \max(0, -2, 0) = 0 \)（无违反）。 \( \nabla f = (2(x_ 1-2), 2(x_ 2-1)) = (-4, -2) \)，\( \nabla g_ 1 = (1, 1) \)，\( \nabla g_ 2 = (2x_ 1, -1) = (0, -1) \)。步骤2：构建二次规划子问题目标函数： \( \min_ d \frac{1}{2} d^T \nabla^2 L d + \nabla f^T d \)，其中 \( \nabla^2 L \) 用单位矩阵近似（简化计算）。约束：仅考虑积极集（当前 \( g_ 1, g_ 2 \) 均非严格活跃，但 \( g_ 2 \) 在边界 \( g_ 2=0 \)）。子问题为： \( \min_ d \frac{1}{2} d^T I d + (-4, -2)^T d \) 受限于 \( \nabla g_ 1^T d + g_ 1 \leq 0 \rightarrow d_ 1 + d_ 2 - 2 \leq 0 \) \( \nabla g_ 2^T d + g_ 2 \leq 0 \rightarrow -d_ 2 \leq 0 \)（因 \( g_ 2=0 \)）。解得 \( d = (1, 0) \)（通过拉格朗日法或求解器），新试探点 \( x_ {\text{trial}} = (1, 0) \)。步骤3：过滤器判断计算 \( f_ {\text{trial}} = (1-2)^2 + (0-1)^2 = 2 \)，\( \theta_ {\text{trial}} = \max(0, 1+0-2, 1-0) = \max(0, -1, 1) = 1 \)。与过滤器内点比较（当前为空），接受该点，更新过滤器为 \( \{ (f=2, \theta=1) \} \)。步骤4：更新乘子与罚参数乘子更新规则：\( \lambda_ i^{(1)} = \max(0, \lambda_ i^{(0)} + \mu g_ i(x_ {\text{trial}})) \)。 \( \lambda_ 1^{(1)} = \max(0, 0 + 10 \cdot (-1)) = 0 \)，\( \lambda_ 2^{(1)} = \max(0, 0 + 10 \cdot 1) = 10 \)。罚参数 \( \mu \) 保持不变（因收敛良好）。第二轮迭代（k=1）当前点 \( x^{(1)} = (1, 0) \)，\( \nabla f = (-2, -2) \)，\( \nabla g_ 2 = (2, -1) \)。子问题约束：积极集为 \( g_ 2 \)（因 \( \lambda_ 2>0 \)），子问题： \( \min_ d \frac{1}{2} d^T I d + (-2, -2)^T d \) 受限于 \( \nabla g_ 2^T d + g_ 2 \leq 0 \rightarrow 2d_ 1 - d_ 2 + 1 \leq 0 \)。解得 \( d = (0.2, 1.4) \)，\( x_ {\text{trial}} = (1.2, 1.4) \)。过滤器检查：\( f_ {\text{trial}} = 0.8 \)，\( \theta_ {\text{trial}} = \max(0, 1.2+1.4-2, 1.44-1.4) = 0.04 \)。优于过滤器点 \( (f=2, \theta=1) \)（目标值更小），接受，更新过滤器。乘子更新：\( \lambda_ 1^{(2)} = 0 \)，\( \lambda_ 2^{(2)} = \max(0, 10 + 10 \cdot 0.04) = 10.4 \)。收敛判断后续迭代继续逼近解 \( x^* \approx (1, 1) \)（满足 \( g_ 1=0, g_ 2=0 \)），当 \( \|d\| \) 和约束违反度小于阈值（如 \( 10^{-6} \)）时停止。关键点总结乘子法避免罚参数无限增大，提升数值稳定性。积极集减少子问题规模，过滤器平衡目标值与可行性。实际应用中需处理海森矩阵近似（如BFGS更新）和约束线性化误差。