非线性规划中的序列线性规划方法（Successive Linear Programming, SLP）
字数 2056 2025-12-07 01:14:10

非线性规划中的序列线性规划方法（Successive Linear Programming, SLP）

  1. 基本思想
    SLP是一种求解非线性规划问题的迭代算法。其核心思想是：在每一次迭代中，在当前点处将原非线性规划的目标函数和约束函数进行一阶泰勒展开，从而构造一个线性规划（LP） 子问题。求解这个线性规划子问题，将其最优解作为新的迭代点，重复此过程，直至满足收敛条件。简单来说，就是通过一系列线性规划来逐步逼近原非线性规划的最优解。

  2. 算法步骤详述
    步骤1：初始化
    给定初始可行点 \(x^0\)（即满足原问题约束的点），设定允许误差 \(\epsilon > 0\)，设置迭代计数器 \(k = 0\)。

    步骤2：构建线性近似子问题
    在当前迭代点 \(x^k\) 处，对目标函数 \(f(x)\) 和所有约束函数 \(g_i(x) \leq 0, h_j(x) = 0\) 进行一阶泰勒展开，忽略高阶项，得到线性近似模型。子问题（LP）形式如下：

\[ \begin{aligned} \min_{\mathbf{d}} \quad & \nabla f(\mathbf{x}^k)^T \mathbf{d} \\ \text{s.t.} \quad & g_i(\mathbf{x}^k) + \nabla g_i(\mathbf{x}^k)^T \mathbf{d} \leq 0, \quad i = 1, \ldots, m \\ & h_j(\mathbf{x}^k) + \nabla h_j(\mathbf{x}^k)^T \mathbf{d} = 0, \quad j = 1, \ldots, p \\ & \mathbf{d}_L \leq \mathbf{d} \leq \mathbf{d}_U \end{aligned} \]

其中，\(\mathbf{d} = \mathbf{x} - \mathbf{x}^k\) 是搜索方向。注意，这里必须包含移动限制（trust region） 约束 \(\mathbf{d}_L \leq \mathbf{d} \leq \mathbf{d}_U\)，通常取为 \(-\delta \leq d_i \leq \delta\)。这是SLP的关键，目的是将步长限制在泰勒展开有效的局部范围内，防止因线性近似误差过大而导致迭代失败。

步骤3：求解线性子问题
使用单纯形法等线性规划求解器，求解上述线性规划，得到最优搜索方向 \(\mathbf{d}^k\)。

步骤4：更新迭代点
令新的迭代点为 \(\mathbf{x}^{k+1} = \mathbf{x}^k + \mathbf{d}^k\)。

步骤5：检查收敛
计算某种收敛度量，例如搜索方向的模长 \(||\mathbf{d}^k||\) 或目标函数值的相对变化。如果 \(||\mathbf{d}^k|| < \epsilon\)，则停止迭代，\(\mathbf{x}^{k+1}\) 即为近似最优解。否则，令 \(k = k+1\)，返回步骤2。

  1. 移动限制的处理与调整
    移动限制（即 \(\delta\) 的取值）是SLP算法的核心控制参数。如果 \(\delta\) 太大，线性近似不准确，可能无法改进甚至破坏可行性；如果 \(\delta\) 太小，收敛速度会非常慢。实践中常采用自适应调整策略：根据本次迭代的“表现”来调整下一步的移动限制大小。“表现”可通过对比线性模型预测的目标函数改进量与实际改进量来评估。如果实际改进与预测改进匹配良好，则可适当放大移动限制；如果匹配很差，则需缩小移动限制。

  2. 算法特点与适用范围
    优点：
    a) 概念直观，易于实现。
    b) 只需计算函数值和一阶梯度，无需二阶导数（Hessian矩阵）。
    c) 可充分利用成熟、高效的线性规划求解器。
    缺点与挑战：
    a) 收敛速度通常是线性的，可能较慢。
    b) 对初始点和移动限制的选取比较敏感。
    c) 对于高度非线性或非凸问题，可能仅收敛到局部最优解甚至稳定点。
    主要应用：常出现在流程工业优化、带有非线性约束的资源分配等问题中，特别适用于那些约束大部分是线性的，非线性部分相对较“温和”的问题。

  3. 与序列二次规划（SQP）的对比
    SLP（序列线性规划）与您已学过的SQP（序列二次规划）是兄弟方法。两者的核心区别在于局部近似子问题的构造：

    • SLP用线性函数近似目标函数和约束，子问题是线性规划（LP）。
    • SQP用二次函数近似目标函数（利用二阶信息），用线性函数近似约束，子问题是二次规划（QP）。
      因此，SQP通常具有更快的收敛速率（局部超线性收敛），但每次迭代需要构造和求解QP，计算量更大。SLP则牺牲了一些收敛速度，换取了子问题更简单、更稳定的优点。
