非线性规划中的序列线性规划-积极集混合算法基础题
字数 2574 2025-11-05 23:45:42

非线性规划中的序列线性规划-积极集混合算法基础题

题目描述
考虑非线性规划问题：
minimize \(f(x) = x_1^2 + 2x_2^2 - 2x_1x_2 - 4x_1\)
subject to:
\(g_1(x) = x_1 + x_2 - 2 \leq 0\)
\(g_2(x) = -x_1 + 2x_2 - 3 \leq 0\)
\(x_1 \geq 0, x_2 \geq 0\)
初始点 \(x^{(0)} = (0, 0)\)，要求使用序列线性规划（SLP）结合积极集策略迭代求解，并解释积极集如何动态调整以处理约束。

解题过程

1. 算法原理概述
序列线性规划-积极集混合算法的核心思想是：

  • 在每次迭代中，将非线性目标函数和约束在当前点线性化（一阶泰勒展开），构建一个线性规划子问题。
  • 利用积极集策略识别当前点处起作用的约束（即等式约束或紧约束），仅将这些约束纳入子问题，减少计算量。
  • 求解线性规划子问题，得到搜索方向，再通过步长控制确保收敛。

2. 初始点与线性化
初始点 \(x^{(0)} = (0, 0)\)，计算目标函数和约束的梯度：

  • \(\nabla f(x) = [2x_1 - 2x_2 - 4, 4x_2 - 2x_1]\) → 在 \(x^{(0)}\) 处：\(\nabla f(0,0) = (-4, 0)\)
  • \(\nabla g_1(x) = (1, 1)\), \(\nabla g_2(x) = (-1, 2)\)
  • 约束函数值：\(g_1(0,0) = -2 \leq 0\)（非积极），\(g_2(0,0) = -3 \leq 0\)（非积极），边界约束 \(x_1 \geq 0, x_2 \geq 0\) 在 \((0,0)\) 处为积极约束。

积极集定义：当前点处满足等式或边界紧的约束集合。此处积极集为 \(\{x_1 \geq 0, x_2 \geq 0\}\)。

3. 构建第一个线性规划子问题
在 \(x^{(0)}\) 处线性化目标函数：
\(f(x) \approx f(0,0) + \nabla f(0,0)^T (x - x^{(0)}) = 0 + (-4, 0)^T (x_1, x_2) = -4x_1\)
约束线性化后，仅保留积极约束的线性近似：

  • \(x_1 \geq 0\), \(x_2 \geq 0\)（直接作为线性约束）
  • 其他约束（\(g_1, g_2\)）当前非积极，暂时忽略，但需在迭代中检验是否被违反。

子问题：
minimize \(-4x_1\)
subject to \(x_1 \geq 0, x_2 \geq 0\)
解此无上界问题：沿 \(-x_1\) 方向减小，需限制步长以避免过度偏离实际非线性问题。引入信赖域约束 \(\|x - x^{(0)}\| \leq \Delta\)（设初始 \(\Delta = 0.5\)），则子问题变为：
minimize \(-4x_1\)
s.t. \(x_1 \geq 0, x_2 \geq 0\), \(x_1^2 + x_2^2 \leq 0.25\)
最优解在信赖域边界上：令 \(x_2 = 0\)，则 \(x_1 = 0.5\)，得 \(x^{(1)} = (0.5, 0)\)。

4. 积极集更新与可行性检验
在 \(x^{(1)} = (0.5, 0)\) 处：

  • 计算约束：\(g_1(0.5,0) = -1.5 \leq 0\)（非积极），\(g_2(0.5,0) = -3.5 \leq 0\)（非积极），边界约束 \(x_2 \geq 0\) 积极。
  • 新积极集：\(\{x_2 \geq 0\}\)（注意 \(x_1 \geq 0\) 不再积极，因 \(x_1 = 0.5 > 0\)）。

