二次规划的积极集方法
字数 3875 2025-12-15 01:10:33

二次规划的积极集方法

我会为您系统讲解二次规划及其求解的核心方法——积极集方法。首先从最基础的概念开始，逐步深入。

步骤1：二次规划的基本形式
二次规划是一类特殊且重要的非线性规划问题，其目标函数为二次函数，约束条件为线性。标准形式可写为：
最小化：\(f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T \mathbf{Q} \mathbf{x} + \mathbf{c}^T \mathbf{x}\)
约束条件：\(\mathbf{A} \mathbf{x} \leq \mathbf{b}\)，以及 \(\mathbf{A}_{eq} \mathbf{x} = \mathbf{b}_{eq}\)
其中，\(\mathbf{Q}\) 是一个 \(n \times n\) 对称矩阵（通常假定至少为半正定以保证凸性），\(\mathbf{c}\) 是 \(n\) 维向量，\(\mathbf{A}\) 和 \(\mathbf{A}_{eq}\) 是约束矩阵，\(\mathbf{b}\)、\(\mathbf{b}_{eq}\) 是对应右端项。当 \(\mathbf{Q}\) 半正定时，问题是凸二次规划，其任一局部最优解也是全局最优解。

步骤2：积极集的概念与KKT条件
对于一个给定的可行解 \(\mathbf{x}^*\)，不等式约束可分为两类：

  • 积极（有效）约束：在 \(\mathbf{x}^*\) 处取等号的约束，即 \(\mathbf{a}_i^T \mathbf{x}^* = b_i\)。这些约束像“墙壁”一样，阻止解向某些方向移动。
  • 非积极约束：在 \(\mathbf{x}^*\) 处取严格不等号的约束，即 \(\mathbf{a}_i^T \mathbf{x}^* < b_i\)。它们像远处的“栅栏”，在当前点附近不影响移动。
    对于凸二次规划，其最优解 \(\mathbf{x}^*\) 必须满足 KKT条件：存在拉格朗日乘子向量 \(\lambda\) 和 \(\mu\)（对应不等式和等式约束），使得：
  1. 平稳性条件：\(\nabla f(\mathbf{x}^*) + \mathbf{A}^T \lambda + \mathbf{A}_{eq}^T \mu = 0\)。
  2. 原始可行性条件：\(\mathbf{A} \mathbf{x}^* \leq \mathbf{b}\)， \(\mathbf{A}_{eq} \mathbf{x}^* = \mathbf{b}_{eq}\)。
  3. 对偶可行性条件：\(\lambda \geq 0\)。
  4. 互补松弛条件：\(\lambda_i (b_i - \mathbf{a}_i^T \mathbf{x}^*) = 0\) 对每个不等式约束成立。这意味着，如果一个不等式约束是非积极的（\(b_i - \mathbf{a}_i^T \mathbf{x}^* > 0\)），其对应的乘子 \(\lambda_i\) 必须为0；如果 \(\lambda_i > 0\)，则该约束必须是积极的。这个条件是连接积极集与最优性的关键。

步骤3：积极集方法的几何与代数直觉
积极集方法的核心思想是迭代式地猜测哪些约束在最优解处是积极的。算法的基本流程如下：

  1. 从一个可行点 \(\mathbf{x}^{(0)}\) 开始，确定其当前的积极约束集 \(\mathcal{W}^{(k)}\)（通常包含所有等式约束和在该点取等的不等式约束）。
  2. 在当前迭代点 \(\mathbf{x}^{(k)}\)，假设 \(\mathcal{W}^{(k)}\) 中的约束在最优解处都是积极的，而其他约束暂时忽略。在此假设下，我们求解一个等式约束二次规划子问题：最小化原目标函数，但要求 \(\mathcal{W}^{(k)}\) 中的约束以等式形式成立。
  3. 求解这个子问题，得到一个候选的“最优点” \(\mathbf{p}^{(k)}\)（从当前点出发的移动方向 \(\mathbf{d}^{(k)} = \mathbf{p}^{(k)} - \mathbf{x}^{(k)}\) ）。
  4. 根据 \(\mathbf{d}^{(k)}\) 和 \(\mathbf{p}^{(k)}\) 的情况，决定如何更新当前点和积极集：
    • 情况A： 如果 \(\mathbf{d}^{(k)} = 0\)（即当前点在当前积极集假设下已是最优），则检查对应的拉格朗日乘子 \(\lambda_i\) 是否都非负。如果全部 \(\lambda_i \geq 0\)，则满足KKT条件，算法终止，\(\mathbf{x}^{(k)}\) 即为最优解。如果存在某个对应于不等式约束的 \(\lambda_i < 0\)，则将该约束从积极集中移除（因为让该约束变得不积极可能进一步降低目标函数值），然后返回步骤2。
    • 情况B： 如果 \(\mathbf{d}^{(k)} \neq 0\)，则沿此方向进行线性搜索，但搜索步长 \(\alpha^{(k)}\) 不能破坏可行性。最大允许步长 \(\alpha_{\max}\) 由第一个将被违反的非积极约束决定。如果 \(\alpha_{\max} < 1\)，则步长取 \(\alpha^{(k)} = \alpha_{\max}\)，并将这个新碰到的约束加入积极集；如果 \(\alpha_{\max} \geq 1\)，则步长取1，点移动到 \(\mathbf{p}^{(k)}\)，积极集暂时不变。然后以新点开始下一轮迭代。

