第 16a 章 二次规划：KKT 系统与有效集方法

原书第 16 章是组合优化最直接的数学工具，本册拆为第 16a、16b 两章。上篇（第 16a 章，本文件）讲等式约束 QP、KKT 系统的各种解法、不等式 QP 的最优性条件和有效集方法；下篇（第 16b 章，16b_二次规划_梯度投影内点法与组合优化实战.md）讲梯度投影法、内点法、对偶，并给出带换手、行业约束的完整组合优化实例。

学习目标

读完本章上篇，你应当能够：

1. 写出 QP 的一般形式，识别凸 QP 与非凸 QP，并把 Markowitz 均值–方差模型写成 QP。
2. 推导等式约束 QP 的 KKT 系统，说明 \(A\) 行满秩加约化 Hessian \(Z^TGZ\) 正定时解唯一且全局最优；知道约化 Hessian 不正定时会发生什么。
3. 比较 KKT 系统的四类解法（对称不定分解、值空间法、零空间法、共轭基方法），能按问题结构（\(G\) 是否易逆、\(m\) 与 \(n-m\) 的大小）选择；会用惯性 \((n,m,0)\) 检查约化 Hessian 的正定性。
4. 写出不等式 QP 的 KKT 条件，理解退化（线性相关、弱有效约束）的含义和危害。
5. 手算并编程实现凸 QP 的原始有效集方法（工作集、阻挡约束、删去最负乘子），理解有限终止的论证和热启动的价值。
6. 了解不定 QP 的惯性控制有效集方法和它可能的失败方式。

读前导读

这一章在解决什么问题

二次规划（QP）就是"目标是二次函数、约束是线性"的优化问题。对读者来说，它有一个再熟悉不过的名字：均值–方差组合优化。组合方差 \(w^T\Sigma w\) 是权重的二次函数，预算、只做多、个股上限、行业偏离全是线性约束。所以本章是整个第 04 册里与组合管理关系最直接的一章。

本章分两半。前一半处理只有等式约束的 QP（如"允许卖空、只有预算和目标收益"的经典 Markowitz 问题）。这时 KKT 条件就是一个线性方程组，CFA 里的有效前沿闭式解、两基金分离都来自它；你会看到求解这个方程组的几种方法和它们各自适用的场景。

后一半处理不等式约束，介绍有效集方法。它的思路和组合经理手工调仓的直觉一致：先猜哪些股票会"顶格"、哪些会"清仓"，把它们固定住，对剩下的自由股票解一个等式约束问题；如果某只自由股票的权重算出来越界了，就把它固定到边界；如果某个被固定的股票，其乘子（影子价格）显示"放开它反而更好"，就放开它。如此反复，直到所有乘子符号都正确。第 12 章 12.10.3 节的"等边际原则"表，就是这个算法的终点检查表。

需要先想起来的数学

1. 二次型与它的梯度。 \(\tfrac12x^TGx\) 是二次函数的矩阵写法。例：\(G=\begin{bmatrix}2&1\\1&4\end{bmatrix}\)，\(\tfrac12x^TGx=x_1^2+x_1x_2+2x_2^2\)。当 \(G\) 对称时，\(q(x)=\tfrac12x^TGx+d^Tx\) 的梯度是 \(Gx+d\)，Hessian 就是 \(G\)，类比一元的 \(\frac d{dx}(\tfrac12ax^2+bx)=ax+b\)。组合方差 \(w^T\Sigma w\) 的梯度 \(2\Sigma w\) 的第 \(i\) 个分量，就是资产 \(i\) 的边际风险（与组合协方差的 2 倍）。见 第 00 册第 05 章 多元微积分与优化。

2. 正定、半正定与特征值。 对称矩阵 \(G\) 正定 ⇔ 所有特征值都大于 0 ⇔ 对任何非零 \(x\)，\(x^TGx>0\)。协方差矩阵永远半正定；若资产数多于样本期数，它是奇异的（有零特征值），意味着存在方差为零的组合。惯性是正、负、零特征值的个数三元组，例如 \(\mathrm{diag}(3,-1,0)\) 的惯性是 \((1,1,1)\)。见 第 00 册第 06 章 线性代数速成。

3. 分块矩阵与方程组。 把几个矩阵拼成一个大矩阵，例如 \(\begin{bmatrix}G&-A^T\\A&0\end{bmatrix}\begin{bmatrix}x\\\lambda\end{bmatrix}=\begin{bmatrix}-d\\b\end{bmatrix}\)，展开就是两组方程 \(Gx-A^T\lambda=-d\) 和 \(Ax=b\)。分块消元和标量消元一样：从一组方程解出一个未知数块，代入另一组。见 第 00 册第 06 章。

4. 零空间与 KKT 条件。 第 12 章的 KKT 条件、乘子符号和互补松弛，第 15 章的零空间基 \(Z\)（"不破坏约束的调仓方向"），本章都直接使用。如果这两处还不熟，建议先回看第 12 章 12.3、12.10 节和第 15 章 15.2.2 节。

怎么读这一章

核心必读是 16.1（QP 与 Markowitz）、16.2（等式约束 QP 的 KKT 系统、约化 Hessian）、16.4（不等式 QP 的最优性条件）和 16.5.1–16.5.5（有效集方法的思路与例 16.3 手算）。建议把例 16.3 用纸笔跟一遍，再对照 16.7.1 代码的输出。

第一次可以只看结论的是 16.3 中四种解法的细节（记住"\(G\) 易逆或约束少用值空间法、自由度少用零空间法"即可）、16.3.4 共轭基方法、16.5.8 分解更新和 16.6 不定 QP。16.6 末尾的量化提示值得一读：协方差矩阵不是半正定时，优化器可能悄悄给出错误结果。

16.1 二次规划与组合优化

二次规划（quadratic program, QP）：目标为二次函数、约束为线性。一般形式

\(G\) 为 \(n\times n\) 对称矩阵。QP 总能在有限步内解出或判定不可行，但工作量强烈依赖于目标的性质和不等式约束的个数：

• \(G\) 半正定时称凸 QP（convex QP），局部解就是全局解，难度有时与 LP 相当；
• \(G\) 不定时为非凸 QP，可能有多个驻点和局部极小；判断一个可行点是否全局极小是 NP-hard 的（Murty–Kabadi）。本章只求凸 QP 的解或一般 QP 的驻点 / 局部解。

QP 本身重要，也是一般约束优化的核心子问题：SQP（第 18 章）每步解一个 QP，增广拉格朗日法（第 17 章）的子问题也常用 QP 技术求解。

16.1.1 引例：Markowitz 组合优化

\(n\) 种资产收益 \(r_i\) 是随机变量，均值 \(\mu_i=E[r_i]\)，方差 \(\sigma_i^2\)，相关系数 \(\rho_{ij}\)。投资比例 \(x_i\)，全额投资且禁止卖空：\(\sum_ix_i=1\)，\(x\ge0\)。组合收益 \(R=\sum_ix_ir_i\) 的期望为 \(x^T\mu\)，方差为

\(G\) 是协方差矩阵，半正定。Markowitz 模型用参数 \(\kappa\ge0\) 把"高收益"与"低风险"合成一个目标：