非线性规划中的序列线性规划方法（Successive Linear Programming, SLP） 基本思想 SLP是一种求解非线性规划问题的迭代算法。其核心思想是：在每一次迭代中，在当前点处将原非线性规划的目标函数和约束函数进行一阶泰勒展开，从而构造一个 线性规划（LP） 子问题。求解这个线性规划子问题，将其最优解作为新的迭代点，重复此过程，直至满足收敛条件。简单来说，就是通过一系列线性规划来逐步逼近原非线性规划的最优解。 算法步骤详述 步骤1：初始化 给定初始可行点 \( x^0 \)（即满足原问题约束的点），设定允许误差 \( \epsilon > 0 \)，设置迭代计数器 \( k = 0 \)。 步骤2：构建线性近似子问题 在当前迭代点 \( x^k \) 处，对目标函数 \( f(x) \) 和所有约束函数 \( g_ i(x) \leq 0, h_ j(x) = 0 \) 进行一阶泰勒展开，忽略高阶项，得到线性近似模型。子问题（LP）形式如下： \[ \begin{aligned} \min_ {\mathbf{d}} \quad & \nabla f(\mathbf{x}^k)^T \mathbf{d} \\ \text{s.t.} \quad & g_ i(\mathbf{x}^k) + \nabla g_ i(\mathbf{x}^k)^T \mathbf{d} \leq 0, \quad i = 1, \ldots, m \\ & h_ j(\mathbf{x}^k) + \nabla h_ j(\mathbf{x}^k)^T \mathbf{d} = 0, \quad j = 1, \ldots, p \\ & \mathbf{d}_ L \leq \mathbf{d} \leq \mathbf{d}_ U \end{aligned} \] 其中，\( \mathbf{d} = \mathbf{x} - \mathbf{x}^k \) 是搜索方向。注意，这里必须包含 移动限制（trust region） 约束 \( \mathbf{d}_ L \leq \mathbf{d} \leq \mathbf{d}_ U \)，通常取为 \( -\delta \leq d_ i \leq \delta \)。这是SLP的关键，目的是将步长限制在泰勒展开有效的局部范围内，防止因线性近似误差过大而导致迭代失败。 步骤3：求解线性子问题 使用单纯形法等线性规划求解器，求解上述线性规划，得到最优搜索方向 \( \mathbf{d}^k \)。 步骤4：更新迭代点 令新的迭代点为 \( \mathbf{x}^{k+1} = \mathbf{x}^k + \mathbf{d}^k \)。 步骤5：检查收敛 计算某种收敛度量，例如搜索方向的模长 \( ||\mathbf{d}^k|| \) 或目标函数值的相对变化。如果 \( ||\mathbf{d}^k|| < \epsilon \)，则停止迭代，\( \mathbf{x}^{k+1} \) 即为近似最优解。否则，令 \( k = k+1 \)，返回步骤2。 移动限制的处理与调整 移动限制（即 \( \delta \) 的取值）是SLP算法的核心控制参数。如果 \( \delta \) 太大，线性近似不准确，可能无法改进甚至破坏可行性；如果 \( \delta \) 太小，收敛速度会非常慢。实践中常采用 自适应调整策略 ：根据本次迭代的“表现”来调整下一步的移动限制大小。“表现”可通过对比线性模型预测的目标函数改进量与实际改进量来评估。如果实际改进与预测改进匹配良好，则可适当放大移动限制；如果匹配很差，则需缩小移动限制。 算法特点与适用范围 优点 ： a) 概念直观，易于实现。 b) 只需计算函数值和一阶梯度，无需二阶导数（Hessian矩阵）。 c) 可充分利用成熟、高效的线性规划求解器。 缺点与挑战 ： a) 收敛速度通常是线性的，可能较慢。 b) 对初始点和移动限制的选取比较敏感。 c) 对于高度非线性或非凸问题，可能仅收敛到局部最优解甚至稳定点。 主要应用 ：常出现在流程工业优化、带有非线性约束的资源分配等问题中，特别适用于那些约束大部分是线性的，非线性部分相对较“温和”的问题。 与序列二次规划（SQP）的对比 SLP（序列线性规划）与您已学过的SQP（序列二次规划）是兄弟方法。两者的核心区别在于局部近似子问题的构造： SLP用 线性函数 近似目标函数和约束，子问题是 线性规划（LP） 。 SQP用 二次函数 近似目标函数（利用二阶信息），用线性函数近似约束，子问题是 二次规划（QP） 。 因此，SQP通常具有更快的收敛速率（局部超线性收敛），但每次迭代需要构造和求解QP，计算量更大。SLP则牺牲了一些收敛速度，换取了子问题更简单、更稳定的优点。