非线性规划中的序列二次约束规划法基础题
字数 2292 2025-10-28 11:34:06

非线性规划中的序列二次约束规划法基础题

题目描述
考虑非线性规划问题：
最小化 \(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
约束条件为：

  1. \(g_1(x) = x_1 + x_2 - 2 \leq 0\)
  2. \(g_2(x) = -x_1^2 + x_2 \geq 0\)
  3. \(x_1, x_2 \in \mathbb{R}\)。
    目标是在满足约束的前提下找到使 \(f(x)\) 最小的点 \(x^*\)。

解题过程
序列二次约束规划法（SQCP）通过迭代求解一系列二次约束子问题逼近原问题解。每个子问题在原当前点对目标函数和约束进行近似，并添加信赖域约束保证收敛。

步骤1: 问题重构

  1. 将不等式约束统一为 \(g_j(x) \leq 0\) 形式：
    • \(g_1(x) = x_1 + x_2 - 2 \leq 0\) 保持不变。
    • \(g_2(x) = -x_1^2 + x_2 \geq 0\) 改写为 \(g_2(x) = x_1^2 - x_2 \leq 0\)。
  2. 目标函数 \(f(x)\) 为二次函数，约束 \(g_2(x)\) 非线性，需线性化。

步骤2: 初始点选择
选择可行点作为初始点 \(x^{(0)}\)。验证可行性：

  • 若选 \(x^{(0)} = (0, 0)\)，则 \(g_1(0,0) = -2 \leq 0\)（满足），\(g_2(0,0) = 0 \leq 0\)（满足）。可行。

步骤3: 构建第k次迭代子问题
在点 \(x^{(k)}\) 处，对目标函数 \(f(x)\) 作二次近似，对非线性约束 \(g_2(x)\) 作线性近似：

  1. 目标函数近似：因 \(f(x)\) 本身为二次函数，直接保留原形式：
    \(f(x) \approx (x_1 - 2)^2 + (x_2 - 1)^2\)。
  2. 约束线性化：
    • \(g_1(x)\) 已是线性，保持不变。
    • \(g_2(x) = x_1^2 - x_2\) 在 \(x^{(k)}\) 处一阶泰勒展开：
      \(g_2(x) \approx g_2(x^{(k)}) + \nabla g_2(x^{(k)})^T (x - x^{(k)})\)，
      其中梯度 \(\nabla g_2(x) = (2x_1, -1)\)。
  3. 添加信赖域约束 \(\|x - x^{(k)}\| \leq \Delta_k\) 控制步长，\(\Delta_k > 0\) 为信赖域半径。

子问题形式为：
最小化 \(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
约束条件：

  • \(g_1(x) = x_1 + x_2 - 2 \leq 0\)
  • \(g_2(x^{(k)}) + \nabla g_2(x^{(k)})^T (x - x^{(k)}) \leq 0\)
  • \(\|x - x^{(k)}\| \leq \Delta_k\)。

步骤4: 迭代求解（以第0次迭代为例）
初始点 \(x^{(0)} = (0, 0)\)，设 \(\Delta_0 = 0.5\)。

  1. 计算梯度： \(\nabla g_2(0,0) = (0, -1)\)，\(g_2(0,0) = 0\)。
  2. 子问题约束：
    • \(g_1(x) \leq 0\)
    • \(0 + (0, -1) \cdot (x_1 - 0, x_2 - 0) \leq 0\) → \(-x_2 \leq 0\) → \(x_2 \geq 0\)（注意符号方向）。
    • \(\|x - (0,0)\| \leq 0.5\)。

子问题简化为：
最小化 \((x_1 - 2)^2 + (x_2 - 1)^2\)
约束：

  • \(x_1 + x_2 \leq 2\)
  • \(x_2 \geq 0\)
  • \(x_1^2 + x_2^2 \leq 0.25\)。
  1. 求解子问题：
    • 可行域是半径为0.5的圆盘与半平面 \(x_2 \geq 0\) 的交集，且包含在 \(x_1 + x_2 \leq 2\) 内（该约束此时松弛）。
    • 目标函数梯度指向点 (2,1)，在圆盘上最小值出现在圆盘边界靠近 (2,1) 的点。通过几何分析或拉格朗日法解出：最优解为 \(x^{(1)} \approx (0.5, 0)\)（详细计算略）。

步骤5: 更新与收敛检查

  1. 计算约束违反度：原约束 \(g_2(x) = x_1^2 - x_2\) 在 \(x^{(1)}\) 处值为 \(0.25 - 0 = 0.25 > 0\)，违反约束。
  2. 调整策略：由于约束被违反，需缩小信赖域半径（如 \(\Delta_1 = 0.3\)）或增加惩罚项，重新求解子问题。
  3. 重复迭代直至 \(\|x^{(k+1)} - x^{(k)}\|\) 和约束违反度小于容忍值（如 \(10^{-6}\)）。

最终解
持续迭代后，收敛至可行点 \(x^* \approx (1, 1)\)，此时 \(f(x^*) = 1\)，约束满足（\(g_1(1,1)=0\), \(g_2(1,1)=0\)）。

非线性规划中的序列二次约束规划法基础题 题目描述 考虑非线性规划问题： 最小化 \( 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 \geq 0 \) \( x_ 1, x_ 2 \in \mathbb{R} \)。 目标是在满足约束的前提下找到使 \( f(x) \) 最小的点 \( x^* \)。 解题过程 序列二次约束规划法（SQCP）通过迭代求解一系列二次约束子问题逼近原问题解。每个子问题在原当前点对目标函数和约束进行近似，并添加信赖域约束保证收敛。 步骤1: 问题重构 将不等式约束统一为 \( g_ j(x) \leq 0 \) 形式： \( g_ 1(x) = x_ 1 + x_ 2 - 2 \leq 0 \) 保持不变。 \( g_ 2(x) = -x_ 1^2 + x_ 2 \geq 0 \) 改写为 \( g_ 2(x) = x_ 1^2 - x_ 2 \leq 0 \)。 目标函数 \( f(x) \) 为二次函数，约束 \( g_ 2(x) \) 非线性，需线性化。 步骤2: 初始点选择 选择可行点作为初始点 \( x^{(0)} \)。验证可行性： 若选 \( x^{(0)} = (0, 0) \)，则 \( g_ 1(0,0) = -2 \leq 0 \)（满足），\( g_ 2(0,0) = 0 \leq 0 \)（满足）。可行。 步骤3: 构建第k次迭代子问题 在点 \( x^{(k)} \) 处，对目标函数 \( f(x) \) 作二次近似，对非线性约束 \( g_ 2(x) \) 作线性近似： 目标函数近似：因 \( f(x) \) 本身为二次函数，直接保留原形式： \( f(x) \approx (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \)。 约束线性化： \( g_ 1(x) \) 已是线性，保持不变。 \( g_ 2(x) = x_ 1^2 - x_ 2 \) 在 \( x^{(k)} \) 处一阶泰勒展开： \( g_ 2(x) \approx g_ 2(x^{(k)}) + \nabla g_ 2(x^{(k)})^T (x - x^{(k)}) \)， 其中梯度 \( \nabla g_ 2(x) = (2x_ 1, -1) \)。 添加信赖域约束 \( \|x - x^{(k)}\| \leq \Delta_ k \) 控制步长，\( \Delta_ k > 0 \) 为信赖域半径。 子问题形式为： 最小化 \( f(x) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \) 约束条件： \( g_ 1(x) = x_ 1 + x_ 2 - 2 \leq 0 \) \( g_ 2(x^{(k)}) + \nabla g_ 2(x^{(k)})^T (x - x^{(k)}) \leq 0 \) \( \|x - x^{(k)}\| \leq \Delta_ k \)。 步骤4: 迭代求解（以第0次迭代为例） 初始点 \( x^{(0)} = (0, 0) \)，设 \( \Delta_ 0 = 0.5 \)。 计算梯度： \( \nabla g_ 2(0,0) = (0, -1) \)，\( g_ 2(0,0) = 0 \)。 子问题约束： \( g_ 1(x) \leq 0 \) \( 0 + (0, -1) \cdot (x_ 1 - 0, x_ 2 - 0) \leq 0 \) → \( -x_ 2 \leq 0 \) → \( x_ 2 \geq 0 \)（注意符号方向）。 \( \|x - (0,0)\| \leq 0.5 \)。 子问题简化为： 最小化 \( (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \) 约束： \( x_ 1 + x_ 2 \leq 2 \) \( x_ 2 \geq 0 \) \( x_ 1^2 + x_ 2^2 \leq 0.25 \)。 求解子问题： 可行域是半径为0.5的圆盘与半平面 \( x_ 2 \geq 0 \) 的交集，且包含在 \( x_ 1 + x_ 2 \leq 2 \) 内（该约束此时松弛）。 目标函数梯度指向点 (2,1)，在圆盘上最小值出现在圆盘边界靠近 (2,1) 的点。通过几何分析或拉格朗日法解出：最优解为 \( x^{(1)} \approx (0.5, 0) \)（详细计算略）。 步骤5: 更新与收敛检查 计算约束违反度：原约束 \( g_ 2(x) = x_ 1^2 - x_ 2 \) 在 \( x^{(1)} \) 处值为 \( 0.25 - 0 = 0.25 > 0 \)，违反约束。 调整策略：由于约束被违反，需缩小信赖域半径（如 \( \Delta_ 1 = 0.3 \)）或增加惩罚项，重新求解子问题。 重复迭代直至 \( \|x^{(k+1)} - x^{(k)}\| \) 和约束违反度小于容忍值（如 \( 10^{-6} \)）。 最终解 持续迭代后，收敛至可行点 \( x^* \approx (1, 1) \)，此时 \( f(x^* ) = 1 \)，约束满足（\( g_ 1(1,1)=0 \), \( g_ 2(1,1)=0 \)）。