\(\kappa\) 是风险厌恶系数（原书称"risk tolerance parameter"，但它越大越保守，实为风险厌恶）。保守投资者取大 \(\kappa\)，激进投资者取接近零的 \(\kappa\)。改写成极小化：\(G\to2\kappa G\)，\(d=-\mu\)，就是标准的凸 QP。

推导拆解：改写只有两步。第一步，\(\max\) 变 \(\min\)：\(\max(x^T\mu-\kappa x^TGx)=-\min(\kappa x^TGx-x^T\mu)\)。第二步，对齐 (16.1a) 的 \(\tfrac12x^TGx\) 写法：\(\kappa x^TGx=\tfrac12x^T(2\kappa G)x\)，所以新 Hessian 是 \(2\kappa G\)，线性项系数 \(d=-\mu\)。 与 CFA 的效用函数对照：CFA 写 \(U=E(R)-\tfrac12A\sigma^2\)，\(A\) 是风险厌恶系数，所以 \(\kappa=A/2\)。\(A=4\) 的投资者对应 \(\kappa=2\)。

原书提醒的实际困难至今没变：\(\mu_i,\sigma_i,\rho_{ij}\) 很难估计。历史数据未必代表未来，新资产没有历史；从业者常把历史数据和主观判断结合。从优化角度，这意味着 QP 的输入有很大噪声——求解器给出的"最优"组合对 \(\mu\) 极其敏感，这是量化实务中做收缩估计、加约束、加换手惩罚的根本原因。

实务中的 QP 组合模型（下篇实现）：

\[\max_w\ \alpha^Tw-\kappa w^T\Sigma w-c^T(b+s)\quad\text{s.t.}\quad \mathbf 1^Tw=1,\ w=w^0+b-s,\ b,s\ge0,\ 0\le w\le u,\ |H^T(w-w_b)|\le\delta,\ \mathbf 1^T(b+s)\le\tau.\]

预算、换手拆分是等式，个股上限、行业偏离、换手预算是不等式——全部线性，目标二次凸。

16.2 等式约束 QP

有效集方法每步都要解一个等式约束 QP，所以先把它彻底弄清楚。设

\(A\) 为 \(m\times n\)（\(m\le n\)）约束 Jacobian，先假设行满秩。

16.2.1 KKT 系统

由定理 12.1，存在乘子 \(\lambda^*\) 使

计算上常写成"步"的形式：设当前估计为 \(x\)，\(x^*=x+p\)，记 \(c=Ax-b\)（约束残差）、\(g=d+Gx\)（当前梯度），则

系数矩阵

推导拆解：(16.4) 怎么来。Lagrange 函数 \(\mathcal L=\tfrac12x^TGx+x^Td-\lambda^T(Ax-b)\)。对 \(x\) 求梯度：二次项给 \(Gx\)，线性项给 \(d\)，约束项给 \(-A^T\lambda\)（\(\lambda^TAx\) 对 \(x\) 的梯度是 \(A^T\lambda\)）。令其为零得 \(Gx-A^T\lambda=-d\)，再配上可行性 \(Ax=b\)，就是 (16.4) 的两行。因为目标二次、约束线性，KKT 条件是线性方程组，一次求解即得答案，不需要迭代。 在 Markowitz 问题 \(\min\tfrac12w^T\Sigma w\) s.t. \(\mathbf 1^Tw=1\)、\(\mu^Tw=R\) 中，第一行读作 \(\Sigma w=\lambda_1\mathbf 1+\lambda_2\mu\)。左边第 \(i\) 个分量是资产 \(i\) 与前沿组合的协方差。移项得 \(\mu_i=(\operatorname{Cov}(r_i,r_p)-\lambda_1)/\lambda_2\)：每个资产的期望收益是它与前沿组合协方差的线性函数。这正是 Black 零 beta CAPM 的数学来源：CAPM 的"期望收益与 beta 成线性关系"，不过是最优组合 KKT 平稳性条件的另一种写法。

称为 KKT 矩阵。记 \(Z\) 为 \(A\) 零空间的一组基（\(n\times(n-m)\)，列满秩，\(AZ=0\)）。\(Z^TGZ\) 称为约化 Hessian（reduced Hessian）：它是目标在可行方向上的曲率。

引理 16.1：若 \(A\) 行满秩、\(Z^TGZ\) 正定，则 KKT 矩阵非奇异，(16.4) 有唯一解。

证明：设 \(K\begin{bmatrix}p\\v\end{bmatrix}=0\)，则 \(Ap=0\)，且 \(0=[p;v]^TK[p;v]=p^TGp\)。\(p\) 在零空间中，写成 \(p=Zu\)，得 \(u^TZ^TGZu=0\)，由正定性 \(u=0\)，\(p=0\)。再由 \(A^Tv=0\) 与 \(A\) 行满秩得 \(v=0\)。∎

注意：\(G\) 本身不必正定，只要在可行方向上正定即可。均值–方差中若协方差矩阵奇异（资产数多于样本数），只要约化 Hessian 正定，等式约束问题仍有唯一解。

金融直觉：\(Z\) 的每一列是一种"不改变约束的调仓"，在只有预算约束时就是多空相抵的自融资调仓。\(u^TZ^TGZu=(Zu)^T\Sigma(Zu)\) 就是这笔调仓本身的方差。约化 Hessian 正定，意思是"任何一笔非零的允许调仓都有风险"，于是最优组合唯一：偏离它的每一种方式都会增加方差。 反过来，如果存在一笔方差为零的允许调仓（例如两只股票在样本里完全同涨同跌，买一只卖一只的组合零波动），沿这个方向加减任意多，组合方差都不变，最优解就有无穷多个，求解器会随便给出其中一个。这就是 12.10.3 节说的"样本协方差在大截面上让解对数据极度敏感"的数学原因。

定理 16.2：在引理 16.1 的条件下，满足 (16.4) 的 \(x^*\) 是 (16.3) 的唯一全局解。

证明：任取可行 \(x\)，令 \(p=x^*-x\)，\(Ap=0\)。展开得 \(q(x)=\frac12p^TGp-p^TGx^*-d^Tp+q(x^*)\)。由 (16.4)，\(Gx^*=-d+A^T\lambda^*\)，所以 \(p^TGx^*=-p^Td+(Ap)^T\lambda^*=-p^Td\)，于是

\(x\ne x^*\) 时 \(u\ne0\)，故 \(q(x)>q(x^*)\)。∎

例 16.1：

即

解为 \(x^*=(2,-1,1)^T\)，\(\lambda^*=(3,-2)^T\)。\(G\) 正定，零空间基可取 \(Z=(-1,-1,1)^T\)（16.10）。

约化 Hessian 不正定时。若 \((x^*,\lambda^*)\) 满足 KKT 但存在 \(u\) 使 \(u^TZ^TGZu\le0\)，令 \(p=Zu\)，则 \(x^*+\alpha p\) 对所有 \(\alpha\) 可行，且

（用到 \(Gx^*+d=A^T\lambda^*\) 和 \(p^TA^T\lambda^*=0\)）。若 \(Z^TGZ\) 有负特征值，沿该方向目标趋于 \(-\infty\)，问题无下界；若只是半正定奇异，解不唯一（习题 16.10）。

