非线性规划中的序列二次规划（SQP）与积极集法的结合

字数 2586 2025-12-11 23:19:12

非线性规划中的序列二次规划（SQP）与积极集法的结合

我将为您详细讲解“序列二次规划与积极集法结合”这一方法。首先，让我们理解为什么需要这种结合，然后一步步拆解其工作原理。

第一步：回顾背景——序列二次规划（SQP）的核心思想

序列二次规划（SQP）是求解非线性规划问题的主要方法之一。它的基本思路是：在每一步迭代中，将原问题（通常是非线性的、带约束的）在当前点 近似为一个二次规划（QP）子问题，然后求解这个二次规划子问题，得到搜索方向，再沿着这个方向进行线搜索，更新当前点，如此反复直至收敛。

对于一个标准的非线性规划问题：

最小化 f(x)
满足约束 g_i(x) = 0, i ∈ E （等式约束）
和 h_j(x) ≤ 0, j ∈ I （不等式约束）

在第k次迭代点 \(x^k\) 处，SQP构造的二次规划子问题通常如下：

最小化 \(\nabla f(x^k)^T d + \frac{1}{2} d^T B_k d\)
满足 \(\nabla g_i(x^k)^T d + g_i(x^k) = 0, i ∈ E\)
和 \(\nabla h_j(x^k)^T d + h_j(x^k) ≤ 0, j ∈ I\)
其中，\(d\) 是待求的搜索方向，\(B_k\) 是拉格朗日函数的海森矩阵或其近似。

第二步：SQP方法的潜在瓶颈——大规模不等式约束

在实际问题中，不等式约束的个数（|I|）可能非常多。每次迭代都求解一个包含所有不等式约束 的二次规划子问题，计算成本会非常高，尤其是当约束数量成百上千时。许多约束在最优解处很可能是“非积极”的（即 \(h_j(x^*) < 0\)），在迭代过程中对搜索方向的影响很小，但计算时仍需处理。

第三步：引入“积极集法”的思想来增效

积极集法的核心思想是：在每次迭代中，只考虑一个“猜测”的积极约束集，而忽略那些被认为是非积极的约束，从而显著减小子问题的规模。

积极约束：在当前迭代点，等式约束和“起作用”的不等式约束（即 \(h_j(x) = 0\) 的不等式约束）。
工作集：算法在当前迭代中“主动”考虑的约束集合，是积极约束集的一个猜测或子集。工作集通常包含所有等式约束和一部分“可能积极”的不等式约束。

将积极集法与SQP结合，就形成了SQP-积极集法。其核心改进在于：在每一步求解的二次规划子问题，只对当前工作集内的约束进行严格满足，而将工作集外的约束暂时忽略。这极大地简化了子问题的求解。

第四步：结合方法的工作流程详解

SQP与积极集法的结合是一个循环迭代过程，每一步都包含以下关键操作：

初始化：给定初始点 \(x^0\)，初始拉格朗日乘子估计 \(\lambda^0, \mu^0\)，以及一个初始工作集 \(W^0\)（通常包含所有等式约束，以及一些在 \(x^0\) 处违反或接近边界的不等式约束）。
主迭代循环（对于第k步）：

构建并求解简化QP子问题：在当前点 \(x^k\)，利用当前工作集 \(W^k\) 构建一个“简化”的二次规划子问题。这个子问题只包含工作集 \(W^k\) 中的约束。由于约束数量少，求解速度更快。

最小化 \(\nabla f(x^k)^T d + \frac{1}{2} d^T B_k d\)
满足 \(\nabla g_i(x^k)^T d + g_i(x^k) = 0, i ∈ E\)（所有等式约束必在工作集中）
和 \(\nabla h_j(x^k)^T d + h_j(x^k) = 0, j ∈ I ∩ W^k\)（只对工作集中的不等式约束施加等式要求）

