非线性规划中的连续线性规划法基础题
字数 3655 2025-11-10 03:24:20

非线性规划中的连续线性规划法基础题

题目描述
考虑非线性规划问题：
minimize \(f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2\)
subject to \(x_1^2 - x_2 \geq 0\)，
其中 \(x = (x_1, x_2) \in \mathbb{R}^2\)。要求使用连续线性规划法（Sequential Linear Programming, SLP）求解该问题，初始点设为 \(x^{(0)} = (0, 1)\)，信赖域半径初始值 \(\Delta_0 = 0.5\)，并详细展示前两次迭代过程。

解题过程
连续线性规划法的核心思想是：在每一步迭代中，将非线性目标函数和约束线性化（即一阶泰勒展开），构建一个线性规划子问题，通过求解该子问题得到搜索方向，并结合信赖域策略确保收敛性。

步骤1: 初始化

  • 初始点 \(x^{(0)} = (0, 1)\)，信赖域半径 \(\Delta_0 = 0.5\)。
  • 计算目标函数值 \(f(x^{(0)}) = (0-2)^4 + (0 - 2 \cdot 1)^2 = 16 + 4 = 20\)。
  • 约束函数 \(g(x) = x_1^2 - x_2\)，当前约束值 \(g(x^{(0)}) = 0 - 1 = -1\)（不满足约束，需在迭代中修复）。

步骤2: 第一次迭代（k=0）

  1. 线性化模型构建：

    • 目标函数梯度：
      \(\nabla f(x) = \left[ 4(x_1 - 2)^3 + 2(x_1 - 2x_2), \ -4(x_1 - 2x_2) \right]\)。
      在 \(x^{(0)}\) 处：
      \(\nabla f(0,1) = [4(-2)^3 + 2(0-2), \ -4(0-2)] = [-32 - 4, \ 8] = [-36, 8]\)。
    • 约束梯度：
      \(\nabla g(x) = [2x_1, -1]\)，在 \(x^{(0)}\) 处：\([0, -1]\)。
    • 线性化子问题（搜索方向 \(d = (d_1, d_2)\)）：
      minimize \(\nabla f(x^{(0)})^T d = -36d_1 + 8d_2\)
      subject to \(g(x^{(0)}) + \nabla g(x^{(0)})^T d \geq 0 \Rightarrow -1 + [0, -1] \cdot [d_1, d_2] \geq 0 \Rightarrow -1 - d_2 \geq 0 \Rightarrow d_2 \leq -1\)，
      且信赖域约束 \(\|d\|_\infty \leq \Delta_0 = 0.5\)（无穷范数简化计算，即 \(|d_1| \leq 0.5, |d_2| \leq 0.5\)）。

  2. 求解线性规划子问题：

    • 约束 \(d_2 \leq -1\) 与信赖域约束 \(d_2 \geq -0.5\) 矛盾，说明线性化模型不可行。此时需放松约束，常见方法是引入松弛变量或放宽信赖域。这里采用约束违规允许策略：将线性约束改为 \(g(x^{(0)}) + \nabla g(x^{(0)})^T d \geq -\delta\)，其中 \(\delta > 0\) 为容忍值。设 \(\delta = 0.2\)，则约束变为 \(-1 - d_2 \geq -0.2 \Rightarrow d_2 \leq -0.8\)。
    • 结合信赖域约束 \(d_2 \geq -0.5\)，无解。进一步调整 \(\delta = 0.5\)，约束变为 \(d_2 \leq -0.5\)。此时与信赖域下界 \(d_2 = -0.5\) 一致，故取 \(d_2 = -0.5\)。
    • 目标函数中 \(d_1\) 的系数为负（-36），为使目标最小化，取 \(d_1 = 0.5\)（信赖域允许的最大值）。
    • 搜索方向 \(d^{(0)} = (0.5, -0.5)\)。

  3. 更新迭代点：
    \(x^{(1)} = x^{(0)} + d^{(0)} = (0.5, 0.5)\)。

    • 计算新点函数值 \(f(x^{(1)}) = (0.5-2)^4 + (0.5 - 1)^2 = (-1.5)^4 + (-0.5)^2 = 5.0625 + 0.25 = 5.3125\)。
    • 约束值 \(g(x^{(1)}) = (0.5)^2 - 0.5 = 0.25 - 0.5 = -0.25\)（仍不满足，但违规减小）。
    • 实际下降量 \(\text{ared} = f(x^{(0)}) - f(x^{(1)}) = 20 - 5.3125 = 14.6875\)。
    • 预测下降量（线性模型预测）\(\text{pred} = -\nabla f(x^{(0)})^T d^{(0)} = -(-36 \cdot 0.5 + 8 \cdot (-0.5)) = -(-18 - 4) = 22\)。
    • 比值 \(r_0 = \text{ared} / \text{pred} = 14.6875 / 22 \approx 0.668\)。
    • 若 \(r > 0.25\)，接受新点；若 \(r > 0.75\)，可扩大信赖域。这里 \(r \approx 0.668\)，故接受新点，保持信赖域半径 \(\Delta_1 = \Delta_0 = 0.5\)。

