非线性规划中的SQP方法（序列二次规划）
字数 3858 2025-12-08 01:04:24

非线性规划中的SQP方法（序列二次规划）

好的，我将为您详细讲解“非线性规划中的SQP方法（序列二次规划）”。请注意，根据您提供的列表，您已经知道“序列二次规划”、“非线性规划中的SQP方法”和“非线性规划中的积极集SQP方法”，但并未系统性地了解“SQP方法”本身作为核心算法的完整机理。本次讲解将聚焦于此核心算法本身，与前序内容形成互补。

我将分步骤，从基本问题模型开始，逐步深入到SQP方法的原理、迭代格式、核心子问题，并解释其收敛特性。

第一步：明确问题——我们想要解决什么？

SQP方法的目标是求解具有约束的非线性规划问题，其标准形式如下：

\[\begin{aligned} & \min_{x \in \mathbb{R}^n} \quad f(x) \\ & \text{subject to} \quad c_i(x) = 0, \quad i \in \mathcal{E}, \\ & \quad \quad \quad \quad \; c_i(x) \geq 0, \quad i \in \mathcal{I}. \end{aligned} \]

这里， \(f(x)\) 是我们要最小化的目标函数（非线性）， \(c_i(x)\) 定义了等式约束（ \(\mathcal{E}\) ）和不等式约束（ \(\mathcal{I}\) ）。所有函数 \(f\) 和 \(c_i\) 都假设是至少二阶连续可微的。这类问题广泛存在于工程、经济、管理等各个领域。

第二步：灵感来源——牛顿法与拉格朗日函数

为了求解无约束优化问题 \(\min f(x)\)，牛顿法 是一个非常强大的工具。其核心思想是：在当前迭代点 \(x_k\)，用目标函数的二阶泰勒展开（一个二次函数）来局部近似原函数，然后求解这个二次模型的最小值点，作为下一个迭代点。

SQP方法正是将这种思想推广到了约束优化问题。如何推广呢？关键的一步是考虑问题的拉格朗日函数：

\[\mathcal{L}(x, \lambda) = f(x) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i c_i(x). \]

其中， \(\lambda_i\) 是对应约束 \(c_i(x)\) 的拉格朗日乘子。对于约束优化问题，最优解 \((x^*, \lambda^*)\) 必须满足一阶必要条件——KKT条件：

\[\begin{aligned} \nabla_x \mathcal{L}(x^*, \lambda^*) &= 0, \\ c_i(x^*) &= 0, \quad i \in \mathcal{E}, \\ c_i(x^*) &\geq 0, \quad i \in \mathcal{I}, \\ \lambda_i^* &\geq 0, \quad i \in \mathcal{I}, \\ \lambda_i^* c_i(x^*) &= 0, \quad i \in \mathcal{I}. \end{aligned} \]

KKT条件构成了一个关于变量 \((x, \lambda)\) 的非线性方程组（包含等式和互补条件）。

第三步：核心思想——用二次规划逼近原问题

SQP方法的灵感可以这样理解：在无约束牛顿法中，我们用一个二次模型逼近目标函数。在约束问题中，我们同时用一个二次模型逼近拉格朗日函数，并用线性模型逼近约束函数。

具体来说，在当前迭代点 \((x_k, \lambda_k)\)，我们构造如下二次规划 子问题：

\[\begin{aligned} & \min_{d \in \mathbb{R}^n} \quad \frac{1}{2} d^T H_k d + \nabla f(x_k)^T d \\ & \text{s.t.} \quad c_i(x_k) + \nabla c_i(x_k)^T d = 0, \quad i \in \mathcal{E}, \\ & \quad \quad \; c_i(x_k) + \nabla c_i(x_k)^T d \geq 0, \quad i \in \mathcal{I}. \end{aligned} \]

让我们来仔细剖析这个子问题：

  1. 决策变量：是搜索方向 \(d\)。我们希望找到从当前点 \(x_k\) 出发的一个方向 \(d_k\)，然后更新 \(x_{k+1} = x_k + d_k\)。
  2. 目标函数：这是原拉格朗日函数 \(\mathcal{L}(x, \lambda)\) 关于变量 \(x\) 的二阶近似（在固定 \(\lambda_k\) 下），忽略常数项后的结果。
  • \(\nabla f(x_k)^T d\) 是目标函数 \(f\) 的一阶项。
  • \(\frac{1}{2} d^T H_k d\) 是二阶项。这里的 \(H_k\) 应该是拉格朗日函数的海森矩阵 \(\nabla_{xx}^2 \mathcal{L}(x_k, \lambda_k)\) 或其近似。这是SQP方法高效性的关键，因为它包含了约束的曲率信息。
  1. 约束：这是原约束函数 \(c_i(x)\) 的一阶线性近似。在 \(x_k\) 处，将约束线性化。这样，子问题的约束是线性的，因此它是一个二次规划。