16.3 求解 KKT 系统

只要 \(m\ge1\)，KKT 矩阵总是不定的（有正有负特征值）。矩阵的**惯性（inertia）**指其正、负、零特征值的个数三元组。

引理 16.3：若 \(A\) 行满秩、\(Z^TGZ\) 正定，则 KKT 矩阵恰有 \(n\) 个正特征值、\(m\) 个负特征值、无零特征值。

更一般的结论是定理 16.6（由 Sylvester 惯性定律推出）：

所以检查 KKT 矩阵的惯性是否为 \((n,m,0)\)，就能判断约化 Hessian 是否正定，而不必显式构造 \(Z\)。这在内点法、SQP 中检测非凸性非常有用。

白话解释：用例 16.1 核对一下定理 16.6。\(n=3\)、\(m=2\)，零空间基 \(Z=(-1,-1,1)^T\)，算得 \(GZ=(-7,-5,1)^T\)，\(Z^TGZ=7+5+1=13>0\)，所以 \(\mathrm{inertia}(Z^TGZ)=(1,0,0)\)。加上 \((m,m,0)=(2,2,0)\)，得 \(K\) 的惯性 \((3,2,0)\)，与 16.7.1 代码输出一致。读法是：KKT 矩阵里"天生"有 \(m\) 个正、\(m\) 个负特征值来自约束结构，剩下的正负号全由约化 Hessian 决定。数一数 \(K\) 有几个负特征值，多于 \(m\) 个就说明某个可行方向上曲率为负，问题非凸。

16.3.1 直接法：对称不定分解

KKT 矩阵不定，不能用 Cholesky；带部分主元的 LU 浪费了对称性。最有效的是对称不定分解（symmetric indefinite factorization）：

\(P\) 为置换阵（为数值稳定并保持稀疏），\(L\) 单位下三角，\(B\) 是由 \(1\times1\) 和 \(2\times2\) 块组成的块对角阵。成本约为 Gauss 消元的一半。求解时依次解 \(Ly=P^T[g;c]\)、\(B\hat y=y\)、\(L^T\bar y=\hat y\)，再置换回来。\(B\) 与 \(K\) 惯性相同，且 \(2\times2\) 块通常一正一负，所以从分解中可以直接读出惯性。

风险在于：若选主元的启发式不能很好保持稀疏性，\(L\) 会比原矩阵稠密得多（填充）。迭代法方面，CG 在不定系统上不稳定，不推荐；可以用 QMR、LSQR 等。

16.3.2 值空间法

假设 \(G\) 正定。用 \(G\) 做块消元：(16.5) 第一行左乘 \(AG^{-1}\) 再减第二行，得

解这个 \(m\times m\) 对称正定系统得 \(\lambda^*\)，再由

得 \(p\)。适用场景：\(G\) 易求逆（对角、块对角、或有 \(G^{-1}\) 的显式拟牛顿近似），或约束个数 \(m\) 很小。对应的显式逆公式为

量化提示：经典的 Markowitz 闭式解就是值空间法。只有预算和收益两条等式约束时 \(m=2\)，\(\lambda\) 由一个 \(2\times2\) 系统给出，\(w=\Sigma^{-1}A^T\lambda\)——这就是"两基金定理"的来源。因子模型 \(\Sigma=BFB^T+D\) 下，\(\Sigma^{-1}\) 可以用 Sherman–Morrison–Woodbury 公式（附录 A）以 \(O(nk^2)\) 的代价作用到向量上，值空间法对数千只股票也极快。

16.3.3 零空间法

零空间法不要求 \(G\) 非奇异，只需引理 16.1 的条件，但需要零空间基 \(Z\)。把步分解为

\(Y\) 为任意使 \([Y\,|\,Z]\) 非奇异的 \(n\times m\) 矩阵。\(Yp_Y\) 负责满足约束，\(Zp_Z\) 是沿约束的位移。

• 代入 (16.5) 第二行（\(AZ=0\)）：\((AY)p_Y=-c\)。（16.17）
• 代入第一行并左乘 \(Z^T\)：

用 \((n-m)\) 阶约化 Hessian 的 Cholesky 分解求解。

• 乘子：第一行左乘 \(Y^T\)，\((AY)^T\lambda^*=Y^T(g+Gp)\)。（16.19）

例 16.2：沿用例 16.1，取 \(Y=\begin{bmatrix}2/3&-1/3\\-1/3&2/3\\1/3&1/3\end{bmatrix}\)（此时 \(AY=I\)），\(Z=(-1,-1,1)^T\)。从 \(x=0\) 出发：\(c=-b\)，\(g=d\)，算得 \(p_Y=(3,0)^T\)，\(p_Z=0\)，\(p=(2,-1,1)^T\)；由 (16.19) 得 \(\lambda^*=(3,-2)^T\)。

适用场景：自由度 \(n-m\) 小时很有效。主要缺点是需要 \(Z\)，大问题中可能昂贵；\(Z\) 选得差会使 (16.18) 病态（第 15 章的数值实验）。中小规模软件常用列正交的 \(Z\)（QR），此时 \(Z^TGZ\) 的条件数不差于 \(G\)。(16.18) 也可以用 CG 求解，只需要 \(Z\)、\(Z^T\) 与向量的乘积，不必显式形成 \(Z^TGZ\)。

选择经验：\(G\) 正定且 \(AG^{-1}A^T\) 便宜（\(G\) 易逆或 \(m\ll n\)）用值空间法；否则零空间法常更好，尤其当分解 \(G\) 比求 \(Z\) 与 \(Z^TGZ\) 的分解昂贵得多时。没有硬性规则。

16.3.4 基于共轭性的方法（简介）

\(G\) 正定时，可以构造非奇异 \(W\) 使

\(U\) 为 \(m\times m\) 上三角。前 \(n-m\) 列（记为 \(Z\)）在零空间中且关于 \(G\) 共轭规范，后 \(m\) 列记为 \(Y\)。于是 \(Z^TGZ=I\)、\(Z^TGY=0\)，(16.17)–(16.19) 简化为

只需两次三角回代和几个矩阵–向量乘。构造方法：对 \(A\) 做 QR 变体得 \(AQ=[0\ \hat U]\)，对 \(Q^TGQ=LL^T\) 做 Cholesky，令 \(W=QL^{-T}\)。这是一些高效凸 QP 有效集代码（如 Goldfarb–Idnani 对偶方法）的基础。

16.4 不等式约束 QP 的最优性条件

求解不等式 QP 的三大类方法：有效集方法（1970 年代以来最常用，凸与非凸都适用，中小规模首选）、梯度投影法（允许有效集快速变化，最适合界约束）、内点法（大规模凸 QP 有效）。也可以用第 17 章的增广拉格朗日法或第 18 章的 S\(\ell_1\)QP。

Lagrange 函数

最优点的有效集（active set） \(\mathcal A(x^*)=\{i\in\mathcal E\cup\mathcal I:\ a_i^Tx^*=b_i\}\)。一阶条件：

由于约束线性本身就是约束规范，QP 的最优性条件不需要假设有效约束梯度线性无关。