获取搜索方向和乘子：求解上述简化QP，得到主搜索方向 \(d^k\) 以及对应于工作集内约束的拉格朗日乘子估计。
线搜索和迭代点更新：沿着方向 \(d^k\) 进行线搜索，考虑所有约束（包括工作集外的），找到一个合适的步长 \(\alpha^k\)，使得某个价值函数（如精确罚函数）充分下降。然后更新迭代点：\(x^{k+1} = x^k + \alpha^k d^k\)。
- 工作集更新（关键步骤）：
  a. 添加约束：在线搜索后得到的新点 \(x^{k+1}\) 处，检查是否有工作集外的不等式约束被违反（\(h_j(x^{k+1}) > 0\)）或变得“足够积极”（接近零）。如果有，则将这些约束加入工作集 \(W^{k+1}\)。
  b. 删除约束：检查当前工作集 \(W^k\) 中不等式约束对应的拉格朗日乘子（从简化QP解中获得）。如果某个乘子为负（对于最小化问题，这通常意味着该约束在边界上但对目标函数下降有“阻力”，可能不是积极约束），则将该约束从工作集中移除。
海森矩阵（或近似）更新：根据新的点 \(x^{k+1}\) 和乘子信息，更新 \(B_k\) 为 \(B_{k+1}\)（常用BFGS等拟牛顿法更新）。

收敛性检查：检查新点 \(x^{k+1}\) 是否满足非线性规划的一阶最优性条件（KKT条件）到指定的精度。如果满足，则算法终止，输出解；否则，返回步骤2继续迭代。

第五步：该结合方法的优势与总结

计算高效：这是最主要优势。通过每次迭代只处理一个小的约束子集（工作集），大大降低了每个QP子问题的求解难度和计算量，特别适用于大规模不等式约束问题。
继承SQP的快速局部收敛性：在最优解附近，如果积极集识别正确，工作集将稳定下来，此时的SQP-积极集法退化为在正确积极集上的SQP，从而保持SQP方法的超线性收敛速度。
物理意义清晰：工作集的动态调整过程，直观地反映了算法在探索解空间时，哪些约束是“活跃”的、正在起作用的，这有助于问题分析和调试。

总结：将序列二次规划（SQP）与积极集法结合，是一种“强强联合”的策略。SQP提供了用二次模型逼近原问题、实现快速收敛的框架，而积极集法则像一位“智能过滤器”，在每个迭代点智能地筛选出最可能起作用的约束集，让SQP只聚焦于关键约束，从而极大地提升了求解大规模、多约束非线性规划问题的效率。这种方法在许多工程优化、经济均衡计算等领域的商业求解器中都有核心应用。