步骤4：等式约束子问题的求解
这是算法每一步的核心计算。子问题是：最小化 \(f(\mathbf{x})\)，满足 \(\mathbf{a}_i^T \mathbf{x} = b_i, \quad i \in \mathcal{W}^{(k)}\)。这是一个只含等式约束的严格凸二次规划（假设 \(\mathbf{Q}\) 在约束子空间正定），其解可以通过求解一个线性系统（KKT系统）得到：

\[\begin{bmatrix} \mathbf{Q} & \mathbf{A}_{\mathcal{W}}^T \\ \mathbf{A}_{\mathcal{W}} & \mathbf{0} \end{bmatrix} \begin{bmatrix} \mathbf{x}^* \\ \lambda_{\mathcal{W}} \end{bmatrix} = \begin{bmatrix} -\mathbf{c} \\ \mathbf{b}_{\mathcal{W}} \end{bmatrix} \]

其中 \(\mathbf{A}_{\mathcal{W}}\) 是由积极约束的行组成的矩阵。求解此系统（例如通过对称不定分解或Schur补方法）不仅能得到候选点 \(\mathbf{x}^*\)，还能得到当前积极约束对应的拉格朗日乘子 \(\lambda_{\mathcal{W}}\)，用于判断是否应移除约束。

步骤5：算法的收敛性与特性

  • 有限步收敛：对于凸二次规划，积极集方法的一个重要性质是它能在有限步内收敛到精确最优解。这是因为在每次迭代中，要么目标函数值严格下降（当 \(\mathbf{d}^{(k)} \neq 0\)），要么积极集发生变化（增加或移除约束）。由于可能的积极集组合是有限的（约束总数有限），算法不可能无限循环。
  • 积极集识别：该算法通常具有超线性收敛的识别性质，即它能够快速识别出在最优解处真正的积极约束集，之后只需很少的迭代就能达到高精度的解。
  • 与单纯形法的类比：在线性规划中，单纯形法在可行域的顶点间移动。对于凸二次规划，积极集方法可以视为其推广：它在可行域表面（由不同的积极集定义）间移动，每次解决一个等式约束子问题。当 \(\mathbf{Q} = \mathbf{0}\) 时，二次规划退化为线性规划，积极集方法的行为类似于单纯形法。

步骤6：算法实现的考虑

  1. 初始可行点的获取：若无现成可行点，可使用“两阶段法”，第一阶段求解一个辅助线性规划来寻找可行点。
  2. 数值稳定性：求解KKT系统时需处理可能出现的病态问题，常用稳定的矩阵分解技术（如LDL^T分解）。
  3. 积极集的管理：高效地添加/移除约束并更新矩阵分解（如利用秩-1更新）对大规模问题至关重要。
  4. 处理非凸问题：对于非凸二次规划（\(\mathbf{Q}\) 不定），积极集方法可能收敛到局部最优解或驻点，且收敛性理论更为复杂。

总结：二次规划的积极集方法是一种直接且强大的算法，它通过系统地探索不同约束子集的组合来寻找最优解。其核心在于将原问题分解为一系列易于求解的等式约束子问题，并利用KKT条件指导积极集的调整。因其有限收敛性和清晰的几何解释，该方法成为求解中小规模凸二次规划问题的标准选择，也是许多序列二次规划（SQP）求解器处理一般非线性规划问题的基础模块。