金融直觉：(16.26) 就是第 12 章 12.10.3 节"等边际原则"表的一般形式。第一行说：在最优点，目标的边际变化 \(Gx^*+d\) 被有效约束"定价"后完全抵消，每条有效约束的乘子 \(\lambda_i^*\) 是它的影子价格。第四行说：不等式约束的影子价格非负，因为放宽一条"\(\ge\)"约束不会让结果变差。非有效约束不出现在第一行，相当于它们的影子价格为零（没用满的限额不值钱）。 组合经理可以把它当检查清单：拿到一个优化结果，算出每只股票的边际"风险减收益"，看自由持仓是否相等、清仓的是否不够好、顶格的是否更好，就能判断结果是否真的最优，而不必信任求解器的"成功"状态码。

• 凸 QP：(16.26) 既必要又充分，满足它的点就是全局解。
• 二阶充分条件：\(Z^TGZ\) 正定，\(Z\) 为有效约束 Jacobian 的零空间基。
• 非凸 QP：可能有多个严格局部极小。例如 \(G\) 一正一负特征值、盒子约束下，盒子中心可能是驻点，某些顶点是局部极大、另一些是局部极小。

16.4.1 退化

"退化（degeneracy）"有两种含义：

(a) 解处有效约束梯度 \(a_i,\ i\in\mathcal A(x^*)\) 线性相关（例如 \(\mathbb R^2\) 中三条约束线交于一点）；

(b) 严格互补不成立：某个有效约束的乘子 \(\lambda_i^*=0\)，称为**弱有效（weakly active）**约束。

一个隐蔽的例子：\(\min x_1^2+(x_2+1)^2\) s.t. \(x\ge0\)，解 \(x^*=0\)。无约束极小点 \((0,-1)\) 不在约束上，有效约束也只有 2 个，但 \(x_1\ge0\) 的乘子为零（\(\partial q/\partial x_1=2x_1=0\)），故退化。

危害：(1) 梯度线性相关使计算 \(Z\) 数值困难，使值空间法的 \(AG^{-1}A^T\) 奇异；(2) 弱有效约束让算法难以判断它在解处是否有效，有效集法和梯度投影法会反复加入、移出它，产生锯齿（zigzag）。

量化提示：组合优化中大量股票恰好卡在 \(w_i=0\) 下界、其乘子又接近零（这只股票"可有可无"），就是弱有效约束。表现是：数据的微小扰动使最优组合里这些股票时进时出，换手率虚高。这是数值性质而不是信号，治理办法是加换手惩罚、提高持仓门槛或做组合平滑。

16.5 凸 QP 的原始有效集方法

16.5.1 思路

若事先知道最优有效集 \(\mathcal A(x^*)\)，只需解等式约束 QP \(\min q(x)\) s.t. \(a_i^Tx=b_i,\ i\in\mathcal A(x^*)\)。难点就是找到这个集合。有效集方法维护一个对它的猜测，每步修正一个指标。

与单纯形法（也是有效集方法）的区别：QP 的迭代点不一定在顶点间移动，解可以在边界的任何位置甚至在可行域内部。有效集方法分原始、对偶、原始–对偶三类，本书讲原始方法：迭代点保持原始可行，目标单调下降。

工作集（working set） \(\mathcal W_k\)：全部等式约束加上部分（不一定全部）在 \(x_k\) 处有效的不等式约束，要求其中梯度线性无关。

白话解释：在只做多、带个股上限的组合问题里，工作集就是"当前被钉在边界上的股票清单"（哪些钉在 0，哪些钉在上限），再加上预算约束。算法每一轮做三件事之一： (1) 把清单里的股票当作固定，对其余自由股票解等式约束 QP（16.5.2 节的子问题），朝那个解移动； (2) 移动途中若某只自由股票先撞到 0 或上限，就停在那里，把它加入清单（"加约束"）； (3) 若已经到达当前清单下的最优，就看清单里每只股票的乘子：乘子为负，说明把它钉住是在"帮倒忙"，就把乘子最负的那只放出来（"删约束"）。 第 12 章 12.11.2 节代码"先识别活跃集、再解 KKT 方程组"做的是最后一轮；有效集方法是把"猜清单"这件事系统化。

16.5.2 子问题与步长

令 \(p=x-x_k\)，\(g_k=Gx_k+d\)，在工作集上求方向：

解为 \(p_k\)。工作集中的约束沿 \(p_k\) 保持有效。

步长：若 \(x_k+p_k\) 对所有约束可行，取全步；否则沿 \(p_k\) 走到第一个碰上的约束。对 \(i\notin\mathcal W_k\)：若 \(a_i^Tp_k\ge0\)，任何 \(\alpha\ge0\) 都不会违反；若 \(a_i^Tp_k<0\)，需要 \(\alpha\le(b_i-a_i^Tx_k)/(a_i^Tp_k)\)。所以

这和单纯形法的比值检验是同一个想法。达到最小值的约束称为阻挡约束（blocking constraints），\(\alpha_k<1\) 时把其中一个加入工作集。\(\alpha_k=0\) 是可能的（某约束在 \(x_k\) 有效但不在 \(\mathcal W_k\) 中且 \(a_i^Tp_k<0\)）。

16.5.3 何时删约束：看乘子符号

不断加约束，直到某点 \(\hat x\) 在当前工作集 \(\hat{\mathcal W}\) 上已经是极小点，即子问题解 \(p=0\)。此时

令工作集外的不等式乘子为零，(16.26) 的前三条都满足。

• 若工作集中不等式约束的乘子全部非负，\(\hat x\) 是 KKT 点，凸 QP 下即全局解。
• 若某个 \(\hat\lambda_j<0\)，说明约束 \(j\) "在往回拉"——放开它能让目标下降，应把它从工作集删去。

定理 16.4：设 \(\hat x\) 在工作集 \(\hat{\mathcal W}\) 上满足 (16.30)，工作集梯度线性无关，\(\hat\lambda_j<0\)。删去 \(j\) 后解 (16.31)（即 (16.27) 去掉第 \(j\) 个约束），则 \(a_j^Tp\ge0\)（新方向不会违反约束 \(j\)）；若 \(p\) 满足二阶充分条件，则 \(a_j^Tp>0\) 且 \(p\) 是下降方向。

证明要点：把新子问题的一阶条件与 (16.30) 相减并与 \(p\) 作内积，利用 \(a_i^Tp=0\)（\(i\ne j\)）得

由 \(\hat\lambda_j<0\) 得 \(a_j^Tp\ge0\)。∎

推导拆解：(16.34) 的来历。删去 \(j\) 前，\(\hat x\) 满足 \(G\hat x+d=\sum_{i\in\hat{\mathcal W}}\hat\lambda_ia_i\)（16.30）。删去 \(j\) 后，新子问题的解 \(p\) 满足 \(Gp+(G\hat x+d)=\sum_{i\ne j}\mu_ia_i\)（\(\mu_i\) 是新乘子）。两式相减得 \(Gp=\sum_{i\ne j}(\mu_i-\hat\lambda_i)a_i-\hat\lambda_ja_j\)。两边与 \(p\) 作内积，因为 \(a_i^Tp=0\)（\(i\ne j\)，其余约束仍在工作集里），求和项全部消失，只剩 \(p^TGp=-\hat\lambda_ja_j^Tp\)。凸 QP 中 \(p^TGp\ge0\)，而 \(-\hat\lambda_j>0\)，所以 \(a_j^Tp\ge0\)：新方向朝约束 \(j\) 的可行一侧离开，不会违反它。