第四步：迭代步骤与乘子更新

求解上述二次规划子问题，我们得到搜索方向 \(d_k\) 以及对应于该子问题的最优拉格朗日乘子估计 \(\hat{\lambda}_k\)。然后，我们进行更新：

  1. 变量更新： \(x_{k+1} = x_k + \alpha_k d_k\)。
    其中 \(\alpha_k \in (0, 1]\) 是步长，通常通过线搜索来确定，以确保目标函数有足够的下降并满足某种可行性条件（例如采用价值函数，如 \(l_1\) 罚函数，来衡量进展）。

  2. 乘子更新： \(\lambda_{k+1} = \hat{\lambda}_k\)。
    这里很精妙：二次规划子问题解出的乘子估计 \(\hat{\lambda}_k\)，直接作为下一次迭代的拉格朗日乘子 \(\lambda_{k+1}\)。这是SQP方法区别于其他方法（如增广拉格朗日法）的一个重要特征。

第五步：理解其本质——对KKT系统的牛顿步

SQP方法有一个非常深刻的解释：它等价于对原始问题的KKT条件应用牛顿迭代法。

考虑由等式和不等式约束定义的KKT系统。牛顿法要求求解一个线性方程组来获得迭代步。当应用于KKT系统时，这个牛顿步的方程，经过整理，恰好等价于求解上面定义的那个二次规划子问题的最优性条件（即该QP的KKT条件）。

因此，SQP方法可以看作是在原始变量空间和对偶变量空间同时执行牛顿步。这解释了为什么当初始点足够好且 \(H_k\) 精确时，它具有局部二次收敛速率——这是牛顿法的典型特征。

第六步：关键实现细节与扩展

基本SQP框架有几个关键点需要处理，这也是其变体产生的原因：

  1. 海森矩阵 \(H_k\) 的处理：精确计算 \(\nabla_{xx}^2 \mathcal{L}(x_k, \lambda_k)\) 可能代价高昂。实践中常用拟牛顿法（如BFGS或SR1更新公式）来构造其近似矩阵 \(B_k \approx H_k\)。这催生了约束拟牛顿法，它保持了超线性收敛性，同时大大降低了计算成本。

  2. 步长与全局化：纯牛顿法（步长 \(\alpha_k=1\)）可能不收敛。为了保证从任意初始点出发都能收敛，需要引入线搜索或信赖域机制。在线搜索中，我们使用一个价值函数（如 \(l_1\) 精确罚函数）来测试候选步长，确保“价值”充分下降。这就是您列表中“信赖域方法”可以结合进来的地方。

  3. 不等式约束与积极集：在每次迭代中求解的QP子问题本身就是一个带不等式约束的优化问题。这通常通过积极集法 来求解。该方法识别在解处“起作用”（积极）的约束，然后主要在这些约束上进行计算，这与您已了解的“积极集SQP方法”直接相关。

第七步：总结与联系

  • SQP是什么：它是一种迭代算法，在每一步通过构造并求解一个二次规划子问题，来获得对原约束非线性规划问题的搜索方向和拉格朗日乘子估计。
  • 核心优势：当接近最优解时，若使用精确二阶信息，它具有快速的局部二次收敛性。通过拟牛顿近似，也能达到超线性收敛。
  • 与已知概念的联系：它本质上是牛顿法在约束优化中的推广；其子问题求解依赖于二次规划 和积极集法；为了保证全局收敛，需要结合线搜索或信赖域（价值函数）策略；其推导根植于KKT条件 和拉格朗日函数。

通过以上步骤，您应该能理解SQP方法是如何从一个简单的类比（牛顿法）出发，通过联合逼近目标函数和约束，形成了一个强大且理论上优雅的约束优化算法框架。

