KNOWECON WIKI

ARTICLE

有效集法

有效集法 (Active Set Method) 有效集法 (Active Set Method) 是求解带不等式约束的凸二次规划 (Convex Quadratic Programming, QP) 问题的经典算法，也是 非线性规划 中 序列二次规划 (Sequential Quadratic Programming, SQP) 方法的核心子问题求解器。其

浏览 10 更新 2025-12-25

有效集法 (Active Set Method)

有效集法 (Active Set Method) 是求解带不等式约束的凸二次规划 (Convex Quadratic Programming, QP) 问题的经典算法，也是 非线性规划 中 序列二次规划 (Sequential Quadratic Programming, SQP) 方法的核心子问题求解器。其基本思想源于对 Karush-Kuhn-Tucker (KKT) 条件 的组合解释：若事先知道最优解处哪些约束是积极的（即等式成立），则原不等式约束问题退化为等式约束问题，可直接通过求解线性方程组获得最优解。

有效集法通过迭代地维护一个工作集 (Working Set) Wk\mathcal{W}_k——当前估计的积极约束指标集合——逐步逼近真实的最优积极集，兼具单纯形法的组合搜索特性与牛顿法的二阶收敛速度。

问题形式与最优性条件

考虑标准的凸二次规划问题：

minimize⁡12x⊤Gx+c⊤xsubject toai⊤x=bi,i∈E,ai⊤x≥bi,i∈I,\begin{aligned} \operatorname{minimize} \quad & \frac{1}{2} x^\top G x + c^\top x \\ \text{subject to} \quad & a_i^\top x = b_i, \quad i \in \mathcal{E}, \\ & a_i^\top x \geq b_i, \quad i \in \mathcal{I}, \end{aligned}

其中 G∈Rn×nG \in \mathbb{R}^{n \times n} 为对称正定（或半正定）矩阵，E\mathcal{E} 为等式约束指标集，I\mathcal{I} 为不等式约束指标集。该问题的 KKT条件 为：存在 Lagrange 乘子 λi\lambda_i 使得

Gx∗+c−∑i∈E∪Iλi∗ai=0,ai⊤x∗=bi,i∈E,ai⊤x∗≥bi,i∈I,λi∗≥0,i∈I,λi∗(ai⊤x∗−bi)=0,i∈I.\begin{aligned} G x^* + c - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i^* a_i &= 0, \\ a_i^\top x^* &= b_i, \quad i \in \mathcal{E}, \\ a_i^\top x^* &\geq b_i, \quad i \in \mathcal{I}, \\ \lambda_i^* &\geq 0, \quad i \in \mathcal{I}, \\ \lambda_i^* (a_i^\top x^* - b_i) &= 0, \quad i \in \mathcal{I}. \end{aligned}

最后一个条件为互补松弛条件 (Complementary Slackness)：若约束 i∈Ii \in \mathcal{I} 在最优解处非积极（ai⊤x∗>bia_i^\top x^* > b_i），则对应的乘子必为零。定义最优积极集 A∗=E∪{i∈I:ai⊤x∗=bi}\mathcal{A}^* = \mathcal{E} \cup \{i \in \mathcal{I} : a_i^\top x^* = b_i\}，则 x∗x^* 也是仅含等式约束 ai⊤x=bi,i∈A∗a_i^\top x = b_i, i \in \mathcal{A}^* 的子问题的解。

算法框架