金融直觉：乘子为负是什么意思？以 \(w_i\ge0\) 为例。工作集把 \(w_i\) 钉在 0，相当于临时把它当作等式 \(w_i=0\)。等式的乘子可正可负；若算出来为负，按 12.4 节的敏感性，意思是"把右端从 0 往上放宽，目标会下降"，也就是这只股票其实值得买，当前是被错误地钉在了零。按第 12 章等边际原则表的语言，它的边际"风险减收益" \(g_i\) 低于预算影子价格 \(\nu\)，应当进入组合。删掉这条约束，让 \(w_i\) 自由变化，目标就会下降。

定理 16.5：若 (16.27) 的解 \(p_k\ne0\) 且满足二阶充分条件，则 \(q\) 沿 \(p_k\) 严格下降。（因为 \(p=0\) 可行，所以 \(\frac12p_k^TGp_k+g_k^Tp_k<0\)，再由 \(p_k^TGp_k\ge0\) 得 \(g_k^Tp_k<0\)。）

实践中通常删最负乘子对应的约束：由第 12 章的敏感性分析，目标对约束的变化率正比于乘子大小。但这个规则对约束缩放敏感（约束乘以 \(\beta>0\)，乘子变为 \(1/\beta\) 倍），与单纯形法的 Dantzig 规则类似。

16.5.4 算法 16.1

计算可行初始点 x0；取 W0 为 x0 处有效约束的子集；
for k = 0,1,2,...
    解 (16.27) 得 pk；
    if pk = 0
        由 (16.30) 计算乘子 λ̂i，令 Ŵ = Wk；
        if 对所有 i ∈ Wk∩I 有 λ̂i ≥ 0：STOP，x* = xk；
        else  j = argmin_{j∈Wk∩I} λ̂j；x_{k+1} = xk；W_{k+1} = Wk \ {j}；
    else
        按 (16.29) 计算 αk；x_{k+1} = xk + αk pk；
        若有阻挡约束：把其中一个加入工作集得 W_{k+1}；否则 W_{k+1} = Wk；
end

16.5.5 例 16.3：手算一遍

s.t.

从 \(x^0=(2,0)\) 出发，约束 3、5 有效，取 \(\mathcal W_0=\{3,5\}\)（上标为迭代号，下标为分量）。

• 迭代 0：\(x^0\) 是顶点，\(p=0\)。\(g=\nabla q=(2,-5)\)。解 \(\begin{bmatrix}-1\\2\end{bmatrix}\hat\lambda_3+\begin{bmatrix}0\\1\end{bmatrix}\hat\lambda_5=\begin{bmatrix}2\\-5\end{bmatrix}\)，得 \((\hat\lambda_3,\hat\lambda_5)=(-2,-1)\)。删去最负的约束 3，\(\mathcal W_1=\{5\}\)。
• 迭代 1：在 \(x_2=0\) 上极小化，\(p^1=(-1,0)\)，无阻挡，\(\alpha=1\)，\(x^2=(1,0)\)。
• 迭代 2：\(p=0\)，\(\hat\lambda_5=-5<0\)，删去，\(\mathcal W_3=\emptyset\)。
• 迭代 3：无约束方向 \(p^3=(0,2.5)\)，碰到约束 1 时 \(\alpha_3=0.6\)，\(x^4=(1,1.5)\)，\(\mathcal W_4=\{1\}\)。
• 迭代 4：在约束 1 上极小化，\(p^4=(0.4,0.2)\)，\(\alpha=1\)，\(x^5=(1.4,1.7)\)。
• 迭代 5：\(p=0\)，\(\nabla q(x^5)=(0.8,-1.6)=\hat\lambda_1(1,-2)\)，\(\hat\lambda_1=0.8\ge0\)，最优 \(x^*=(1.4,1.7)\)。

（原书正文此处印为 \(\hat\lambda_1=1.25\)；按 \(\nabla q(x^*)=\hat\lambda_1a_1\) 直接计算应为 \(0.8\)，下面的程序也给出 0.8。）

推导拆解：几个关键数字的手算过程。 迭代 0 的乘子：\(\hat\lambda_3a_3+\hat\lambda_5a_5=g\) 逐分量写出，第一个分量 \(-\hat\lambda_3=2\) 得 \(\hat\lambda_3=-2\)；第二个分量 \(2\hat\lambda_3+\hat\lambda_5=-5\) 得 \(\hat\lambda_5=-1\)。 迭代 1 的方向：工作集只剩 \(x_2=0\)，在这条线上极小化 \((x_1-1)^2+(0-2.5)^2\)，最优 \(x_1=1\)，所以 \(p=(1,0)-(2,0)=(-1,0)\)。 迭代 3 的步长：无约束极小点是 \((1,2.5)\)，\(p=(0,2.5)\)。检查每个不在工作集的约束：约束 1 是 \(x_1-2x_2+2\ge0\)，沿 \(p\) 有 \(a_1^Tp=-5<0\)，当前余量 \(b_1-a_1^Tx=-2-(1-0)=-3\)，比值 \(-3/-5=0.6\)；其余约束比值更大或不受影响，所以 \(\alpha=0.6\)，到达 \((1,1.5)\)。这就是 (16.29) 的比值检验。 迭代 4 的方向：在直线 \(x_1-2x_2=-2\) 上找离 \((1,2.5)\) 最近的点（目标就是到 \((1,2.5)\) 的距离平方）。沿法向 \(a_1=(1,-2)\) 投影：\((1,2.5)\) 处 \(a_1^Tx=-4\)，需要调到 \(-2\)，移动 \(t\,a_1\) 使 \(-4+5t=-2\)，\(t=0.4\)，得 \((1.4,1.7)\)。 迭代 5 的乘子：\(\nabla q=(2(1.4-1),2(1.7-2.5))=(0.8,-1.6)=0.8\,(1,-2)\)，所以 \(\hat\lambda_1=0.8>0\)，停止。

几点观察：

• 初始工作集不同，路径不同。\(\mathcal W_0=\emptyset\) 时，无约束方向 \(p=(-1,2.5)\)，\(\alpha=2/3\)，\(x^1=(4/3,5/3)\) 碰到约束 1，再一步即得最优——只用 3 次迭代。
• 每步至多增删一个约束，这给迭代次数一个下界：若解处有 \(t\) 个有效约束而 \(x_0\) 严格可行，至少需要 \(t\) 次迭代。这是有效集法在大规模问题上的软肋（下篇的梯度投影法和内点法解决这个问题）。
• 线性无关性自动保持：阻挡约束的法向不可能是当前工作集法向的线性组合（习题 16.15），删约束也不会引入相关性。

16.5.6 有限终止

设 \(G\) 正定，且 \(p_k\ne0\) 时 \(\alpha_k>0\)。

