第 15 章 约束优化算法基础：分类、消元与价值函数
学习目标
读完本章，你应当能够：
- 识别约束优化问题的类型（LP、QP、线性约束、界约束、凸规划、一般非线性规划），区分硬约束与软约束，并据此判断该选哪类算法。
- 知道后续三章（二次规划、罚/障碍/增广拉格朗日、SQP）各自的基本思路和适用场景。
- 用零空间表示 \(x=Y(AY)^{-1}b+Zx_Z\) 把线性等式约束问题化为无约束问题，比较简单消元与 QR 正交消元在成本和数值稳定性上的取舍。
- 解释非线性消元为什么危险（例 15.1），以及为什么存在不等式约束时消元未必划算。
- 写出 \(\ell_1\) 精确价值函数与 Fletcher 增广拉格朗日价值函数，说明"精确"的含义、罚参数阈值 \(1/\mu>\max|\lambda_i^*|\)，以及"形如 \(f+h(c)/\mu\) 的精确价值函数必不可微"。
读前导读
这一章在解决什么问题
第 12 章告诉我们最优点满足什么条件，第 13、14 章解决了最简单的线性规划。从本章开始转向一般约束优化的算法。本章是一个"工具箱 + 路线图"章节，讲三件事：问题怎么分类、对应用什么算法；怎样用等式约束消去一部分变量；算法每走一步，怎样判断这一步算不算"进步"（价值函数）。
变量消元你早就做过。CFA 里两资产组合的最小方差权重是这样推出来的：利用 \(w_1+w_2=1\) 把 \(w_2\) 写成 \(1-w_1\)，代入方差公式，对 \(w_1\) 求导令其为零。这就是"用约束消元，把约束问题变成无约束问题"。本章把它推广到多个约束、多个变量，并讨论怎么做才数值稳定。
价值函数可以用监管罚款来理解。一个算法在途中可能暂时违反约束，好比一家机构为了收益暂时突破限额。要让它最终守规矩，罚款必须足够重：罚款单价必须高于违规能带来的边际收益，而这个边际收益正是第 12 章的影子价格（乘子）。本章 15.3 节把这句话写成了精确的阈值 \(1/\mu>\max|\lambda_i^*|\)。
需要先想起来的数学
1. 线性方程组的通解 = 特解 + 齐次解。 方程 \(Ax=b\) 若有无穷多解，任意一个解都可写成"某个特解"加上"满足 \(Ax=0\) 的向量"。例：\(x_1+x_2=1\) 的特解可取 \((0,1)\)，\(Ax=0\) 的解是 \(t(1,-1)\)，所以全部解是 \((t,1-t)\)。满足 \(Ax=0\) 的全体叫 \(A\) 的零空间，其中一组线性无关的"方向"叫一组基。见 第 00 册第 06 章 线性代数速成。
2. 正交矩阵与 QR 分解。 列向量两两垂直且长度为 1 的矩阵 \(Q\) 叫标准正交矩阵，满足 \(Q^TQ=I\)，用它变换坐标不会放大误差，好比旋转坐标轴。QR 分解把矩阵写成"正交矩阵 × 上三角矩阵"，是数值计算中最稳的分解之一。这里只需知道它能给出零空间的一组"互相垂直"的基。见 第 00 册第 06 章。
3. 条件数。 矩阵的条件数衡量"输入的小误差会被放大多少倍"。条件数 10 意味着误差最多放大约 10 倍；\(10^{10}\) 意味着结果基本不可信。协方差矩阵中两只股票高度相关时，条件数就会很大。
4. 可微与不可微。 \(|x|\) 在 \(x=0\) 处有一个尖角，左导数 \(-1\)、右导数 \(+1\)，没有导数；\(x^2\) 在 0 处光滑，导数为 0。这个区别是 15.3.3 节的关键：光滑的罚项在零点"太平"，起不到一阶作用。见 第 00 册第 02 章 导数与泰勒展开。
怎么读这一章
核心必读是 15.1.1–15.1.3（问题分类、硬约束与软约束）、15.2.2 的简单消元和几何解释、15.3.2 的 \(\ell_1\) 价值函数与阈值。15.1.4 的算法地图建议先浏览，学完第 16–18 章再回来看会更有体会。
第一次可以只看结论的是 15.2.3 的 QR 细节（记住"正交基最稳、特解是最小范数解"即可）、15.3.3 的不可微证明和 15.3.4 的 Fletcher 函数。15.4.2 的代码用三种方法解同一个行业中性最小方差组合，值得跑一遍，体会"同样的答案，数值性质可以差好几倍"。
15.1 从理论到算法
第 12 章给出了一般约束优化问题
的最优性理论。本章开始讨论求解它的算法。最优性条件为算法设计提供了方向，但高效的算法必须利用目标和约束的具体结构。
15.1.1 问题的分类
- 线性规划：\(f\) 与所有 \(c_i\) 都是线性的（第 13、14 章）；
- 二次规划：约束线性、目标二次（第 16 章）；
- 线性约束优化：所有约束线性，目标任意；
- 界约束优化：约束只有 \(l_i\le x_i\le u_i\)；
- 凸规划：\(f\) 凸，等式约束线性，不等式约束 \(c_i\) 凹（即 \(\{c_i\ge0\}\) 是凸集）；
- 非线性规划：至少有部分约束是一般非线性函数。
这些类别既不互斥也不穷尽。分类越细，算法越能利用结构：例如凸二次规划（目标凸的 QP）是 QP 的子类，局部解就是全局解。本书只研究求局部解的算法，全局优化不在范围内。若问题含离散变量（0/1 变量、整数手数），本书技术不直接适用，需要整数规划算法（分支定界中会反复求解本书的连续松弛）。
量化映射：均值–方差 → 凸 QP；最小 CVaR、\(\ell_1\) 跟踪 → LP；只有个股上下限的多空组合 → 界约束 QP；波动率目标、风险预算、市场冲击成本 → 非线性规划；最小交易手数、持仓只数上限 → 混合整数规划。
15.1.2 先研究问题本身
动手求解前，先看问题能否简化。有时不用计算机就能看出可行域为空或目标无界（习题 15.1）。也可以猜测哪些不等式在解处活跃，把 KKT 条件化为方程组——但这很少实用：识别活跃约束恰恰是约束优化中最难的部分；即使识别出来，非线性方程组也不能保证从任意起点解出（原书第 11 章）。所以需要直接处理 (15.1) 的算法。
15.1.3 硬约束与软约束
**硬约束（hard constraints）**是函数有意义所必须满足的约束：例如目标中有 \(\sqrt{x}\) 就必须 \(x\ge0\)；守恒律要求所有变量之和为零。某些函数在不可行点甚至没有定义。**软约束（soft constraints）**则可以被建模者改写进目标——加一个惩罚违反量的罚项。
必须在所有迭代点满足硬约束时，要用可行算法（feasible algorithms）：从满足硬约束的点出发并始终保持可行。可行算法通常更慢（不能"抄近路"穿越不可行区域），但好处是可以直接用 \(f\) 判断迭代点的好坏，无需引入复杂的价值函数。
量化提示：预算约束、杠杆上限、监管限额通常是硬约束；跟踪误差目标、换手偏好、因子暴露"尽量接近零"常被处理为软约束。第 17 章会说明：用罚项处理软约束时，罚系数越大越接近硬约束，但数值越病态。
15.1.4 后续各章的算法地图
**I. 第 17 章：罚函数、障碍函数、增广拉格朗日方法，以及序列线性约束方法。**它们用一列无约束（或界约束）子问题代替原问题。
- 二次罚函数：只有等式约束时极小化
并让罚参数 \(\mu\downarrow0\)（即罚权重 \(1/\mu\) 越来越大）。
- 精确罚函数：如 \(f(x)+\frac1\mu\sum|c_i(x)|\)，\(\mu\) 足够小时一次极小化就能得到原问题的解，但函数不可微。
- 对数障碍函数：\(f(x)-\mu\sum_{i\in\mathcal I}\log c_i(x)\)，在可行域内部光滑，接近边界时趋于 \(+\infty\)；对递减的 \(\mu\) 序列求极小点。
- 增广拉格朗日方法：结合 Lagrange 函数与二次罚函数，
交替极小化 \(x\) 和更新乘子估计 \(\lambda\)，避免了罚函数与障碍函数的病态。
- 序列线性约束方法：每步在线性化约束下极小化某个（增广）Lagrange 函数，主要用于大规模问题。
**II. 第 18 章：序列二次规划（SQP）。**在每个迭代点用二次子问题近似 (15.1)。等式约束时子问题为
其中 \(W_k\) 是 Lagrange 函数的 Hessian（或其近似），约束是线性化的约束；再沿得到的方向搜索直到某个价值函数下降。SQP 函数求值次数少，是许多最好的约束优化软件的基础；代价是每步要解一个相对复杂的 QP。scipy.optimize.minimize(method="SLSQP") 就是一种 SQP。
**III. 第 16 章（本册拆为第 16a、16b 两章）：二次规划算法。**有效集方法（16a）与梯度投影法、内点法（16b）；有效集 QP 方法也是 SQP 的子问题求解器。
II、III 类算法都要用到约束消元技术，还需要价值函数来衡量进展。本章接下来介绍这两个基础工具，可以先浏览，学到第 16–18 章时再回看。
15.2 变量消元
最自然的想法是用约束消去部分变量，把约束问题变成无约束问题。但消元必须谨慎：它可能改变问题，也可能引入病态。
15.2.1 一个安全的例子和一个危险的例子
安全的例子：\(\min f(x_1,x_2,x_3,x_4)\) s.t. \(x_1+x_3^2-x_4x_3=0\)，\(-x_2+x_4+x_3^2=0\)。令 \(x_1=x_4x_3-x_3^2\)，\(x_2=x_4+x_3^2\)，问题变成对 \((x_3,x_4)\) 的无约束极小化
可以用前面章节的任何无约束算法求解。（原书第一个约束印作 \(x_4x_5\)，按代入式应为 \(x_4x_3\)。）
例 15.1（非线性消元的陷阱，Fletcher）：
解是 \((1,0)\)。消去 \(y\) 得 \(h(x)=x^2+(x-1)^3\)，当 \(x\to-\infty\) 时 \(h\to-\infty\)——盲目变换会误以为问题无界。原因在于约束隐含了 \((x-1)^3=y^2\ge0\)，即 \(x\ge1\)，而且这个隐含的界恰好在解处活跃。消元时必须把它显式加回来。（反过来用 \(y\) 消去 \(x\) 则不会出错，见习题 15.2。）
推导拆解：把 \(h(x)=x^2+(x-1)^3\) 看清楚。\(h'(x)=2x+3(x-1)^2\)，在 \(x=1\) 处等于 \(2\ne0\)，所以无约束地看，\(x=1\) 甚至不是 \(h\) 的驻点，算法会继续往左走，一路走向 \(-\infty\)。错误出在：原约束 \(y^2=(x-1)^3\) 只有在右边非负时才有实数 \(y\)，所以它暗含 \(x\ge1\)。把这个界加回来，问题变成 \(\min h(x)\) s.t. \(x\ge1\)；\(h\) 在 \(x\ge1\) 上递增，解在边界 \(x=1\)，正确。教训是：代入消元时，被消去变量的"定义域"会变成剩余变量的隐含约束，好比用"收益率 = 价格比的对数"做替换时，要记得价格必须为正。
所以非线性消元容易产生难以察觉的错误，多数算法不做非线性消元，而是先线性化约束，再对线性约束做消元。下面系统介绍线性约束的消元。
15.2.2 线性等式约束的简单消元
考虑
\(A\in\mathbb R^{m\times n}\)，\(m\le n\)，行满秩（否则约束要么不相容，要么有冗余行可删）。选 \(m\) 个线性无关的列组成基矩阵（basis matrix） \(B\)，用置换矩阵 \(P\) 把它们换到前面：\(AP=[B\,|\,N]\)（15.5）。相应地 \(P^Tx=(x_B,x_N)\)，\(x_B\) 称为基变量（记号与第 13 章单纯形法一致）。由 \(Bx_B+Nx_N=b\)，
任取 \(x_N\)，按 (15.7) 定出 \(x_B\) 就得到可行点，所以 (15.4) 等价于无约束问题
这称为简单变量消元（simple elimination of variables）。结论：线性等式约束下的非线性优化，数学上等价于一个 \(n-m\) 维的无约束问题。
例 15.2：
把 \(x\) 重排为 \((x_3,x_6,x_1,x_2,x_4,x_5)\)，则 \(B=\mathrm{diag}(1,4)\)，求逆极其简单：
代入后得到四变量无约束问题。选别的两列做基也可以，但 \(B^{-1}N\) 会更复杂。一般用 Gauss 消元化为行阶梯形，取主元列作基；大规模稀疏情形可用兼顾稀疏性与舍入误差的稀疏 LU（如 Harwell 库的 MA48）。
几何解释（设 \(P=I\)）。任一可行点可写成
- \(AZ=0\) 且 \(Z\) 列满秩，所以 \(Z\) 的列是 \(A\) 的**零空间（null space）**的一组基；
- \(Yb\) 是 \(Ax=b\) 的一个特解：把 \(n-m\) 个分量固定为零，只动其余 \(m\) 个分量直到满足约束（称为坐标松弛步）；
- 可行点 = 特解 + 沿约束零空间（切空间）的任意位移。
金融直觉：用两资产最小方差组合把 \(Y\)、\(Z\) 具体化。约束只有 \(w_1+w_2=1\)，即 \(A=(1,1)\)，\(b=1\)。选 \(w_2\) 为基变量（\(B=1\)），\(w_1\) 为非基变量，则特解 \(Yb=(0,1)^T\)（全仓资产 2），零空间方向 \(Z=(1,-1)^T\)（加 1 单位资产 1、减 1 单位资产 2）。所有可行组合都是 \(w=(0,1)^T+w_1(1,-1)^T\)。 代入方差 \(\sigma_p^2=w_1^2\sigma_1^2+(1-w_1)^2\sigma_2^2+2w_1(1-w_1)\rho\sigma_1\sigma_2\)，对 \(w_1\) 求导令为零，得到 CFA 教材里的公式 \(w_1^*=\dfrac{\sigma_2^2-\rho\sigma_1\sigma_2}{\sigma_1^2+\sigma_2^2-2\rho\sigma_1\sigma_2}\)。这正是"在零空间里做无约束极小化"的最小例子。 多资产时，\(Z\) 的每一列是一种"自融资调仓"（买卖金额相抵、总权重不变）；加上行业中性约束后，\(Z\) 的列还要保证每个行业的总权重不变，即"行业内部互换"。
数值风险。简单消元很便宜，但可能不稳定。若约束超平面几乎平行于某个坐标轴，沿该轴的特解会非常大，而真正的可行点通常不大，于是 \(x\) 成了两个巨大向量之差，产生数值抵消（cancellation）（附录 A）。\(B\) 病态时 \(Z\) 也会有大误差。补救的思路是把特解取成最小范数解。
白话解释：数值抵消就是"两个很接近的大数相减，有效数字大量丢失"。例如两个价格 1,000,000.37 和 1,000,000.12 只保留 7 位有效数字时都记成 1,000,000，相减得 0，真实差值 0.25 完全丢失。简单消元若选到一个几乎与约束平行的坐标方向做特解，特解会非常大，最终的可行点（通常不大）就成了"大特解 + 大位移"相互抵消的结果，误差随之放大。
15.2.3 一般约化策略与 QR 正交基
一般地，选 \(Y\in\mathbb R^{n\times m}\)、\(Z\in\mathbb R^{n\times(n-m)}\)，要求
则 \(Ax=b\) 的全部解为
问题化为 \(\min_{x_Z}f(Y(AY)^{-1}b+Zx_Z)\)（15.19）。
数值上最好的选择来自 \(A^T\) 的带列置换 QR 分解：
\(Y,Z\) 合起来是 \(\mathbb R^n\) 的标准正交基，\(AY=\Pi R^T\) 的条件数与 \(A\) 相同，\(Z\) 的列正交规范。此时特解
正是约束 \(Ax=b\) 的最小范数解（\(\min\|x\|\) s.t. \(Ax=b\) 的解）。
推导拆解：为什么 \(x_p=A^T(AA^T)^{-1}b\) 是最小范数解，两步就能看出来。第一步，它满足约束：\(Ax_p=AA^T(AA^T)^{-1}b=b\)。第二步，它最短：任何其他可行点是 \(x=x_p+Zu\)（\(AZ=0\)）。\(x_p\) 是 \(A^T\) 乘某个向量，所以 \(x_p^TZu=(\cdot)^TAZu=0\)，即 \(x_p\) 与零空间方向垂直。由勾股定理 \(\|x\|^2=\|x_p\|^2+\|Zu\|^2\ge\|x_p\|^2\)，等号仅当 \(Zu=0\)。 组合含义：在所有满足预算和中性约束的组合里，\(x_p\) 是"权重平方和最小"、也就是最不集中的一个。
取舍：正交消元数值上最理想，代价是 QR 分解；对大规模稀疏 \(A\)，稀疏 QR 比稀疏 LU 贵得多。折中方案（习题 15.6）：取 \(Y=\begin{bmatrix}I\\(B^{-1}N)^T\end{bmatrix}\)、\(Z\) 同 (15.14)，可以证明 \(Y(AY)^{-1}=A^T(AA^T)^{-1}\)，即特解仍是最小范数解；但 \(Z\) 仍依赖 \(B\) 的选择。
15.2.4 不等式约束的影响
有不等式时，消去等式未必划算。若在例 15.2 中再加 \(x\ge0\)，消去 \(x_3,x_6\) 后，原本简单的界 \(x_3\ge0\)、\(x_6\ge0\) 变成了一般线性不等式 \(8x_1-6x_2+9x_4+4x_5\le6\) 等，对许多算法反而更难。若加的是一般不等式 \(3x_1+2x_3\ge1\)，消元后变为 \(-13x_1+12x_2-18x_4-8x_5\ge-11\)（15.23），复杂度没有明显增加，此时消元值得做。
量化提示：组合优化中的预算约束 \(\mathbf 1^Tw=1\) 和行业/风格中性约束 \(H^Tw=H^Tw_b\) 是线性等式，可以用零空间法消去。但通常同时有 \(w\ge0\) 和个股上限，消元会把简单的界变成一般不等式——这正是主流组合优化器不消元、而直接用 QP 有效集法或内点法的原因。
15.3 价值函数：如何衡量进展
15.3.1 为什么需要价值函数
无约束优化里，"目标下降"就是进展。约束优化中，降低目标与满足约束常常冲突：一步让目标大降却离可行域更远，该不该接受？价值函数（merit function） \(\phi\) 把两者合成一个数，只有当步 \(p\) 使 \(\phi\) 充分下降时才接受。
- 可行方法（初始点和所有迭代点都可行）中，目标函数本身就能当价值函数。例如约束全线性时，有效集方法先用 Phase I 找可行点，此后保持可行（第 16a 章 16.5.7 节）。
- 允许迭代点不可行的算法（大多数 SQP、罚方法）必须用价值函数。
15.3.2 \(\ell_1\) 精确价值函数
\(\mu>0\) 为罚参数。称它"精确"，是因为在一定范围的 \(\mu\) 下，(15.1) 的解就是 \(\phi_1\) 的局部极小点——不需要 \(\mu\to0\)。
定义 15.1（精确价值函数）：若存在 \(\mu^*>0\)，使对任意 \(\mu\in(0,\mu^*]\)，(15.1) 的任一局部解都是 \(\phi(x;\mu)\) 的局部极小点，则称 \(\phi\) 精确。
对 \(\ell_1\) 价值函数，阈值为
即罚权重 \(1/\mu\) 必须大于最大乘子的绝对值。直观理解：乘子 \(\lambda_i^*\) 是"违反约束 \(i\) 一个单位能让目标改善多少"（影子价格）；罚权重必须超过这个收益，违反约束才不划算。许多算法用当前乘子估计来调整 \(\mu\)，第 18 章给出精确规则。
本章代码会在例子 \(\min x_1+x_2\) s.t. \(x_1^2+x_2^2=2\)（\(\lambda^*=-0.5\)）上验证：\(1/\mu<0.5\) 时 \(\phi_1\) 的极小点不在约束上，\(1/\mu>0.5\) 时恰好是解 \((-1,-1)\)。
金融直觉：把罚参数想成监管罚款。由第 12 章 12.4 节，约束右端放松 1 单位，目标能改善约 \(|\lambda_i^*|\)，这是"违规的边际收益"。\(\ell_1\) 罚项对每单位违规收 \(1/\mu\) 的罚款，这是"违规的边际成本"。罚款单价低于违规收益（\(1/\mu<|\lambda_i^*|\)），理性的优化器就会违规，极小点跑到可行域外；罚款单价一旦高于违规收益，违规就不划算，极小点停在约束上。罚款不必无限大，只要超过影子价格即可，这就是"精确"的含义。 用例子核对：约束是圆 \(x_1^2+x_2^2=2\)，\(|\lambda^*|=0.5\)。往圆外走（\(x_1^2+x_2^2>2\)）能让 \(x_1+x_2\) 更小，边际收益 0.5；当罚款单价 \(0.3<0.5\) 时，沿对角线 \(x_1=x_2=t\) 极小化 \(2t+0.3(2t^2-2)\)，令导数 \(2+1.2t=0\) 得 \(t\approx-1.667\)，与代码输出 \((-1.666,-1.666)\) 一致。
15.3.3 精确罚函数必不可微
\(\phi_1\) 因绝对值而不可微。这不是偶然：
命题：只考虑等式约束，令 \(\phi(x;\mu)=f(x)+\frac1\mu h(c(x))\)（15.27），其中 \(h\ge0\)，\(h(0)=0\)。若 \(h\) 可微且 \(\phi\) 精确，则矛盾。
证明：\(h\) 在 0 处取极小，所以 \(\nabla h(0)=0\)。在解 \(x^*\) 处 \(c(x^*)=0\)，若 \(x^*\) 是 \(\phi\) 的局部极小点，则
但约束问题解处 \(\nabla f\) 一般不为零，矛盾。∎
所以 \(\ell_1\)、不平方的 \(\ell_2\)、\(\ell_\infty\) 范数型价值函数都不可微。要得到可微的精确价值函数，必须额外加项。
白话解释：这个命题用罚款类比最好懂。若罚款与违规量的平方成正比（\(h(c)=c^2\)，光滑），违规 0.01 单位只罚 0.0001，小违规几乎免费；而违规带来的收益是一阶的（影子价格 × 0.01）。一阶收益总能压过二阶成本，所以优化器总会"稍微违规一点"，罚得再重也只是让违规量变小，不会变成零。只有罚款与违规量成正比（\(|c|\)，在 0 处有尖角），小违规的成本才也是一阶的，才可能与收益正面抗衡。尖角正是不可微的来源，所以"精确"和"光滑"不可兼得。
15.3.4 Fletcher 增广拉格朗日价值函数
称为最小二乘乘子估计（即 \(\min_\lambda\|\nabla f-A^T\lambda\|\) 的解；形式上就是 OLS 公式 \(\hat\beta=(X^TX)^{-1}X^Ty\)，取 \(X=A^T\)、\(y=\nabla f\)，即把目标梯度对各约束梯度做回归，回归系数就是乘子估计。在最优点，KKT 条件 \(\nabla f=A^T\lambda^*\) 成立，回归残差为零，估计恰好等于真实乘子）。\(\phi_F\) 可微且精确，但阈值涉及二阶导数的界，不易写出（第 18 章 18.5 节）。
两者比较：
| \(\ell_1\) 价值函数 \(\phi_1\) | Fletcher 函数 \(\phi_F\) | |
|---|---|---|
| 光滑性 | 不可微 | 可微 |
| 求值代价 | 便宜（\(f\)、\(c\) 本来就要算） | 每个试探点都要解线性方程组 (15.26) |
| 罚参数阈值 | \(1/\mu>\max\vert \lambda_i^*\vert \)，易估计 | 依赖导数界，难写出 |
| Maratos 效应 | 有：可能拒绝好步，阻碍超线性收敛（第 18 章） | 无 |
| 其他 | \(A\) 近秩亏时 \(\lambda(x)\) 可能很大 |
原–对偶增广拉格朗日价值函数（多个流行 NLP 软件采用）：
它把 \(\lambda\) 当作独立变量，比较原–对偶步前后的值。\((x^*,\lambda^*)\) 是它的驻点但一般不是极小点，需要自适应调整 \(\mu\) 和 \(\lambda\)。
15.4 量化实战
15.4.1 在哪里用
- 零空间法处理中性约束：预算约束和行业中性约束是线性等式。只有等式约束的最小方差（或均值–方差）问题可以用零空间法变成 \(n-m\) 维的无约束二次问题，一次线性求解即得；QR 正交基最稳。
- 最小范数特解：\(x_p=A^T(AA^T)^{-1}b\) 是"满足所有中性约束且离零最近"的组合，常用作优化的初始点或对冲组合的起点。
- 罚系数的设定：用 \(\ell_1\) 罚处理软约束（如因子暴露偏离、跟踪误差上限的软化）时，罚权重必须超过该约束的影子价格，否则在最优点约束不会被精确满足。
15.4.2 代码：三种消元法求行业中性最小方差组合 + \(\ell_1\) 罚阈值
import numpy as np
from scipy.linalg import qr, solve
rng = np.random.default_rng(3)
n, k = 12, 3 # 12 只股票，3 个行业
F = rng.standard_normal((n, 2)) * 0.15
Sigma = F @ F.T + np.diag(rng.uniform(0.02, 0.06, n))
ind = np.repeat(np.arange(k), n // k) # 行业标签
w_b = np.full(n, 1 / n) # 基准：等权
# 约束：预算 1^T w = 1；行业中性：每个行业权重与基准相同（共 k 行，其中一行与预算冗余）
H = np.array([(ind == j).astype(float) for j in range(k)])
A = np.vstack([np.ones(n), H[:-1]]) # 去掉一行避免行秩亏
b = np.r_[1.0, H[:-1] @ w_b]
m = A.shape[0]
# (1) 直接解 KKT 系统 (16.4)：[2Σ -A^T; A 0][w; λ] = [0; b]
K = np.block([[2 * Sigma, -A.T], [A, np.zeros((m, m))]])
sol = solve(K, np.r_[np.zeros(n), b])
w_kkt, lam = sol[:n], sol[n:]
# (2) 正交零空间法 (15.20)-(15.22)：A^T Π = [Q1 Q2][R;0]
Q, R, piv = qr(A.T, pivoting=True)
Q1, Q2 = Q[:, :m], Q[:, m:]
x_p = A.T @ np.linalg.solve(A @ A.T, b) # 最小范数特解
# 极小化 (x_p + Z u)^T Σ (x_p + Z u)：(Z^T Σ Z) u = -Z^T Σ x_p
u = np.linalg.solve(Q2.T @ Sigma @ Q2, -Q2.T @ Sigma @ x_p)
w_ns = x_p + Q2 @ u
# (3) 简单消去 (15.7)：选前 m 列（每行业一只 + 任一只）为基
basic = [0, 4, 8][:m]
nonb = [j for j in range(n) if j not in basic]
B, N = A[:, basic], A[:, nonb]
def full_w(xN):
w = np.zeros(n); w[nonb] = xN; w[basic] = np.linalg.solve(B, b - N @ xN); return w
Zs = np.vstack([-np.linalg.solve(B, N), np.eye(n - m)]) # 置换前的 Z
P = np.zeros((n, n)); P[basic + nonb, np.arange(n)] = 1 # x = P [xB; xN]
Zs = P @ Zs; xs0 = full_w(np.zeros(n - m))
v = np.linalg.solve(Zs.T @ Sigma @ Zs, -Zs.T @ Sigma @ xs0)
w_se = xs0 + Zs @ v
print("三种方法最大差异:", np.abs(w_kkt - w_ns).max(), np.abs(w_kkt - w_se).max())
print("最小范数特解 ||x_p|| =", np.linalg.norm(x_p).round(4),
" 简单消去特解 ||Yb|| =", np.linalg.norm(xs0).round(4))
print("cond(Z^T Σ Z): 正交 Z =", np.linalg.cond(Q2.T @ Sigma @ Q2).round(1),
" 简单消去 Z =", np.linalg.cond(Zs.T @ Sigma @ Zs).round(1))
print("乘子 λ =", lam.round(4), " λ^T b =", (lam @ b).round(5),
" 2 w'Σw =", (2 * w_kkt @ Sigma @ w_kkt).round(5))
print("最小方差权重:", w_kkt.round(3))
# ℓ1 精确罚函数的阈值：min x1+x2 s.t. x1^2+x2^2=2，λ* = -0.5
g = np.linspace(-2, 2, 2001); X1, X2 = np.meshgrid(g, g)
for inv_mu in [0.3, 0.45, 0.55, 1.0]:
phi = X1 + X2 + inv_mu * np.abs(X1**2 + X2**2 - 2)
i = np.unravel_index(phi.argmin(), phi.shape)
print(f"1/μ = {inv_mu:4.2f}: φ1 网格极小点 = ({X1[i]:.3f}, {X2[i]:.3f})")
输出：
三种方法最大差异: 2.3592239273284576e-16 3.7470027081099033e-16
最小范数特解 ||x_p|| = 0.2887 简单消去特解 ||Yb|| = 0.5774
cond(Z^T Σ Z): 正交 Z = 17.9 简单消去 Z = 61.1
乘子 λ = [ 0.0067 0.0008 -0.0014] λ^T b = 0.00657 2 w'Σw = 0.00657
最小方差权重: [0.085 0.092 0.094 0.063 0.096 0.058 0.077 0.103 0.076 0.064 0.113 0.08 ]
1/μ = 0.30: φ1 网格极小点 = (-1.666, -1.666)
1/μ = 0.45: φ1 网格极小点 = (-1.112, -1.112)
1/μ = 0.55: φ1 网格极小点 = (-1.000, -1.000)
1/μ = 1.00: φ1 网格极小点 = (-1.000, -1.000)
解读：
- 三种方法给出同一个解（差异在机器精度量级），但数值性质不同：正交零空间法的约化 Hessian \(Z^T\Sigma Z\) 条件数 17.9，简单消元为 61.1——同样的问题，选择不同的 \(Z\) 会让病态程度差几倍。资产多、约束多时，这个差距会放大。
- 最小范数特解的范数只有简单消元特解的一半：它把权重"均匀摊开"，而简单消元把整个行业权重压在基变量那一只股票上。
- 乘子的含义：由 KKT 条件 \(2\Sigma w=A^T\lambda\)，左乘 \(w^T\) 得 \(\lambda^Tb=2w^T\Sigma w\)，输出验证了这一点。每个 \(\lambda_i\) 是对应约束右端变化一单位时最小方差（的 2 倍）的变化率。
推导拆解（对上一条末句的更正）：代码中的目标是 \(f=w^T\Sigma w\)（梯度 \(2\Sigma w\)），由第 12 章 (12.33) 的等式约束版本，\(\lambda_i=\partial f^*/\partial b_i\)，即 \(\lambda_i\) 就是最小方差本身对 \(b_i\) 的变化率，不需要"2 倍"。可以直接验证：记 \(M=A\Sigma^{-1}A^T\)，由 KKT 解出 \(\lambda=2M^{-1}b\)，\(f^*(b)=b^TM^{-1}b\)，于是 \(\nabla_bf^*=2M^{-1}b=\lambda\)。\(\lambda^Tb=2f^*\) 中的 2 来自另一件事：\(f^*\) 是 \(b\) 的二次齐次函数，由欧拉定理 \(b^T\nabla_bf^*=2f^*\)。
- 精确罚的阈值：\(1/\mu=0.3\) 或 \(0.45\)（小于 \(|\lambda^*|=0.5\)）时，\(\phi_1\) 的极小点跑到可行圆外面；\(1/\mu\) 一旦超过 0.5，极小点就精确落在解 \((-1,-1)\) 上，不需要无穷大的罚权重。注意 \(1/\mu=0.45\) 的结果 \((-1.112,-1.112)\) 与第 17 章二次罚函数在 \(\mu=1\) 时的结果很接近，但二次罚需要 \(\mu\to0\) 才收敛，\(\ell_1\) 罚只要过阈值就精确。
本章小结
约束优化算法要针对问题结构选择：LP、QP、线性约束、界约束、凸规划、一般非线性规划各有专门方法；硬约束需要可行算法，软约束可以罚进目标。后续三章的路线是：二次规划（有效集与内点法）、罚/障碍/增广拉格朗日（用无约束子问题序列逼近）、SQP（用 QP 子问题序列逼近）。线性等式约束可以通过 \(x=Y(AY)^{-1}b+Zx_Z\) 消去，得到 \(n-m\) 维无约束问题；简单消元便宜但可能不稳，QR 正交基最稳且特解是最小范数解；有不等式时消元可能把简单的界变复杂。非线性消元可能悄悄改变问题（例 15.1）。价值函数用来平衡目标下降与约束违反：\(\ell_1\) 精确价值函数在罚权重超过最大乘子绝对值时精确但不可微；Fletcher 函数可微、无 Maratos 效应但求值贵；任何形如 \(f+h(c)/\mu\) 的精确价值函数必不可微。
| 概念 | 公式 / 要点 |
|---|---|
| 简单消元 | \(x_B=B^{-1}b-B^{-1}Nx_N\)；\(Y=[B^{-1};0]\)，\(Z=[-B^{-1}N;I]\) |
| 一般约化 | \(x=Y(AY)^{-1}b+Zx_Z\)，\(AY\) 非奇异，\(AZ=0\) |
| QR 正交基 | \(A^T\Pi=[Q_1\ Q_2][R;0]\)，\(Y=Q_1\)，\(Z=Q_2\) |
| 最小范数解 | \(x_p=A^T(AA^T)^{-1}b\) |
| \(\ell_1\) 价值函数 | \(\phi_1=f+\frac1\mu\sum_{\mathcal E}\vert c_i\vert +\frac1\mu\sum_{\mathcal I}[c_i]^-\) |
| 精确性阈值 | \(1/\mu>\max\{\vert \lambda_i^*\vert _{\mathcal E},\ \lambda_i^*{}_{\mathcal I}\}\) |
| Fletcher 函数 | \(\phi_F=f-\lambda(x)^Tc+\frac1{2\mu}|c|^2\)，\(\lambda(x)=(AA^T)^{-1}A\nabla f\) |
| 不可微定理 | \(f+h(c)/\mu\) 型精确价值函数必不可微 |
练习
基础
- 判断以下问题是否有解：(a) \(\min x_1+x_2\) s.t. \(x_1^2+x_2^2=2\)，\(0\le x_1,x_2\le1\)；(b) \(\min x_1+x_2\) s.t. \(x_1^2+x_2^2\le1\)，\(x_1+x_2=3\)；(c) \(\min x_1x_2\) s.t. \(x_1+x_2=2\)。 提示：(a) 唯一可行点 \((1,1)\)；(b) 不可行；(c) 无下界（取 \(x_1=t,\ x_2=2-t\)，\(t\to\infty\)）。
- 在例 15.1 中改用 \(y\) 消去 \(x\)：\(x=1+y^{2/3}\)，说明此时无约束极小化得到正确解。
- 证明 (15.14) 中 \(Z\) 列线性无关，且 \(Y,Z\) 的列合起来线性无关。
- 验证加入 \(3x_1+2x_3\ge1\) 后用 (15.11) 消元得到 (15.23)。
- 在 15.4.2 的代码中，把行业约束三行全部保留（不删冗余行），观察 KKT 矩阵、\(AA^T\) 和 QR 分解各自出现什么问题。
进阶
- 证明 \(Q_1R^{-T}\Pi^Tb=A^T(AA^T)^{-1}b\)。
- 对折中基 \(Y=\begin{bmatrix}I\\(B^{-1}N)^T\end{bmatrix}\)，\(Z=\begin{bmatrix}-B^{-1}N\\I\end{bmatrix}\)：(a) 证明 \(AZ=0\)、\(Y^TZ=0\)；(b) 证明 \(Y(AY)^{-1}=A^T(AA^T)^{-1}\)。
- 用 15.3.3 节的论证说明为什么平方 \(\ell_2\) 罚 \(f+\frac1{2\mu}\|c\|^2\) 不是精确的，并与第 17 章定理 17.2 的结论 \(c(x_k)\approx-\mu_k\lambda^*\) 联系起来。
- 一个组合有预算约束和 \(K\) 个因子中性约束 \(B^Tw=0\)，目标是 \(\min w^T\Sigma w-\gamma\alpha^Tw\)。用零空间法推导闭式解，并说明当 \(\Sigma=BFB^T+D\) 时为什么零空间法中因子部分会"消失"。 提示：\(B^TZ=0\) 意味着 \(Z^T\Sigma Z=Z^TDZ\)。
- 在 15.4.2 的 \(\ell_1\) 罚实验中，把约束换成不等式 \(x_1^2+x_2^2\le2\)，阈值是否改变？用乘子的符号说明。
原书推荐习题：15.5、15.6（最小范数解与零空间基的构造）、15.1（可行性与有界性判断）、15.7（消元对不等式结构的影响）。原书第 15 章共 15.1–15.7 题。
原书对照
| 本章内容 | 原书位置 | PDF 页码 |
|---|---|---|
| 15.1 问题分类、硬/软约束、算法地图 | 第 15 章引言、§15.1 Categorizing Optimization Algorithms，式 (15.1)–(15.3) | PDF p.438–443 |
| 15.2.1 安全与危险的消元、例 15.1 | §15.2 Elimination of Variables（开头） | PDF p.443–445 |
| 15.2.2–15.2.4 简单消元、例 15.2、QR 正交基、不等式的影响 | §15.2，式 (15.4)–(15.23) | PDF p.445–451 |
| 15.3 价值函数、定义 15.1、不可微定理 | §15.3 Measuring Progress: Merit Functions，式 (15.24)–(15.28) | PDF p.451–455 |
| 习题 15.1–15.7 | Exercises | PDF p.455–456 |
说明：原书第 15 章引言中二次罚函数一段写"increasing values of \(\mu\)"，与 \(1/(2\mu)\) 的写法不一致，应理解为罚权重 \(1/\mu\) 增大；对数障碍项在边界处趋于 \(+\infty\) 而非趋于零；(15.22) 是 \(\min\|x\|\) s.t. \(Ax=b\) 的解。原书正文页码 = PDF 页码减 19（已用 PDF 页眉核对，第 12–16 章均如此）。