非线性规划中的序列二次规划（SQP）与积极集法的结合我将为您详细讲解“序列二次规划与积极集法结合”这一方法。首先，让我们理解为什么需要这种结合，然后一步步拆解其工作原理。第一步：回顾背景——序列二次规划（SQP）的核心思想序列二次规划（SQP）是求解非线性规划问题的主要方法之一。它的基本思路是：在每一步迭代中，将原问题（通常是非线性的、带约束的）在当前点近似为一个二次规划（QP）子问题，然后求解这个二次规划子问题，得到搜索方向，再沿着这个方向进行线搜索，更新当前点，如此反复直至收敛。对于一个标准的非线性规划问题：最小化 f(x) 满足约束 g_ i(x) = 0, i ∈ E （等式约束）和 h_ j(x) ≤ 0, j ∈ I （不等式约束）在第k次迭代点 \(x^k\) 处，SQP构造的二次规划子问题通常如下：最小化 \( \nabla f(x^k)^T d + \frac{1}{2} d^T B_ k d \) 满足 \( \nabla g_ i(x^k)^T d + g_ i(x^k) = 0, i ∈ E \) 和 \( \nabla h_ j(x^k)^T d + h_ j(x^k) ≤ 0, j ∈ I \) 其中，\(d\) 是待求的搜索方向，\(B_ k\) 是拉格朗日函数的海森矩阵或其近似。第二步：SQP方法的潜在瓶颈——大规模不等式约束在实际问题中，不等式约束的个数（|I|）可能非常多。每次迭代都求解一个包含所有不等式约束的二次规划子问题，计算成本会非常高，尤其是当约束数量成百上千时。许多约束在最优解处很可能是“非积极”的（即 \(h_ j(x^* ) < 0\)），在迭代过程中对搜索方向的影响很小，但计算时仍需处理。第三步：引入“积极集法”的思想来增效积极集法的核心思想是：在每次迭代中，只考虑一个“猜测”的积极约束集，而忽略那些被认为是非积极的约束，从而显著减小子问题的规模。积极约束：在当前迭代点，等式约束和“起作用”的不等式约束（即 \(h_ j(x) = 0\) 的不等式约束）。工作集：算法在当前迭代中“主动”考虑的约束集合，是积极约束集的一个猜测或子集。工作集通常包含所有等式约束和一部分“可能积极”的不等式约束。将积极集法与SQP结合，就形成了 SQP-积极集法。其核心改进在于：在每一步求解的二次规划子问题，只对当前工作集内的约束进行严格满足，而将工作集外的约束暂时忽略。这极大地简化了子问题的求解。第四步：结合方法的工作流程详解 SQP与积极集法的结合是一个循环迭代过程，每一步都包含以下关键操作：初始化：给定初始点 \(x^0\)，初始拉格朗日乘子估计 \(\lambda^0, \mu^0\)，以及一个初始工作集 \(W^0\)（通常包含所有等式约束，以及一些在 \(x^0\) 处违反或接近边界的不等式约束）。主迭代循环（对于第k步）：构建并求解简化QP子问题：在当前点 \(x^k\)，利用当前工作集 \(W^k\) 构建一个“简化”的二次规划子问题。这个子问题只包含工作集 \(W^k\) 中的约束。由于约束数量少，求解速度更快。最小化 \( \nabla f(x^k)^T d + \frac{1}{2} d^T B_ k d \) 满足 \( \nabla g_ i(x^k)^T d + g_ i(x^k) = 0, i ∈ E \)（所有等式约束必在工作集中）和 \( \nabla h_ j(x^k)^T d + h_ j(x^k) = 0, j ∈ I ∩ W^k \)（只对工作集中的不等式约束施加等式要求）获取搜索方向和乘子：求解上述简化QP，得到主搜索方向 \(d^k\) 以及对应于工作集内约束的拉格朗日乘子估计。线搜索和迭代点更新：沿着方向 \(d^k\) 进行线搜索，考虑所有约束（包括工作集外的），找到一个合适的步长 \(\alpha^k\)，使得某个价值函数（如精确罚函数）充分下降。然后更新迭代点：\(x^{k+1} = x^k + \alpha^k d^k\)。工作集更新（关键步骤）： a. 添加约束：在线搜索后得到的新点 \(x^{k+1}\) 处，检查是否有工作集外的不等式约束被违反（\(h_ j(x^{k+1}) > 0\)）或变得“足够积极”（接近零）。如果有，则将这些约束加入工作集 \(W^{k+1}\)。 b. 删除约束：检查当前工作集 \(W^k\) 中不等式约束对应的拉格朗日乘子（从简化QP解中获得）。如果某个乘子为负（对于最小化问题，这通常意味着该约束在边界上但对目标函数下降有“阻力”，可能不是积极约束），则将该约束从工作集中移除。海森矩阵（或近似）更新：根据新的点 \(x^{k+1}\) 和乘子信息，更新 \(B_ k\) 为 \(B_ {k+1}\)（常用BFGS等拟牛顿法更新）。收敛性检查：检查新点 \(x^{k+1}\) 是否满足非线性规划的一阶最优性条件（KKT条件）到指定的精度。如果满足，则算法终止，输出解；否则，返回步骤2继续迭代。第五步：该结合方法的优势与总结计算高效：这是最主要优势。通过每次迭代只处理一个小的约束子集（工作集），大大降低了每个QP子问题的求解难度和计算量，特别适用于大规模不等式约束问题。继承SQP的快速局部收敛性：在最优解附近，如果积极集识别正确，工作集将稳定下来，此时的SQP-积极集法退化为在正确积极集上的SQP，从而保持SQP方法的超线性收敛速度。物理意义清晰：工作集的动态调整过程，直观地反映了算法在探索解空间时，哪些约束是“活跃”的、正在起作用的，这有助于问题分析和调试。总结：将序列二次规划（SQP）与积极集法结合，是一种“强强联合”的策略。SQP提供了用二次模型逼近原问题、实现快速收敛的框架，而积极集法则像一位“智能过滤器”，在每个迭代点智能地筛选出最可能起作用的约束集，让SQP只聚焦于关键约束，从而极大地提升了求解大规模、多约束非线性规划问题的效率。这种方法在许多工程优化、经济均衡计算等领域的商业求解器中都有核心应用。