1. 若 \(p_k=0\)，\(x_k\) 是 \(q\) 在 \(\mathcal W_k\) 上的唯一全局极小。若非最优，由定理 16.4、16.5，删约束后下一方向严格下降，此后 \(q\) 始终低于 \(q(x_k)\)，因此永远不会回到 \(\mathcal W_k\)。
2. 至少每 \(n\) 步出现一次 \(p_k=0\)：\(p_k\ne0\) 时要么 \(\alpha_k=1\)（到达当前工作集的极小，下一步 \(p=0\)），要么加一个约束；连加 \(n\) 次后工作集含 \(n\) 个线性无关约束，只有 \(p=0\)。
3. 工作集个数有限，每个至多访问一次，故有限终止。∎

假设 \(\alpha_k>0\) 排除了循环：删约束后立刻碰到新约束、原地不动、若干步后回到同一工作集。处理方法与 LP 类似，但多数 QP 实现直接忽略这种情况。

16.5.7 初始可行点

• Phase I：同第 13 章。变体是允许用户给一个"不太不可行"的初值 \(\tilde x\)，求解可行性 LP

\(\gamma_i=-\mathrm{sign}(a_i^T\tilde x-b_i)\)（\(\mathcal E\)），\(\gamma_i=1\)（\(\mathcal I\)），以 \(x=\tilde x\) 和相应的 \(z\) 为初始可行点。

• 大 M 法（big M）：省去 Phase I，引入一个标量 \(t\) 度量最大违反量：

由精确罚理论，原问题可行时 \(M\) 足够大（大于乘子的某种范数）则解有 \(t=0\)。启发式选 \(M\)，若解出 \(t>0\) 就增大 \(M\) 重解。它基于 \(\ell_\infty\) 范数，与第 18 章的 S\(\ell_1\)QP 思想相通。

白话解释：大 M 法与第 15 章 15.3.2 节的"罚款必须高于违规收益"是同一个道理。\(t\) 是最大违规量，\(M\) 是每单位违规的罚款。只要 \(M\) 超过各约束影子价格（乘子）合起来的某个量级，违规就不划算，解自动落在 \(t=0\) 的可行区域里。\(M\) 太小，求解器会"交罚款换收益"；\(M\) 太大，数值上又会病态，所以实务中从中等大小开始、不够再加。

量化提示：热启动。日频调仓时，昨天的最优组合和最优工作集是今天极好的初始猜测：大部分"顶格"和"零持仓"的股票不会变。有效集法从昨日工作集出发，往往几步就收敛。这是有效集类 QP 求解器（如 qpOASES、Gurobi 的单纯形型 QP）在日常再平衡中的一大优势；内点法很难利用这类先验信息。

16.5.8 分解的更新

工作集每步只变一个指标，KKT 矩阵至多变一行一列（\(G\) 不变），所以应该更新分解而不是重算。以零空间法 + QR 为例，\(A^T\Pi=Q\begin{bmatrix}R\\0\end{bmatrix}=[Q_1\ Q_2]\begin{bmatrix}R\\0\end{bmatrix}\)，\(Z=Q_2\)：

• 加一个约束 \(a\)：利用 \(Q_1Q_1^T+Q_2Q_2^T=I\)，

再用一个正交变换 \(\hat Q\)（Householder 或一串 Givens 旋转）把 \(Q_2^Ta\) 变成 \((\gamma,0,\dots,0)^T\)。新零空间基是 \(Q_2\hat Q^T\) 的后 \(n-m-1\) 列。成本 \(O(n(n-m))\)，而重算 QR 是 \(O(n^2m)\)。

• 删一个约束：从 \(R\) 删一列，次对角线出现非零元，用一串 Givens 旋转恢复上三角；新零空间基为 \(\bar Z=[Z\ \bar z]\)，多一列。
• 约化 Hessian 的 Cholesky 因子也随之更新：子问题中 \(c=0\)，\(p_Y=0\)，\((Z^TGZ)p_Z=-Z^Tg\)（16.40）。删约束时 \(Z\) 增一列，用平面旋转把 \(L\) 扩展为 \(\bar L\)。

16.6 不定 QP 的有效集方法（简介）

\(G\) 有负特征值时，若约化 Hessian \(Z^TGZ\) 正定，算法逻辑不变；若它有负特征值，子问题解只是鞍点，不能用。这时改用约化 Hessian 的负曲率方向 \(s_Z\)：

选符号使其非上升。沿此方向必然碰到某个约束（否则问题无界），加入工作集，重复直到约化 Hessian 正定。

惯性控制方法（inertia-controlling methods）：从不让约化 Hessian 有多于一个负特征值。要求初始点是顶点（约化 Hessian 为空矩阵）或约化 Hessian 正定的约束驻点。加约束只会让约化 Hessian 维数变小、保持正定，所以不定性只可能在删约束时出现。具体做法（Fletcher 的伪约束 + Gill–Murray 的 \(LDL^T\)）：设 \(Z^TGZ=LDL^T\)，删约束后 \(Z\) 增一列，\(D\) 增一个对角元 \(d_{\rm new}\)。若 \(d_{\rm new}<0\)，解 \(L_+^Ts_Z=e_{\rm last}\) 得负曲率方向 \(s=Z_+s_Z\)，\(s^TGs=d_{\rm new}<0\)；同时把被删的约束作为**伪约束（pseudo-constraint）**暂留在工作集中，等以后能删且保持约化 Hessian 正定时再删。

原书用

演示了完整过程：从顶点 \((2,0)\) 出发，先后删约束、发现约化 Hessian \(Z^TGZ=16-25=-9<0\)、沿负曲率方向 \((4,5)\) 走到 \((3,25/4)\)，最终乘子 \((\lambda_3,\lambda_4)=(25/16,77/16)>0\)，得到局部解（也是全局解）。

有效集方法的失败：\(G\) 不正定时，惯性控制算法不保证找到局部极小。例：\(\min -x_1x_2\) s.t. \(0\le x_1,x_2\le1\)，从 \((0,0)\)、两个下界都在工作集出发。该点是驻点，乘子为零；删去任一约束后约化 Hessian 为 0（奇异），找不到负曲率方向，算法停止——但沿 \((1,1)\) 目标是下降的，它不是局部解。根本原因是：对有效集方法而言，一阶最优并不导致二阶最优，有时需要同时删两个约束。实践中舍入误差往往让算法离开这类点。

量化提示：协方差矩阵由成对删除缺失数据、或直接用样本估计而资产数超过样本数时，可能不是半正定的，均值–方差就变成不定 QP。有效集法可能停在非最优点、内点法可能失败。务必先修正协方差（特征值截断、收缩到对角或单因子目标、最近相关阵投影），保证凸性。

16.7 量化实战（上）

16.7.1 代码一：KKT 系统的三种解法与有效集法

import numpy as np
from scipy.linalg import ldl

