非线性规划中的逐步线性规划（SLP）算法基础题

字数 4954 2025-11-02 10:11:21

非线性规划中的逐步线性规划（SLP）算法基础题

题目描述：
考虑一个简单的非线性规划问题：
最小化目标函数：\(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_1 \geq 0, x_2 \geq 0\)
初始点为 \(x^{(0)} = (0.5, 0.5)\)，信赖域半径初始值 \(\Delta_0 = 0.5\)。使用逐步线性规划（SLP）算法进行两次迭代，求解近似最优解。

解题过程：

SLP算法的核心思想是将非线性规划问题在每次迭代点处进行线性化（即一阶泰勒展开），构建一个线性规划子问题，通过求解该子问题得到搜索方向，并结合信赖域策略控制步长，逐步逼近原问题的最优解。

第一步：初始化

设定初始点 \(x^{(0)} = (0.5, 0.5)\)，当前迭代次数 \(k = 0\)。
设定初始信赖域半径 \(\Delta_0 = 0.5\)。
计算初始点的函数值及约束值：
- \(f(x^{(0)}) = (0.5 - 2)^2 + (0.5 - 1)^2 = 2.25 + 0.25 = 2.5\)
- \(g_1(x^{(0)}) = 0.5 + 0.5 - 2 = -1 \leq 0\)（满足）
- \(g_2(x^{(0)}) = (0.5)^2 - 0.5 = 0.25 - 0.5 = -0.25 \leq 0\)（满足）

第二步：第一次迭代（k=0）

线性化模型构建：
- 目标函数线性化：\(f(x) \approx f(x^{(0)}) + \nabla f(x^{(0)})^T (x - x^{(0)})\)
  - 梯度 \(\nabla f(x) = [2(x_1 - 2), 2(x_2 - 1)]\)，在 \(x^{(0)}\) 处为 \(\nabla f(x^{(0)}) = [2(0.5 - 2), 2(0.5 - 1)] = [-3, -1]\)
  - 线性化目标：\(\min -3(x_1 - 0.5) -1(x_2 - 0.5)\)（常数项可忽略）
- 约束线性化：
  - \(g_1(x) \approx g_1(x^{(0)}) + \nabla g_1(x^{(0)})^T (x - x^{(0)})\)。梯度 \(\nabla g_1 = [1, 1]\)，线性化后为 \(x_1 + x_2 - 2 \leq 0\)（线性约束不变）。
  - \(g_2(x) \approx g_2(x^{(0)}) + \nabla g_2(x^{(0)})^T (x - x^{(0)})\)。梯度 \(\nabla g_2 = [2x_1, -1]\)，在 \(x^{(0)}\) 处为 \([1, -1]\)，线性化后为 \(0.25 + 1 \cdot (x_1 - 0.5) -1 \cdot (x_2 - 0.5) \leq 0\)，即 \(x_1 - x_2 + 0.25 \leq 0\)。
- 加上边界约束 \(x_1 \geq 0, x_2 \geq 0\)。
- 信赖域约束：\(|x - x^{(0)}| \leq \Delta_0\)，即 \(|x_1 - 0.5| \leq 0.5\)、\(|x_2 - 0.5| \leq 0.5\)，等价于 \(0 \leq x_1 \leq 1\)、\(0 \leq x_2 \leq 1\)（与边界约束重叠）。
求解线性规划子问题：
- 子问题形式：

\[ \begin{aligned} \min \quad & -3x_1 - x_2 \\ \text{s.t.} \quad & x_1 + x_2 \leq 2 \\ & x_1 - x_2 \leq -0.25 \\ & 0 \leq x_1 \leq 1, \quad 0 \leq x_2 \leq 1 \end{aligned} \]