非线性规划中的SQP方法（序列二次规划） 好的，我将为您详细讲解“非线性规划中的SQP方法（序列二次规划）”。请注意，根据您提供的列表，您已经知道“序列二次规划”、“非线性规划中的SQP方法”和“非线性规划中的积极集SQP方法”，但并未系统性地了解“SQP方法”本身作为核心算法的完整机理。本次讲解将聚焦于此核心算法本身，与前序内容形成互补。 我将分步骤，从基本问题模型开始，逐步深入到SQP方法的原理、迭代格式、核心子问题，并解释其收敛特性。 第一步：明确问题——我们想要解决什么？ SQP方法的目标是求解 具有约束的非线性规划 问题，其标准形式如下： \[ \begin{aligned} & \min_ {x \in \mathbb{R}^n} \quad f(x) \\ & \text{subject to} \quad c_ i(x) = 0, \quad i \in \mathcal{E}, \\ & \quad \quad \quad \quad \; c_ i(x) \geq 0, \quad i \in \mathcal{I}. \end{aligned} \] 这里， \( f(x) \) 是我们要最小化的目标函数（非线性）， \( c_ i(x) \) 定义了等式约束（ \( \mathcal{E} \) ）和不等式约束（ \( \mathcal{I} \) ）。所有函数 \( f \) 和 \( c_ i \) 都假设是至少二阶连续可微的。这类问题广泛存在于工程、经济、管理等各个领域。 第二步：灵感来源——牛顿法与拉格朗日函数 为了求解无约束优化问题 \( \min f(x) \)， 牛顿法 是一个非常强大的工具。其核心思想是：在当前迭代点 \( x_ k \)，用目标函数的二阶泰勒展开（一个二次函数）来局部近似原函数，然后求解这个二次模型的最小值点，作为下一个迭代点。 SQP方法正是将这种思想 推广到了约束优化问题 。如何推广呢？关键的一步是考虑问题的 拉格朗日函数 ： \[ \mathcal{L}(x, \lambda) = f(x) - \sum_ {i \in \mathcal{E} \cup \mathcal{I}} \lambda_ i c_ i(x). \] 其中， \( \lambda_ i \) 是对应约束 \( c_ i(x) \) 的 拉格朗日乘子 。对于约束优化问题，最优解 \( (x^ , \lambda^ ) \) 必须满足 一阶必要条件——KKT条件 ： \[ \begin{aligned} \nabla_ x \mathcal{L}(x^ , \lambda^ ) &= 0, \\ c_ i(x^ ) &= 0, \quad i \in \mathcal{E}, \\ c_ i(x^ ) &\geq 0, \quad i \in \mathcal{I}, \\ \lambda_ i^* &\geq 0, \quad i \in \mathcal{I}, \\ \lambda_ i^* c_ i(x^* ) &= 0, \quad i \in \mathcal{I}. \end{aligned} \] KKT条件构成了一个关于变量 \( (x, \lambda) \) 的非线性方程组（包含等式和互补条件）。 第三步：核心思想——用二次规划逼近原问题 SQP方法的灵感可以这样理解：在无约束牛顿法中，我们用一个二次模型逼近目标函数。在约束问题中，我们 同时用一个二次模型逼近拉格朗日函数，并用线性模型逼近约束函数 。 具体来说，在当前迭代点 \( (x_ k, \lambda_ k) \)，我们构造如下 二次规划 子问题： \[ \begin{aligned} & \min_ {d \in \mathbb{R}^n} \quad \frac{1}{2} d^T H_ k d + \nabla f(x_ k)^T d \\ & \text{s.t.} \quad c_ i(x_ k) + \nabla c_ i(x_ k)^T d = 0, \quad i \in \mathcal{E}, \\ & \quad \quad \; c_ i(x_ k) + \nabla c_ i(x_ k)^T d \geq 0, \quad i \in \mathcal{I}. \end{aligned} \] 让我们来仔细剖析这个子问题： 决策变量 ：是 搜索方向 \( d \)。我们希望找到从当前点 \( x_ k \) 出发的一个方向 \( d_ k \)，然后更新 \( x_ {k+1} = x_ k + d_ k \)。 目标函数 ：这是原拉格朗日函数 \( \mathcal{L}(x, \lambda) \) 关于变量 \( x \) 的二阶近似（在固定 \( \lambda_ k \) 下），忽略常数项后的结果。 \( \nabla f(x_ k)^T d \) 是目标函数 \( f \) 的一阶项。 \( \frac{1}{2} d^T H_ k d \) 是二阶项。这里的 \( H_ k \) 应该是拉格朗日函数的海森矩阵 \( \nabla_ {xx}^2 \mathcal{L}(x_ k, \lambda_ k) \) 或其近似。这是SQP方法高效性的关键，因为它包含了约束的曲率信息。 约束 ：这是原约束函数 \( c_ i(x) \) 的一阶线性近似。在 \( x_ k \) 处，将约束线性化。这样，子问题的约束是线性的，因此它是一个 二次规划 。 第四步：迭代步骤与乘子更新 求解上述二次规划子问题，我们得到 搜索方向 \( d_ k \) 以及对应于该子问题的 最优拉格朗日乘子估计 \( \hat{\lambda}_ k \)。然后，我们进行更新： 变量更新 ： \( x_ {k+1} = x_ k + \alpha_ k d_ k \)。 其中 \( \alpha_ k \in (0, 1] \) 是 步长 ，通常通过线搜索来确定，以确保目标函数有足够的下降并满足某种可行性条件（例如采用 价值函数 ，如 \( l_ 1 \) 罚函数，来衡量进展）。 乘子更新 ： \( \lambda_ {k+1} = \hat{\lambda}_ k \)。 这里很精妙：二次规划子问题解出的乘子估计 \( \hat{\lambda} k \)，直接作为下一次迭代的拉格朗日乘子 \( \lambda {k+1} \)。这是SQP方法区别于其他方法（如增广拉格朗日法）的一个重要特征。 第五步：理解其本质——对KKT系统的牛顿步 SQP方法有一个非常深刻的解释： 它等价于对原始问题的KKT条件应用牛顿迭代法 。 考虑由等式和不等式约束定义的KKT系统。牛顿法要求求解一个线性方程组来获得迭代步。当应用于KKT系统时，这个牛顿步的方程，经过整理，恰好等价于求解上面定义的那个二次规划子问题的 最优性条件 （即该QP的KKT条件）。 因此，SQP方法可以看作是 在原始变量空间和对偶变量空间同时执行牛顿步 。这解释了为什么当初始点足够好且 \( H_ k \) 精确时，它具有 局部二次收敛速率 ——这是牛顿法的典型特征。 第六步：关键实现细节与扩展 基本SQP框架有几个关键点需要处理，这也是其变体产生的原因： 海森矩阵 \( H_ k \) 的处理 ：精确计算 \( \nabla_ {xx}^2 \mathcal{L}(x_ k, \lambda_ k) \) 可能代价高昂。实践中常用 拟牛顿法 （如BFGS或SR1更新公式）来构造其近似矩阵 \( B_ k \approx H_ k \)。这催生了 约束拟牛顿法 ，它保持了超线性收敛性，同时大大降低了计算成本。 步长与全局化 ：纯牛顿法（步长 \( \alpha_ k=1 \)）可能不收敛。为了保证从任意初始点出发都能收敛，需要引入 线搜索 或 信赖域 机制。在线搜索中，我们使用一个价值函数（如 \( l_ 1 \) 精确罚函数）来测试候选步长，确保“价值”充分下降。这就是您列表中“信赖域方法”可以结合进来的地方。 不等式约束与积极集 ：在每次迭代中求解的QP子问题本身就是一个带不等式约束的优化问题。这通常通过 积极集法 来求解。该方法识别在解处“起作用”（积极）的约束，然后主要在这些约束上进行计算，这与您已了解的“积极集SQP方法”直接相关。 第七步：总结与联系 SQP是什么 ：它是一种迭代算法，在每一步通过构造并求解一个二次规划子问题，来获得对原约束非线性规划问题的搜索方向和拉格朗日乘子估计。 核心优势 ：当接近最优解时，若使用精确二阶信息，它具有快速的 局部二次收敛性 。通过拟牛顿近似，也能达到 超线性收敛 。 与已知概念的联系 ：它本质上是 牛顿法 在约束优化中的推广；其子问题求解依赖于 二次规划 和 积极集法 ；为了保证全局收敛，需要结合 线搜索 或 信赖域 （价值函数）策略；其推导根植于 KKT条件 和 拉格朗日函数 。 通过以上步骤，您应该能理解SQP方法是如何从一个简单的类比（牛顿法）出发，通过联合逼近目标函数和约束，形成了一个强大且理论上优雅的约束优化算法框架。