5. 第二次迭代
在 \(x^{(1)}\) 处线性化：
\(\nabla f(0.5, 0) = (-3, -1)\)
目标近似：\(f(x) \approx f(0.5,0) + (-3, -1)^T (x_1 - 0.5, x_2) = -2.25 - 3x_1 - x_2 + 1.5 = -0.75 - 3x_1 - x_2\)
子问题（含信赖域 \(\Delta = 0.5\)）：
minimize \(-3x_1 - x_2\)
s.t. \(x_2 \geq 0\), \((x_1 - 0.5)^2 + x_2^2 \leq 0.25\)
解此问题：梯度方向为 \((-3, -1)\)，在圆内最小化。通过拉格朗日法或几何分析，得最优解为沿方向 \((3, 1)\) 的负投影（需归一化）。计算得 \(x^{(2)} \approx (0.86, 0.29)\)。

6. 约束处理与收敛判断
在 \(x^{(2)}\) 处检验约束：

  • \(g_1(0.86, 0.29) = 1.15 - 2 = -0.85 \leq 0\)（满足）
  • \(g_2(0.86, 0.29) = -0.86 + 0.58 - 3 = -3.28 \leq 0\)（满足）
    边界约束均满足。计算目标函数减少量 \(|f(x^{(2)}) - f(x^{(1)})|\)，若小于阈值（如 0.01），则停止；否则继续迭代并调整信赖域半径。

7. 算法总结

  • 积极集动态调整：每次迭代后，重新评估约束状态，移除不再积极的约束，添加新违反或紧的约束。
  • 收敛性：通过线性逼近和信赖域控制，确保序列逼近原问题的最优解。
  • 优势：结合SLP的简单性和积极集的高效性，适用于中等规模非线性约束问题。

通过以上步骤，可逐步逼近最优解 \(x^* \approx (1.33, 0.67)\)（实际解析解可通过KKT条件验证）。