二次规划的积极集方法 我会为您系统讲解二次规划及其求解的核心方法——积极集方法。首先从最基础的概念开始，逐步深入。 步骤1：二次规划的基本形式 二次规划是一类特殊且重要的非线性规划问题，其目标函数为二次函数，约束条件为线性。标准形式可写为： 最小化：\( f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T \mathbf{Q} \mathbf{x} + \mathbf{c}^T \mathbf{x} \) 约束条件：\( \mathbf{A} \mathbf{x} \leq \mathbf{b} \)，以及 \( \mathbf{A} {eq} \mathbf{x} = \mathbf{b} {eq} \) 其中，\( \mathbf{Q} \) 是一个 \( n \times n \) 对称矩阵（通常假定至少为半正定以保证凸性），\( \mathbf{c} \) 是 \( n \) 维向量，\( \mathbf{A} \) 和 \( \mathbf{A} {eq} \) 是约束矩阵，\( \mathbf{b} \)、\( \mathbf{b} {eq} \) 是对应右端项。当 \( \mathbf{Q} \) 半正定时，问题是凸二次规划，其任一局部最优解也是全局最优解。 步骤2：积极集的概念与KKT条件 对于一个给定的可行解 \( \mathbf{x}^* \)，不等式约束可分为两类： 积极（有效）约束 ：在 \( \mathbf{x}^* \) 处取等号的约束，即 \( \mathbf{a}_ i^T \mathbf{x}^* = b_ i \)。这些约束像“墙壁”一样，阻止解向某些方向移动。 非积极约束 ：在 \( \mathbf{x}^* \) 处取严格不等号的约束，即 \( \mathbf{a}_ i^T \mathbf{x}^* < b_ i \)。它们像远处的“栅栏”，在当前点附近不影响移动。 对于凸二次规划，其最优解 \( \mathbf{x}^* \) 必须满足 KKT条件 ：存在拉格朗日乘子向量 \( \lambda \) 和 \( \mu \)（对应不等式和等式约束），使得： 平稳性条件 ：\( \nabla f(\mathbf{x}^* ) + \mathbf{A}^T \lambda + \mathbf{A}_ {eq}^T \mu = 0 \)。 原始可行性条件 ：\( \mathbf{A} \mathbf{x}^* \leq \mathbf{b} \)， \( \mathbf{A} {eq} \mathbf{x}^* = \mathbf{b} {eq} \)。 对偶可行性条件 ：\( \lambda \geq 0 \)。 互补松弛条件 ：\( \lambda_ i (b_ i - \mathbf{a}_ i^T \mathbf{x}^ ) = 0 \) 对每个不等式约束成立。这意味着，如果一个不等式约束是非积极的（\( b_ i - \mathbf{a}_ i^T \mathbf{x}^ > 0 \)），其对应的乘子 \( \lambda_ i \) 必须为0；如果 \( \lambda_ i > 0 \)，则该约束必须是积极的。这个条件是连接积极集与最优性的关键。 步骤3：积极集方法的几何与代数直觉 积极集方法的核心思想是 迭代式地猜测哪些约束在最优解处是积极的 。算法的基本流程如下： 从一个可行点 \( \mathbf{x}^{(0)} \) 开始，确定其当前的积极约束集 \( \mathcal{W}^{(k)} \)（通常包含所有等式约束和在该点取等的不等式约束）。 在当前迭代点 \( \mathbf{x}^{(k)} \)， 假设 \( \mathcal{W}^{(k)} \) 中的约束在最优解处都是积极的 ，而其他约束暂时忽略。在此假设下，我们求解一个 等式约束二次规划子问题 ：最小化原目标函数，但要求 \( \mathcal{W}^{(k)} \) 中的约束以等式形式成立。 求解这个子问题，得到一个候选的“最优点” \( \mathbf{p}^{(k)} \)（从当前点出发的移动方向 \( \mathbf{d}^{(k)} = \mathbf{p}^{(k)} - \mathbf{x}^{(k)} \) ）。 根据 \( \mathbf{d}^{(k)} \) 和 \( \mathbf{p}^{(k)} \) 的情况，决定如何更新当前点和积极集： 情况A： 如果 \( \mathbf{d}^{(k)} = 0 \)（即当前点在当前积极集假设下已是最优），则检查对应的拉格朗日乘子 \( \lambda_ i \) 是否都非负。如果全部 \( \lambda_ i \geq 0 \)，则满足KKT条件，算法终止，\( \mathbf{x}^{(k)} \) 即为最优解。如果存在某个对应于不等式约束的 \( \lambda_ i < 0 \)，则将该约束从积极集中移除（因为让该约束变得不积极可能进一步降低目标函数值），然后返回步骤2。 情况B： 如果 \( \mathbf{d}^{(k)} \neq 0 \)，则沿此方向进行 线性搜索 ，但搜索步长 \( \alpha^{(k)} \) 不能破坏可行性。最大允许步长 \( \alpha_ {\max} \) 由第一个将被违反的非积极约束决定。如果 \( \alpha_ {\max} < 1 \)，则步长取 \( \alpha^{(k)} = \alpha_ {\max} \)，并将这个新碰到的约束加入积极集；如果 \( \alpha_ {\max} \geq 1 \)，则步长取1，点移动到 \( \mathbf{p}^{(k)} \)，积极集暂时不变。然后以新点开始下一轮迭代。 步骤4：等式约束子问题的求解 这是算法每一步的核心计算。子问题是：最小化 \( f(\mathbf{x}) \)，满足 \( \mathbf{a} i^T \mathbf{x} = b_ i, \quad i \in \mathcal{W}^{(k)} \)。这是一个只含等式约束的严格凸二次规划（假设 \( \mathbf{Q} \) 在约束子空间正定），其解可以通过求解一个线性系统（KKT系统）得到： \[ \begin{bmatrix} \mathbf{Q} & \mathbf{A} {\mathcal{W}}^T \\ \mathbf{A} {\mathcal{W}} & \mathbf{0} \end{bmatrix} \begin{bmatrix} \mathbf{x}^* \\ \lambda {\mathcal{W}} \end{bmatrix} \begin{bmatrix} -\mathbf{c} \\ \mathbf{b} {\mathcal{W}} \end{bmatrix} \] 其中 \( \mathbf{A} {\mathcal{W}} \) 是由积极约束的行组成的矩阵。求解此系统（例如通过对称不定分解或Schur补方法）不仅能得到候选点 \( \mathbf{x}^* \)，还能得到当前积极约束对应的拉格朗日乘子 \( \lambda_ {\mathcal{W}} \)，用于判断是否应移除约束。 步骤5：算法的收敛性与特性 有限步收敛 ：对于凸二次规划，积极集方法的一个重要性质是它能在 有限步内 收敛到精确最优解。这是因为在每次迭代中，要么目标函数值严格下降（当 \( \mathbf{d}^{(k)} \neq 0 \)），要么积极集发生变化（增加或移除约束）。由于可能的积极集组合是有限的（约束总数有限），算法不可能无限循环。 积极集识别 ：该算法通常具有 超线性收敛 的识别性质，即它能够快速识别出在最优解处真正的积极约束集，之后只需很少的迭代就能达到高精度的解。 与单纯形法的类比 ：在线性规划中，单纯形法在可行域的顶点间移动。对于凸二次规划，积极集方法可以视为其推广：它在可行域表面（由不同的积极集定义）间移动，每次解决一个等式约束子问题。当 \( \mathbf{Q} = \mathbf{0} \) 时，二次规划退化为线性规划，积极集方法的行为类似于单纯形法。 步骤6：算法实现的考虑 初始可行点的获取 ：若无现成可行点，可使用“两阶段法”，第一阶段求解一个辅助线性规划来寻找可行点。 数值稳定性 ：求解KKT系统时需处理可能出现的病态问题，常用稳定的矩阵分解技术（如LDL^T分解）。 积极集的管理 ：高效地添加/移除约束并更新矩阵分解（如利用秩-1更新）对大规模问题至关重要。 处理非凸问题 ：对于非凸二次规划（\( \mathbf{Q} \) 不定），积极集方法可能收敛到局部最优解或驻点，且收敛性理论更为复杂。 总结 ：二次规划的积极集方法是一种直接且强大的算法，它通过系统地探索不同约束子集的组合来寻找最优解。其核心在于将原问题分解为一系列易于求解的等式约束子问题，并利用KKT条件指导积极集的调整。因其有限收敛性和清晰的几何解释，该方法成为求解中小规模凸二次规划问题的标准选择，也是许多序列二次规划（SQP）求解器处理一般非线性规划问题的基础模块。