# ---------- 例 16.1：等式约束 QP 的三种解法 ----------
G = np.array([[6., 2, 1], [2, 5, 2], [1, 2, 4]]); d = np.array([-8., -3, -3])
A = np.array([[1., 0, 1], [0, 1, 1]]); b = np.array([3., 0])
n, m = 3, 2
K = np.block([[G, -A.T], [A, np.zeros((m, m))]])
sol = np.linalg.solve(K, np.r_[-d, b])
print("KKT 直接解: x* =", sol[:n], " λ* =", sol[n:])
# 惯性：对称不定分解 LBL^T，B 的特征值符号 = K 的惯性
_, Bblk, _ = ldl(K)
ev = np.linalg.eigvalsh(Bblk)
print("KKT 惯性 (正,负,零) =", (int((ev > 0).sum()), int((ev < 0).sum()), int((abs(ev) < 1e-12).sum())))
# 值空间法 (16.13)-(16.14)，从 x=0 出发：g = d, c = -b
g, c = d.copy(), -b
Gi = np.linalg.inv(G)
lam = np.linalg.solve(A @ Gi @ A.T, A @ Gi @ g - c)
p = np.linalg.solve(G, A.T @ lam - g)
print("值空间法:   x* =", p, " λ* =", lam)
# 零空间法 (16.16)-(16.19)，用例 16.2 的 Y, Z
Y = np.array([[2/3, -1/3], [-1/3, 2/3], [1/3, 1/3]]); Z = np.array([[-1.], [-1], [1]])
pY = np.linalg.solve(A @ Y, -c)
pZ = np.linalg.solve(Z.T @ G @ Z, -(Z.T @ G @ Y @ pY + Z.T @ g))
p = Y @ pY + Z @ pZ
lam = np.linalg.solve((A @ Y).T, Y.T @ (g + G @ p))
print("零空间法:   x* =", p, " λ* =", lam, " pY =", pY, " pZ =", pZ)

# ---------- 算法 16.1：凸 QP 原始有效集法，复现例 16.3 ----------
def fmt(W, lam):
    return "{" + ", ".join(f"λ{i+1}={float(l):.3g}" for i, l in zip(W, lam)) + "}"

def active_set_qp(G, d, Ain, bin_, x, W, verbose=True, max_iter=50):
    """min 1/2 x'Gx + d'x  s.t.  Ain x >= bin_（只含不等式）。W: 初始工作集。"""
    W = list(W)
    for k in range(max_iter):
        gk = G @ x + d
        Aw = Ain[W] if W else np.zeros((0, len(x)))
        mw = len(W)
        KK = np.block([[G, -Aw.T], [Aw, np.zeros((mw, mw))]])
        sol = np.linalg.solve(KK, np.r_[-gk, np.zeros(mw)])   # 子问题 (16.27)
        p, lam = sol[:len(x)], sol[len(x):]
        if np.linalg.norm(p) < 1e-10:
            if mw == 0 or lam.min() >= -1e-10:
                if verbose: print(f"  迭代 {k}: p=0, 乘子 {fmt(W, lam)} 全非负 → 最优 x* = {x}")
                return x, W, dict(zip(W, lam))
            j = int(np.argmin(lam))
            if verbose: print(f"  迭代 {k}: p=0, 乘子 {fmt(W, lam)}，删去约束 {W[j]+1}")
            W.pop(j)
        else:
            alpha, block = 1.0, None
            for i in range(len(bin_)):
                if i in W: continue
                ap = Ain[i] @ p
                if ap < -1e-12:
                    t = (bin_[i] - Ain[i] @ x) / ap
                    if t < alpha: alpha, block = t, i
            x = x + alpha * p
            if block is not None: W.append(block)
            if verbose: print(f"  迭代 {k}: p={p.round(3)}, α={alpha:.3f}, x={x.round(3)}, "
                              f"{'加入约束 ' + str(block+1) if block is not None else '无阻挡'}")
    raise RuntimeError

G2 = 2 * np.eye(2); d2 = np.array([-2., -5])            # (x1-1)^2+(x2-2.5)^2
Ain = np.array([[1., -2], [-1, -2], [-1, 2], [1, 0], [0, 1]])
bin_ = np.array([-2., -6, -2, 0, 0])
print("例 16.3，W0 = {3,5}：")
active_set_qp(G2, d2, Ain, bin_, np.array([2., 0]), W=[2, 4])
print("例 16.3，W0 = ∅：")
active_set_qp(G2, d2, Ain, bin_, np.array([2., 0]), W=[])

输出：

KKT 直接解: x* = [ 2. -1.  1.]  λ* = [ 3. -2.]
KKT 惯性 (正,负,零) = (3, 2, 0)
值空间法:   x* = [ 2. -1.  1.]  λ* = [ 3. -2.]
零空间法:   x* = [ 2. -1.  1.]  λ* = [ 3. -2.]  pY = [3. 0.]  pZ = [-1.36642834e-16]
例 16.3，W0 = {3,5}：
  迭代 0: p=0, 乘子 {λ3=-2, λ5=-1}，删去约束 3
  迭代 1: p=[-1.  0.], α=1.000, x=[1. 0.], 无阻挡
  迭代 2: p=0, 乘子 {λ5=-5}，删去约束 5
  迭代 3: p=[-0.   2.5], α=0.600, x=[1.  1.5], 加入约束 1
  迭代 4: p=[0.4 0.2], α=1.000, x=[1.4 1.7], 无阻挡
  迭代 5: p=0, 乘子 {λ1=0.8} 全非负 → 最优 x* = [1.4 1.7]
例 16.3，W0 = ∅：
  迭代 0: p=[-1.   2.5], α=0.667, x=[1.333 1.667], 加入约束 1
  迭代 1: p=[0.067 0.033], α=1.000, x=[1.4 1.7], 无阻挡
  迭代 2: p=0, 乘子 {λ1=0.8} 全非负 → 最优 x* = [1.4 1.7]

三种 KKT 解法结果一致，与例 16.1、16.2 的手算相同；KKT 矩阵惯性为 \((n,m,0)=(3,2,0)\)，验证了约化 Hessian 正定。有效集法完整复现了例 16.3 的六步迭代；换成空的初始工作集只需三步，说明好的初始工作集（热启动）能显著减少迭代。

16.7.2 代码二：等式约束均值–方差、影子价格与两基金定理

允许卖空、只有预算和收益两条等式约束时，均值–方差问题 \(\min\frac12w^T\Sigma w\) s.t. \(\mathbf 1^Tw=1,\ \mu^Tw=R\) 就是 16.2 节的等式 QP。第 12 章 12.10.2 节已从 KKT 条件推导过有效前沿与两基金分离，这里从 KKT 系统的数值解法角度复核同一结论。

import numpy as np

# 等式约束均值-方差：min 1/2 w'Σw  s.t.  1'w = 1,  μ'w = R   （允许卖空）
rng = np.random.default_rng(1)
n = 6
L = rng.standard_normal((n, n)) * 0.1
Sigma = L @ L.T + np.diag(rng.uniform(0.01, 0.04, n))
mu = rng.uniform(0.02, 0.12, n)
A = np.vstack([np.ones(n), mu])
K = np.block([[Sigma, -A.T], [A, np.zeros((2, 2))]])
print(" R      σ(R)     λ_budget  λ_return  d(½σ²)/dR 数值")
prev = None
for R in [0.04, 0.06, 0.08, 0.10]:
    sol = np.linalg.solve(K, np.r_[np.zeros(n), 1.0, R])
    w, lam = sol[:n], sol[n:]
    var = w @ Sigma @ w
    # 数值导数：目标 1/2 w'Σw 对 R 的导数应等于 λ_return
    sol2 = np.linalg.solve(K, np.r_[np.zeros(n), 1.0, R + 1e-6])
    dobj = (0.5 * sol2[:n] @ Sigma @ sol2[:n] - 0.5 * var) / 1e-6
    print(f"{R:.2f}  {np.sqrt(var):.4%}  {lam[0]:+.5f}  {lam[1]:+.5f}  {dobj:+.5f}")