分析约束：
- 第一个约束 \(x_1 + x_2 \leq 2\) 在定义域内总是成立（因 \(x_1, x_2 \leq 1\)）。
- 第二个约束 \(x_1 - x_2 \leq -0.25\) 要求 \(x_1 \leq x_2 - 0.25\)。
- 目标函数系数为负，需最大化 \(x_1\) 和 \(x_2\) 以最小化线性化目标，但受约束限制。
求解：在 \(x_2\) 最大为 1 时，\(x_1 \leq 1 - 0.25 = 0.75\)。取 \(x_1 = 0.75, x_2 = 1\)（边界点），目标值 \(-3 \times 0.75 - 1 = -3.25\)。验证约束：\(0.75 - 1 = -0.25 \leq -0.25\)（紧约束）。故子问题解为 \(d^{(0)} = (0.75, 1) - (0.5, 0.5) = (0.25, 0.5)\)，新点 \(x^{(1)} = x^{(0)} + d^{(0)} = (0.75, 1)\)。

接受性检验：
- 计算实际下降量 \(\text{ared} = f(x^{(0)}) - f(x^{(1)}) = 2.5 - f(0.75, 1)\)。
  - \(f(0.75, 1) = (0.75 - 2)^2 + (1 - 1)^2 = 1.5625\)。
  - \(\text{ared} = 2.5 - 1.5625 = 0.9375\)。
- 预测下降量 \(\text{pred} = -\nabla f(x^{(0)})^T d^{(0)} = -[-3, -1] \cdot [0.25, 0.5] = 3 \times 0.25 + 1 \times 0.5 = 1.25\)。
- 比率 \(\rho = \frac{\text{ared}}{\text{pred}} = \frac{0.9375}{1.25} = 0.75\)。
- 由于 \(\rho > 0.25\)，接受新点 \(x^{(1)} = (0.75, 1)\)。
- 更新信赖域半径：若 \(\rho > 0.75\)，可扩大半径；此处 \(\rho = 0.75\)，保持半径 \(\Delta_1 = \Delta_0 = 0.5\)。

第三步：第二次迭代（k=1）

线性化模型构建：
- 在 \(x^{(1)} = (0.75, 1)\) 处计算梯度和约束值：
  - \(\nabla f(x^{(1)}) = [2(0.75 - 2), 2(1 - 1)] = [-2.5, 0]\)
  - \(g_1(x^{(1)}) = 0.75 + 1 - 2 = -0.25 \leq 0\)
  - \(g_2(x^{(1)}) = (0.75)^2 - 1 = 0.5625 - 1 = -0.4375 \leq 0\)
  - \(\nabla g_2(x^{(1)}) = [2 \times 0.75, -1] = [1.5, -1]\)
- 线性化子问题：
  - 目标：\(\min -2.5(x_1 - 0.75) + 0 \cdot (x_2 - 1)\)（即 \(\min -2.5x_1\)）。
  - 约束：
    - \(g_1: x_1 + x_2 \leq 2\)（不变）
    - \(g_2: -0.4375 + 1.5(x_1 - 0.75) -1(x_2 - 1) \leq 0\)，简化得 \(1.5x_1 - x_2 - 0.0625 \leq 0\)。
  - 信赖域约束：\(|x_1 - 0.75| \leq 0.5\)、\(|x_2 - 1| \leq 0.5\)，即 \(0.25 \leq x_1 \leq 1.25\)、\(0.5 \leq x_2 \leq 1.5\)（结合边界 \(x_1, x_2 \geq 0\)）。
求解线性规划子问题：
- 子问题形式：

\[ \begin{aligned} \min \quad & -2.5x_1 \\ \text{s.t.} \quad & x_1 + x_2 \leq 2 \\ & 1.5x_1 - x_2 \leq 0.0625 \\ & 0.25 \leq x_1 \leq 1.25, \quad 0.5 \leq x_2 \leq 1.5 \end{aligned} \]

目标函数最小化需最大化 \(x_1\)。
分析约束：
- 第一个约束在 \(x_1\) 最大时要求 \(x_2 \leq 2 - x_1\)。
- 第二个约束 \(1.5x_1 - x_2 \leq 0.0625\) 可写为 \(x_2 \geq 1.5x_1 - 0.0625\)。
- 结合 \(x_2\) 的上下界，求最大 \(x_1\) 时，需满足 \(1.5x_1 - 0.0625 \leq x_2 \leq 2 - x_1\) 且 \(x_2 \leq 1.5\)。
解方程 \(1.5x_1 - 0.0625 = 2 - x_1\) 得 \(2.5x_1 = 2.0625\)，\(x_1 = 0.825\)；此时 \(x_2 = 2 - 0.825 = 1.175\)（在 \(x_2\) 范围内）。
验证：若 \(x_1 = 0.825\)，则 \(x_2 \geq 1.5 \times 0.825 - 0.0625 = 1.175\)，且 \(x_2 \leq 1.5\)，取 \(x_2 = 1.175\)。
故子问题解为 \(d^{(1)} = (0.825, 1.175) - (0.75, 1) = (0.075, 0.175)\)，新点 \(x^{(2)} = (0.825, 1.175)\)。