有效集法每次迭代维持一个工作集 Wk⊆E∪I\mathcal{W}_k \subseteq \mathcal{E} \cup \mathcal{I}，其中包含所有等式约束指标及当前估计为积极的不等式约束指标。给定当前迭代点 xkx_k（始终对 Wk\mathcal{W}_k 中所有约束可行），算法执行以下步骤：

  1. 求解等式约束子问题。在工作集 Wk\mathcal{W}_k 下，求解仅含等式约束的 QP 子问题，等价于求解如下 KKT 系统： \[ \begin{bmatrix} G & -A_{\mathcal{W}_k}^\top \\ A_{\mathcal{W}_k} & 0 \end{bmatrix} \begin{bmatrix} p_k \\ \lambda_{\mathcal{W}_k} \end{bmatrix} = \begin{bmatrix} -G x_k - c \\ 0 \end{bmatrix}, \] 其中 AWkA_{\mathcal{W}_k} 为工作集中约束梯度 ai⊤a_i^\top 组成的矩阵。由此得到搜索方向 pkp_k 及对应的 Lagrange 乘子估计 λ^i\hat{\lambda}_i。
  2. 检查最优性与删除约束。若 pk=0p_k = 0，则当前点 xkx_k 是当前工作集下的驻点。检查所有 i∈Wk∩Ii \in \mathcal{W}_k \cap \mathcal{I} 对应的乘子：若存在 λ^i<0\hat{\lambda}_i < 0，则将最负乘子对应的约束从 Wk\mathcal{W}_k 中移除，进入下一次迭代；若所有 λ^i≥0\hat{\lambda}_i \geq 0，则满足全部 KKT 条件，xkx_k 为原问题的最优解，算法终止。
  3. 沿方向搜索与添加约束。若 pk≠0p_k \neq 0，沿 pkp_k 方向进行线搜索，计算不违反任何非工作集不等式约束的最大步长 αk\alpha_k： \[ \alpha_k = \min\left(1, \min_{i \notin \mathcal{W}_k, a_i^\top p_k < 0} \frac{b_i - a_i^\top x_k}{a_i^\top p_k}\right). \] 若 αk<1\alpha_k < 1，则存在某个约束在达到无约束极小值之前被触达，将该约束的指标加入 Wk\mathcal{W}_k（称为阻塞约束，Blocking Constraint）。更新 xk+1=xk+αkpkx_{k+1} = x_k + \alpha_k p_k。

该框架的核心洞见在于：若每次迭代添加正确的约束且不删除应保留的约束，算法在有限步内终止——因为工作集只有有限种组合，且目标函数值单调不减（或不增，视最小化/最大化而定），不可能重复访问同一工作集。

初始可行点的构造

有效集法要求初始点 x0x_0 对等式约束及工作集中约束可行。当缺乏自然可行的初始点时，通常采用 Phase I 方法：引入人工变量，构造一个辅助线性规划或二次规划问题以找到任意可行点，或直接将所有不等式约束的违反程度作为惩罚项进行优化。Phase I 的求解本身也可利用有效集法完成。

与相关算法的联系

有效集法与 单纯形法 在思想上高度相似：单纯形法在可行域的顶点间移动，每次交换基变量与非基变量；有效集法在积极集的组合结构中搜索，工作集的增删等价于在 KKT 系统的不同子集间切换。两者的核心差异在于：有效集法不限于线性目标，可以处理二次目标，且搜索方向并不总是指向顶点。

与 内点法 相比，有效集法的优势在于：对于中小规模问题（n≲1000n \lesssim 1000）收敛极快，尤其适合需要求解一系列仅约束右侧略有变化的 QP 子问题（如 SQP 迭代中）；有效集法从上一个最优解"热启动" (Warm Start) 的效率远高于内点法，因为最优积极集通常仅需少量调整。对于大规模稀疏问题，内点法在计算复杂度上通常更优。

收敛性质与退化处理

有效集法在非退化假设下具有有限终止性：由于工作集组合数量有限且目标函数值严格单调，算法在至多 2∣I∣2^{|\mathcal{I}|} 次迭代内终止于最优解。但在实际计算中，退化 (Degeneracy) 是影响鲁棒性的关键问题——当多个约束线性相关或在同一点同时积极时，工作集的选择可能不唯一，导致算法在同一步长处反复增删同一约束（循环）。实践中通过摄动法 (Perturbation)、优先保留策略（仅当乘子显著为负时才删除约束）以及基于 QR 分解的数值稳定的 KKT 系统求解来应对退化。现代求解器（如 QPOPT、quadprog）在实现中通常结合了这些技巧，确保算法的数值稳定性。

经济学与金融学应用

在 投资组合优化 中，Markowitz 均值-方差模型为典型二次规划问题：最小化组合方差 12w⊤Σw\frac{1}{2} w^\top \Sigma w，满足权重之和为 1、目标收益下限等约束。约束包括不允许卖空（wi≥0w_i \geq 0）、行业集中度上限等不等式，有效集法可直接求解并给出哪些约束在最优配置下是积极的（即哪些资产的权重被压至零或上限）。

在 计量经济学 中，带不等式约束的最小二乘估计（如非负最小二乘、单调回归）构成 QP 问题；LASSO 回归的 LARS 算法在结构上与有效集法密切相关——变量进入或离开模型的过程对应约束的添加与删除。在 可计算一般均衡 (CGE) 模型的数值求解中，有效集法也用于处理价格非负、数量非负等互补条件。