步骤3: 第二次迭代（k=1）

  1. 线性化模型：

    • 在 \(x^{(1)} = (0.5, 0.5)\) 处：
      \(\nabla f(0.5,0.5) = [4(-1.5)^3 + 2(0.5-1), \ -4(0.5-1)] = [4(-3.375) + 2(-0.5), \ 2] = [-13.5 - 1, \ 2] = [-14.5, 2]\)。
      \(\nabla g(0.5,0.5) = [2 \cdot 0.5, -1] = [1, -1]\)。
    • 子问题：
      minimize \(-14.5d_1 + 2d_2\)
      subject to \(g(x^{(1)}) + \nabla g(x^{(1)})^T d \geq 0 \Rightarrow -0.25 + [1, -1] \cdot [d_1, d_2] \geq 0 \Rightarrow d_1 - d_2 \geq 0.25\)，
      且 \(\|d\|_\infty \leq 0.5\)。

  2. 求解线性规划：

    • 约束 \(d_1 - d_2 \geq 0.25\)，结合 \(d_1 \leq 0.5, d_2 \geq -0.5\)。
      目标函数中 \(d_1\) 系数负，为使目标最小化，取 \(d_1 = 0.5\)；约束要求 \(d_2 \leq d_1 - 0.25 = 0.25\)，同时 \(d_2\) 系数为正（2），故取 \(d_2 = -0.5\)（最小化目标）。
      但 \(d_1 - d_2 = 0.5 - (-0.5) = 1 \geq 0.25\)，满足约束。
    • 搜索方向 \(d^{(1)} = (0.5, -0.5)\)。

  3. 更新迭代点：
    \(x^{(2)} = (0.5, 0.5) + (0.5, -0.5) = (1, 0)\)。

    • \(f(x^{(2)}) = (1-2)^4 + (1 - 0)^2 = 1 + 1 = 2\)，
      \(g(x^{(2)}) = 1^2 - 0 = 1 \geq 0\)（满足约束）。
    • 实际下降量 \(\text{ared} = 5.3125 - 2 = 3.3125\)，
      预测下降量 \(\text{pred} = -(-14.5 \cdot 0.5 + 2 \cdot (-0.5)) = -(-7.25 - 1) = 8.25\)，
      比值 \(r_1 = 3.3125 / 8.25 \approx 0.402\)。
    • 接受新点，保持 \(\Delta_2 = 0.5\)。

总结
经过两次迭代，点从 \((0,1)\) 移动到 \((1,0)\)，目标函数值从 20 降至 2，且满足约束。SLP 通过线性逼近和信赖域控制，逐步逼近最优解（该问题最优解在 \((2,1)\) 附近，需更多迭代）。