# 两基金定理：任意两个前沿组合的线性组合仍在前沿上
w1 = np.linalg.solve(K, np.r_[np.zeros(n), 1.0, 0.04])[:n]
w2 = np.linalg.solve(K, np.r_[np.zeros(n), 1.0, 0.10])[:n]
w_mix = 0.5 * w1 + 0.5 * w2
w_07 = np.linalg.solve(K, np.r_[np.zeros(n), 1.0, 0.07])[:n]
print("两基金定理: ||0.5 w(4%) + 0.5 w(10%) - w(7%)|| =", np.linalg.norm(w_mix - w_07))

输出：

 R      σ(R)     λ_budget  λ_return  d(½σ²)/dR 数值
0.04  14.3814%  +0.04021  -0.48831  -0.48830
0.06  9.0229%  +0.01647  -0.13875  -0.13874
0.08  9.7890%  -0.00728  +0.21081  +0.21082
0.10  15.8133%  -0.03103  +0.56037  +0.56038
两基金定理: ||0.5 w(4%) + 0.5 w(10%) - w(7%)|| = 1.1385919347227337e-16

解读：

1. 乘子 = 影子价格：收益约束的乘子与目标对 \(R\) 的数值导数完全一致。
2. 乘子符号与有效集逻辑：\(R=4\%,6\%\) 时 \(\lambda_{\rm return}<0\)，说明这两个收益目标低于最小方差组合的收益，把等式约束换成"\(\mu^Tw\ge R\)"时它会被有效集法删除（定理 16.4）；\(R=8\%,10\%\) 时乘子为正，约束有效。这正是"有效前沿只取最小方差组合以上那一半"的优化解释。
3. 两基金定理：KKT 系统是线性的，解 \(w(R)\) 关于 \(R\) 是仿射函数，所以任意两个前沿组合的凸组合仍在（等式约束的）前沿上。加入 \(w\ge0\) 后，有效集随 \(R\) 变化，\(w(R)\) 变成分段仿射——前沿由若干段"拐点"连接，每个拐点就是一次工作集的增删。

本章（上）小结

QP 由二次目标和线性约束组成；凸 QP 局部即全局，非凸 QP 判全局最优是 NP-hard。Markowitz 均值–方差是 QP 的标准应用。等式约束 QP 的解由 KKT 系统给出；\(A\) 行满秩且约化 Hessian \(Z^TGZ\) 正定时 KKT 矩阵非奇异、惯性为 \((n,m,0)\)，解唯一且全局最优；约化 Hessian 有负特征值时问题无下界。KKT 系统可用对称不定分解直接求解，\(G\) 易逆或 \(m\) 小时用值空间法（Markowitz 闭式解即此），\(n-m\) 小时用零空间法，\(G\) 正定时还可用共轭基方法。不等式 QP 的 KKT 条件不需要约束规范；退化（梯度相关或弱有效约束）会导致锯齿。原始有效集方法维护工作集，每步解等式子问题，用比值检验 (16.29) 决定步长并加入阻挡约束，在工作集极小点处检查乘子、删去最负者；严格凸且无循环时有限终止。分解更新与热启动是有效集法高效的关键。不定 QP 需要惯性控制，且可能停在一阶驻点。

练习

基础

1. 证明从定理 12.1、12.6 可以推出 (16.4) 与等式 QP 的二阶充分条件。
2. 点 \(x_0\) 到仿射集 \(\{x:Ax=b\}\) 的最短距离：解 \(\min\frac12\|x-x_0\|^2\) s.t. \(Ax=b\)，证明 \(\lambda^*=(AA^T)^{-1}(b-Ax_0)\)，\(x^*=x_0+A^T(AA^T)^{-1}(b-Ax_0)\)；\(A\) 为行向量 \(a^T\) 时距离为 \(|b-a^Tx_0|/\|a\|\)。（原书习题给出的 \(x^*\) 符号有误，应为加号。）
3. 证明：只要 \(A\ne0\)，KKT 矩阵一定不定；若 KKT 矩阵非奇异，则 \(A\) 行满秩。
4. 对例 16.3 分别取 \(\mathcal W_0=\{3\}\) 和 \(\mathcal W_0=\{5\}\)，手算前两步，再用 16.7.1 的代码核对。 提示：\(\mathcal W_0=\{3\}\) 时 \(p^0=(0.2,0.1)\)，\(x^1=(2.2,0.1)\)。
5. 证明乘子的大小依赖约束的缩放：把约束 \(a_i^Tx\ge b_i\) 乘以 \(\beta>0\)，乘子变为 \(\lambda_i/\beta\)。由此说明"删最负乘子"规则对缩放不变性的缺陷。

进阶

6. 等式 QP 的三种情形：(a) \(Z^TGZ\) 正定 ⇔ 有唯一强局部极小；(b) \(Z^TGZ\) 半正定奇异且 KKT 系统相容 ⇒ 无穷多解；(c) \(Z^TGZ\) 不定或 KKT 系统不相容 ⇒ 无有限解。
7. 证明阻挡约束的梯度不可能是当前工作集梯度的线性组合，从而工作集始终保持线性无关。
8. 用 Sylvester 惯性定律证明定理 16.6。 提示：用 \([Y\ Z]\) 构造合同变换，把 \(K\) 化为块三角形式。
9. 在 16.7.2 的代码中加入 \(w\ge0\)，用 16.7.1 的 active_set_qp（把等式约束写成两条不等式，或修改代码支持等式）求解 \(R\) 从最小方差收益到最大单资产收益的一系列前沿组合，记录每个 \(R\) 的工作集，找出前沿的"拐点"。
10. 设 \(\Sigma=BFB^T+D\)（\(k\) 个因子），给出值空间法 (16.13)–(16.14) 中所有含 \(\Sigma^{-1}\) 运算的 \(O(nk^2)\) 实现，并估计 \(n=5000,\ k=40,\ m=50\) 时的运算量。

原书推荐习题：16.2（最小距离投影，组合约束投影的原型）、16.8、16.9（手算/编程有效集法）、16.10、16.11（KKT 矩阵与约化 Hessian 的性质）、16.15（工作集线性无关性）。原书第 16 章共 16.1–16.18 题，其余在下篇列出。

原书对照

更正说明：例 16.3 最后一步的乘子按 \(\nabla q(x^*)=\hat\lambda_1a_1\) 计算为 \(\hat\lambda_1=0.8\)；原书 16.3 节"不需要假设有效约束梯度线性相关"应为"线性无关"；习题 16.2 中 \(x^*\) 的符号应为加号。原书正文页码 = PDF 页码减 19（已用 PDF 页眉核对，第 12–16 章均如此）。