非线性规划中的序列线性规划-积极集混合算法基础题 题目描述 考虑非线性规划问题： minimize \( f(x) = x_ 1^2 + 2x_ 2^2 - 2x_ 1x_ 2 - 4x_ 1 \) subject to: \( g_ 1(x) = x_ 1 + x_ 2 - 2 \leq 0 \) \( g_ 2(x) = -x_ 1 + 2x_ 2 - 3 \leq 0 \) \( x_ 1 \geq 0, x_ 2 \geq 0 \) 初始点 \( x^{(0)} = (0, 0) \)，要求使用序列线性规划（SLP）结合积极集策略迭代求解，并解释积极集如何动态调整以处理约束。 解题过程 1. 算法原理概述 序列线性规划-积极集混合算法的核心思想是： 在每次迭代中，将非线性目标函数和约束在当前点线性化（一阶泰勒展开），构建一个线性规划子问题。 利用积极集策略识别当前点处起作用的约束（即等式约束或紧约束），仅将这些约束纳入子问题，减少计算量。 求解线性规划子问题，得到搜索方向，再通过步长控制确保收敛。 2. 初始点与线性化 初始点 \( x^{(0)} = (0, 0) \)，计算目标函数和约束的梯度： \( \nabla f(x) = [ 2x_ 1 - 2x_ 2 - 4, 4x_ 2 - 2x_ 1 ] \) → 在 \( x^{(0)} \) 处：\( \nabla f(0,0) = (-4, 0) \) \( \nabla g_ 1(x) = (1, 1) \), \( \nabla g_ 2(x) = (-1, 2) \) 约束函数值：\( g_ 1(0,0) = -2 \leq 0 \)（非积极），\( g_ 2(0,0) = -3 \leq 0 \)（非积极），边界约束 \( x_ 1 \geq 0, x_ 2 \geq 0 \) 在 \( (0,0) \) 处为积极约束。 积极集定义 ：当前点处满足等式或边界紧的约束集合。此处积极集为 \( \{x_ 1 \geq 0, x_ 2 \geq 0\} \)。 3. 构建第一个线性规划子问题 在 \( x^{(0)} \) 处线性化目标函数： \( f(x) \approx f(0,0) + \nabla f(0,0)^T (x - x^{(0)}) = 0 + (-4, 0)^T (x_ 1, x_ 2) = -4x_ 1 \) 约束线性化后，仅保留积极约束的线性近似： \( x_ 1 \geq 0 \), \( x_ 2 \geq 0 \)（直接作为线性约束） 其他约束（\( g_ 1, g_ 2 \)）当前非积极，暂时忽略，但需在迭代中检验是否被违反。 子问题： minimize \( -4x_ 1 \) subject to \( x_ 1 \geq 0, x_ 2 \geq 0 \) 解此无上界问题：沿 \( -x_ 1 \) 方向减小，需限制步长以避免过度偏离实际非线性问题。引入信赖域约束 \( \|x - x^{(0)}\| \leq \Delta \)（设初始 \( \Delta = 0.5 \)），则子问题变为： minimize \( -4x_ 1 \) s.t. \( x_ 1 \geq 0, x_ 2 \geq 0 \), \( x_ 1^2 + x_ 2^2 \leq 0.25 \) 最优解在信赖域边界上：令 \( x_ 2 = 0 \)，则 \( x_ 1 = 0.5 \)，得 \( x^{(1)} = (0.5, 0) \)。 4. 积极集更新与可行性检验 在 \( x^{(1)} = (0.5, 0) \) 处： 计算约束：\( g_ 1(0.5,0) = -1.5 \leq 0 \)（非积极），\( g_ 2(0.5,0) = -3.5 \leq 0 \)（非积极），边界约束 \( x_ 2 \geq 0 \) 积极。 新积极集：\( \{x_ 2 \geq 0\} \)（注意 \( x_ 1 \geq 0 \) 不再积极，因 \( x_ 1 = 0.5 > 0 \)）。 5. 第二次迭代 在 \( x^{(1)} \) 处线性化： \( \nabla f(0.5, 0) = (-3, -1) \) 目标近似：\( f(x) \approx f(0.5,0) + (-3, -1)^T (x_ 1 - 0.5, x_ 2) = -2.25 - 3x_ 1 - x_ 2 + 1.5 = -0.75 - 3x_ 1 - x_ 2 \) 子问题（含信赖域 \( \Delta = 0.5 \)）： minimize \( -3x_ 1 - x_ 2 \) s.t. \( x_ 2 \geq 0 \), \( (x_ 1 - 0.5)^2 + x_ 2^2 \leq 0.25 \) 解此问题：梯度方向为 \( (-3, -1) \)，在圆内最小化。通过拉格朗日法或几何分析，得最优解为沿方向 \( (3, 1) \) 的负投影（需归一化）。计算得 \( x^{(2)} \approx (0.86, 0.29) \)。 6. 约束处理与收敛判断 在 \( x^{(2)} \) 处检验约束： \( g_ 1(0.86, 0.29) = 1.15 - 2 = -0.85 \leq 0 \)（满足） \( g_ 2(0.86, 0.29) = -0.86 + 0.58 - 3 = -3.28 \leq 0 \)（满足） 边界约束均满足。计算目标函数减少量 \( |f(x^{(2)}) - f(x^{(1)})| \)，若小于阈值（如 0.01），则停止；否则继续迭代并调整信赖域半径。 7. 算法总结 积极集动态调整 ：每次迭代后，重新评估约束状态，移除不再积极的约束，添加新违反或紧的约束。 收敛性 ：通过线性逼近和信赖域控制，确保序列逼近原问题的最优解。 优势 ：结合SLP的简单性和积极集的高效性，适用于中等规模非线性约束问题。 通过以上步骤，可逐步逼近最优解 \( x^* \approx (1.33, 0.67) \)（实际解析解可通过KKT条件验证）。