非线性规划中的连续线性规划法基础题 题目描述 考虑非线性规划问题： minimize \( f(x) = (x_ 1 - 2)^4 + (x_ 1 - 2x_ 2)^2 \) subject to \( x_ 1^2 - x_ 2 \geq 0 \)， 其中 \( x = (x_ 1, x_ 2) \in \mathbb{R}^2 \)。要求使用连续线性规划法（Sequential Linear Programming, SLP）求解该问题，初始点设为 \( x^{(0)} = (0, 1) \)，信赖域半径初始值 \( \Delta_ 0 = 0.5 \)，并详细展示前两次迭代过程。 解题过程 连续线性规划法的核心思想是：在每一步迭代中，将非线性目标函数和约束线性化（即一阶泰勒展开），构建一个线性规划子问题，通过求解该子问题得到搜索方向，并结合信赖域策略确保收敛性。 步骤1: 初始化 初始点 \( x^{(0)} = (0, 1) \)，信赖域半径 \( \Delta_ 0 = 0.5 \)。 计算目标函数值 \( f(x^{(0)}) = (0-2)^4 + (0 - 2 \cdot 1)^2 = 16 + 4 = 20 \)。 约束函数 \( g(x) = x_ 1^2 - x_ 2 \)，当前约束值 \( g(x^{(0)}) = 0 - 1 = -1 \)（不满足约束，需在迭代中修复）。 步骤2: 第一次迭代（k=0） 线性化模型构建 ： 目标函数梯度： \( \nabla f(x) = \left[ 4(x_ 1 - 2)^3 + 2(x_ 1 - 2x_ 2), \ -4(x_ 1 - 2x_ 2) \right ] \)。 在 \( x^{(0)} \) 处： \( \nabla f(0,1) = [ 4(-2)^3 + 2(0-2), \ -4(0-2)] = [ -32 - 4, \ 8] = [ -36, 8 ] \)。 约束梯度： \( \nabla g(x) = [ 2x_ 1, -1] \)，在 \( x^{(0)} \) 处：\( [ 0, -1 ] \)。 线性化子问题（搜索方向 \( d = (d_ 1, d_ 2) \)）： minimize \( \nabla f(x^{(0)})^T d = -36d_ 1 + 8d_ 2 \) subject to \( g(x^{(0)}) + \nabla g(x^{(0)})^T d \geq 0 \Rightarrow -1 + [ 0, -1] \cdot [ d_ 1, d_ 2] \geq 0 \Rightarrow -1 - d_ 2 \geq 0 \Rightarrow d_ 2 \leq -1 \)， 且信赖域约束 \( \|d\|_ \infty \leq \Delta_ 0 = 0.5 \)（无穷范数简化计算，即 \( |d_ 1| \leq 0.5, |d_ 2| \leq 0.5 \)）。 求解线性规划子问题 ： 约束 \( d_ 2 \leq -1 \) 与信赖域约束 \( d_ 2 \geq -0.5 \) 矛盾，说明线性化模型不可行。此时需放松约束，常见方法是引入松弛变量或放宽信赖域。这里采用约束违规允许策略：将线性约束改为 \( g(x^{(0)}) + \nabla g(x^{(0)})^T d \geq -\delta \)，其中 \( \delta > 0 \) 为容忍值。设 \( \delta = 0.2 \)，则约束变为 \( -1 - d_ 2 \geq -0.2 \Rightarrow d_ 2 \leq -0.8 \)。 结合信赖域约束 \( d_ 2 \geq -0.5 \)，无解。进一步调整 \( \delta = 0.5 \)，约束变为 \( d_ 2 \leq -0.5 \)。此时与信赖域下界 \( d_ 2 = -0.5 \) 一致，故取 \( d_ 2 = -0.5 \)。 目标函数中 \( d_ 1 \) 的系数为负（-36），为使目标最小化，取 \( d_ 1 = 0.5 \)（信赖域允许的最大值）。 搜索方向 \( d^{(0)} = (0.5, -0.5) \)。 更新迭代点 ： \( x^{(1)} = x^{(0)} + d^{(0)} = (0.5, 0.5) \)。 计算新点函数值 \( f(x^{(1)}) = (0.5-2)^4 + (0.5 - 1)^2 = (-1.5)^4 + (-0.5)^2 = 5.0625 + 0.25 = 5.3125 \)。 约束值 \( g(x^{(1)}) = (0.5)^2 - 0.5 = 0.25 - 0.5 = -0.25 \)（仍不满足，但违规减小）。 实际下降量 \( \text{ared} = f(x^{(0)}) - f(x^{(1)}) = 20 - 5.3125 = 14.6875 \)。 预测下降量（线性模型预测）\( \text{pred} = -\nabla f(x^{(0)})^T d^{(0)} = -(-36 \cdot 0.5 + 8 \cdot (-0.5)) = -(-18 - 4) = 22 \)。 比值 \( r_ 0 = \text{ared} / \text{pred} = 14.6875 / 22 \approx 0.668 \)。 若 \( r > 0.25 \)，接受新点；若 \( r > 0.75 \)，可扩大信赖域。这里 \( r \approx 0.668 \)，故接受新点，保持信赖域半径 \( \Delta_ 1 = \Delta_ 0 = 0.5 \)。 步骤3: 第二次迭代（k=1） 线性化模型 ： 在 \( x^{(1)} = (0.5, 0.5) \) 处： \( \nabla f(0.5,0.5) = [ 4(-1.5)^3 + 2(0.5-1), \ -4(0.5-1)] = [ 4(-3.375) + 2(-0.5), \ 2] = [ -13.5 - 1, \ 2] = [ -14.5, 2 ] \)。 \( \nabla g(0.5,0.5) = [ 2 \cdot 0.5, -1] = [ 1, -1 ] \)。 子问题： minimize \( -14.5d_ 1 + 2d_ 2 \) subject to \( g(x^{(1)}) + \nabla g(x^{(1)})^T d \geq 0 \Rightarrow -0.25 + [ 1, -1] \cdot [ d_ 1, d_ 2] \geq 0 \Rightarrow d_ 1 - d_ 2 \geq 0.25 \)， 且 \( \|d\|_ \infty \leq 0.5 \)。 求解线性规划 ： 约束 \( d_ 1 - d_ 2 \geq 0.25 \)，结合 \( d_ 1 \leq 0.5, d_ 2 \geq -0.5 \)。 目标函数中 \( d_ 1 \) 系数负，为使目标最小化，取 \( d_ 1 = 0.5 \)；约束要求 \( d_ 2 \leq d_ 1 - 0.25 = 0.25 \)，同时 \( d_ 2 \) 系数为正（2），故取 \( d_ 2 = -0.5 \)（最小化目标）。 但 \( d_ 1 - d_ 2 = 0.5 - (-0.5) = 1 \geq 0.25 \)，满足约束。 搜索方向 \( d^{(1)} = (0.5, -0.5) \)。 更新迭代点 ： \( x^{(2)} = (0.5, 0.5) + (0.5, -0.5) = (1, 0) \)。 \( f(x^{(2)}) = (1-2)^4 + (1 - 0)^2 = 1 + 1 = 2 \)， \( g(x^{(2)}) = 1^2 - 0 = 1 \geq 0 \)（满足约束）。 实际下降量 \( \text{ared} = 5.3125 - 2 = 3.3125 \)， 预测下降量 \( \text{pred} = -(-14.5 \cdot 0.5 + 2 \cdot (-0.5)) = -(-7.25 - 1) = 8.25 \)， 比值 \( r_ 1 = 3.3125 / 8.25 \approx 0.402 \)。 接受新点，保持 \( \Delta_ 2 = 0.5 \)。 总结 经过两次迭代，点从 \( (0,1) \) 移动到 \( (1,0) \)，目标函数值从 20 降至 2，且满足约束。SLP 通过线性逼近和信赖域控制，逐步逼近最优解（该问题最优解在 \( (2,1) \) 附近，需更多迭代）。