接受性检验：
- 计算实际下降量 \(\text{ared} = f(x^{(1)}) - f(x^{(2)}) = 1.5625 - f(0.825, 1.175)\)。
  - \(f(0.825, 1.175) = (0.825 - 2)^2 + (1.175 - 1)^2 = 1.3806 + 0.0306 = 1.4112\)。
  - \(\text{ared} = 1.5625 - 1.4112 = 0.1513\)。
- 预测下降量 \(\text{pred} = -\nabla f(x^{(1)})^T d^{(1)} = -[-2.5, 0] \cdot [0.075, 0.175] = 2.5 \times 0.075 = 0.1875\)。
- 比率 \(\rho = \frac{0.1513}{0.1875} \approx 0.807\)。
- 由于 \(\rho > 0.25\)，接受新点 \(x^{(2)} = (0.825, 1.175)\)。

第四步：结果分析
经过两次SLP迭代，点从 \((0.5, 0.5)\) 移动到 \((0.825, 1.175)\)，目标函数值从 2.5 降低到 1.4112。继续迭代将逼近理论最优解（此问题最优解在约束边界 \(g_2 = 0\) 上，约在 \((1, 1)\) 附近）。SLP通过线性逼近和信赖域控制，有效处理了非线性约束。

非线性规划中的逐步线性规划（SLP）算法基础题题目描述：考虑一个简单的非线性规划问题：最小化目标函数：\( 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_ 1 \geq 0, x_ 2 \geq 0 \) 初始点为 \( x^{(0)} = (0.5, 0.5) \)，信赖域半径初始值 \( \Delta_ 0 = 0.5 \)。使用逐步线性规划（SLP）算法进行两次迭代，求解近似最优解。解题过程： SLP算法的核心思想是将非线性规划问题在每次迭代点处进行线性化（即一阶泰勒展开），构建一个线性规划子问题，通过求解该子问题得到搜索方向，并结合信赖域策略控制步长，逐步逼近原问题的最优解。第一步：初始化设定初始点 \( x^{(0)} = (0.5, 0.5) \)，当前迭代次数 \( k = 0 \)。设定初始信赖域半径 \( \Delta_ 0 = 0.5 \)。计算初始点的函数值及约束值： \( f(x^{(0)}) = (0.5 - 2)^2 + (0.5 - 1)^2 = 2.25 + 0.25 = 2.5 \) \( g_ 1(x^{(0)}) = 0.5 + 0.5 - 2 = -1 \leq 0 \)（满足） \( g_ 2(x^{(0)}) = (0.5)^2 - 0.5 = 0.25 - 0.5 = -0.25 \leq 0 \)（满足）第二步：第一次迭代（k=0）线性化模型构建：目标函数线性化：\( f(x) \approx f(x^{(0)}) + \nabla f(x^{(0)})^T (x - x^{(0)}) \) 梯度 \( \nabla f(x) = [ 2(x_ 1 - 2), 2(x_ 2 - 1)] \)，在 \( x^{(0)} \) 处为 \( \nabla f(x^{(0)}) = [ 2(0.5 - 2), 2(0.5 - 1)] = [ -3, -1 ] \) 线性化目标：\( \min -3(x_ 1 - 0.5) -1(x_ 2 - 0.5) \)（常数项可忽略）约束线性化： \( g_ 1(x) \approx g_ 1(x^{(0)}) + \nabla g_ 1(x^{(0)})^T (x - x^{(0)}) \)。梯度 \( \nabla g_ 1 = [ 1, 1] \)，线性化后为 \( x_ 1 + x_ 2 - 2 \leq 0 \)（线性约束不变）。 \( g_ 2(x) \approx g_ 2(x^{(0)}) + \nabla g_ 2(x^{(0)})^T (x - x^{(0)}) \)。梯度 \( \nabla g_ 2 = [ 2x_ 1, -1] \)，在 \( x^{(0)} \) 处为 \( [ 1, -1] \)，线性化后为 \( 0.25 + 1 \cdot (x_ 1 - 0.5) -1 \cdot (x_ 2 - 0.5) \leq 0 \)，即 \( x_ 1 - x_ 2 + 0.25 \leq 0 \)。加上边界约束 \( x_ 1 \geq 0, x_ 2 \geq 0 \)。信赖域约束：\( |x - x^{(0)}| \leq \Delta_ 0 \)，即 \( |x_ 1 - 0.5| \leq 0.5 \)、\( |x_ 2 - 0.5| \leq 0.5 \)，等价于 \( 0 \leq x_ 1 \leq 1 \)、\( 0 \leq x_ 2 \leq 1 \)（与边界约束重叠）。求解线性规划子问题：子问题形式： \[ \begin{aligned} \min \quad & -3x_ 1 - x_ 2 \\ \text{s.t.} \quad & x_ 1 + x_ 2 \leq 2 \\ & x_ 1 - x_ 2 \leq -0.25 \\ & 0 \leq x_ 1 \leq 1, \quad 0 \leq x_ 2 \leq 1 \end{aligned} \] 分析约束：第一个约束 \( x_ 1 + x_ 2 \leq 2 \) 在定义域内总是成立（因 \( x_ 1, x_ 2 \leq 1 \)）。第二个约束 \( x_ 1 - x_ 2 \leq -0.25 \) 要求 \( x_ 1 \leq x_ 2 - 0.25 \)。目标函数系数为负，需最大化 \( x_ 1 \) 和 \( x_ 2 \) 以最小化线性化目标，但受约束限制。求解：在 \( x_ 2 \) 最大为 1 时，\( x_ 1 \leq 1 - 0.25 = 0.75 \)。取 \( x_ 1 = 0.75, x_ 2 = 1 \)（边界点），目标值 \( -3 \times 0.75 - 1 = -3.25 \)。验证约束：\( 0.75 - 1 = -0.25 \leq -0.25 \)（紧约束）。故子问题解为 \( d^{(0)} = (0.75, 1) - (0.5, 0.5) = (0.25, 0.5) \)，新点 \( x^{(1)} = x^{(0)} + d^{(0)} = (0.75, 1) \)。接受性检验：计算实际下降量 \( \text{ared} = f(x^{(0)}) - f(x^{(1)}) = 2.5 - f(0.75, 1) \)。 \( f(0.75, 1) = (0.75 - 2)^2 + (1 - 1)^2 = 1.5625 \)。 \( \text{ared} = 2.5 - 1.5625 = 0.9375 \)。预测下降量 \( \text{pred} = -\nabla f(x^{(0)})^T d^{(0)} = -[ -3, -1] \cdot [ 0.25, 0.5 ] = 3 \times 0.25 + 1 \times 0.5 = 1.25 \)。比率 \( \rho = \frac{\text{ared}}{\text{pred}} = \frac{0.9375}{1.25} = 0.75 \)。由于 \( \rho > 0.25 \)，接受新点 \( x^{(1)} = (0.75, 1) \)。更新信赖域半径：若 \( \rho > 0.75 \)，可扩大半径；此处 \( \rho = 0.75 \)，保持半径 \( \Delta_ 1 = \Delta_ 0 = 0.5 \)。第三步：第二次迭代（k=1）线性化模型构建：在 \( x^{(1)} = (0.75, 1) \) 处计算梯度和约束值： \( \nabla f(x^{(1)}) = [ 2(0.75 - 2), 2(1 - 1)] = [ -2.5, 0 ] \) \( g_ 1(x^{(1)}) = 0.75 + 1 - 2 = -0.25 \leq 0 \) \( g_ 2(x^{(1)}) = (0.75)^2 - 1 = 0.5625 - 1 = -0.4375 \leq 0 \) \( \nabla g_ 2(x^{(1)}) = [ 2 \times 0.75, -1] = [ 1.5, -1 ] \) 线性化子问题：目标：\( \min -2.5(x_ 1 - 0.75) + 0 \cdot (x_ 2 - 1) \)（即 \( \min -2.5x_ 1 \)）。约束： \( g_ 1: x_ 1 + x_ 2 \leq 2 \)（不变） \( g_ 2: -0.4375 + 1.5(x_ 1 - 0.75) -1(x_ 2 - 1) \leq 0 \)，简化得 \( 1.5x_ 1 - x_ 2 - 0.0625 \leq 0 \)。信赖域约束：\( |x_ 1 - 0.75| \leq 0.5 \)、\( |x_ 2 - 1| \leq 0.5 \)，即 \( 0.25 \leq x_ 1 \leq 1.25 \)、\( 0.5 \leq x_ 2 \leq 1.5 \)（结合边界 \( x_ 1, x_ 2 \geq 0 \)）。求解线性规划子问题：子问题形式： \[ \begin{aligned} \min \quad & -2.5x_ 1 \\ \text{s.t.} \quad & x_ 1 + x_ 2 \leq 2 \\ & 1.5x_ 1 - x_ 2 \leq 0.0625 \\ & 0.25 \leq x_ 1 \leq 1.25, \quad 0.5 \leq x_ 2 \leq 1.5 \end{aligned} \] 目标函数最小化需最大化 \( x_ 1 \)。分析约束：第一个约束在 \( x_ 1 \) 最大时要求 \( x_ 2 \leq 2 - x_ 1 \)。第二个约束 \( 1.5x_ 1 - x_ 2 \leq 0.0625 \) 可写为 \( x_ 2 \geq 1.5x_ 1 - 0.0625 \)。结合 \( x_ 2 \) 的上下界，求最大 \( x_ 1 \) 时，需满足 \( 1.5x_ 1 - 0.0625 \leq x_ 2 \leq 2 - x_ 1 \) 且 \( x_ 2 \leq 1.5 \)。解方程 \( 1.5x_ 1 - 0.0625 = 2 - x_ 1 \) 得 \( 2.5x_ 1 = 2.0625 \)，\( x_ 1 = 0.825 \)；此时 \( x_ 2 = 2 - 0.825 = 1.175 \)（在 \( x_ 2 \) 范围内）。验证：若 \( x_ 1 = 0.825 \)，则 \( x_ 2 \geq 1.5 \times 0.825 - 0.0625 = 1.175 \)，且 \( x_ 2 \leq 1.5 \)，取 \( x_ 2 = 1.175 \)。故子问题解为 \( d^{(1)} = (0.825, 1.175) - (0.75, 1) = (0.075, 0.175) \)，新点 \( x^{(2)} = (0.825, 1.175) \)。接受性检验：计算实际下降量 \( \text{ared} = f(x^{(1)}) - f(x^{(2)}) = 1.5625 - f(0.825, 1.175) \)。 \( f(0.825, 1.175) = (0.825 - 2)^2 + (1.175 - 1)^2 = 1.3806 + 0.0306 = 1.4112 \)。 \( \text{ared} = 1.5625 - 1.4112 = 0.1513 \)。预测下降量 \( \text{pred} = -\nabla f(x^{(1)})^T d^{(1)} = -[ -2.5, 0] \cdot [ 0.075, 0.175 ] = 2.5 \times 0.075 = 0.1875 \)。比率 \( \rho = \frac{0.1513}{0.1875} \approx 0.807 \)。由于 \( \rho > 0.25 \)，接受新点 \( x^{(2)} = (0.825, 1.175) \)。第四步：结果分析经过两次SLP迭代，点从 \( (0.5, 0.5) \) 移动到 \( (0.825, 1.175) \)，目标函数值从 2.5 降低到 1.4112。继续迭代将逼近理论最优解（此问题最优解在约束边界 \( g_ 2 = 0 \) 上，约在 \( (1, 1) \) 附近）。SLP通过线性逼近和信赖域控制，有效处理了非线性约束。