元信息：《Numerical Optimization》(2nd ed., Springer)，Jorge Nocedal & Stephen J. Wright；本笔记覆盖 PDF 第 445–651 页（原书页码约 426–634；文本章节结构与第 1 版一致，见第 17 章版本说明）。

第 15 章约束优化算法基础（Fundamentals of Constrained Algorithms）（接上一块）

本块从 15.2 节「变量消去」中段开始。第 15 章的问题记号沿用前文：一般非线性规划 (15.1) 为 $\min f(x)$，s.t. $c_i(x)=0,\ i\in\mathcal E$；$c_i(x)\ge 0,\ i\in\mathcal I$。

15.2 变量消去（Elimination of Variables）（接上一块，PDF p.445–451）

线性约束的简单消去（Simple Elimination for Linear Constraints）

问题：

\min f(x)\quad \text{s.t. } Ax=b,\tag{15.4}

$A\in\mathbb R^{m\times n}$，$m\le n$，假设 $A$ 行满秩（若不满秩，要么约束不相容，要么有冗余约束可删去而不改变解）。

行满秩意味着可选出 $m$ 个线性无关的列组成 $m\times m$ 的基矩阵（basis matrix） $B$；用 $n\times n$ 置换矩阵 $P$ 把这些列换到前 $m$ 列：$AP=[B\,|\,N]$ (15.5)，$N$ 为其余 $n-m$ 列（记号与第 13 章单纯形法一致）。
相应划分 $P^Tx=\begin{bmatrix}x_B\\x_N\end{bmatrix}$ (15.6)，$x_B\in\mathbb R^m$ 称为基变量（basic variables），$x_N$ 为非基变量。
由 $PP^T=I$，$b=Ax=AP(P^Tx)=Bx_B+Nx_N$，得 $x_B=B^{-1}b-B^{-1}Nx_N.\tag{15.7}$
任取 $x_N$，按 (15.7) 定出 $x_B$ 即得可行点。于是 (15.4) 等价于无约束问题 $\min_{x_N}\ h(x_N)\stackrel{\text{def}}{=} f\!\left(P\begin{bmatrix}B^{-1}b-B^{-1}Nx_N\\x_N\end{bmatrix}\right).\tag{15.8}$ 称 (15.7) 为简单变量消去（simple elimination of variables）。结论：线性等式约束下的非线性优化在数学上等价于一个无约束问题。

例 15.2：

\min\ \sin(x_1+x_2)+x_3^2+\tfrac13\big(x_4+x_5^4+x_6/2\big)\tag{15.9}

s.t.

8x_1-6x_2+x_3+9x_4+4x_5=6,\qquad 3x_1+2x_2-x_4+6x_5+4x_6=-4.\tag{15.10}

取置换使 $x$ 重排为 $(x_3,x_6,x_1,x_2,x_4,x_5)^T$，则 $AP=\begin{bmatrix}1&0&8&-6&9&4\\0&4&3&2&-1&6\end{bmatrix}$，基矩阵 $B=\mathrm{diag}(1,4)$ 对角、易求逆。由 (15.7)：

\begin{bmatrix}x_3\\x_6\end{bmatrix}=-\begin{bmatrix}8&-6&9&4\\ \tfrac34&\tfrac12&-\tfrac14&\tfrac32\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_4\\x_5\end{bmatrix}+\begin{bmatrix}6\\-1\end{bmatrix}.\tag{15.11}

代入后问题变为四变量无约束问题

\min_{x_1,x_2,x_4,x_5}\ \sin(x_1+x_2)+(8x_1-6x_2+9x_4+4x_5-6)^2+\tfrac13\Big(x_4+x_5^4-\big[\tfrac12+\tfrac38x_1+\tfrac14x_2-\tfrac18x_4+\tfrac34x_5\big]\Big).\tag{15.12}

也可选别的两列做基，但那样 $B^{-1}N$ 会更复杂。

如何选基：一般用高斯消去求行阶梯形（row echelon form），取主元列作为 $B$ 的列。理想的 $B$ 应易于分解且条件数好；大规模稀疏情形可用兼顾稀疏性与舍入误差控制的稀疏高斯消去，代表实现是 Harwell 库的 MA48。但高斯消去并不保证选出"最好"的基。

几何解释（为简化取 $P=I$）：任一可行点可写成

x=Yb+Zx_N,\tag{15.13}\qquad Y=\begin{bmatrix}B^{-1}\\0\end{bmatrix},\quad Z=\begin{bmatrix}-B^{-1}N\\I\end{bmatrix}.\tag{15.14}

$Z$ 有 $n-m$ 个线性无关列（下块是单位阵），且 $AZ=0$，故 $Z$ 是 $A$ 的**零空间（null space）**的一组基；$Y$ 与 $Z$ 的列合起来线性无关，所以 $Y$ 张成 $A^T$ 值域空间的一个补（原书称 $Y$ 为 range space of $A^T$ 的基）。
$Yb$ 是 $Ax=b$ 的一个特解（particular solution）：把 $n-m$ 个分量固定为 0，放松其余 $m$ 个分量直到碰到约束（图 15.2，固定 $x_2=0$ 沿 $x_1$ 轴走到约束线），称坐标松弛步（coordinate relaxation step）。换一个基对应沿另一坐标轴的特解。
可行点 = 特解 + 沿约束零空间（切空间）的位移。

数值风险：简单消去便宜，但可能数值不稳定。若可行集（直线）几乎平行于 $x_1$ 轴，沿 $x_1$ 轴的特解会非常大，而总位移 (15.13) 通常不大，于是 $x$ 是两个巨大向量之差，产生数值抵消（cancellation）。此时应改选沿 $x_2$ 轴的特解（换基），但一般而言选最优基并不容易；$B$ 病态时 $Z$ 的计算也会有误差。解决思路：把特解取为到约束的最小范数步（minimum-norm step），这是下面一般消去策略的特例。

线性约束的一般约化策略（General Reduction Strategies）

选 $Y\in\mathbb R^{n\times m}$、$Z\in\mathbb R^{n\times(n-m)}$，列合起来线性无关，把 $Ax=b$ 的解写成

x=Yx_Y+Zx_Z,\tag{15.15}

要求

AY\ \text{非奇异},\qquad AZ=0.\tag{15.16}

$Z$ 仍是零空间基，$Y$ 的选择留作自由（图 15.3）。代入得 $(AY)x_Y=b$，故

x_Y=(AY)^{-1}b,\tag{15.17}\qquad x=Y(AY)^{-1}b+Zx_Z\tag{15.18}

对任意 $x_Z\in\mathbb R^{n-m}$ 均可行，问题等价于

\min_{x_Z} f\big(Y(AY)^{-1}b+Zx_Z\big).\tag{15.19}

用 QR 分解构造正交基：希望 $AY$ 条件数尽可能好（因为要分解它）。对 $A^T$ 做带列置换的 QR 分解

A^T\Pi=\begin{bmatrix}Q_1&Q_2\end{bmatrix}\begin{bmatrix}R\\0\end{bmatrix},\tag{15.20}

$[Q_1\ Q_2]$ 正交，$Q_1\in\mathbb R^{n\times m}$、$Q_2\in\mathbb R^{n\times(n-m)}$ 列正交规范，$R$ 为 $m\times m$ 非奇异上三角，$\Pi$ 为 $m\times m$ 置换阵（见附录 (A.54) 后的讨论）。令

Y=Q_1,\quad Z=Q_2,\tag{15.21}

则 $Y,Z$ 构成 $\mathbb R^n$ 的标准正交基，且 $AY=\Pi R^T$，$AZ=0$。$AY$ 的条件数与 $R$ 相同，也即与 $A$ 相同。可行点为 $x=Q_1R^{-T}\Pi^Tb+Q_2x_Z$，$R^{-T}\Pi^Tb$ 只需一次三角回代。

可验证特解 $Q_1R^{-T}\Pi^Tb$ 等于

x_p=A^T(AA^T)^{-1}b,\tag{15.22}

即约束 $Ax=b$ 的最小范数解（minimum-norm solution）（图 15.4）。（原文写成 "$\min\|Ax-b\|^2$ 的解"，准确说法是 $\min\|x\|$ s.t. $Ax=b$ 的解。）

取舍：正交基消去在数值稳定性上是理想的，主要代价是 QR 分解；对大规模稀疏 $A$，稀疏 QR 比稀疏高斯消去贵得多。因此有折中方案（习题 15.6）。

不等式约束的影响（The Effect of Inequality Constraints）

存在不等式时，消去等式约束未必有利。

若例 15.2 再加 $x\ge 0$，消去 $x_3,x_6$ 后得到约束 $(x_1,x_2,x_4,x_5)\ge 0$，$8x_1-6x_2+9x_4+4x_5\le 6$，$\tfrac34x_1+\tfrac12x_2-\tfrac14x_4+\tfrac32x_5\le -1$：原先简单的界约束变成一般线性不等式，对许多算法而言没有好处。
若改加一般不等式 $3x_1+2x_3\ge 1$，消去后变为 $-13x_1+12x_2-18x_4-8x_5\ge -11$ (15.23)，复杂度没有明显增加，此时消去值得做。

15.3 度量进展：价值函数（Measuring Progress: Merit Functions）（PDF p.451–455）

动机：若某步使目标大幅下降却离可行域更远，是否接受？约束优化中"降低目标"与"满足约束"两个目标常冲突，需要一个度量来平衡。价值函数（merit function） $\phi$ 量化这种平衡：只有当步 $p$ 使 $\phi$ 充分下降时才接受。

无约束优化里 $f$ 本身就是价值函数。
可行方法（feasible methods）（初始点及所有迭代点都满足约束）中，目标函数仍可作价值函数。例如约束全线性时，某些有效集方法（第 16、18 章）先用 phase-1 求可行初始点，之后每步保持可行。
允许迭代点违反约束的算法需要价值函数。

$\ell_1$ 精确价值函数：

\phi_1(x;\mu)=f(x)+\frac1\mu\sum_{i\in\mathcal E}|c_i(x)|+\frac1\mu\sum_{i\in\mathcal I}[c_i(x)]^-,\qquad [y]^-=\max\{0,-y\}.\tag{15.24}

$\mu>0$ 为罚参数（penalty parameter），决定约束满足相对于目标最小化的权重。称为"精确（exact）"是因为在一定范围的 $\mu$ 下，(15.1) 的解就是 $\phi_1$ 的局部极小点。$\phi_1$ 因绝对值和 $[\cdot]^-$ 而不可微。

Fletcher 增广拉格朗日价值函数（仅等式约束）：

\phi_F(x;\mu)=f(x)-\lambda(x)^Tc(x)+\frac1{2\mu}\sum_{i\in\mathcal E}c_i(x)^2,\tag{15.25}

\lambda(x)=[A(x)A(x)^T]^{-1}A(x)\nabla f(x)\tag{15.26}

称为最小二乘乘子估计（least-squares multiplier estimates）。$\phi_F$ 可微且精确；含不等式时可引入松弛变量。

定义 15.1（精确价值函数）：若存在 $\mu^*>0$，使对任意 $\mu\in(0,\mu^*]$，(15.1) 的任一局部解都是 $\phi(x;\mu)$ 的局部极小点，则称 $\phi(x;\mu)$ 精确。（约定：通过减小 $\mu$ 来加重对约束的惩罚。）

$\ell_1$ 价值函数对所有 $\mu<\mu^*$ 精确，其中 $\frac1{\mu^*}=\max\{|\lambda_i^*|,\ i\in\mathcal E;\ \lambda_i^*,\ i\in\mathcal I\},$ $\lambda^*$ 为最优解处的拉格朗日乘子。即罚权 $1/\mu$ 要大于最大乘子绝对值。许多算法含启发式规则：若判断当前 $\mu$ 可能不满足阈值，就调整 $\mu$（可用当前乘子估计近似 $\mu^*$）。精确规则见第 18 章。
$\phi_F$ 也精确，但阈值涉及导数界，不易写出，留到具体算法（18.5 节）讨论。

两者比较：

$\phi_1$：求值便宜（函数和约束值每步本来就有）；缺点是可能拒绝向解推进良好的步——Maratos 效应（Maratos effect）（第 18 章），已有若干补救策略，但增加算法复杂性。
$\phi_F$：可微、不受 Maratos 效应影响；缺点是每个试探点求值都要解线性方程组 (15.26)。线搜索中可在算出 $\lambda(x_k+p)$ 后用线性插值 $\lambda(x_k)+\alpha(\lambda(x_k+p)-\lambda(x_k))$ 代替 $\lambda(x_k+\alpha p)$。另外 $A$ 秩亏时 $\lambda$ 不唯一，近秩亏时 $\lambda$ 可能过大。

定理（精确罚函数必不可微）：仅考虑等式约束，令 $\phi(x;\mu)=f(x)+\frac1\mu h(c(x))$ (15.27)，$h:\mathbb R^m\to\mathbb R$，$h\ge0$，$h(0)=0$。反证：若 $h$ 可微，因 $h$ 在 0 处取极小，$\nabla h(0)=0$；在解 $x^*$ 处 $c(x^*)=0$，若 $x^*$ 是 $\phi$ 的局部极小点，则

0=\nabla\phi(x^*)=\nabla f(x^*)+\tfrac1\mu\nabla c(x^*)\nabla h(c(x^*))=\nabla f(x^*),

原–对偶增广拉格朗日价值函数（多个流行 NLP 软件采用）：

\mathcal L_A(x,\lambda;\mu)=f(x)-\lambda^Tc(x)+\frac1{2\mu}\|c(x)\|_2^2.\tag{15.28}

算法在 $(x_k,\lambda_k)$ 生成原–对偶步 $(p_x,p_\lambda)$，比较 $\mathcal L_A(x_k+p_x,\lambda_k+p_\lambda;\mu)$ 与 $\mathcal L_A(x_k,\lambda_k;\mu)$。与 $\phi_1,\phi_F$ 不同，它依赖对偶变量；$(x^*,\lambda^*)$ 是 $\mathcal L_A$ 的驻点而一般不是极小点，但某些 SQP 程序通过自适应调整 $\mu,\lambda$ 成功使用它。

注记与文献：一般消去技术见 Fletcher [83]；价值函数综述见 Boggs & Tolle [23]；$\ell_1$ 作为 SQP 价值函数由 Han [132] 提出；(15.25) 由 Fletcher [81] 提出；原–对偶函数 (15.28) 由 Wright [250] 和 Schittkowski [222] 提出。

第 15 章习题概括（PDF p.455–456）

15.1：判断三个小问题是否有解（$\min x_1+x_2$ s.t. $x_1^2+x_2^2=2$, $0\le x_i\le1$；$\min x_1+x_2$ s.t. $x_1^2+x_2^2\le1$, $x_1+x_2=3$（不可行）；$\min x_1x_2$ s.t. $x_1+x_2=2$（无下界））。考查可行性与有界性。
15.2：例 15.1 中用 $y$ 消去 $x$，说明此时无约束极小化得到正确解（与消元方向的选择有关）。
15.3/15.4：证明 (15.14) 中 $Z$ 列无关、$Y,Z$ 合起来线性无关。
15.5：证明 $Q_1R^{-T}\Pi^Tb=A^T(AA^T)^{-1}b$。
15.6：折中基 $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}$，即特解是最小范数解、与基选择无关，条件数仅由 $A$ 决定；但 $Z$ 仍依赖 $B$，仍需谨慎选基。
15.7：验证加 $3x_1+2x_3\ge1$ 后消去得到 (15.23)。

第 15 章（本块部分）本章要点

线性等式约束可通过 $x=Y(AY)^{-1}b+Zx_Z$ 化为 $n-m$ 维无约束问题；$Z$ 是零空间基，$Y$ 决定特解。
简单消去（$Y=[B^{-1};0]$）便宜但可能因基选择不当而数值不稳；QR 正交基最稳定，特解为最小范数解，代价是 QR 分解；有中间方案。
有不等式时消去可能把简单界约束变复杂，需权衡。
价值函数平衡目标下降与约束违反：$\ell_1$ 精确罚函数（不可微、便宜、有 Maratos 效应，罚权需超过最大乘子）、Fletcher 增广拉格朗日（可微、精确、求值贵）、原–对偶增广拉格朗日 $\mathcal L_A$。
"精确且形如 $f+h(c)/\mu$" 的价值函数必不可微。

与量化交易的关联

组合优化中的预算约束 $\mathbf 1^Tw=1$、行业/风格中性约束 $B^Tw=0$ 都是线性等式约束：可用零空间法消去，把问题转成对 $x_Z$ 的无约束（或只剩界约束的）问题；正交零空间基（QR）是数值上最稳的做法。最小范数特解 $A^T(AA^T)^{-1}b$ 在构造满足中性约束的初始组合时常用。
但若同时有 $w\ge0$ 等界约束，消去会把界约束变成一般不等式——这正是许多组合优化器不消去等式、而直接用 QP/内点法的原因。
$\ell_1$ 罚函数的"罚权须大于最大乘子"结论，对用罚函数处理软约束（如换手率、跟踪误差上限的软化）时如何设罚系数有直接指导意义：罚权太小，约束在最优点不会被精确满足。

第 16 章二次规划（Quadratic Programming）（PDF p.457–505）

PDF p.457 为章名页。二次规划（quadratic program, QP）：目标为二次函数、约束为线性。它本身重要，也是一般约束优化方法（SQP 第 18 章、增广拉格朗日第 17 章）的子问题。一般形式：

\min_x\ q(x)=\tfrac12x^TGx+x^Td\tag{16.1a}

\text{s.t.}\quad a_i^Tx=b_i,\ i\in\mathcal E;\qquad a_i^Tx\ge b_i,\ i\in\mathcal I.\tag{16.1b,c}

$G$ 为 $n\times n$ 对称阵。QP 总能在有限步内解出（或判定不可行），但工作量强烈依赖于目标函数性质和不等式约束数量。$G$ 半正定时称凸 QP（convex QP），难度有时与 LP 相当；$G$ 不定时为非凸 QP，可能有多个驻点和局部极小。本章只研究求凸 QP 的解或一般 QP 的驻点的算法。

引例：组合优化（Portfolio Optimization）（PDF p.459–460）

$n$ 种投资收益 $r_i$ 为随机变量（常假设正态），均值 $\mu_i=E[r_i]$，方差 $\sigma_i^2=E[(r_i-\mu_i)^2]$。投资比例 $x_i$，全额投资且禁止卖空：$\sum_i x_i=1$，$x\ge0$。组合收益 $R=\sum_i x_ir_i$ (16.2)，期望 $E[R]=x^T\mu$。相关系数 $\rho_{ij}=E[(r_i-\mu_i)(r_j-\mu_j)]/(\sigma_i\sigma_j)$，越接近 1 两资产越同涨同跌；反向变动则为负。组合方差

E[(R-E[R])^2]=\sum_i\sum_j x_ix_j\sigma_i\sigma_j\rho_{ij}=x^TGx,\quad G_{ij}=\rho_{ij}\sigma_i\sigma_j,

$G$ 半正定。Markowitz 模型用风险容忍参数（原文称 risk tolerance parameter，实际是风险厌恶系数）$\kappa\in[0,\infty)$ 合成单一目标：

\max\ x^T\mu-\kappa x^TGx\quad\text{s.t.}\ \sum_ix_i=1,\ x\ge0.

保守投资者取大 $\kappa$，激进投资者取接近 0 的 $\kappa$。实际困难在于估计 $\mu_i,\sigma_i,\rho_{ij}$：可用历史数据（如过去五年），但未来未必重复过去，新兴投资没有历史数据；从业者常把历史数据与主观判断结合。

16.1 等式约束 QP（Equality-Constrained Quadratic Programs）（PDF p.460–464）

有效集方法每步都要解一个等式约束 QP，所以先研究它。设 $m\le n$ 个约束：

\min_x\ q(x)=\tfrac12x^TGx+x^Td\quad\text{s.t. } Ax=b,\tag{16.3}

$A=[a_i]^T_{i\in\mathcal E}$ 为 $m\times n$ 约束雅可比，先假设行满秩、约束相容。

一阶必要条件：存在 $\lambda^*$ 使

\begin{bmatrix}G&-A^T\\A&0\end{bmatrix}\begin{bmatrix}x^*\\\lambda^*\end{bmatrix}=\begin{bmatrix}-d\\b\end{bmatrix}.\tag{16.4}

（由定理 12.1 直接得到。）计算上常写成步长形式：设当前估计 $x$，$x^*=x+p$，

\begin{bmatrix}G&A^T\\A&0\end{bmatrix}\begin{bmatrix}-p\\\lambda^*\end{bmatrix}=\begin{bmatrix}g\\c\end{bmatrix},\quad c=Ax-b,\ g=d+Gx,\ p=x^*-x.\tag{16.5–16.6}

系数矩阵称 KKT 矩阵（Karush–Kuhn–Tucker matrix）。记 $Z$ 为 $A$ 零空间基（$n\times(n-m)$，满秩，$AZ=0$）。

引理 16.1：$A$ 行满秩、约化 Hessian（reduced Hessian） $Z^TGZ$ 正定，则 KKT 矩阵 $K=\begin{bmatrix}G&A^T\\A&0\end{bmatrix}$ (16.7) 非奇异，(16.4) 有唯一解 $(x^*,\lambda^*)$。证明：设 $K\begin{bmatrix}p\\v\end{bmatrix}=0$。由 $Ap=0$，$0=[p;v]^TK[p;v]=p^TGp$。$p=Zu$，$0=u^TZ^TGZu\Rightarrow u=0\Rightarrow p=0$；再由 $A^Tv=0$ 与行满秩得 $v=0$。

例 16.1：$\min q(x)=3x_1^2+2x_1x_2+x_1x_3+2.5x_2^2+2x_2x_3+2x_3^2-8x_1-3x_2-3x_3$，s.t. $x_1+x_3=3$，$x_2+x_3=0$。即 $G=\begin{bmatrix}6&2&1\\2&5&2\\1&2&4\end{bmatrix}$，$d=(-8,-3,-3)^T$，$A=\begin{bmatrix}1&0&1\\0&1&1\end{bmatrix}$，$b=(3,0)^T$。解 $x^*=(2,-1,1)^T$，$\lambda^*=(3,-2)^T$。$G$ 正定，零空间基 $Z=(-1,-1,1)^T$ (16.10)。

定理 16.2：在引理 16.1 条件下，满足 (16.4) 的 $x^*$ 是 (16.3) 的唯一全局解。证明：任一可行 $x$，令 $p=x^*-x$，$Ap=0$。代入得 $q(x)=\tfrac12p^TGp-p^TGx^*-d^Tp+q(x^*)$ (16.11)。由 (16.4)，$Gx^*=-d+A^T\lambda^*$，故 $p^TGx^*=-p^Td$，于是 $q(x)=\tfrac12p^TGp+q(x^*)=\tfrac12u^TZ^TGZu+q(x^*)$，$p=Zu$；正定性给出 $q(x)>q(x^*)$（$x\ne x^*$）。

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

q(x^*+\alpha p)=q(x^*)+\alpha p^T(Gx^*+d)+\tfrac12\alpha^2p^TGp=q(x^*)+\tfrac12\alpha^2p^TGp\le q(x^*)

（用到 $Gx^*+d=A^T\lambda^*$ 和 $p^TA^T\lambda^*=u^TZ^TA^T\lambda^*=0$）。若 $Z^TGZ$ 有负特征值则有严格下降方向，问题无下界。只有当存在 KKT 点且 $Z^TGZ$ 半正定时 (16.3) 才有解，且此时解不是严格局部极小。

16.2 求解 KKT 系统（Solving the KKT System）（PDF p.464–470）

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

引理 16.3：$A$ 行满秩、$Z^TGZ$ 正定，则 KKT 矩阵 (16.7) 有 $n$ 个正特征值、$m$ 个负特征值、无零特征值。（由后文定理 16.6 推出。）

直接解法（Direct Solution of the KKT System）

KKT 矩阵不定，不能用 Cholesky；带部分主元的 LU 忽略了对称性。最有效的是对称不定分解（symmetric indefinite factorization）（第 6 章）： $P^TKP=LBL^T,\tag{16.12}$ $P$ 置换阵（为数值稳定、并在稀疏时保持稀疏性），$L$ 单位下三角，$B$ 为 $1\times1$ 或 $2\times2$ 块的块对角阵。成本约为稀疏高斯消去的一半。
求解步骤：解 $Ly=P^T\begin{bmatrix}g\\c\end{bmatrix}$；解 $B\hat y=y$；解 $L^T\bar y=\hat y$；令 $\begin{bmatrix}-p\\\lambda^*\end{bmatrix}=P\bar y$。置换只是重排分量；$B\hat y=y$ 只需解若干小系统，成本为 $(m+n)$ 的小倍数；与 $L,L^T$ 的三角回代成本较大但通常远小于分解本身。
风险：若选置换的启发式不能很好保持稀疏性，$L$ 会比原矩阵稠密得多（填充）。
迭代法：CG 在非正定系统上不稳定，不推荐；可用一般或对称不定系统的方法，如 QMR、LSQR。

值空间法（Range-Space Method）

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

(AG^{-1}A^T)\lambda^*=AG^{-1}g-c,\tag{16.13}

解此对称正定系统得 $\lambda^*$，再由

Gp=A^T\lambda^*-g\tag{16.14}

得 $p$。需要对 $G^{-1}$ 运算并分解 $m\times m$ 矩阵 $AG^{-1}A^T$。适用于：$G$ 条件好且易求逆（如对角或块对角）；$G^{-1}$ 由拟牛顿公式显式给出；$m$ 很小，形成 $AG^{-1}A^T$ 所需回代次数不多。它是对称消去的特例：相当于在 (16.12) 中取 $P=\mathrm{diag}(P_1,P_2)$，先消前 $n$ 个变量。显式逆公式：

\begin{bmatrix}G&A^T\\A&0\end{bmatrix}^{-1}=\begin{bmatrix}C&E\\E^T&F\end{bmatrix},\tag{16.15}

$C=G^{-1}-G^{-1}A^T(AG^{-1}A^T)^{-1}AG^{-1}$，$E=G^{-1}A^T(AG^{-1}A^T)^{-1}$，$F=-(AG^{-1}A^T)^{-1}$。

零空间法（Null-Space Method）

不要求 $G$ 非奇异，只需引理 16.1 的条件（$A$ 行满秩、$Z^TGZ$ 正定），但需要零空间基 $Z$。分解

p=Yp_Y+Zp_Z,\tag{16.16}

$Y$ 为任意使 $[Y|Z]$ 非奇异的 $n\times m$ 阵。$Yp_Y$ 是特解，$Zp_Z$ 是沿约束的位移。

代入 (16.5) 第二行（$AZ=0$）：$(AY)p_Y=-c$ (16.17)。$A[Y|Z]=[AY|0]$ 秩为 $m$，故 $AY$ 非奇异。
代入第一行：$-GYp_Y-GZp_Z+A^T\lambda^*=g$，左乘 $Z^T$： $(Z^TGZ)p_Z=-[Z^TGYp_Y+Z^Tg],\tag{16.18}$ 用 $(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$ 同 (16.10)。从 $x=(0,0,0)^T$ 出发：$c=-b$，$g=d=(-8,-3,-3)^T$，算得 $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) 病态。中小规模软件常取列正交的 $Z$，此时 $Z^TGZ$ 的条件数不差于 $G$；大规模稀疏时只能用不那么可靠的 $Z$。 (16.18) 也可用 CG 求解：只需矩阵–向量乘，无需显式形成 $Z^TGZ$，甚至无需显式 $Z$，只要能算 $Z$、$Z^T$ 与向量之积；缺点是无显式 $Z$ 时无法使用修正 Cholesky 等标准预条件，有效预条件仍是研究课题。

选择经验：$G$ 正定且 $AG^{-1}A^T$ 便宜（$G$ 易求逆或 $m\ll n$）时用值空间法；否则零空间法常更好，特别是分解 $G$ 比求 $Z$ 与 $Z^TGZ$ 的分解昂贵得多时。没有硬性规则，因为计算 $Z$ 时的填充即使在同维问题间差别也很大。

基于共轭性的方法（A Method Based on Conjugacy）

适用于 $G$ 正定，是巧用共轭性的零空间法，是高效凸 QP 方法的基础。构造非奇异 $W\in\mathbb R^{n\times n}$：

W^TGW=I,\qquad AW=\begin{bmatrix}0&U\end{bmatrix},\tag{16.20}

$U$ 为 $m\times m$ 上三角。第一式说明 $W$ 的列关于 $G$ 共轭；第二式说明前 $n-m$ 列在 $A$ 的零空间中。构造：用 QR 变体（习题 16.6）求正交 $Q$ 与上三角 $\hat U$ 使 $AQ=[0\ \hat U]$；对 $Q^TGQ=LL^T$ 做 Cholesky；令 $W=QL^{-T}$，则 $U=\hat UL^{-T}$。划分 $W=[Z\ Y]$（前 $n-m$ 列为 $Z$），得

Z^TGZ=I,\ Z^TGY=0,\ Y^TGY=I;\qquad AY=U,\ AZ=0.\tag{16.21–16.22}

于是 (16.17)–(16.19) 简化为

Up_Y=-c,\qquad p_Z=-Z^Tg,\qquad U^T\lambda^*=Y^Tg+p_Y,\tag{16.23}

只需两次 $U$ 的三角回代和与 $Y^T,Z^T$ 的矩阵–向量乘。

16.3 不等式约束问题（Inequality-Constrained Problems）（PDF p.470–473）

方法概览：经典**有效集方法（active-set methods）**适用于凸与非凸问题，自 1970 年代起最常用；**梯度投影法（gradient projection）**允许有效集快速变化，最适合只有变量界约束的问题；**内点法（interior-point methods）**对大规模凸 QP 有效。QP 也可用第 17 章增广拉格朗日法或第 18 章 S$\ell_1$QP 精确罚方法求解。

最优性条件：拉格朗日函数

\mathcal L(x,\lambda)=\tfrac12x^TGx+x^Td-\sum_{i\in\mathcal I\cup\mathcal E}\lambda_i(a_i^Tx-b_i).\tag{16.24}

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

Gx^*+d-\sum_{i\in\mathcal A(x^*)}\lambda_i^*a_i=0;\quad a_i^Tx^*=b_i\ (i\in\mathcal A(x^*));\quad a_i^Tx^*\ge b_i\ (i\in\mathcal I\setminus\mathcal A(x^*));\quad \lambda_i^*\ge0\ (i\in\mathcal I\cap\mathcal A(x^*)).\tag{16.26}

技术要点：定理 12.1 原本假设 LICQ，但约束线性本身就是一种约束规范，所以 QP 的最优性条件不需要假设有效约束梯度线性无关（原文此处笔误写成 "linearly dependent"）。二阶充分条件：$Z^TGZ$ 正定，$Z$ 为有效约束雅可比 $[a_i]^T_{i\in\mathcal A(x^*)}$ 的零空间基；等式情形下此时 $x^*$ 为全局解。$G$ 不正定时可能有多个满足二阶必要条件的严格局部极小，称"非凸"或"不定" QP。图 16.1：左图 $G$ 一正一负特征值，盒子约束下 $x^{**}$ 为局部极大、$x^*$ 为局部极小、盒子中心为驻点；右图两个特征值都为负，$\tilde x$ 为全局极大，$x^*,x^{**}$ 为局部极小。

退化（Degeneracy）：该术语含义多样，本质指以下之一： (a) 解处有效约束梯度 $a_i,\ i\in\mathcal A(x^*)$ 线性相关； (b) 严格互补（定义 12.2）不成立，即某有效约束 $\lambda_i^*=0$（**弱有效（weakly active）**约束，定义 12.3）。图 16.2：左图唯一有效约束处恰好也是无约束极小点，$Gx^*+d=0$，乘子为零；右图 $\mathbb R^2$ 中三个约束在解处同时有效，必线性相关。更隐蔽的例子：$\min x_1^2+(x_2+1)^2$ s.t. $x\ge0$，解 $x^*=0$，无约束极小点不在约束上，有效约束也不多于 $n=2$，但 $x_1\ge0$ 的乘子为零，故退化。危害：(1) 梯度线性相关使计算 $Z$ 数值困难，使值空间法中 $AG^{-1}A^T$ 奇异；(2) 弱有效约束让算法难以判断其在解处是否有效，有效集法和梯度投影法会因此"犹豫"而锯齿式（zigzag）地反复加入/移出该约束，需加保护措施。

16.4 凸 QP 的有效集方法（Active-Set Methods for Convex QP）（PDF p.474–487）

有效集方法一般是中小规模问题最有效的方法。凸情形（$G$ 半正定）下可行域凸，局部解即全局解。称 $\mathcal A(x^*)$ 为最优有效集；若事先知道它，只需解等式约束 QP $\min q(x)$ s.t. $a_i^Tx=b_i,\ i\in\mathcal A(x^*)$。难点就是确定这个集合。与单纯形法（第 13 章，也是有效集方法）的区别：QP 的迭代点不一定在顶点间移动，可能（包括解本身）在边界其他位置或可行域内部。有效集法分原始、对偶、原始–对偶三类；本书只讲原始方法：迭代点保持原始可行，目标单调下降。

工作集（working set） $\mathcal W_k$：所有等式约束 + 部分（未必全部）有效不等式约束；要求其中约束梯度线性无关（即使该点全部有效约束梯度线性相关）。

子问题：令 $p=x-x_k$，$g_k=Gx_k+d$，$q(x_k+p)=\tfrac12p^TGp+g_k^Tp+\text{const}$，

\min_p\ \tfrac12p^TGp+g_k^Tp\quad\text{s.t. } a_i^Tp=0,\ i\in\mathcal W_k.\tag{16.27}

解记 $p_k$。工作集中的约束沿 $p_k$ 保持满足（$a_i^T(x_k+\alpha p_k)=b_i$）。$G$ 正定时可用 16.2 节任一方法求解。

步长：若 $x_k+p_k$ 可行则取全步；否则 $x_{k+1}=x_k+\alpha_kp_k$ (16.28)。对 $i\notin\mathcal W_k$：若 $a_i^Tp_k\ge0$，任何 $\alpha\ge0$ 都满足；若 $a_i^Tp_k<0$，需 $\alpha_k\le(b_i-a_i^Tx_k)/(a_i^Tp_k)$。故

\alpha_k=\min\Big(1,\ \min_{i\notin\mathcal W_k,\ a_i^Tp_k<0}\frac{b_i-a_i^Tx_k}{a_i^Tp_k}\Big).\tag{16.29}

达到最小值的约束称阻挡约束（blocking constraints）。$\alpha_k=0$ 完全可能（某约束在 $x_k$ 有效但不在 $\mathcal W_k$ 中且 $a_i^Tp_k<0$）。$\alpha_k<1$ 时把一个阻挡约束加入工作集。

终止与删约束：持续加约束直到某点 $\hat x$ 在工作集 $\hat{\mathcal W}$ 上极小化 $q$，即子问题解 $p=0$。此时

\sum_{i\in\hat{\mathcal W}}a_i\hat\lambda_i=g=G\hat x+d.\tag{16.30}

令不在工作集的不等式乘子为零，则 (16.26a–c) 满足。若 $\hat{\mathcal W}\cap\mathcal I$ 中乘子都非负，(16.26d) 也满足，$\hat x$ 为 KKT 点；$G$ 半正定时为局部（即全局）极小，$G$ 正定时为严格局部极小。若某 $\hat\lambda_j<0$，按 12.2 节，删去该约束可使目标下降。

定理 16.4：设 $\hat x$ 满足工作集 $\hat{\mathcal W}$ 上等式子问题的一阶条件（(16.30) 及 $a_i^T\hat x=b_i$），工作集约束梯度线性无关，存在 $j\in\hat{\mathcal W}$ 使 $\hat\lambda_j<0$。删去 $j$ 后解

\min_p\ \tfrac12p^TGp+(G\hat x+d)^Tp\quad\text{s.t. } a_i^Tp=0,\ i\in\hat{\mathcal W},\ i\ne j,\tag{16.31}

则 $a_j^Tp\ge0$（$p$ 对约束 $j$ 可行）；若 $p$ 满足 (16.31) 的二阶充分条件，则 $a_j^Tp>0$ 且 $p$ 是 $q$ 的下降方向。证明：存在 $\tilde\lambda_i$ 使 $\sum_{i\ne j}\tilde\lambda_ia_i=Gp+(G\hat x+d)$ (16.32)；二阶必要条件给出 $p^TGp\ge0$（$p=Zp_Z$）。与 (16.30) 相减：$\sum_{i\ne j}(\tilde\lambda_i-\hat\lambda_i)a_i-\hat\lambda_ja_j=Gp$ (16.33)。与 $p$ 作内积，利用 $a_i^Tp=0$：

-\hat\lambda_ja_j^Tp=p^TGp\tag{16.34}

由 $p^TGp\ge0$、$\hat\lambda_j<0$ 得 $a_j^Tp\ge0$。若二阶充分条件成立且 $a_j^Tp=0$，则 $p^TGp=0\Rightarrow p=0$，代回 (16.33) 由线性无关得 $\hat\lambda_j=0$，矛盾。

实践中通常删最负乘子对应的约束：第 12 章灵敏度分析表明，删去一个约束时目标的下降率与其乘子大小成正比。

定理 16.5：若 (16.27) 的解 $p_k\ne0$ 且满足二阶充分条件，则 $q$ 沿 $p_k$ 严格下降。证明：由定理 16.2，$p_k$ 是唯一全局解；$p=0$ 可行，故 $\tfrac12p_k^TGp_k+g_k^Tp_k<0$；凸性给出 $p_k^TGp_k\ge0$，所以 $g_k^Tp_k<0$，小 $\alpha$ 下 $q(x_k+\alpha p_k)<q(x_k)$。推论：$G$ 正定（严格凸）时所有子问题都满足二阶充分条件，$p_k\ne0$ 就严格下降——这是有限终止论证的关键。

算法 16.1（凸 QP 有效集方法）：

计算可行初始点 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

初始可行点：可用第 13 章 Phase I。变体：允许用户给不必可行的初值 $\tilde x$（"不太不可行"可减少 Phase I 工作量），解可行性 LP

\min_{(x,z)} e^Tz\quad\text{s.t. } a_i^Tx+\gamma_iz_i=b_i\ (i\in\mathcal E),\ a_i^Tx+\gamma_iz_i\ge b_i\ (i\in\mathcal I),\ z\ge0,

$\gamma_i=-\mathrm{sign}(a_i^T\tilde x-b_i)$（$i\in\mathcal E$），$\gamma_i=1$（$i\in\mathcal I$）。初始可行点 $x=\tilde x$，$z_i=|a_i^T\tilde x-b_i|$（$\mathcal E$），$z_i=\max(b_i-a_i^T\tilde x,0)$（$\mathcal I$）。原问题可行则最优值为零，其解的 $x$ 部分可行；$\mathcal W_0$ 取其处有效约束的线性无关子集。

大 M 法（big M）：省去 Phase I，引入标量人工变量 $t$ 度量违反量：

\min_{(x,t)}\ \tfrac12x^TGx+x^Td+Mt\quad\text{s.t. } t\ge a_i^Tx-b_i,\ t\ge-(a_i^Tx-b_i)\ (i\in\mathcal E);\ t\ge b_i-a_i^Tx\ (i\in\mathcal I);\ t\ge0.\tag{16.35}

由精确罚函数理论，原问题可行时 $M$ 足够大则解有 $t=0$。做法：启发式选 $M$，若解得 $t>0$ 就增大 $M$ 重解。初始可行点易得：$x=\tilde x$，$t$ 取足够大。与 S$\ell_1$QP 相关，区别在于大 M 法基于 $\ell_\infty$ 范数而非 $\ell_1$。

例 16.3（图 16.3；下标为分量、上标为迭代号）：

\min q(x)=(x_1-1)^2+(x_2-2.5)^2

s.t. (1) $x_1-2x_2+2\ge0$；(2) $-x_1-2x_2+6\ge0$；(3) $-x_1+2x_2+2\ge0$；(4) $x_1\ge0$；(5) $x_2\ge0$。

$x^0=(2,0)$，约束 3、5 有效，$\mathcal W_0=\{3,5\}$（也可取 $\{5\}$、$\{3\}$ 或 $\emptyset$，迭代路径不同）。顶点处 $p=0$。由 (16.30)：$\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：$p^1=(-1,0)^T$，$\alpha_1=1$，$x^2=(1,0)$，无阻挡，$\mathcal W_2=\{5\}$。
迭代 2：$p^2=0$，$\hat\lambda_5=-5$，删去，$\mathcal W_3=\emptyset$。
迭代 3：无约束解 $p^3=(0,2.5)$，$\alpha_3=0.6$，$x^4=(1,1.5)$，阻挡约束 1，$\mathcal W_4=\{1\}$。
迭代 4：$p^4=(0.4,0.2)$，步长 1，无阻挡，$x^5=(1.4,1.7)$，$\mathcal W_5=\{1\}$。
迭代 5：$p^5=0$，$\hat\lambda_1=1.25\ge0$，最优 $x^*=(1.4,1.7)$。

补充说明：

不同初始工作集：$\mathcal W_0=\{3\}$ 时 $p^0=(0.2,0.1)$，$x^1=(2.2,0.1)$；$\mathcal W_0=\{5\}$ 时直接到 $(1,0)$；$\mathcal W_0=\emptyset$ 时 $p=(-1,2.5)$，$\alpha=2/3$，$x^1=(4/3,5/3)$，$\mathcal W_1=\{1\}$，下一步即得最优。
即使 $\mathcal W_0$ 等于初始有效集，之后 $\mathcal W_k$ 与 $\mathcal A(x_k)$ 也可能不同（多个阻挡约束只加一个）。
线性无关性的维持：阻挡约束的法向不可能是当前工作集法向的线性组合（习题 16.15），删约束不会引入相关性。
删最负乘子对约束缩放敏感（约束乘 $\beta>0$，乘子变为 $1/\beta$ 倍），类似单纯形法的 Dantzig 规则；更抗缩放的策略常更好，本书不展开。
每步至多加/删一个约束，给迭代次数一个下界：若解处有 $m$ 个有效约束而 $x_0$ 严格可行，至少需 $m$ 次迭代；加了又删会更多。

有限终止（严格凸，假设 $p_k\ne0$ 时 $\alpha_k>0$）：

若 $p_k=0$，$x_k$ 是 $q$ 在 $\mathcal W_k$ 上的唯一全局极小；若非最优（有负乘子），由定理 16.4、16.5，删约束后下一方向严格下降，此后 $q$ 始终低于 $q(x_k)$，故永不返回 $\mathcal W_k$。
至少每 $n$ 步出现一次 $p_k=0$：$p_k\ne0$ 时要么 $\alpha_k=1$（到达当前工作集极小，下一步 $p=0$），要么加一个约束；连续加 $n$ 次后工作集含 $n$ 个线性无关约束，只有 $p=0$ 可行。
工作集数目有限，每个至多访问一次，故有限步终止。 $\alpha_k>0$ 的假设排除了循环（cycling）：$x_k=x_{k+l}$ 且 $\mathcal W_k=\mathcal W_{k+l}$——删约束后立刻碰到新约束、原地不动。处理方法与 LP（第 13 章）类似；多数 QP 实现直接忽略循环。

分解更新（Updating Factorizations）：工作集每步只变一个指标，KKT 矩阵至多变一行一列（$G$ 不变），可更新而非重算分解，这对有效集法的效率至关重要。以零空间法 + QR 为例：

A^T\Pi=Q\begin{bmatrix}R\\0\end{bmatrix}=[Q_1\ Q_2]\begin{bmatrix}R\\0\end{bmatrix},\tag{16.37}

取 $Z=Q_2$。

加一个约束：$\bar A^T=[A^T,\ a]$。利用 $Q_1Q_1^T+Q_2Q_2^T=I$， $\bar A^T\begin{bmatrix}\Pi&0\\0&1\end{bmatrix}=Q\begin{bmatrix}R&Q_1^Ta\\0&Q_2^Ta\end{bmatrix}.\tag{16.38}$ 取正交阵 $\hat Q$ 使 $\hat Q(Q_2^Ta)=(\gamma,0,\dots,0)^T$（$|\gamma|=\|Q_2^Ta\|$），得 $\bar A^T\bar\Pi=\bar Q\begin{bmatrix}\bar R\\0\end{bmatrix}$，$\bar Q=[Q_1\ \ Q_2\hat Q^T]$，$\bar R=\begin{bmatrix}R&Q_1^Ta\\0&\gamma\end{bmatrix}$。新零空间基 $\bar Z$ 取 $Q_2\hat Q^T$ 的后 $n-m-1$ 列。利用 $\hat Q$ 的特殊结构（如 Householder/Givens），成本 $O(n(n-m))$，而从头做 QR 为 $O(n^2m)$；零空间小时尤其划算。
删一个约束：相当于从 $R$ 删一列，破坏上三角（次对角线出现非零），用一串平面旋转（Givens）恢复；新零空间基形如 $\bar Z=[Z\ \bar z]$ (16.39)，即增加一列。成本视删除列位置而定，但总比重算便宜（详见 Gill 等 [105, §5]）。
约化 Hessian：子问题中 $c=0$，故 $p_Y=0$，$p_Z$ 满足 $(Z^TGZ)p_Z=-Z^Tg$ (16.40)。若已有 $Z^TGZ=LL^T$，删约束后 $Z$ 增一列，可用平面旋转把 $L$ 更新为 $\bar L$。还可同步更新约化梯度 $Z^Tg$（见 16.6 节）。

16.5 不定 QP 的有效集方法（Active-Set Methods for Indefinite QP）（PDF p.487–493）

$G$ 有负特征值时需修改搜索方向和步长。若 $Z^TGZ$ 正定，$p=Zp_Z$ 指向子问题极小点，逻辑不变；若 $Z^TGZ$ 有负特征值，$p$ 只指向鞍点，不能用。此时改求约化 Hessian 的负曲率方向（direction of negative curvature） $s_Z$，使

q(x+\alpha Zs_Z)\to-\infty\quad(\alpha\to\infty),\tag{16.41}

并选符号使 $\nabla q(x)^TZs_Z\le0$（非上升）。沿此方向会碰到某个约束并加入工作集（碰不到则问题无界）；重复直到约化 Hessian 正定。困难：允许多个负特征值就需要谱分解或对称不定分解，且工作集变化时难以高效更新。

惯性控制方法（inertia-controlling methods）：从不让约化 Hessian 有多于一个负特征值。要求初始点 $x_0$ 要么是顶点（约化 Hessian 为空矩阵），要么是约化 Hessian 正定的约束驻点。每步加或删一个约束：加约束时约化 Hessian 维数减小，保持正定或为空矩阵（见习题）；因此不定只可能在删约束时出现，而删约束只发生在当前点是工作集上的极小点时，此时取负曲率方向作为新搜索方向。

具体算法（Fletcher [80] 的伪约束 + Gill–Murray [107] 的 $LDL^T$ 负曲率）：设 $Z^TGZ=LDL^T$ 正定（$D$ 对角元为正），工作集元素个数为 $t$。删约束后 $Z_+=[Z\ z]$，

L_+=\begin{bmatrix}L&0\\l^T&1\end{bmatrix},\qquad D_+=\begin{bmatrix}D&0\\0&d_{n-t+1}\end{bmatrix}.

若 $d_{n-t+1}<0$，约化 Hessian 在新工作集上不定。解 $L_+^Ts_Z=e_{n-t+1}$，$s=Z_+s_Z$，则

s^TGs=s_Z^TL_+D_+L_+^Ts_Z=e_{n-t+1}^TD_+e_{n-t+1}=d_{n-t+1}<0.

此时不显式删除约束 $i$，而把它作为**伪约束（pseudo-constraint）**留在工作集中，保证工作集的约化 Hessian 正定。沿 $s$ 走到碰到约束，然后照常迭代加约束直到求得等式子问题的解；若此时能删去伪约束且保持约化 Hessian 正定就删，否则保留到以后。

示例：

\min\ \tfrac12x^T\begin{bmatrix}1&0\\0&-1\end{bmatrix}x\quad\text{s.t. (1) }x_2\ge0;\ (2)\ x_1+2x_2\ge2;\ (3)\ -5x_1+4x_2\le10;\ (4)\ x_1\le3.\tag{16.42}

（图 16.4）

$x^1=(2,0)$，$\mathcal W=\{1,2\}$，顶点。解 $\begin{bmatrix}0&1\\1&2\end{bmatrix}\begin{bmatrix}\lambda_1\\\lambda_2\end{bmatrix}=\begin{bmatrix}2\\0\end{bmatrix}$ 得 $(\lambda_1,\lambda_2)=(-4,2)$，删约束 1。
$\mathcal W=\{2\}$，$Z=(2,-1)^T$，$Z^TGZ=3$（$L=1,D=3>0$）。子问题解 $x^2=(-2/3,4/3)^T$，$\lambda_2=-2/3<0$，需删约束 2。
$\mathcal W=\emptyset$，取 $Z=I$，$L=I$，$D=G$，第二个对角元为负——不定情形。解 $L^Ts_Z=e_2$ 得 $s=(0,1)^T$；$\nabla q(x^2)^Ts=(-2/3,-4/3)\cdot(0,1)<0$，为下降方向（否则取反号）。把约束 2 作为伪约束保留，$\mathcal W=\{2\}$。
沿 $s$ 走 $\alpha=1/3$ 碰到约束 3：$x^3=(-2/3,5/3)$，$\mathcal W=\{2,3\}$，顶点，$L,D$ 为空。
试删伪约束：工作集 $\{3\}$ 时 $Z=(4,5)^T$，$Z^TGZ=16-25=-9<0$，不能删，继续保留；但用这个假想删除求负曲率方向：$L^Ts_Z=e_1$，$s_Z=1$，$s=(4,5)^T$（下降方向）。
步长 $\alpha=11/12$ 碰到约束 4：$x^4=(3,25/4)$，$\mathcal W=\{2,3,4\}$。此时可删伪约束 2：工作集 $\{3,4\}$ 的约化 Hessian 为空矩阵，$x^4$ 是其子问题解。
乘子：$\begin{bmatrix}3\\-25/4\end{bmatrix}=\begin{bmatrix}5&-1\\-4&0\end{bmatrix}\begin{bmatrix}\lambda_3\\\lambda_4\end{bmatrix}$，得 $(\lambda_3,\lambda_4)=(25/16,77/16)>0$，$x^4$ 为局部解（实际也是全局解）。缺点：工作集中约束更多，增加退化可能。

初始点选择：初始点须为顶点或约化 Hessian 正定的点，可能需引入在初始点有效、且与工作集其他约束线性无关的人工约束。例：$\min -x_1x_2$ s.t. $-1\le x_1,x_2\le1$，从 $(0,0)$ 出发无约束有效，$\mathcal W_0=\emptyset$ 时约化 Hessian 不定；引入人工约束 $x_1=0$、$x_1-x_2=0$ 即可起步。求得当前工作集极小后，选择每个人工约束法向的符号使其乘子非正，从而可删除；若有选择，优先删临时约束。

有效集方法的失败：$G$ 不正定时惯性控制算法不保证找到局部极小。可能存在非最优点：满足一阶条件、约化 Hessian 正定，但某不等式乘子为零；此时一次删一个约束找不到改进方向，需同时删两个以上。例：$\min -x_1x_2$ s.t. $0\le x_1,x_2\le1$，从 $(0,0)$、两约束都在工作集出发：该点是驻点、作为顶点是工作集上的极小，但删任一约束后约化 Hessian 奇异（为 0），找不到可行负曲率方向，算法在此终止，而它不是局部解（沿 $(1,1)$ 可下降）。这种失败不常见，舍入误差往往使算法离开这类点；已有若干降低失败概率的手段但都不能保证成功。本例中可先固定 $x_2=0$ 把 $x_1$ 移到 1（目标不变），再把 $x_2$ 移到 1 得最优解。根本原因：对有效集方法而言，一阶最优并不导致二阶最优。

用 $LBL^T$ 分解检测不定性（Detecting Indefiniteness Using the LBLᵀ Factorization）（PDF p.492–493）：对称不定分解 (16.12) 也可判断约化 Hessian 是否正定，在内点法、SQP 中同样有用。记 $\mathrm{inertia}(K)=(n_+,n_-,n_0)$。Sylvester 惯性定律：$C$ 非奇异则 $\mathrm{inertia}(C^TKC)=\mathrm{inertia}(K)$。反复应用得：

定理 16.6：$K$ 如 (16.7)，$A$ 秩为 $m$，则

\mathrm{inertia}(K)=\mathrm{inertia}(Z^TGZ)+(m,m,0).

因此 $Z^TGZ$ 正定时 $K$ 的惯性为 $(n,m,0)$（即引理 16.3）；并且即使 $G$ 负定，$K$ 也至少有 $m$ 个正特征值。若 $K=LBL^T$（设 $P=I$），$B$ 与 $K$ 同惯性；$2\times2$ 块通常构造成一正一负特征值，所以 $K$ 的正特征值数 = $2\times2$ 块数 + 正的 $1\times1$ 块数。于是对称不定分解可用来控制惯性控制方法的逻辑：只要检查 KKT 矩阵惯性是否为 $(n,m,0)$，就知道约化 Hessian 是否正定，而不必显式构造 $Z$。

16.6 梯度投影法（The Gradient-Projection Method）（PDF p.493–498）

经典有效集法每步只改一个指标，大规模问题可能需要很多步（如初始无有效约束、解处 200 个有效约束，至少 200 步）。梯度投影法能快速改变有效集，在约束简单（尤其只有界约束）时最高效。考虑界约束 QP：

\min_x\ q(x)=\tfrac12x^TGx+x^Td\quad\text{s.t. } l\le x\le u.\tag{16.43}

（凸 QP 的对偶是界约束问题，故适用面广。）可行域称"盒子（box）"；缺失的界令为 $\pm\infty$。不要求 $G$ 正定，凸与非凸都可用。

每次迭代两阶段：

从当前点沿最速下降方向 $-g$（$g=Gx+d$）搜索，碰到界就把方向"折弯"保持可行，沿此分段路径找 $q$ 的第一个局部极小点，称 Cauchy 点 $x^c$（类比第 4 章）。工作集取 $\mathcal W=\mathcal A(x^c)$（在 $x^c$ 处有效的界）。
在 $x^c$ 所在的面上"探索"：固定 $x_i=x_i^c,\ i\in\mathcal A(x^c)$，求解子问题。（本节上标表示迭代号，下标表示分量。）

Cauchy 点计算：投影算子

P(x,l,u)_i=\begin{cases}l_i,&x_i<l_i\\x_i,&x_i\in[l_i,u_i]\\u_i,&x_i>u_i\end{cases}\tag{16.44}

分段线性路径 $x(t)=P(x^0-tg,l,u)$ (16.45)，$g=\nabla q(x^0)$（图 16.5，$\mathbb R^3$ 示例）。各分量到达界的时刻

\bar t_i=\begin{cases}(x_i^0-u_i)/g_i,&g_i<0,\ u_i<+\infty\\(x_i^0-l_i)/g_i,&g_i>0,\ l_i>-\infty\\\infty,&\text{otherwise}\end{cases}\tag{16.46}

$x_i(t)=x_i^0-tg_i$（$t\le\bar t_i$），否则 $x_i^0-\bar t_ig_i$：分量以投影梯度速率移动，碰界后固定。去掉重复和零值后把 $\bar t_i$ 排序为断点 $0<t_1<t_2<\cdots$，依次检查区间 $[t_{j-1},t_j]$。在该段上 $x(t)=x(t_{j-1})+\Delta t\,p^{j-1}$，$\Delta t=t-t_{j-1}\in[0,t_j-t_{j-1}]$，

p_i^{j-1}=\begin{cases}-g_i,&t_{j-1}<\bar t_i\\0,&\text{otherwise}\end{cases}\tag{16.47}

q(x(t))=f_{j-1}+f'_{j-1}\Delta t+\tfrac12f''_{j-1}(\Delta t)^2,\tag{16.48}

$f_{j-1}=d^Tx(t_{j-1})+\tfrac12x(t_{j-1})^TGx(t_{j-1})$，$f'_{j-1}=d^Tp^{j-1}+x(t_{j-1})^TGp^{j-1}$，$f''_{j-1}=(p^{j-1})^TGp^{j-1}$。令导数为零得 $\Delta t^*=-f'_{j-1}/f''_{j-1}$。若 $\Delta t^*\in[0,t_j-t_{j-1})$ 且 $f''_{j-1}>0$，则局部极小在 $t=t_{j-1}+\Delta t^*$；否则若 $f'_{j-1}>0$，极小在 $t=t_{j-1}$；其余情形进入下一区间。$p^j$ 与 $p^{j-1}$ 通常只差一个分量，可增量更新系数以省计算。

子空间极小化（Subspace Minimization）：

\min_x q(x)\quad\text{s.t. } x_i=x_i^c\ (i\in\mathcal A(x^c));\ l_i\le x_i\le u_i\ (i\notin\mathcal A(x^c)).\tag{16.49}

不必（也不宜）精确求解——它可能几乎与原问题一样难。全局收敛只需近似解 $x^+$ 满足 $q(x^+)\le q(x^c)$ 且可行。折中做法：忽略 (16.49c) 界约束，对 (16.49a,b) 用迭代法（如 16.2 节零空间法 + CG），从 $x^c$ 出发，一碰到界或 CG 产生负曲率方向就停止（参见算法 4.3）。此问题的零空间基 $Z$ 形式特别简单（就是自由变量对应的单位列，习题 16.17）。

算法 16.2（QP 的梯度投影法）：

计算可行初始点 x0；
for k = 0,1,2,...
    若 xk 满足 (16.43) 的 KKT 条件：STOP，x* = xk；
    令 x = xk，求 Cauchy 点 xc；
    求 (16.49) 的近似解 x+，使 q(x+) ≤ q(xc) 且可行；
    x_{k+1} = x+；
end

收敛性质：若满足严格互补（解处有效界的乘子都非零），$\mathcal A(x^c)$ 最终稳定，不会反复进出；退化时可能不稳定，有若干防止手段。 一般线性约束：原理上可用，但投影到 $\{a_i^Tx\ge b_i\}$ 需要解凸 QP $\min\|x-\bar x\|^2$ s.t. $a_i^Tx\ge b_i$，成本可能接近原问题，通常不划算。

16.7 内点法（Interior-Point Methods）（PDF p.498–501）

把第 14 章 LP 的原始–对偶内点法简单推广到凸 QP；描述简单、相对易实现，对某些问题很高效。非凸推广仍在研究中，不讨论。考虑

\min_x\ q(x)=\tfrac12x^TGx+x^Td\quad\text{s.t. } Ax\ge b,\tag{16.50}

$G$ 对称半正定，$A=[a_i]_{i\in\mathcal I}$（$m\times n$），$\mathcal I=\{1,\dots,m\}$（等式约束只需简单修改）。KKT 条件：$Gx-A^T\lambda+d=0$，$Ax-b\ge0$，$(Ax-b)_i\lambda_i=0$，$\lambda\ge0$。引入松弛 $y=Ax-b$：

Gx-A^T\lambda+d=0,\quad Ax-y-b=0,\quad y_i\lambda_i=0,\quad (y,\lambda)\ge0.\tag{16.51}

与 LP 的 KKT (14.3) 对应；由于目标和可行域都凸，KKT 条件既必要又充分，解 (16.51) 即解 QP。定义

F(x,y,\lambda)=\begin{bmatrix}Gx-A^T\lambda+d\\Ax-y-b\\Y\Lambda e\end{bmatrix},\ (y,\lambda)\ge0,

$Y=\mathrm{diag}(y)$，$\Lambda=\mathrm{diag}(\lambda)$，$e=(1,\dots,1)^T$。对偶度量（duality measure）

\mu=\frac1m\sum_{i=1}^my_i\lambda_i=\frac{y^T\lambda}m.\tag{16.52}

中心路径（central path） $\mathcal C$：满足 $F(x_\tau,y_\tau,\lambda_\tau)=(0,0,\tau e)$，$(y_\tau,\lambda_\tau)>0$ 的点集。一般步是朝中心路径上点 $(x_{\sigma\mu},y_{\sigma\mu},\lambda_{\sigma\mu})$ 的类牛顿步，$\sigma\in[0,1]$ 为中心化参数：

\begin{bmatrix}G&0&-A^T\\A&-I&0\\0&\Lambda&Y\end{bmatrix}\begin{bmatrix}\Delta x\\\Delta y\\\Delta\lambda\end{bmatrix}=\begin{bmatrix}-r_d\\-r_b\\-\Lambda Ye+\sigma\mu e\end{bmatrix},\tag{16.53}

$r_d=Gx-A^T\lambda+d$，$r_b=Ax-y-b$。（文本抽取的矩阵列序混乱，此为按含义还原的形式。）更新 $(x^+,y^+,\lambda^+)=(x,y,\lambda)+\alpha(\Delta x,\Delta y,\Delta\lambda)$，$\alpha$ 保证 $(y^+,\lambda^+)>0$ 及其他条件。

Mehrotra 预测–校正算法也可推广，唯一例外：原始变量 $(x,y)$ 和对偶变量 $\lambda$ 不能用不同步长（LP 中可以），因为两者通过 $G$ 耦合，不同步长会破坏 (16.51a) 的可行性。

线性代数：主要计算量是每步解 (16.53)。消去 $\Delta y$ 得增广系统（augmented system）

\begin{bmatrix}G&-A^T\\A&\Lambda^{-1}Y\end{bmatrix}\begin{bmatrix}\Delta x\\\Delta\lambda\end{bmatrix}=\begin{bmatrix}-r_d\\-r_b+(-y+\sigma\mu\Lambda^{-1}e)\end{bmatrix},\tag{16.54}

可用对称不定分解；再消去 $\Delta\lambda$ 得正规方程（normal equations）

(G+A^T(Y^{-1}\Lambda)A)\Delta x=-r_d+A^T(Y^{-1}\Lambda)[-r_b-y+\sigma\mu\Lambda^{-1}e],

可用修正 Cholesky 求解。由于 $y,\lambda$ 变化会改变 $A^T(Y^{-1}\Lambda)A$ 的数值，每步需重新分解。

推广与对比：第 14 章所有算法都可推广。严格可行集 $\mathcal F^o=\{(x,y,\lambda):Gx-A^T\lambda+d=0,\ Ax-y-b=0,\ (y,\lambda)>0\}$；邻域 $\mathcal N_2(\theta)=\{\in\mathcal F^o:\|Y\Lambda e-\mu e\|\le\theta\mu\}$，$\mathcal N_{-\infty}(\gamma)=\{\in\mathcal F^o:y_i\lambda_i\ge\gamma\mu\ \forall i\}$，$\theta\in[0,1)$，$\gamma\in(0,1]$；路径跟踪法要求迭代点留在其一。势函数下降法用 Tanabe–Todd–Ye 势函数 $\Phi_\rho(y,\lambda)=\rho\log y^T\lambda-\sum_i\log y_i\lambda_i$，$\rho>m$，迭代限制在 $\mathcal F^o$，步由 $r_d=r_b=0$ 的 (16.53) 得到，步长使势函数显著下降。

有效集法：步数多、每步便宜；内点法：步数少、每步贵。
有效集法实现更复杂，尤其要利用 $G,A$ 稀疏性时，每次工作集变化后的稀疏分解更新很难高效实现；内点法每步要分解的矩阵非零结构不变（只变数值），可直接用标准稀疏分解软件。

16.8 对偶（Duality）（PDF p.501–502）

利用对偶的特殊结构有时能更高效求解。$G$ 正定时，

\min_x\ \tfrac12x^TGx+x^Td\quad\text{s.t. } Ax\ge b\tag{16.55}

的对偶为

\max_{x,\lambda}\ \tfrac12x^TGx+x^Td-\lambda^T(Ax-b)\quad\text{s.t. } Gx+d-A^T\lambda=0,\ \lambda\ge0.\tag{16.56}

由约束 $x=G^{-1}(A^T\lambda-d)$ 消去 $x$，得界约束问题

\max_\lambda\ -\tfrac12\lambda^T(AG^{-1}A^T)\lambda+\lambda^T(b+AG^{-1}d)-\tfrac12d^TG^{-1}d\quad\text{s.t. }\lambda\ge0.\tag{16.57}

可用梯度投影法求解，通常比经典有效集法更快识别有效集。某些应用（如熵最大化）中可证明界在解处不有效，(16.57) 退化为无约束二次优化。大问题中目标形式复杂是缺点：直接法需显式形成 $AG^{-1}A^T$；替代做法是分解 $G$ 后对 $AG^{-1}A^T$ 用 CG。

注记与文献：

$G$ 非正定时，判断 (16.1) 的可行点是否为全局极小是 NP-hard（Murty & Kabadi [176]）。
Markowitz 1952 年提出组合优化 [157]，详见其专著 [159]。
QMR 见 Freund & Nachtigal [94]；LSQR 等价于对 (16.5) 的正规方程用 CG（Paige & Saunders [188]）。
若 $A$ 秩亏，可删冗余约束：对 $A^T$ 做 QR 通常（并非总能）指示秩和可删行；大规模时一般用高斯消去，但更难判断删哪些。
首个不定 QP 惯性控制方法：Fletcher [80]；一般 QP 见 Gill 等 [110]、Gould [120]。梯度投影见 Conn–Gould–Toint [51]、Burke–Moré [32]。
最优控制和模型预测控制中的 QP 有带状 $G,A$（Wright [253]）；内点法中 (16.54) 可重排为块带状结构，易于利用；有效集法几次基更新后带状与稀疏优势就丢失。凸 QP 内点法详见 Wright [255] 第 8 章。

第 16 章习题概括（PDF p.503–505）

16.1：解一个二维 QP 并作图（$\max 2x_1+3x_2+4x_1^2+2x_1x_2+x_2^2$，含三条线性约束）。
16.2：点 $x_0$ 到超平面 $\{Ax=b\}$ 的最短距离：证 $\lambda^*=(AA^T)^{-1}(b-Ax_0)$，$x^*=x_0-A^T(AA^T)^{-1}(b-Ax_0)$（原文符号如此，实际应为 $x_0+A^T(AA^T)^{-1}(b-Ax_0)$），$A$ 为行向量时距离 $|b-Ax_0|/\|A\|$。
16.3/16.4：由定理 12.1、12.6 推出 (16.4) 及二阶充分条件。
16.5：$Z^TGZ$ 有负特征值时 KKT 点只是驻点非极小。
16.6：构造 $AQ=[0\ \hat U]$（共轭法所需）。
16.7：(16.26) 与一般一阶条件等价。
16.8：例 16.3 不同初始工作集下走两步。
16.9、16.12：编程实现算法 16.1 并求解给定 QP（内点、顶点、边界三种初始点）。
16.10：等式 QP 的三种情形：$Z^TGZ$ 正定 ⇔ 强局部极小；半正定奇异且相容 ⇒ 无穷多解；不定或不相容 ⇒ 无有限解。
16.11、16.13：KKT 矩阵在 $A\ne0$ 时不定；KKT 矩阵非奇异 ⇒ $A$ 满秩。
16.14：乘子大小依赖目标和约束的缩放。
16.15：阻挡约束梯度不是工作集梯度的线性组合，故工作集保持线性无关。
16.16：$Z^TWZ$ 正定、$\bar Z=[Z,z]$ 时 $\bar Z^TW\bar Z$ 正定（原文如此陈述；实际上一般不成立，应理解为删去一列——即加约束——时保持正定，这正是惯性控制所需的性质）。
16.17：求 (16.49a,b) 的零空间基。
16.18：写出含等式与不等式的凸 QP 的 KKT 条件并推导类似 (16.53) 的原始–对偶步。

第 16 章本章要点

QP：二次目标 + 线性约束；凸 QP（$G\succeq0$）局部解即全局解，非凸 QP 判全局最优是 NP-hard。
等式 QP 的解由 KKT 系统给出；$A$ 行满秩且约化 Hessian $Z^TGZ$ 正定时 KKT 矩阵非奇异、惯性 $(n,m,0)$、解唯一且全局最优。
KKT 系统解法：对称不定分解 $LBL^T$（通用）；值空间法（$G$ 易逆或 $m$ 小）；零空间法（$n-m$ 小，不要求 $G$ 正定）；共轭基方法；迭代法（QMR、LSQR、约化 CG）。
原始有效集法：工作集 + 等式子问题 + 比率检验 (16.29) 步长 + 删最负乘子；严格凸且无循环时有限终止；靠 QR/Cholesky 的增删更新维持效率；初始可行点用 Phase I 或大 M。
不定 QP：惯性控制（约化 Hessian 至多一个负特征值）、伪约束、$LDL^T$ 负曲率方向；可能停在一阶驻点（需同时删两个约束）。
梯度投影法：Cauchy 点（沿投影梯度分段路径的第一个局部极小）+ 子空间极小化，适合界约束，有效集可一次大幅变化。
内点法：凸 QP 的原始–对偶路径跟踪，步数少、稀疏结构固定；原始与对偶步长须相同。
对偶：严格凸 QP 的对偶是 $\lambda\ge0$ 的界约束 QP。

与量化交易的关联

组合优化是 QP 的标准应用：Markowitz 均值–方差 $\max\mu^Tw-\kappa w^T\Sigma w$，s.t. $\mathbf 1^Tw=1$、$w\ge0$，加上行业/风格暴露约束、个股上下限、换手约束（线性化后）都是本章的 QP。协方差矩阵半正定保证凸性；若协方差估计非正定（如成对缺失数据导致），问题会变成不定 QP，有效集法可能失败——实务中要先做协方差修正（特征值截断、收缩）。
求解器选择：中小规模（几百只股票、约束不多）用有效集法速度快、支持热启动（每日调仓时上一日的工作集是很好的初始猜测）；全市场数千只股票加大量约束时用内点法（如 MOSEK、OSQP/ECOS 系的思路），稀疏结构固定、步数少。只有个股上下限约束时，梯度投影法很合适。
KKT 乘子的经济含义：乘子是约束的影子价格，例如预算约束乘子是边际风险调整收益，个股上限乘子告诉你放宽该限制能带来多少目标改善——可用于约束诊断、风控限额设定。
因子模型结构：$\Sigma=BFB^T+D$ 时，值空间法 / Sherman–Morrison–Woodbury 思路（$G$ 易逆 + 低秩）可大幅加速；正规方程 $G+A^TDA$ 的结构也可利用。
对偶：严格凸 QP 的对偶是非负约束的 QP，在稀疏组合、指数增强的大规模求解中，通过对偶求解有时更快。
退化：大量个股恰好卡在 0 下界且乘子为零（弱有效）时，有效集法会锯齿，回测中表现为调仓结果对微小数据扰动敏感——这是数值问题而非信号问题。

第 17 章罚函数、障碍函数与增广拉格朗日方法（Penalty, Barrier, and Augmented Lagrangian Methods）（PDF p.506–543）

版本说明：本块文本的第 17 章含"对数障碍法"一节、第 16 章无"迭代求解 KKT/投影 CG"一节，章节结构与原书第 1 版（1999）一致（第 2 版把障碍法移到第 19 章）。笔记按文本实际内容整理，编号以文本为准。

PDF p.506 为章名页。核心思路：用一系列无约束子问题代替原约束问题。三种算法：

二次罚函数法（quadratic penalty method）：把约束违反量的平方乘系数加进目标；简单直观、常用，但有病态问题；可视为乘子法的前身。
增广拉格朗日法 / 乘子法（augmented Lagrangian / method of multipliers）：显式引入拉格朗日乘子估计以避免二次罚函数固有的病态。
对数障碍法（log-barrier method）：对数项阻止可行迭代点过于靠近可行域边界；也是原始及原始–对偶内点法（LP、凸 QP、半定规划）的基础。另有 17.3 精确罚函数（单个无约束问题代替一列问题，但难以极小化）与 17.5 序列线性约束方法（大规模问题的重要实用方法）。

17.1 二次罚函数法（The Quadratic Penalty Method）（PDF p.508–516）

动机：罚函数 = 原目标 + 每个约束一项（违反时为正、否则为零），罚项乘正系数；系数越来越大，极小点越来越接近可行域。称外点罚方法（exterior penalty methods）：罚函数极小点通常对原问题不可行，只在极限下趋于可行。等式约束问题

\min_x f(x)\quad\text{s.t. } c_i(x)=0,\ i\in\mathcal E,\tag{17.1}

二次罚函数

Q(x;\mu)=f(x)+\frac1{2\mu}\sum_{i\in\mathcal E}c_i^2(x),\tag{17.2}

$\mu>0$ 为罚参数，$\mu_k\downarrow0$。罚项光滑（$c_i^2$ 与 $c_i$ 同阶可微），可用无约束方法；前面的近似极小点可用来给下一个 $\mu_{k+1}$ 提供好的起点，选得好时每个 $\mu_k$ 只需几步无约束迭代。

例 17.1：$\min x_1+x_2$ s.t. $x_1^2+x_2^2-2=0$（解 $(-1,-1)^T$），

Q(x;\mu)=x_1+x_2+\frac1{2\mu}(x_1^2+x_2^2-2)^2.\tag{17.4}

$\mu=1$（图 17.1）：极小点约在 $(-1.1,-1.1)^T$，另在 $(0.3,0.3)^T$ 附近有局部极大。$\mu=0.1$（图 17.2）：不在可行圆上的点受重罚，出现明显的低值"槽"，极小点更接近 $(-1,-1)$，$(0,0)$ 附近有局部极大，圆外 $Q$ 迅速趋于 $\infty$。

含不等式：

Q(x;\mu)=f(x)+\frac1{2\mu}\sum_{i\in\mathcal E}c_i^2(x)+\frac1{2\mu}\sum_{i\in\mathcal I}([c_i(x)]^-)^2,\quad[y]^-=\max(-y,0).\tag{17.5}

此时 $Q$ 可能不如 $f,c_i$ 光滑：如约束 $x_1\ge0$ 对应 $\min(0,x_1)^2$，二阶导不连续，$Q$ 不再二阶连续可微（习题 17.1）。

框架 17.1（二次罚函数）：

给定 μ0 > 0，容差 τ0 > 0，起点 x0^s；
for k = 0,1,2,...
    从 xk^s 出发求 Q(·;μk) 的近似极小点 xk，当 ‖∇Q(x;μk)‖ ≤ τk 时停止；
    若满足最终收敛测试：STOP，返回 xk；
    选新罚参数 μ_{k+1} ∈ (0, μk)；选新起点 x_{k+1}^s；
end

$\mu_k$ 自适应：极小化代价大时温和减小（如 $\mu_{k+1}=0.7\mu_k$），代价小时激进（如 $0.1\mu_k$）。收敛理论只要求 $\tau_k\to0$。
困难：$\mu_k$ 小时 $\nabla^2_{xx}Q$ 在极小点附近严重病态，使拟牛顿、CG 表现很差。牛顿法对 Hessian 病态不敏感，但仍有两个问题：(1) 求牛顿步的线性方程组病态（节末说明影响不那么严重且可重写）；(2) 二次 Taylor 模型只在很小邻域内准确——图 17.2 中极小点附近等高线呈香蕉形而非椭圆，牛顿步可能进展缓慢，需靠选好起点部分克服。
总体上 17.4 节乘子法更有效，因为它避免了病态。

定理 17.1：若每个 $x_k$ 是 $Q(x;\mu_k)$ 的精确全局极小点且 $\mu_k\downarrow0$，则 $\{x_k\}$ 的每个极限点都是 (17.1) 的（全局）解。证明：设 $\bar x$ 为全局解。$Q(x_k;\mu_k)\le Q(\bar x;\mu_k)$ 给出

f(x_k)+\frac1{2\mu_k}\sum c_i^2(x_k)\le f(\bar x),\tag{17.6}\qquad \sum c_i^2(x_k)\le2\mu_k[f(\bar x)-f(x_k)].\tag{17.7}

沿子列取极限，右端 $\to0$，故 $c_i(x^*)=0$，$x^*$ 可行；由 (17.6) 取极限 $f(x^*)\le f(\bar x)$，故 $x^*$ 为全局极小。（实际中每个子问题求全局极小很难。）

定理 17.2：若 $\tau_k\to0$、$\mu_k\downarrow0$，则对 $\{x_k\}$ 的任一使 $\nabla c_i(x^*)$ 线性无关的极限点 $x^*$，$x^*$ 是 (17.1) 的 KKT 点，且沿相应子列

\lim_{k\in\mathcal K}-c_i(x_k)/\mu_k=\lambda_i^*,\quad i\in\mathcal E.\tag{17.8}

证明要点：

\nabla_xQ(x_k;\mu_k)=\nabla f(x_k)+\sum_i\frac{c_i(x_k)}{\mu_k}\nabla c_i(x_k),\tag{17.9}

终止准则给出 $\|\cdot\|\le\tau_k$ (17.10)，整理得 $\|\sum c_i(x_k)\nabla c_i(x_k)\|\le\mu_k[\tau_k+\|\nabla f(x_k)\|]$ (17.11)，取极限得 $\sum c_i(x^*)\nabla c_i(x^*)=0$ (17.12)，由线性无关得 $c_i(x^*)=0$。记 $A(x)^T=[\nabla c_i(x)]_{i\in\mathcal E}$ (17.13)，$\lambda^k=-c(x_k)/\mu_k$，则 $A(x_k)^T\lambda^k=\nabla f(x_k)-\nabla_xQ(x_k;\mu_k)$ (17.14)，$\lambda^k=[A(x_k)A(x_k)^T]^{-1}A(x_k)[\nabla f(x_k)-\nabla_xQ]$，取极限 $\lambda^*=[A(x^*)A(x^*)^T]^{-1}A(x^*)\nabla f(x^*)$ 且 $\nabla f(x^*)-A(x^*)^T\lambda^*=0$。注意：结果是吸引到 KKT 点而非全局极小；$-c_i(x_k)/\mu_k$ 是乘子估计，这对 17.4 节很关键。约束梯度线性相关时极限点可能不可行；即使可行且乘子存在，也不满足定理 12.1 的必要条件前提。不可行极限点至少是 $\|c(x)\|^2$ 的驻点——牛顿类方法总可能被吸引到这类点（与第 11 章非线性方程平方和价值函数相同）。原问题不可行时，二次罚方法常收敛到 $\|c(x)\|^2$ 的驻点/极小点。

Hessian 的病态结构：

\nabla^2_{xx}Q(x;\mu_k)=\nabla^2f(x)+\sum_i\frac{c_i(x)}{\mu_k}\nabla^2c_i(x)+\frac1{\mu_k}A(x)^TA(x).\tag{17.15}

在极小点附近由 (17.8)，

\nabla^2_{xx}Q(x;\mu_k)\approx\nabla^2_{xx}\mathcal L(x,\lambda^*)+\frac1{\mu_k}A(x)^TA(x),\tag{17.16}

即"与 $\mu_k$ 无关的拉格朗日 Hessian" + "秩为 $|\mathcal E|$、非零特征值为 $O(1/\mu_k)$ 的矩阵"。$|\mathcal E|<n$ 时，一部分特征值趋于常数，另一部分为 $O(1/\mu_k)$，病态随 $\mu_k\to0$ 加剧。牛顿方程 $\nabla^2_{xx}Q\,p=-\nabla_xQ$ (17.17) 的解会有显著舍入误差，矩阵数值奇异时算法崩溃；不过误差可能集中在 $Q$ 变化不大的方向上，对步的质量影响有限。避免病态的重写：引入辅助向量 $\zeta$，

\begin{bmatrix}\nabla^2f(x)+\sum_i\frac{c_i(x)}{\mu_k}\nabla^2c_i(x)&A(x)^T\\A(x)&-\mu_kI\end{bmatrix}\begin{bmatrix}p\\\zeta\end{bmatrix}=\begin{bmatrix}-\nabla_xQ(x;\mu)\\0\end{bmatrix},\tag{17.18}

与 (17.17) 有相同的 $p$（由第二行 $\zeta=A p/\mu_k$ 代回即得）。$\mu_k\downarrow0$ 时，若 $x^*$ 处满足二阶充分条件，系数矩阵趋于一个条件良好的极限（类 KKT 矩阵）。

17.2 对数障碍法（The Logarithmic Barrier Method）（PDF p.516–528）

障碍函数性质：对

\min_x f(x)\quad\text{s.t. } c_i(x)\ge0,\ i\in\mathcal I,\tag{17.19}

严格可行域 $\mathcal F^o=\{x:c_i(x)>0\ \forall i\in\mathcal I\}$ (17.20)，设非空。障碍函数：在 $\mathcal F^o$ 外为无穷；在 $\mathcal F^o$ 内光滑；趋近边界时 $\to\infty$。最重要的是对数障碍 $-\sum_{i\in\mathcal I}\log c_i(x)$ (17.21)，组合函数

P(x;\mu)=f(x)-\mu\sum_{i\in\mathcal I}\log c_i(x),\tag{17.22}

$\mu$ 为障碍参数（barrier parameter），极小点记 $x(\mu)$，一定条件下 $\mu\downarrow0$ 时趋于解（定理 17.3、17.4）。

例 17.2：$\min x$ s.t. $x\ge0$，$1-x\ge0$，$P(x;\mu)=x-\mu\log x-\mu\log(1-x)$。图 17.3 画 $\mu=1,0.4,0.1,0.01$：$\mu$ 小时 $P$ 在大部分可行集上接近 $f$，只在窄"边界层（boundary layers）"趋于无穷；$x(\mu)\to x^*=0$。

$x(\mu)$ 位于 $\mathcal F^o$ 内，原则上可用无约束方法（需稍作修改保持迭代点在 $\mathcal F^o$ 中），但 $\mu\downarrow0$ 时越来越难：尺度越来越差，二次 Taylor 模型只在 $x(\mu)$ 小邻域内有效。

例 17.3：

\min(x_1+0.5)^2+(x_2-0.5)^2\quad\text{s.t. }x_1,x_2\in[0,1],\tag{17.23}

P(x;\mu)=(x_1+0.5)^2+(x_2-0.5)^2-\mu[\log x_1+\log(1-x_1)+\log x_2+\log(1-x_2)].\tag{17.24}

图 17.4 画 $\mu=1,0.1,0.01$：前两者极小点周围等高线不太偏心、接近椭圆，多数无约束算法可用；$\mu=0.01$ 时极小点被推入边界层，等高线拉长且非椭圆（图 17.5 特写：左边缘几乎是直线、右侧接近圆形）。拉长意味着尺度差，拟牛顿、最速下降、CG 表现差；牛顿法对尺度不敏感，但非椭圆性说明二次模型不能很好刻画真实函数，牛顿法也只在 $x(\mu)$ 小邻域内快速收敛。

梯度与 Hessian：

\nabla_xP=\nabla f(x)-\sum_i\frac{\mu}{c_i(x)}\nabla c_i(x),\tag{17.25}

\nabla^2_{xx}P=\nabla^2f(x)-\sum_i\frac{\mu}{c_i(x)}\nabla^2c_i(x)+\sum_i\frac{\mu}{c_i^2(x)}\nabla c_i(x)\nabla c_i(x)^T.\tag{17.26}

在 $x(\mu)$ 附近 $\lambda_i^*\approx\mu/c_i(x)$，代入得

\nabla^2_{xx}P(x;\mu)\approx\nabla^2_{xx}\mathcal L(x,\lambda^*)+\sum_i\frac1\mu(\lambda_i^*)^2\nabla c_i(x)\nabla c_i(x)^T,\tag{17.27}

与二次罚的 (17.16) 相似。若 $x^*$ 处有 $t$ 个有效不等式且 $x(\mu)$ 处 LICQ 成立，则 $t$ 个特征值为 $O(1/\mu)$，其余 $n-t$ 个为 $O(1)$；除 $t=0$ 或 $t=n$ 外，$\mu\to0$ 时越来越病态。牛顿方程 $\nabla^2_{xx}P\,p=-\nabla_xP$ (17.28) 可类似 (17.18) 重写（不等式情形不那么直接）；不过直接消去法算出的 $p$ 尽管有舍入误差，仍是好的牛顿方向（见注记）。

框架 17.2（对数障碍）：与框架 17.1 相同，只是把 $Q$ 换成 $P$、罚参数换成障碍参数。由于病态，牛顿法几乎是唯一有效的内层求解方法；为让牛顿法几步内进入 $P(x;\mu_k)$ 的收敛域：

加线搜索或信赖域全局化，保证迭代点留在 $\mathcal F^o$ 内，并考虑对数障碍的特点（专门的线搜索）。
好的起点：沿以往近似极小点 $x_{k-1},x_{k-2},\dots$ 外推；或对 $\nabla_xP(x;\mu)=0$ 关于 $\mu$ 全微分求中心路径切向： $\nabla^2_{xx}P(x;\mu)\dot x-\sum_{i\in\mathcal I}\frac1{c_i(x)}\nabla c_i(x)=0,\tag{17.29}$ 在 $x_{k-1},\mu_{k-1}$ 处求 $\dot x$，令 $x_k^s=x_{k-1}+(\mu_k-\mu_{k-1})\dot x.\tag{17.30}$
若子问题不难且有可信起点，激进地取 $\mu_{k+1}=0.2\mu_k$ 或 $0.1\mu_k$。基于该框架的软件尚未进入主流，没有公认最佳启发式。对数障碍法由 Frisch [95] 约 45 年前提出、Fiacco & McCormick [79] 30 年前系统研究，因与原始–对偶内点法（在大规模 LP、凸 QP 上表现极好）的联系而重新受到关注。

性质与收敛：记 $\mathcal M$ 为 (17.19) 的解集，$f^*$ 为最优值。 定理 17.3（凸规划）：$f$ 与 $-c_i$ 均凸，$\mathcal F^o$ 非空，$\mu_k\downarrow0$，$\mathcal M$ 非空有界。则 (i) 对任意 $\mu>0$，$P(x;\mu)$ 在 $\mathcal F^o$ 上凸并取得极小点 $x(\mu)$（不必唯一），任何局部极小都是全局极小；(ii) 任一极小点序列 $x(\mu_k)$ 有收敛子列，极限点都在 $\mathcal M$ 中；(iii) $f(x(\mu_k))\to f^*$，$P(x(\mu_k);\mu_k)\to f^*$。（证明见 M. Wright [251, Thm 5]。）反例：$\mathcal M$ 可能为空（$\min x$ s.t. $-x\ge0$）或无界（$\min x_1$ s.t. $x_1\ge0$），此时结论一般不成立。一般非凸问题结论是局部的：对"良态"局部解（满足二阶充分条件、严格互补、约束规范），$\mu$ 足够小时 $P$ 在 $x^*$ 附近有局部极小；但 $\mathcal F^o$ 无界时 $P$ 可能无下界，局部极小序列也可能收敛到非解点（习题 17.2、17.3）。

与 KKT 的关系：$x(\mu)$ 处

\nabla f(x(\mu))-\sum_i\frac{\mu}{c_i(x(\mu))}\nabla c_i(x(\mu))=0.\tag{17.31}

定义乘子估计

\lambda_i(\mu)=\frac{\mu}{c_i(x(\mu))},\tag{17.32}

则 $\nabla f-\sum\lambda_i(\mu)\nabla c_i=0$ (17.33)，即 $\nabla_x\mathcal L=0$，$\mathcal L=f-\sum\lambda_ic_i$ (17.34)。其余 KKT 条件 $c_i\ge0$、$\lambda_i\ge0$、$\lambda_ic_i=0$ (17.35)：前两条严格成立（均为正），只有互补条件不满足，而是

\lambda_i(\mu)c_i(x(\mu))=\mu.\tag{17.36}

所以 $\mu\downarrow0$ 时 $(x(\mu),\lambda(\mu))$ 越来越接近满足 KKT。

定理 17.4：$\mathcal F^o$ 非空，$x^*$ 为局部解且 KKT 对某 $\lambda^*$ 成立，且 LICQ、严格互补、二阶充分条件成立。则 (i) 对充分小的 $\mu$ 存在唯一连续可微的 $x(\mu)$（$x^*$ 某邻域内 $P$ 的局部极小）且 $x(\mu)\to x^*$；(ii) $\lambda(\mu)\to\lambda^*$；(iii) $\mu$ 足够小时 $\nabla^2_{xx}P$ 正定。（Fiacco & McCormick [79, Thm 12]；M. Wright [251, Thm 8]。）轨迹 $\mathcal C_p=\{x(\mu):\mu>0\}$ (17.37) 称**（原始）中心路径（primal central path）**。

处理等式约束：一般问题 (17.38)（含 $\mathcal E$ 与 $\mathcal I$）。不能把等式拆成两个不等式（那样 $\mathcal F^o$ 为空）。办法：对等式加二次罚项（系数取 $1/\mu$）：

B(x;\mu)=f(x)-\mu\sum_{i\in\mathcal I}\log c_i(x)+\frac1{2\mu}\sum_{i\in\mathcal E}c_i^2(x).\tag{17.39}

兼具两者性质与问题（$\mu$ 要趋于零、Hessian 病态、减小 $\mu$ 后需仔细选起点、需专门线搜索）。仍需对不等式严格可行的起点；引入松弛变量即可轻松解决：

\min_{(x,s)}f(x)\quad\text{s.t. } c_i(x)=0\ (\mathcal E),\ c_i(x)-s_i=0\ (\mathcal I),\ s_i\ge0,\tag{17.40}

对应函数 $f(x)-\mu\sum\log s_i+\frac1{2\mu}\sum_{\mathcal E}c_i^2+\frac1{2\mu}\sum_{\mathcal I}(c_i(x)-s_i)^2$，任何 $s>0$ 的点都在定义域内。

与原始–对偶方法的关系：原始–对偶内点法（1984 年以来的研究热点）把乘子当作与 $x$ 同等地位的独立变量，仍寻找满足近似条件的 $(x(\mu),\lambda(\mu))$。对 (17.19) 加松弛 $s$：

\nabla f(x)-\sum_i\lambda_i\nabla c_i(x)=0,\quad c(x)-s=0,\quad\lambda_is_i=\mu,\quad(\lambda,s)\ge0.\tag{17.41}

$(x(\mu),\lambda(\mu),s(\mu)=c(x(\mu)))$ 是其解；原始–对偶中心路径 $\mathcal C_{pd}=\{(x(\mu),\lambda(\mu),s(\mu)):\mu>0\}$，其在 $x$ 空间的投影就是 $\mathcal C_p$。界约束 (17.41d) 至关重要：满足前三式但违反它的点通常离解很远，故多数算法要求迭代中 $\lambda,s$ 严格为正，前三式只在极限中满足。原始–对偶法对三个等式整体用修正牛顿法；对数障碍法则先用 (17.41b,c) 消去 $s,\lambda$ 再用牛顿法。记

F_\mu(x,\lambda,s)=\begin{bmatrix}\nabla f(x)-A(x)^T\lambda\\c(x)-s\\\Lambda Se-\mu e\end{bmatrix},\tag{17.42}

修正牛顿步 $DF_\mu\,\Delta=-F_\mu+(0,0,r_{\lambda s})$，即

\begin{bmatrix}\nabla^2_{xx}\mathcal L(x,\lambda)&-A(x)^T&0\\A(x)&0&-I\\0&S&\Lambda\end{bmatrix}\begin{bmatrix}\Delta x\\\Delta\lambda\\\Delta s\end{bmatrix}=\begin{bmatrix}-\nabla f(x)+A(x)^T\lambda\\-c(x)+s\\-\Lambda Se+\mu e+r_{\lambda s}\end{bmatrix},\tag{17.43}

$r_{\lambda s}$ 是修正项（如 Mehrotra 校正），选得好是理论与实践性能的关键（见第 14 章）。结构与 (14.11)、(14.20)、(16.53) 相同——LP、QP 的公式就是它的特例。完整算法还需：减小 $\mu$ 的策略、步长、修正项选择、迭代点需满足的条件；非线性情形还要选价值函数（文献提出用 $B(x;\mu)$ 或结合障碍与约束的精确罚函数），这是当时活跃的研究课题。也可把 (17.41) 直接看作 KKT 系统的扰动来引出原始–对偶法。

17.3 精确罚函数（Exact Penalty Functions）（PDF p.528–529）

二次罚和对数障碍都不是精确罚函数。精确罚函数（第 15.3 节，"价值函数"与"罚函数"在此可视为同义）在某些参数下一次极小化就得到精确解。$\ell_1$ 精确罚：

\phi_1(x;\mu)=f(x)+\frac1\mu\sum_{\mathcal E}|c_i(x)|+\frac1\mu\sum_{\mathcal I}[c_i(x)]^-.\tag{17.44}

$\mu$ 足够小时一次极小化即得解，但实践中难以事先确定 $\mu$，需要在计算中调整的规则。$\phi_1$ 在任何 $c_i(x)=0$ 的点不可微；一般不可微优化技术（如丛方法 bundle methods [137]）效率不高。实践中有效的方法：解一系列子问题，把 $f$ 换成以拉格朗日 Hessian 为 Hessian 的二次近似、把 $c_i$ 换成在 $x_k$ 处的线性近似——这与 SQP 密切相关（S$\ell_1$QP，18.5 节），是最强的约束优化技术之一。另有基于可微精确价值函数（如 (15.25)）的算法，但尚未证明能成为可靠高效软件的基础。

17.4 增广拉格朗日法（Augmented Lagrangian Method）（PDF p.529–540）

乘子法与二次罚法相关，但每步在目标中显式引入乘子估计，降低子问题病态的可能；病态也比对数障碍法轻，且不要求迭代点对不等式严格可行；不引入不光滑性（不同于 $\ell_1$ 罚）；可用标准的无约束或界约束优化软件实现。高质量实现 LANCELOT 即基于此。本节乘子上标表示迭代号、下标表示分量。

动机与框架：由定理 17.2，二次罚的近似极小点满足

c_i(x_k)\approx-\mu_k\lambda_i^*,\tag{17.45}

即存在系统性扰动，只有 $\mu_k\downarrow0$ 才消失。增广拉格朗日函数：

\mathcal L_A(x,\lambda;\mu)=f(x)-\sum_{i\in\mathcal E}\lambda_ic_i(x)+\frac1{2\mu}\sum_{i\in\mathcal E}c_i^2(x),\tag{17.46}

是拉格朗日函数与二次罚函数的结合。

\nabla_x\mathcal L_A=\nabla f(x)-\sum_i[\lambda_i-c_i(x)/\mu]\nabla c_i(x).\tag{17.47}

固定 $\mu_k$、$\lambda^k$，对 $x$ 极小化得 $x_k$，类似定理 17.2 的推理得

\lambda_i^*\approx\lambda_i^k-c_i(x_k)/\mu_k,\tag{17.48}\qquad c_i(x_k)\approx-\mu_k(\lambda_i^*-\lambda_i^k).

所以若 $\lambda^k$ 接近 $\lambda^*$，不可行量远小于 $\mu_k$（而不是与 $\mu_k$ 成比例）。乘子更新：

\lambda_i^{k+1}=\lambda_i^k-c_i(x_k)/\mu_k.\tag{17.49}

框架 17.3（乘子法，等式约束）：

给定 μ0 > 0，τ0 > 0，起点 x0^s 和 λ^0；
for k = 0,1,2,...
    从 xk^s 出发求 L_A(·, λ^k; μk) 的近似极小点 xk，当 ‖∇x L_A(x, λ^k; μk)‖ ≤ τk 时停止；
    若满足最终收敛测试：STOP；
    按 (17.49) 更新乘子得 λ^{k+1}；
    选新罚参数 μ_{k+1} ∈ (0, μk)；
    令 x_{k+1}^s = xk；
end

无需把 $\mu$ 减到很小就能保证收敛，病态问题较轻，起点选择也不那么关键（直接用上一步极小点）。Bertsekas [9, p.347] 建议 $\tau_k=\min(\epsilon_k,\gamma_k\|c(x_k)\|)$，$\{\epsilon_k\},\{\gamma_k\}\to0$；LANCELOT 另有选择（算法 17.4）。

例 17.4：对问题 (17.3)，$\mathcal L_A(x,\lambda;\mu)=x_1+x_2-\lambda(x_1^2+x_2^2-2)+\frac1{2\mu}(x_1^2+x_2^2-2)^2$ (17.50)。$x^*=(-1,-1)^T$，$\lambda^*=-0.5$。取 $\mu_k=1$、$\lambda^k=-0.4$（图 17.6）：等高线间距显示条件数与 $Q(x;1)$ 相近，但极小点 $x_k\approx(-1.02,-1.02)$，比 $Q(x;1)$ 的 $(-1.1,-1.1)$ 近得多。说明引入乘子项带来实质改进。

推广到不等式约束：

法一：引入松弛 $c_i(x)-s_i=0$，$s_i\ge0$ (17.51)，得到等式 + 界约束问题，由 LANCELOT 显式处理界约束（见 (17.66)）。
法二：在子问题中显式消去松弛（设 $\mathcal E=\emptyset$）。子问题 $\min_{x,s}\ f(x)-\sum_i\lambda_i^k(c_i(x)-s_i)+\frac1{2\mu_k}\sum_i(c_i(x)-s_i)^2\quad\text{s.t. }s_i\ge0.\tag{17.52}$ 每个 $s_i$ 只出现在两项中，且关于 $s_i$ 是凸二次函数。偏导 $\lambda_i^k-(c_i(x)-s_i)/\mu_k=0$ 给出无约束极小 $s_i=c_i(x)-\mu\lambda_i^k$ (17.53)；若小于 0 则取 0： $s_i=\max(c_i(x)-\mu\lambda_i^k,0).\tag{17.54}$ 代回得 $-\lambda_i^k(c_i-s_i)+\frac1{2\mu}(c_i-s_i)^2=\begin{cases}-\lambda_i^kc_i(x)+\frac1{2\mu}c_i^2(x),&c_i(x)-\mu\lambda_i^k\le0\\-\frac\mu2(\lambda_i^k)^2,&\text{otherwise.}\end{cases}\tag{17.55}$ 定义 $\psi(t,\sigma;\mu)=\begin{cases}-\sigma t+\frac1{2\mu}t^2,&t-\mu\sigma\le0\\-\frac\mu2\sigma^2,&\text{otherwise},\end{cases}\tag{17.56}$ 子问题变为 $\min_x\ \mathcal L_A(x,\lambda^k;\mu_k)=f(x)+\sum_{i\in\mathcal I}\psi(c_i(x),\lambda_i^k;\mu_k),\tag{17.57}$ 这是增广拉格朗日对不等式的自然推广。乘子更新 $\lambda_i^{k+1}=\max(\lambda_i^k-c_i(x_k)/\mu_k,\ 0).\tag{17.58}$ 推导：$\nabla_x\mathcal L_A(x_k)=\nabla f(x_k)-\sum_{i:c_i(x)\le\mu\lambda_i^k}(\lambda_i^k-c_i(x_k)/\mu_k)\nabla c_i(x_k)\approx0$，与 KKT 条件 $\nabla f(x^*)-\sum_{i:c_i(x^*)=0}\lambda_i^*\nabla c_i(x^*)=0$ 对比；保持乘子非负也符合 KKT (12.30d)。光滑性：每个 $\psi(c_i(x),\lambda_i;\mu)$ 关于 $x$ 连续可微，但在 $c_i(x)=\mu\lambda_i$ 处二阶导一般不连续。严格互补成立时 $x_k$ 通常远离此区域：有效约束 $c_i(x_k)\approx0$ 而 $\lambda_i^k,\mu_k$ 明显大于 0；非有效约束 $c_i(x_k)>0$ 而 $\lambda_i^k\approx0$。两种情况都远离 $c_i=\mu\lambda_i$。

增广拉格朗日的性质（仅等式约束）： 定理 17.5：$x^*$ 为 (17.1) 局部解，LICQ 成立，$\lambda=\lambda^*$ 时二阶充分条件成立。则存在阈值 $\bar\mu$，使对所有 $\mu\in(0,\bar\mu]$，$x^*$ 是 $\mathcal L_A(x,\lambda^*;\mu)$ 的严格局部极小。证明：验证 $\nabla_x\mathcal L_A(x^*,\lambda^*;\mu)=0$ 且 $\nabla^2_{xx}\mathcal L_A$ 正定 (17.59)。第一条：由 (17.47) 与 $c(x^*)=0$，$\nabla_x\mathcal L_A=\nabla_x\mathcal L(x^*,\lambda^*)=0$，与 $\mu$ 无关。第二条：

\nabla^2_{xx}\mathcal L_A(x^*,\lambda^*;\mu)=\nabla^2_{xx}\mathcal L(x^*,\lambda^*)+\frac1\mu A^TA.\tag{17.60}

任意 $u=w+A^Tv$，$w\in\mathrm{Null}A$（线性代数基本定理；原文误写为"代数基本定理"）。展开 (17.61) 并逐项下界：由二阶充分条件与单位球紧性，$w^T\nabla^2\mathcal Lw\ge a\|w\|^2$（$a>0$）；$b=\|\nabla^2\mathcal LA^T\|$ 给出交叉项 $\ge-2b\|w\|\|v\|$；$c=\|A\nabla^2\mathcal LA^T\|$ 给出 $\ge-c\|v\|^2$；$d$ 为 $AA^T$ 最小特征值，罚项 $\ge(d^2/\mu)\|v\|^2$。合并配方：

u^T\nabla^2_{xx}\mathcal L_Au\ge a\big[\|w\|-(b/a)\|v\|\big]^2+\big(d^2/\mu-c-b^2/a\big)\|v\|^2.\tag{17.62}

取 $\bar\mu$ 使 $d^2/\bar\mu-c-b^2/a>0$，则 $\mu\le\bar\mu$ 时右端除 $v=w=0$ 外严格为正。含义：只要 $\lambda$ 是 $\lambda^*$ 的合理估计，即使 $\mu$ 不很小也能通过极小化 $\mathcal L_A$ 得到 $x^*$ 的好估计（例 17.4 已观察到）。

定理 17.6（Bertsekas [9, Prop 4.2.3]）：在定理 17.5 假设下，存在 $\delta,\epsilon,M>0$ 使： (a) 对满足 $\|\lambda^k-\lambda^*\|\le\delta/\mu_k$，$\mu_k\le\bar\mu$ (17.63) 的 $\lambda^k,\mu_k$，问题 $\min_x\mathcal L_A(x,\lambda^k;\mu_k)$ s.t. $\|x-x^*\|\le\epsilon$ 有唯一解 $x_k$，且 $\|x_k-x^*\|\le M\mu_k\|\lambda^k-\lambda^*\|$； (b) $\|\lambda^{k+1}-\lambda^*\|\le M\mu_k\|\lambda^k-\lambda^*\|$（$\lambda^{k+1}$ 由 (17.49) 给出）； (c) $\nabla^2_{xx}\mathcal L_A(x_k,\lambda^k)$ 正定，$\nabla c_i(x_k)$ 线性无关。即乘子误差以因子 $M\mu_k$ 线性收缩：$\mu_k$ 不必趋零也能收敛，$\mu_k$ 越小收敛越快。

实际实现（LANCELOT，Conn–Gould–Toint [53]）：用松弛把不等式变等式，求解

\min_{x\in\mathbb R^n}f(x)\quad\text{s.t. } c_i(x)=0,\ i=1,\dots,m;\ l\le x\le u,\tag{17.64}

松弛并入 $x$，$l,u$ 可含 $\pm\infty$。对界约束问题（$m=0$）和无约束问题也高效，并能利用目标与约束的部分可分结构（第 9 章）。增广拉格朗日只含等式：

\mathcal L_A(x,\lambda;\mu)=f(x)-\sum_{i=1}^m\lambda_ic_i(x)+\frac1{2\mu}\sum_{i=1}^mc_i^2(x),\tag{17.65}

子问题显式处理界：$\min_x\mathcal L_A(x,\lambda;\mu)$ s.t. $l\le x\le u$ (17.66)，子问题中 $\lambda,\mu$ 固定。求解时构造 $\mathcal L_A$ 的二次模型（精确二阶导或拟牛顿）并用 16.6 节梯度投影法。一阶条件

P_{[l,u]}\nabla\mathcal L_A(x,\lambda;\mu)=0,\tag{17.67}

(P_{[l,u]}g)_i=\begin{cases}\min(0,g_i),&x_i=l_i\\g_i,&x_i\in(l_i,u_i)\\\max(0,g_i),&x_i=u_i.\end{cases}\tag{17.68}

算法 17.4（LANCELOT 乘子法）：

选正常数 η̄, ω̄, μ̄ ≤ 1, τ < 1, γ̄ < 1, αω, βω, αη, βη, α*, β*，满足 αη < min(1,αω)，βη < min(1,βω)；
选 λ^0；令 μ0 = μ̄，α0 = min(μ0, γ̄)，ω0 = ω̄ α0^{αω}，η0 = η̄ α0^{αη}；
for k = 0,1,2,...
    求 (17.66) 的近似解 xk，使 ‖P_[l,u] ∇L_A(xk, λ^k; μk)‖ ≤ ωk；
    if ‖c(xk)‖ ≤ ηk                                  (* 约束违反足够小 *)
        若 ‖c(xk)‖ ≤ η* 且 ‖P_[l,u]∇L_A‖ ≤ ω*：STOP；
        λ^{k+1} = λ^k − c(xk)/μk；  μ_{k+1} = μk；   (* 更新乘子，收紧容差 *)
        α_{k+1} = μ_{k+1}；η_{k+1} = ηk α_{k+1}^{βη}；ω_{k+1} = ωk α_{k+1}^{βω}；
    else                                             (* 减小罚参数，收紧容差 *)
        λ^{k+1} = λ^k；  μ_{k+1} = τ μk；
        α_{k+1} = μ_{k+1} γ̄；η_{k+1} = η̄ α_{k+1}^{βη}；ω_{k+1} = ω̄ α_{k+1}^{βω}；
end

逻辑：$\|c(x_k)\|>\eta_k$ 时减小 $\mu$ 以更重视降低约束违反；否则认为当前 $\mu$ 能维持近可行，按 (17.49) 更新乘子而不减 $\mu$。两种情况都收紧 $\omega_k,\eta_k$，使后续子问题求解越来越精确。

17.5 序列线性约束方法（Sequential Linearly Constrained Methods）（PDF p.540–541）

SLC（又称约化拉格朗日法，reduced Lagrangian methods）：在约束线性化下极小化拉格朗日函数。与 SQP（二次近似目标 + 线性约束）不同，SLC 子问题的目标是非线性的。等式情形：

\min_x F_k(x)\quad\text{s.t. }\nabla c_i(x_k)^T(x-x_k)+c_i(x_k)=0,\ i\in\mathcal E.\tag{17.69}

早期选择 $F_k(x)=f(x)-\sum_i\lambda_i^k\bar c_i^k(x)$ (17.70)，其中

\bar c_i^k(x)=c_i(x)-c_i(x_k)-\nabla c_i(x_k)^T(x-x_k)\tag{17.71}

是 $c_i$ 与其线性化之差。$x_k\to x^*$ 时子问题 (17.69) 的乘子收敛到最优乘子，所以 $\lambda^k$ 取上一次子问题的乘子。为从远处起点可靠收敛，最流行的 SLC 取增广拉格朗日形式

F_k(x)=f(x)-\sum_i\lambda_i^k\bar c_i^k(x)+\frac1{2\mu}\sum_i[\bar c_i^k(x)]^2,\tag{17.72}

与 (17.46) 的区别是用 $\bar c_i^k$ 代替 $c_i$（合理：线性化约束可行点处 $\bar c_i^k=c_i$）。该模型被用于非常成功的 MINOS [175]。

每步需极小化非线性子问题，需多次内迭代及函数/约束求值，但外迭代很少。
子问题用牛顿或拟牛顿法求解，并用第 15 章稀疏消去利用约束梯度的稀疏性。
不等式：引入松弛化为等式 + 界约束 $l\le x\le u$；在满足二阶充分条件的解附近，子问题能识别最优有效集。
缺点：子问题需解得相当精确才能保证乘子估计质量，每次外迭代函数求值多。普遍认为 SQP 优于 SLC，但 MINOS 仍是大规模非线性规划最有效的实现之一。

注记与文献：二次罚函数由 Courant [60] 提出；Gould [118] 研究 $Q$ 的牛顿步稳定计算（其公式右端不同但 $p$ 相同），对数障碍系统的重写需估计有效集；Gould [119] 讨论外推起点，障碍法类似技术见 Conn–Gould–Toint [55]、Dussault [78]。障碍法历史见 Nash [178]；"内点（interior-point）"一词似源于 Fiacco & McCormick [79]，该书也引入了 (17.39) 和中心路径 $\mathcal C_p$，1984 年 Karmarkar [140] 之后其重要性更加突出。线性目标重构使牛顿步最终接近 $x(\mu_{k+1})$：Wright & Jarre [258]；牛顿/障碍法收敛域与超线性收敛：S. Wright [254]。(17.28) 病态的误差分析：朴素分析认为误差大，但由于梯度和 Hessian 的特殊结构，算出的 $p$ 在 $\mu$ 很小前仍是好方向（M. Wright [252]、S. Wright [256]）。障碍函数专用线搜索：Murray & Wright [174]、Fletcher & McCann [87]。原始–对偶法价值函数：Forsgren & Gill [91] 用 $B(x;\mu)$；Gay–Overton–Wright [99] 加拉格朗日项；Byrd–Hribar–Nocedal [34] 用不可微 $\ell_2$ 价值函数；凸规划可用更接近 LP 原始–对偶的算法（Ralph & Wright [211]）。乘子法由 Hestenes [134] 和 Powell [195] 提出，权威著作为 Bertsekas [8]；不等式推广：Rockafellar [216]、Powell [198]。SLC：Robinson [215]、Rosen & Kreuser [218]；MINOS：Murtagh & Saunders [175]。

第 17 章习题概括（PDF p.542–543）

17.1：$\min(0,z)^2$ 在 $z=0$ 处二阶导不连续（故 (17.5) 不二阶连续可微）。
17.2：$\min 1/(1+x^2)$ s.t. $x\ge1$，对数障碍函数对任意 $\mu>0$ 无下界。
17.3：$\min x$ s.t. $x^2\ge0$，$x+1\ge0$（解 $x^*=-1$），障碍函数存在收敛到 0（非解）的局部极小序列。
17.4：求 $P$ 的三阶导张量，用 $\lambda_i^*\approx\mu/c_i$ 估计最大项量级（说明二次 Taylor 模型不足）。
17.5：从 $P(\cdot;\mu_k)$ 的精确极小点出发对 $P(\cdot;\mu_{k+1})$ 做牛顿步，与 (17.29)–(17.30) 的预测步比较。
17.6：把 (17.41) 推广到含等式约束。
17.7：界约束问题 KKT ⇔ $P_{[l,u]}\nabla\phi(x)=0$。
17.8：$\psi$ 在 $t=\mu\sigma$ 处二阶导不连续，写出两种情形下 $\psi(c_i(x),\lambda_i;\mu)$ 关于 $x$ 的 Hessian。

第 17 章本章要点

二次罚：$Q=f+\frac1{2\mu}\|c\|^2$，$\mu\to0$ 收敛到 KKT 点，$-c_i/\mu$ 估计乘子；代价是 Hessian 有 $O(1/\mu)$ 的特征值、严重病态，可用 (17.18) 增广形式缓解。
对数障碍：$P=f-\mu\sum\log c_i$，内点法；$\mu/c_i$ 估计乘子，$\lambda_ic_i=\mu$ 是扰动互补；中心路径；凸问题全局收敛（定理 17.3），良态局部解附近存在光滑路径（定理 17.4）；同样病态，牛顿法 + 外推起点。
原始–对偶内点：把扰动 KKT 系统 (17.41) 当作非线性方程组，用修正牛顿法，(17.43) 统一了 LP/QP/NLP 的内点步。
精确罚 $\ell_1$：一次极小化即可，但不光滑，实用中通过 S$\ell_1$QP 实现。
增广拉格朗日：$\mathcal L_A=f-\lambda^Tc+\frac1{2\mu}\|c\|^2$，乘子更新 $\lambda\leftarrow\lambda-c/\mu$；$\lambda=\lambda^*$ 时 $x^*$ 对一切小于阈值的 $\mu$ 都是严格极小（定理 17.5），$\mu$ 无需趋零，乘子误差以 $M\mu$ 线性收缩（定理 17.6）；不等式通过 $\psi$ 函数或松弛 + 界约束（LANCELOT）处理。
SLC/MINOS：线性化约束 + 非线性（增广拉格朗日）目标，外迭代少、每次贵。

与量化交易的关联

软约束建模：组合优化中常把跟踪误差、换手、因子暴露偏离写成罚项 $\frac1{2\mu}\|c(w)\|^2$ 加进目标。本章说明：罚系数越大越接近硬约束，但 Hessian 越病态、求解越慢、数值越不稳；若需要精确满足，应改用增广拉格朗日（乘子更新、罚系数适中）或直接用约束求解器，而不是把罚系数调到极大。
增广拉格朗日 / ADMM 的基础：大规模组合优化、稀疏回归（Lasso、组 Lasso 因子选择）、带约束的风险平价常用 ADMM，其每步就是增广拉格朗日的分块极小 + 乘子更新 $\lambda\leftarrow\lambda-c/\mu$。理解定理 17.5–17.6 有助于选罚参数和判断收敛。
对数障碍：风险平价（risk parity）的标准凸化形式 $\min\frac12w^T\Sigma w-\sum_i b_i\log w_i$ 正是对数障碍型函数，$\mu/c_i$ 型乘子估计与"风险贡献 = $b_i$"条件一一对应；Kelly/对数效用 $\max E[\log(1+r^Tw)]$ 也天然带障碍性质（保证财富为正）。
内点法：商业求解器（MOSEK、Gurobi barrier、IPOPT）求解大规模组合 QP/SOCP、带非线性约束（如 CVaR、二次换手成本）的问题，内核就是 (17.43) 型原始–对偶牛顿步；理解中心路径、对偶度量 $\mu$ 有助于解读求解器日志与设置收敛容差。
校准与拟合：期权模型（如 SVI、局部波动率）校准中的无套利约束、参数界约束可用 LANCELOT 式"增广拉格朗日 + 界约束梯度投影"处理。
SLC：在量化中直接用到的场景较少，主要作为理解 MINOS 等老牌 NLP 求解器的背景。

第 18 章序列二次规划（Sequential Quadratic Programming）（PDF p.544–591）

PDF p.544 为章名页。SQP 通过求解二次子问题产生步，是非线性约束优化最有效的方法之一；可用于线搜索和信赖域框架，适用于小或大规模问题。与 SLC（多数约束为线性时有效）不同，SQP 在显著非线性问题上更有优势。展开分两阶段：先给出局部算法（引入步计算与 Hessian 近似），再给出能从远处起点收敛的实用线搜索与信赖域方法。

18.1 局部 SQP 方法（Local SQP Method）（PDF p.546–550）

等式约束问题

\min f(x)\quad\text{s.t. } c(x)=0,\tag{18.1}

$f:\mathbb R^n\to\mathbb R$，$c:\mathbb R^n\to\mathbb R^m$ 光滑。（纯等式问题实践中不多，但理解它对设计一般 SQP 至关重要。）基本思想：在 $x_k$ 处用 QP 子问题建模，以其极小点定义 $x_{k+1}$。最简单的推导：对 KKT 条件用牛顿法。拉格朗日 $\mathcal L(x,\lambda)=f(x)-\lambda^Tc(x)$，约束雅可比 $A(x)^T=[\nabla c_1,\dots,\nabla c_m]$ (18.2)。KKT 方程组（$n+m$ 个方程与未知数）：

F(x,\lambda)=\begin{bmatrix}\nabla f(x)-A(x)^T\lambda\\c(x)\end{bmatrix}=0.\tag{18.3}

其雅可比 $\begin{bmatrix}W(x,\lambda)&-A(x)^T\\A(x)&0\end{bmatrix}$ (18.4)，$W(x,\lambda)=\nabla^2_{xx}\mathcal L(x,\lambda)$ (18.5)。牛顿步 $(x_{k+1},\lambda_{k+1})=(x_k,\lambda_k)+(p_k,p_\lambda)$ (18.6)：

\begin{bmatrix}W_k&-A_k^T\\A_k&0\end{bmatrix}\begin{bmatrix}p_k\\p_\lambda\end{bmatrix}=\begin{bmatrix}-\nabla f_k+A_k^T\lambda_k\\-c_k\end{bmatrix}.\tag{18.7}

称 Newton–Lagrange 方法。KKT 矩阵非奇异的条件：

假设 18.1：(a) $A_k$ 行满秩（LICQ，本章全程假设）；(b) $W_k$ 在约束切空间上正定：$d^TW_kd>0$，$\forall d\ne0,\ A_kd=0$（在满足二阶充分条件的解附近成立）。在此假设下牛顿迭代二次收敛，起点足够近时是求解等式约束问题的优秀算法。

SQP 框架：在 $(x_k,\lambda_k)$ 定义 QP

\min_p\ \tfrac12p^TW_kp+\nabla f_k^Tp\quad\text{s.t. } A_kp+c_k=0.\tag{18.8}

假设 18.1 下有唯一解 $(p_k,\mu_k)$：$W_kp_k+\nabla f_k-A_k^T\mu_k=0$，$A_kp_k+c_k=0$ (18.9)。把 (18.7) 第一式两边减去 $A_k^T\lambda_k$：

\begin{bmatrix}W_k&-A_k^T\\A_k&0\end{bmatrix}\begin{bmatrix}p_k\\\lambda_{k+1}\end{bmatrix}=\begin{bmatrix}-\nabla f_k\\-c_k\end{bmatrix},\tag{18.10}

故 $p=p_k$，$\lambda_{k+1}=\mu_k$。SQP 与牛顿法等价：新迭代点既可视为 QP (18.8) 的解，也可视为对 KKT 条件的牛顿迭代。牛顿观点便于分析，SQP 观点便于设计实用算法并推广到不等式。

算法 18.1（局部 SQP）：

选初始 (x0, λ0)；
for k = 0,1,2,...
    计算 fk, ∇fk, Wk = W(xk, λk), ck, Ak；
    解 (18.8) 得 pk 与 μk；
    x_{k+1} = xk + pk；λ_{k+1} = μk；
    若满足收敛测试：STOP；
end

局部收敛：若解处假设 18.1 成立，$f,c$ 二阶可微且二阶导 Lipschitz 连续，初始点足够近，则二次收敛到 $(x^*,\lambda^*)$（见 18.10 节）。另一种动机：(18.8a) 中线性项 $\nabla f_k^Tp$ 可换成 $\nabla_x\mathcal L(x_k,\lambda_k)^Tp$（在约束 (18.8b) 下等价），此时 (18.8a) 是拉格朗日函数的二次近似——即"在线性化约束下极小化拉格朗日函数的二次近似"。

不等式约束：一般问题

\min f(x)\quad\text{s.t. }c_i(x)=0\ (i\in\mathcal E),\ c_i(x)\ge0\ (i\in\mathcal I).\tag{18.11}

子问题线性化所有约束：

\min\ \tfrac12p^TW_kp+\nabla f_k^Tp\quad\text{s.t. }\nabla c_i(x_k)^Tp+c_i(x_k)=0\ (\mathcal E);\ \nabla c_i(x_k)^Tp+c_i(x_k)\ge0\ (\mathcal I).\tag{18.12}

用第 16 章 QP 算法求解，$p_k$ 与 $\lambda_{k+1}$ 取其解与乘子。严格互补：不存在 $i\in\mathcal I$ 使 $\lambda_i^*=c_i(x^*)=0$。

定理 18.1：$x^*$ 为 (18.11) 的解，有效约束雅可比 $A_*$ 行满秩，$d^TW_*d>0$（$\forall d\ne0,\ A_*d=0$），严格互补成立。则 $(x_k,\lambda_k)$ 足够接近 $(x^*,\lambda^*)$ 时，子问题 (18.12) 有一个局部解，其有效集 $\mathcal A_k$ 与 $\mathcal A(x^*)$ 相同。即接近解时有效集固定，子问题表现得像等式约束 QP。

IQP 与 EQP：

IQP（不等式约束 QP）：每步解完整的 (18.12)，以其解的有效集作为最优有效集的猜测；实践中很成功，缺点是大问题中解一般 QP 代价高；但接近解时借助上一步信息"热启动（hot-start）"会很便宜。
EQP（等式约束 QP）：每步选一个工作集，只解形如 (18.8) 的等式子问题（工作集约束作等式、其余忽略），工作集按乘子估计规则或辅助子问题更新；子问题更便宜，软件要求低。例：16.6 节梯度投影（沿投影最速下降路径极小化模型确定工作集）；序列线性规划（SLP）变体：去掉 $p^TW_kp$ 并加信赖域 $\|p\|\le\Delta_k$ 得 LP，以其有效集为工作集，再固定工作集、加回二次项解等式 QP 得步。

18.2 实用 SQP 方法预览（Preview of Practical SQP Methods）（PDF p.550–551）

实用 SQP 需能从远处起点、在非凸问题上收敛。类比无约束：牛顿模型 $m_k(p)=f_k+\nabla f_k^Tp+\frac12p^T\nabla^2f_kp$ 在解附近 Hessian 正定时好用，远离解时模型可能非凸；信赖域限制步在邻域内，线搜索把 Hessian 修正为正定（或用拟牛顿 $B_k$）保证下降。

线搜索 SQP：$W_k$ 在约束切空间不正定时，用正定近似 $B_k$ 代替，或在分解时直接修改 $W_k$，或取某个具有凸性的增广拉格朗日 Hessian。
信赖域 SQP：子问题加信赖域约束，可以用不满足凸性的 $W_k$；但信赖域可能使线性化约束不可行，需要放松约束，增加复杂性与成本。两类方法各有取舍，无明显优劣。
子问题求解技术对效率与稳健性影响很大（尤其大问题）：线搜索可用第 16 章 QP 算法，信赖域需特殊技术。
价值函数选择：可用第 15 章任一价值函数，但参数可能需在某些迭代中调整以保证方向是下降方向，参数更新规则对实际表现影响很大。

18.3 步的计算（Step Computation）（PDF p.552–555）

等式约束：解 KKT 系统 (18.10)（此处 $W_k$ 可以是精确 Hessian 或拟牛顿 $B_k$）。

直接解 KKT 系统（增广系统法，augmented system approach）：对称不定分解 $LDL^T$（$D$ 为 $1\times1$/$2\times2$ 块），稠密用 Bunch–Kaufman [30]，稀疏用 Duff–Reid [75]；直接得到 $p_k$ 和 $\lambda_{k+1}$。也可用 QMR、LSQR 迭代，但提前终止可能得到不指向极小点的方向，终止准则和预条件仍是研究课题，实用中尚不常见。
对偶 / 值空间法：$W_k$ 正定时 $(A_kW_k^{-1}A_k^T)\lambda_{k+1}=A_kW_k^{-1}\nabla f_k-c_k,\qquad W_kp_k=-\nabla f_k+A_k^T\lambda_{k+1}.\tag{18.13}$ 对显式维护 $H_k\approx W_k^{-1}$ 的拟牛顿法特别有效。
零空间法（许多 SQP 的核心）：$p_k=Y_kp_Y+Z_kp_Z$，
\[(A_kY_k)p_Y=-c_k,\qquad (Z_k^TW_kZ_k)p_Z=-Z_k^TW_kY_kp_Y-Z_k^T\nabla f_k,\tag{18.14}\]
QP 乘子：$(A_kY_k)^T\lambda_{k+1}=Y_k^T(\nabla f_k+W_kp_k)$ (18.15)。唯一要求：约化 Hessian $Z_k^TW_kZ_k$ 正定。
- 变体一：去掉 (18.15) 右端的 $W_kp_k$（接近解时 $p_k\to0$ 而 $\nabla f_k$ 一般不趋零），取 $Y_k=A_k^T$ 得最小二乘乘子（least-squares multipliers） $\hat\lambda_{k+1}=(A_kA_k^T)^{-1}A_k\nabla f_k,\tag{18.16}\qquad \text{即}\ \min_\lambda\|\nabla f_k-A_k^T\lambda\|_2^2.\tag{18.17}$ 远离解时也有用（尽量满足一阶条件）。实践中用最新信息：算法 18.3 先求 $p_k$，在 $x_{k+1}$ 处计算梯度后再用 (18.16) 求 $\lambda_{k+1}$。概念上这把 SQP 从 $(x,\lambda)$ 迭代变成纯原始 $x$ 迭代。
- 变体二：约化 Hessian 方法（reduced-Hessian methods）——再去掉交叉项 $Z_k^TW_kY_kp_Y$： $(Z_k^TW_kZ_k)p_Z=-Z_k^T\nabla f_k.\tag{18.18}$ 只需存储/近似并分解 $Z_k^TW_kZ_k$；合理性在于法向分量 $p_Y$ 通常比切向分量 $p_Z$ 收敛得快。

不等式约束：用有效集 QP（算法 16.1；$W_k$ 非凸时用不定 QP 变体）解 (18.12)。热启动：用上一子问题的解 $\tilde p$ 作起点（第 16 章两种 Phase I 可利用好起点）；工作集初始化为上一次 SQP 迭代的最终有效集；有时（特别是只有线性约束时）可复用/更新上一步的矩阵分解。热启动对线搜索 SQP 的效率至关重要。 线性化后不可行：例 $n=1$，约束 $x\le1$、$x^2\ge0$，在 $x_k=3$ 线性化得 $3+p\le1$ 与 $9+6p\ge0$，矛盾。解决：保证可行的松弛子问题。如 SNOPT [108]：若 (18.12) 不可行，改解

\min f(x)+\gamma e^T(v+w)\quad\text{s.t. }c_i(x)-v_i+w_i=0\ (\mathcal E),\ c_i(x)-v_i+w_i\ge0\ (\mathcal I),\ v,w\ge0,\tag{18.19}

$\gamma\ge0$ 为罚参数。原问题可行且 $\gamma$ 足够大时两者解相同；原问题不可行时通常给出一个"好的"不可行点。SNOPT 取 $\gamma=100\|\nabla f(x_s)\|$（$x_s$ 为首次检测到线性化约束不相容的迭代点），此后所有迭代都解 (18.19)。 内点法解子问题：一般问题只在早期迭代（有效集变化大、热启动收益小）与有效集法竞争；内点法不能像有效集法那样利用先验信息；某些特殊结构问题（如控制）内点法更能利用结构。 信赖域 SQP：加信赖域并重写约束保证可行（18.8 节）；S$\ell_1$QP 把线性化约束以罚项形式移进目标；18.9 节方法先用 (18.47) 求法向步间接放松约束。

18.4 二次模型的 Hessian（The Hessian of the Quadratic Model）（PDF p.555–560）

取 $W_k=\nabla^2_{xx}\mathcal L(x_k,\lambda_k)$ 带来二次收敛，远离解时也常进展迅速；但需要二阶导（可能难算），且在约束零空间上不一定正定。替代选择：

完整拟牛顿近似：对 $\nabla^2_{xx}\mathcal L$ 维护 BFGS 近似 $B_k$，

s_k=x_{k+1}-x_k,\qquad y_k=\nabla_x\mathcal L(x_{k+1},\lambda_{k+1})-\nabla_x\mathcal L(x_k,\lambda_{k+1}),\tag{18.20}

用 BFGS 公式 (8.19)（相当于把 $\lambda$ 固定的拉格朗日函数当目标）。若 $\nabla^2_{xx}\mathcal L$ 在相关区域正定，效果如无约束 BFGS；若有负特征值，用正定矩阵近似可能无效，且曲率条件 $s_k^Ty_k>0$ 即使在解附近也可能不成立。

跳过更新：若不满足 $s_k^Ty_k\ge\theta s_k^TB_ks_k$（$\theta$ 如 $10^{-2}$）(18.21) 就跳过。在许多问题上表现好，但有些问题上很差甚至失败，不足以作为通用策略。
过程 18.2（SQP 阻尼 BFGS，damped BFGS）：$r_k=\theta_ky_k+(1-\theta_k)B_ks_k$， $\theta_k=\begin{cases}1,&s_k^Ty_k\ge0.2\,s_k^TB_ks_k\\\dfrac{0.8\,s_k^TB_ks_k}{s_k^TB_ks_k-s_k^Ty_k},&s_k^Ty_k<0.2\,s_k^TB_ks_k\end{cases}\tag{18.22}$ $B_{k+1}=B_k-\frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k}+\frac{r_kr_k^T}{s_k^Tr_k}.\tag{18.23}$ 即用 $r_k$ 代替 $y_k$ 的 BFGS；$\theta_k\ne1$ 时 $s_k^Tr_k=0.2\,s_k^TB_ks_k>0$ (18.24)，保证 $B_{k+1}$ 正定。$\theta_k=0$ 时 $B_{k+1}=B_k$，$\theta_k=1$ 为原 BFGS，中间值在两者之间插值。（Powell 的阻尼策略。）已被多个 SQP 程序采用、表现良好，但困难问题上仍可能很差，因为没有解决拉格朗日 Hessian 本身不正定的根本问题。此时 SR1 (8.24) 更合适，是信赖域 SQP 的好选择；线搜索不能接受不定近似，需修改 SR1，不太理想。

增广拉格朗日 Hessian：

\mathcal L_A(x,\lambda;\mu)=f(x)-\lambda^Tc(x)+\frac1{2\mu}\|c(x)\|^2,\tag{18.25}

在满足二阶充分条件的解处

\nabla^2_{xx}\mathcal L_A=\nabla^2_{xx}\mathcal L(x^*,\lambda^*)+\mu^{-1}A(x^*)^TA(x^*)\tag{18.26}

对小于阈值 $\mu^*$ 的 $\mu$ 正定：末项在 $A^T$ 列空间上增加正曲率，零空间曲率不变。可取 $W_k=\nabla^2_{xx}\mathcal L_A$ 或其拟牛顿近似。困难：$\mu^*$ 依赖未知量（如二阶导界）；$\mu$ 太小末项主导，实际表现差；$\mu$ 太大 Hessian 可能不正定。变体：$y_k^A=\nabla_x\mathcal L_A(x_{k+1},\lambda_{k+1};\mu)-\nabla_x\mathcal L_A(x_k,\lambda_{k+1};\mu)=y_k+\mu^{-1}A_{k+1}^Tc_{k+1}$，解附近存在保证 $(y_k^A)^Ts$ 一致为正的最大 $\mu$，可自适应选 $\mu$ 并用 $y_k^A$ 代替 $y_k$；数值经验尚不足。

约化 Hessian 近似：只近似 $(n-m)$ 维的 $Z_k^T\nabla^2_{xx}\mathcal L Z_k$（标准假设下在解附近正定）。约化 Hessian 拟牛顿方法：

\lambda_k=(A_kA_k^T)^{-1}A_k\nabla f_k,\quad (A_kY_k)p_Y=-c_k,\quad M_kp_Z=-Z_k^T\nabla f_k,\tag{18.27}

$M_k$ 为约化 Hessian 近似（与完整近似 $B_k$ 区分）。构造：由 Taylor 定理 $W_{k+1}\alpha_kp_k\approx\nabla_x\mathcal L(x_k+\alpha_kp_k,\lambda_{k+1})-\nabla_x\mathcal L(x_k,\lambda_{k+1})$，左乘 $Z_k^T$：

Z_k^TW_{k+1}Z_k\alpha_kp_Z\approx-Z_k^TW_{k+1}Y_k\alpha_kp_Y+Z_k^T[\nabla_x\mathcal L(x_k+\alpha_kp_k,\lambda_{k+1})-\nabla_x\mathcal L(x_k,\lambda_{k+1})].\tag{18.28}

去掉交叉项得割线方程 $M_{k+1}s_k=y_k$ (18.29)，

s_k=\alpha_kp_Z,\qquad y_k=Z_k^T[\nabla_x\mathcal L(x_k+\alpha_kp_k,\lambda_{k+1})-\nabla_x\mathcal L(x_k,\lambda_{k+1})],\tag{18.30}

再用 BFGS 更新 $M_{k+1}$（保证 $s_k^Ty_k>0$ 的措施见 18.7 节）。左端用 $Z_k$ 而非 $Z_{k+1}$ 的指标不一致无关紧要，收敛性质同样强。变体：$y_k=Z_k^T[\nabla f(x_{k+1})-\nabla f(x_k)]$ (18.31)。Coleman–Conn [45] 沿约束切空间收集曲率：

y_k=Z_k^T[\nabla_x\mathcal L(x_k+Z_kp_Z,\lambda_{k+1})-\nabla_x\mathcal L(x_k,\lambda_{k+1})],\tag{18.32}

需在中间点 $x_k+Z_kp_Z$ 额外求梯度；可证在解附近保证 $y_k^Ts_k>0$（习题），故接近解时可安全 BFGS；因额外梯度代价大，实用中只在部分迭代用 (18.32)，其余用 (18.30b)。

18.5 价值函数与下降性（Merit Functions and Descent）（PDF p.560–563）

价值函数 $\phi$ 控制步长（线搜索）或决定是否接受步及调整信赖域半径，扮演无约束中目标函数的角色。重点：不可微 $\ell_1$ 与 Fletcher 可微精确函数（代表实用中多数价值函数）。限于等式约束。要求价值函数不妨碍"好"步。

$\ell_1$ 价值函数：

\phi_1(x;\mu)=f(x)+\frac1\mu\|c(x)\|_1.\tag{18.33}

在某些 $c_i(x)=0$ 处不可微，但总存在方向导数（附录 (A.14)）。

引理 18.2：$p_k,\lambda_{k+1}$ 由 (18.10) 生成，则

D(\phi_1(x_k;\mu);p_k)\le-p_k^TW_kp_k-(\mu^{-1}-\|\lambda_{k+1}\|_\infty)\|c_k\|_1.\tag{18.34}

证明：Taylor 展开，$\gamma$ 界定二阶项：$\phi_1(x_k+\alpha p)-\phi_1(x_k)\le\alpha\nabla f_k^Tp+\gamma\alpha^2\|p\|^2+\mu^{-1}\|c_k+\alpha A_kp\|_1-\mu^{-1}\|c_k\|_1$。由 $A_kp_k=-c_k$，$\alpha\le1$ 时 $\|c_k+\alpha A_kp_k\|_1=(1-\alpha)\|c_k\|_1$，得上界 $\alpha[\nabla f_k^Tp_k-\mu^{-1}\|c_k\|_1]+\alpha^2\gamma\|p_k\|^2$，类似得下界，取极限得 $D=\nabla f_k^Tp_k-\mu^{-1}\|c_k\|_1$。由 (18.10) 第一式 $\nabla f_k^Tp_k=-p_k^TW_kp_k+p_k^TA_k^T\lambda_{k+1}$，再由第二式 $p_k^TA_k^T\lambda_{k+1}=-c_k^T\lambda_{k+1}\le\|c_k\|_1\|\lambda_{k+1}\|_\infty$。因此 $W_k$ 正定且 $\mu$ 足够小时 $p_k$ 是下降方向；更细分析只需 $W_k$ 在切空间上正定。罚参数取

\mu^{-1}=\|\lambda_{k+1}\|_\infty+\bar\delta,\quad\bar\delta>0.\tag{18.35}

Fletcher 增广拉格朗日价值函数：

\phi_F(x;\mu)=f(x)-\lambda(x)^Tc(x)+\frac1{2\mu}\|c(x)\|^2,\tag{18.36}\qquad\lambda(x)=[A(x)A(x)^T]^{-1}A(x)\nabla f(x).\tag{18.37}

可微，梯度 $\nabla\phi_F(x_k;\mu)=\nabla f_k-A_k^T\lambda_k-(\lambda_k')^Tc_k+\mu^{-1}A_k^Tc_k$（$\lambda_k'$ 为 $\lambda(x)$ 的 $m\times n$ 雅可比）。写 $p_k=Z_kp_Z+A_k^Tp_Y$（$Y_k=A_k^T$），由 $A_k^Tp_Y=-A_k^T[A_kA_k^T]^{-1}c_k$ 得 $\nabla f_k^TA_k^Tp_Y=-\lambda_k^Tc_k$，再用 $W_kp_k=-\nabla f_k$（原文如此，严格说应为 $-\nabla f_k+A_k^T\lambda_{k+1}$，与 $Z_k$ 内积后乘子项消失）：

\nabla\phi_F(x_k;\mu)^Tp_k=-p_Z^T(Z_k^TW_kZ_k)p_Z-p_Y^TA_kW_kZ_kp_Z-c_k^T\lambda_k'p_k-\mu^{-1}\|c_k\|^2.\tag{18.38}

故若约化 Hessian 正定且

\mu^{-1}>\frac{-\frac12p_Z^TZ_k^TW_kZ_kp_Z-p_Y^TA_kW_kZ_kp_Z-c_k^T\lambda_k'p_k}{\|c_k\|^2}+\bar\delta,\tag{18.39}

$p_k$ 是 $\phi_F$ 的下降方向（$c_k=0$ 时任意 $\mu$ 都成立）。因子 $\frac12$ 是任意的，目的是保证方向导数至少为 $-p_Z^TZ^TWZp_Z$ 的一部分。该公式比 $\ell_1$ 的复杂，依赖 $A_k$ 与 $Z_k^TW_kZ_k$ 的奇异值，但可行且能建立全局收敛。

定理 18.3：$x_k$ 非 (18.1) 驻点，$Z_k^TW_kZ_k$ 正定，则纯 SQP 方向 (18.10) 在 $\mu$ 按 (18.35) 取时是 $\phi_1$ 的下降方向，在 $\mu$ 满足 (18.39) 时是 $\phi_F$ 的下降方向。

罚参数更新：希望 $\{\mu_k\}$ 最终不变。取 $\delta>0$，

\mu_k=\begin{cases}\mu_{k-1},&\mu_{k-1}^{-1}\ge\gamma+\delta\\(\gamma+2\delta)^{-1},&\text{otherwise},\end{cases}\tag{18.40}

$\ell_1$ 中 $\gamma=\|\lambda_{k+1}\|_\infty$，$\phi_F$ 中 $\gamma$ 为 (18.39) 方括号内的项。该规则使 $\mu$ 单调减，但若早期 $\mu$ 变得很小，后续约束被过度惩罚；所以有的实现加入允许 $\mu$ 增大的启发式而不破坏全局收敛。以上下降性基于纯 SQP 步；约化 Hessian 法、信赖域法等方向不同，但可类似分析。

18.6 线搜索 SQP 方法（A Line Search SQP Method）（PDF p.563–564）

各种线搜索 SQP 的区别在于 Hessian 近似、价值函数和步计算方式。

算法 18.3（非线性规划的 SQP 算法）：

选参数 η ∈ (0, 0.5)，τ ∈ (0, 1)；选初始 (x0, λ0)；选 n×n 对称正定初始 Hessian 近似 B0；
计算 f0, ∇f0, c0, A0；
for k = 0,1,2,...
    若满足终止测试：STOP；
    解 (18.12)（以 Bk 为 Hessian）得 pk；
    选 μk 使 pk 是 φ 在 xk 处的下降方向；
    αk = 1；
    while φ(xk + αk pk; μk) > φ(xk; μk) + η αk Dφ(xk; pk)
        αk ← τα αk，τα ∈ (0, τ)；
    x_{k+1} = xk + αk pk；
    计算 f_{k+1}, ∇f_{k+1}, c_{k+1}, A_{k+1}；
    λ_{k+1} = [A_{k+1} A_{k+1}^T]^{-1} A_{k+1} ∇f_{k+1}；   （最小二乘乘子；原文多一个负号，应为笔误）
    sk = αk pk，yk = ∇x L(x_{k+1}, λ_{k+1}) − ∇x L(xk, λ_{k+1})；
    用拟牛顿公式更新 Bk 得 B_{k+1}；
end

用精确 Hessian $W_k$ 替换 $B_k$ 即得二阶版本；需注意 (18.12) 约束相容。只要求 $B_k$ 正定，可用阻尼 BFGS；价值函数未指定（$\phi_1$ 或 $\phi_F$）。（对含不等式的问题，乘子在实际中取 QP 子问题的乘子更自然；算法中写的最小二乘乘子适用于等式情形。）

18.7 约化 Hessian SQP 方法（Reduced-Hessian SQP Methods）（PDF p.564–569）

只近似拉格朗日约化 Hessian，在最优控制等领域非常有效。适用于二阶导难算、自由度 $n-m$ 小的问题：维护 $(n-m)\times(n-m)$ 的 $M_k\approx Z_k^TW_kZ_k$，满足 (18.29)。优点：$n-m$ 小时 $M_k$ 质量高、$p_Z$ 计算便宜；约化 Hessian 即使离解较远也更可能正定，拟牛顿保护机制较少触发。

性质：若保留 $p_Y$ 并用完整拟牛顿近似，$p_Y$ 来自对 $c(x)=0$ 的类牛顿迭代 (18.27b)，通常二次收敛到零；$p_Z$ 用拟牛顿近似，只超线性收敛。因此实践中常见

\|p_Y\|/\|p_Z\|\to0,\tag{18.41}

称切向收敛（tangential convergence）。故去掉交叉项 $Z_k^TW_kY_k$ 是合理的；代价是步不再精确满足 KKT 系统 (18.10)，收敛速度从一步超线性降为两步超线性，实践中差别不显著（且实际方法常仍达一步超线性，见 18.10 节）。 Coleman–Conn 方法（基于 (18.32)）：

M_kp_Z=-Z_k^T\nabla f_k,\qquad A_kY_kp_Y=-c(x_k+Z_kp_Z),\tag{18.42}

约束在中间点求值；可证达到一步超线性并避免 Maratos 效应（18.11 节）。

更新准则：定义沿步的"平均"拉格朗日 Hessian

\bar W_k=\int_0^1\nabla^2_{xx}\mathcal L(x_k+\tau p_k,\lambda_{k+1})\,d\tau.\tag{18.43}

对 (18.30b) 的 $y_k$，Taylor 定理给出 $y_k=Z_k^T\bar W_kp_k$，若 $s_k$ 取完整步（$p_Z$ 部分）：

y_k^Ts_k=p_Z^TZ_k^T\bar W_kZ_kp_Z+p_Z^TZ_k^T\bar W_kY_kp_Y.\tag{18.44}

第一项在二阶充分条件下为正，第二项符号不定；由切向收敛，第一项最终占优，但即使任意接近解也不能保证，需保护机制。约化 Hessian 方法中跳过更新比完整 Hessian 方法更合理：发生得少；而且跳过时说明 $p_Y$ 相对 $p_Z$ 不小，$p_Y$ 由精确的一阶信息决定、本身就能推进，$p_Z$ 的质量此时不那么重要。

过程 18.4（更新–跳过）：给定正数列 $\gamma_k$，$\sum\gamma_k<\infty$；若 $y_k^Ts_k>0$ 且 $\|p_Y\|\le\gamma_k\|p_Z\|$，由 (18.30) 计算 $s_k,y_k$ 并 BFGS 更新 $M_k$；否则 $M_{k+1}=M_k$。实践中用过 $\gamma_k=0.1k^{-1.1}$。 Coleman–Conn 情形把 (18.43) 中 $\tau p_k$ 换成 $\tau p_Z$，得 $y_k^Ts_k=p_Z^TZ_k^T\bar W_kZ_kp_Z$，在解附近保证为正；远离解时可能为负或很小，可用大致沿约束的曲线线搜索 [101] 保证其足够大（类似无约束中用线搜索保证曲率条件）。

基变换（Changes of Bases）：工作集变化时约化 Hessian 维数改变——加约束时可用有效约束梯度把 $M_k$ 投影到更小的 $M_{k+1}$；删约束时 $M_{k+1}$ 维数变大，新行列如何初始化不明显，需要若干迭代积累信息，若约束频繁增删则拟牛顿近似质量差（接近解时工作集稳定，问题消失）。已有若干方案但都不完全令人满意，因此下面只给等式约束算法，不等式见 [108]。即使维数不变，基变量选择不同（(15.14)）也会使 $Z$ 突变；基选择不当 $Z$ 病态会引入舍入误差。稳健实现相当复杂（[108]、[86]、[146]）。

算法 18.5（约化 Hessian 方法，等式约束）：

选参数 η ∈ (0, 0.5)，τ ∈ (0, 1)；选初始 (x0, λ0)；选 (n−m)×(n−m) 对称正定 M0；
计算 f0, ∇f0, c0, A0；计算张成 A0^T 值空间与 A0 零空间的 Y0, Z0；
for k = 0,1,2,...
    若满足终止测试：STOP；
    解 (Ak Yk) pY = −ck，Mk pZ = −Zk^T ∇fk；pk = Yk pY + Zk pZ；
    选 μk 使 pk 为 φ 在 xk 的下降方向；
    αk = 1；while φ(xk + αk pk; μk) > φ(xk; μk) + η αk Dφ(xk; pk)：αk ← τα αk（τα ∈ (0, τ)）；
    x_{k+1} = xk + αk pk；计算 f_{k+1}, ∇f_{k+1}, c_{k+1}, A_{k+1}；计算 Y_{k+1}, Z_{k+1}；
    λ_{k+1} = [Y_{k+1}^T A_{k+1}^T]^{-1} Y_{k+1}^T ∇f_{k+1}；（原文带负号，按 (18.15) 应无负号）
    sk = αk pZ，yk = Zk^T [∇x L(x_{k+1}, λ_{k+1}) − ∇x L(xk, λ_{k+1})]；
    若满足更新准则：用 BFGS (8.19) 更新得 M_{k+1}；否则 M_{k+1} = Mk；
end

$M_k$ 应是约化 Hessian 的拟牛顿近似，必要时修正使其充分正定。

18.8 信赖域 SQP 方法（Trust-Region SQP Methods）（PDF p.569–576）

优点：能处理有效约束梯度线性相关的情形，能直接使用二阶导信息。部分算法较新，只对等式约束完全发展。等式情形子问题：

\min_p\ \tfrac12p^TW_kp+\nabla f_k^Tp\quad\text{s.t. }A_kp+c_k=0,\ \|p\|\le\Delta_k.\tag{18.45}

（暂取 $\ell_2$ 范数，实践中常用缩放 $\|Sp\|\le\Delta_k$。）$\Delta_k$ 按价值函数实际下降与预测下降之比调整。困难：(18.45) 比 (18.8) 难解得多，且约束可能不相容（图 18.1：满足线性化约束的步都在信赖域外）。简单扩大 $\Delta_k$ 违背信赖域初衷并损害收敛性；正确观点是每步只改进可行性，仅在极限中精确满足约束。由此有三种重构：

方法 I：平移约束（Shifting the Constraints）：把 (18.45b) 换成

A_kp+\theta c_k=0,\quad\theta\in(0,1],\tag{18.46}

$\theta$ 足够小可使约束与信赖域相交（图 18.2，平移线性化约束线）。易找到可行的 $\theta$，但难以选得使算法表现好：$\theta$ 控制步偏向改善可行性还是降低目标；若总取得远小于最大可接受值，步几乎不改善可行性。两阶段实现：

法向子问题（normal subproblem）：忽略目标，求在信赖域内部能多接近满足线性化约束： $\min_v\ \|A_kv+c_k\|_2\quad\text{s.t. }\|v\|_2\le\zeta\Delta_k,\tag{18.47}$ $\zeta\in(0,1)$，典型 0.8。解 $v_k$ 称法向步（normal step）。
要求总步至少与法向步一样改善约束：把 $\theta c_k$ 换成 $-A_kv_k$： $\min_p\ \tfrac12p^TW_kp+\nabla f_k^Tp\quad\text{s.t. }A_kp=A_kv_k,\ \|p\|_2\le\Delta_k.\tag{18.48}$ $p=v_k$ 满足两约束，故相容。等式约束可消去，化为第 4 章的标准信赖域子问题（见 18.9 节）。

方法 II：两个椭球约束（Two Elliptical Constraints）：

\min_p\ \tfrac12p^TW_kp+\nabla f_k^Tp\quad\text{s.t. }\|A_kp+c_k\|_2\le\pi_k,\ \|p\|\le\Delta_k.\tag{18.49}

（$\pi_k=0$ 时退化为 (18.45)。）取法一：$\pi_k=\|A_kp^C+c_k\|_2$，$p^C$ 为

\min_v\ m(v)=\|A_kv+c_k\|_2^2\quad\text{s.t. }\|v\|_2\le\Delta_k\tag{18.50}

的 Cauchy 点（沿 $-\nabla m(0)$ 在信赖域内的极小点）；$p^C$ 满足两约束故相容，并迫使步至少与 Cauchy 点一样推进可行性，有良好全局收敛性。取法二：$\pi_k$ 满足 $\min_{\|p\|\le b_1\Delta_k}\|A_kp+c_k\|^2\le\pi_k\le\min_{\|p\|\le b_2\Delta_k}\|A_kp+c_k\|^2$，$0<b_2\le b_1<1$，要求更严格、可能表现更好。无论哪种，(18.49) 都比标准信赖域问题难；$n$ 小或 $A_k,W_k$ 稠密时已有满意方法，大规模高效算法尚未建立，本书不展开。

方法 III：S$\ell_1$QP（序列 $\ell_1$ 二次规划）：前两种为等式约束设计，推广到不等式不平凡；S$\ell_1$QP 直接处理一般问题 (18.11)。把线性化约束以 $\ell_1$ 罚项移入目标，只保留信赖域约束：

\min_p\ \nabla f_k^Tp+\tfrac12p^TW_kp+\frac1{\mu_k}\sum_{\mathcal E}|c_i(x_k)+\nabla c_i(x_k)^Tp|+\frac1{\mu_k}\sum_{\mathcal I}[c_i(x_k)+\nabla c_i(x_k)^Tp]^-\quad\text{s.t. }\|p\|_\infty\le\Delta_k.\tag{18.51}

用 $\ell_\infty$ 信赖域使子问题更易解：引入松弛和人工变量即可写成 QP（习题 18.9），用标准 QP 算法（可利用特殊结构和热启动信息：初始点、最优有效集猜测、分解复用）。价值函数用

\phi_1(x;\mu)=f(x)+\frac1\mu\sum_{\mathcal E}|c_i(x)|+\frac1\mu\sum_{\mathcal I}[c_i(x)]^-,\tag{18.52}

(18.51) 可视为 (18.52) 的近似：$c_i$ 线性化、光滑部分 $f$ 换成曲率含目标与约束信息的二次函数。实际/预测下降比不太小则接受步，否则缩小 $\Delta_k$ 重解；其余细节同无约束信赖域法。优点：克服线性化约束与信赖域的冲突；放松了对 $A_k$ 正则性的要求；$W_k$ 可为精确 Hessian 或拟牛顿近似，不要求正定；$1/\mu_k$ 足够大时 $\phi_1$ 的局部极小通常对应 (18.11) 的局部解，全局收敛性好。缺点：据推测（未完全证实）对罚参数很敏感：罚权刚好超过阈值时 (18.51) 目标可能无下界导致行为不稳定；罚权极大时约束项"淹没"目标，至多表现得像未修改的 SQP，最坏终止于可行但非最优点。另有 Maratos 效应：好步因 $\phi_1$ 增加被拒绝，可能使算法极慢。 二阶校正（second-order correction）：若 $p_k$ 使 $\phi_1$ 增加，说明线性近似不够准确。把约束换成二次近似 $c_i(x_k)+\nabla c_i(x_k)^Tp+\frac12p^T\nabla^2c_i(x_k)p$ (18.53) 不实际（子问题太难）。改为在 $x_k+p_k$ 求约束值：忽略三阶项 $c_i(x_k+p_k)=c_i(x_k)+\nabla c_i(x_k)^Tp_k+\frac12p_k^T\nabla^2c_ip_k$ (18.54)，并假设 $p^T\nabla^2c_ip\approx p_k^T\nabla^2c_ip_k$ (18.55)，得校正子问题

\min_p\ \nabla f_k^Tp+\tfrac12p^TW_kp+\frac1{\mu_k}\sum_{\mathcal E}|d_i+\nabla c_i(x_k)^Tp|+\frac1{\mu_k}\sum_{\mathcal I}[d_i+\nabla c_i(x_k)^Tp]^-\quad\text{s.t. }\|p\|_\infty\le\Delta_k,\tag{18.56}

$d_i=c_i(x_k+p_k)-\nabla c_i(x_k)^Tp_k$。形式同 (18.51)，有效集常相同或相近，可热启动、额外代价小。但需额外求约束值，不宜每次价值函数增加都用；(18.55) 在步大时一般不成立，需保证信赖域渐近地足够大以免干扰校正步。需要精巧的启发式（Fletcher [83, Ch.14]）。

18.9 一个实用的信赖域 SQP 算法（A Practical Trust-Region SQP Algorithm）（PDF p.576–579）

细化方法 I。法向子问题 (18.47) 和主子问题 (18.48) 只需近似解。 法向步：用 CG（算法 4.3）或 dogleg。dogleg 不能照搬：(18.47a) 的 Hessian $A_k^TA_k$ 奇异，"牛顿步"不唯一；取满足 $A_kv+c_k=0$ 的最小范数解 $p^B=-A_k^T[A_kA_k^T]^{-1}c_k$；Cauchy 点沿 $-A_k^Tc_k$，也在 $A_k^T$ 值空间；故 dogleg 步 $v_k$ 在 $A_k^T$ 值空间中（习题 18.8 证明法向问题总有此类解）。 切向步：用约化 Hessian 方法。令

p_k=v_k+Z_ku_k,\quad u\in\mathbb R^{n-m},\tag{18.57}

（$Z_k$ 为 $A_k$ 零空间基；值空间分量固定为 $v_k$。）代入 (18.48a,b)，得切向子问题

\min_u\ m_k(u)=(\nabla f_k+W_kv_k)^TZ_ku+\tfrac12u^TZ_k^TW_kZ_ku\quad\text{s.t. }\|Z_ku\|_2\le(\Delta_k^2-\|v_k\|_2^2)^{1/2},\tag{18.58}

（$v_k$ 与 $Z_ku$ 正交，故信赖域约束如此简单。）可写成 $u^TS_k^2u\le\cdot$，$S_k^2=Z_k^TZ_k$ 正定。解 $Z_ku_k$ 称切向步（tangent step）。除非保证 $Z_k^TW_kZ_k$ 正定，否则不能用 dogleg；但 CG（算法 4.3，Steihaug）总能用，预条件仍是研究课题。图 18.3：二维、一个非线性等式约束；虚线椭圆为 $f$ 等值线（极小在右下），实线为约束，虚圆为信赖域；过 $x_k$ 的点线为切空间，法向步垂直于它；平移到 $x_k+v_k$ 的流形给出切向步的可能集合；本例最终步到达信赖域边界。

价值函数：不可微 $\ell_2$（不平方）

\phi(x;\mu)=f(x)+\frac1\mu\|c(x)\|_2.\tag{18.59}

实际下降 $\mathrm{ared}=\phi(x_k;\mu_k)-\phi(x_k+p_k;\mu_k)$；预测下降 $\mathrm{pred}=m_k(0)-m_k(u)+\mu_k^{-1}\mathrm{vpred}$，$\mathrm{vpred}=\|c(x_k)\|-\|c(x_k)+A_kv_k\|$（法向步带来的模型下降）。要求

\mathrm{pred}\ge\rho\mu_k^{-1}\mathrm{vpred},\quad0<\rho<1\ (\text{如 }0.3),\tag{18.60}

可通过取

\mu_k^{-1}\ge\frac{m_k(0)-m_k(u)}{(1-\rho)\mathrm{vpred}}\tag{18.61}

保证。（原文写作 $m_k(0)-m_k(u)$，按推导应为 $m_k(u)-m_k(0)$ 的正部，即切向模型增加量。）

算法 18.6（信赖域 SQP）：

选常数 ε > 0，η, ζ, γ ∈ (0,1)；选起点 x0，初始信赖域 Δ0 > 0；
for k = 0,1,2,...
    计算 fk, ck, ∇fk, Ak；按 (18.16) 计算乘子估计 λ̂k；
    若 ‖∇fk − Ak^T λ̂k‖∞ < ε 且 ‖ck‖∞ < ε：STOP；
    解法向子问题 (18.47) 得 vk；
    计算张成 Ak 零空间的 Zk；计算或更新 Wk；
    解 (18.58) 得 uk；pk = vk + Zk uk；
    ρk = ared / pred；
    if ρk > η：x_{k+1} = xk + pk；取 Δ_{k+1} ≥ Δk；
    else：x_{k+1} = xk；取 Δ_{k+1} ≤ γ‖pk‖；
end

$\zeta$ 常取 0.8，对性能影响不大。推广到不等式：有效集式，或内点框架（用改造的算法 18.6 解障碍子问题）。零空间法的缺点是需要 $Z_k$，但可重排 CG 绕过 $Z$（习题 18.10）。价值函数 (18.59) 有 Maratos 效应，应加 watchdog 或二阶校正 (18.67)；若用后者，有效启发式是只在法向步明显小于切向步和信赖域半径时才校正。

18.10 收敛速度（Rate of Convergence）（PDF p.579–583）

限于等式约束的算法 18.1（精确 Hessian 与拟牛顿版本）。结果可用于有效集稳定后的不等式问题（定理 18.1），也可用于全局算法（解附近全局化策略通常不干扰局部行为，Maratos 效应除外）。

假设 18.2：(a) $A_*$ 行满秩，$\nabla^2_{xx}\mathcal L(x^*,\lambda^*)$ 在约束切空间上正定；(b) $\{B_k\}$、$\{B_k^{-1}\}$ 有界：$\|B_k\|\le\beta_2$，$\|B_k^{-1}\|\le\beta_2$。

定理 18.4：假设 18.2(a)，$f,c$ 在 $(x^*,\lambda^*)$ 邻域二阶可微且二阶导 Lipschitz 连续，则 $(x_0,\lambda_0)$ 足够近时，用精确拉格朗日 Hessian 的算法 18.1 产生的 $(x_k,\lambda_k)$ 二次收敛到 $(x^*,\lambda^*)$。（由定理 11.2 直接得到。）

拟牛顿版本：投影矩阵

P_k=I-A_k^T(A_kA_k^T)^{-1}A_k=Z_kZ_k^T\ (Z_k\text{ 列正交}),

把向量投影到约束梯度零空间。(18.10) 第一式乘 $P_k$（$P_kA_k^T=0$）得 $P_kW_kp_k=-P_k\nabla f_k$：步完全由单侧投影 $P_kW_k$ 决定。故若 $P_kB_k$ 合理近似 $P_kW_k$ 则局部收敛，精确近似则超线性。

定理 18.5（Boggs–Tolle–Wang [24]）：假设 18.2(a)，算法 18.1 的拟牛顿迭代 $x_k\to x^*$。则 $x_k$ 超线性收敛当且仅当

\lim_{k\to\infty}\frac{\|P_k(B_k-W_*)(x_{k+1}-x_k)\|}{\|x_{k+1}-x_k\|}=0.\tag{18.62}

这是无约束 Dennis–Moré 条件 (3.5) 的推广。

定理 18.6：$W_*$、$B_0$ 对称正定，假设 18.2(a)(b) 成立，$\|x_0-x^*\|$、$\|B_0-W_*\|$ 足够小，则用 (18.20)、(18.23)（$r_k=y_k$）的 BFGS 迭代满足 (18.62)，超线性收敛。（需要拉格朗日 Hessian 在解处正定这一强假设以保证更新良定义。）阻尼 BFGS（过程 18.2）只得到较弱结果：若收敛，则为 R-超线性（非通常的 Q-超线性）。基于增广拉格朗日 Hessian 的更新有类似结果。

约化 Hessian 方法的收敛速度：$Z_kM_kZ_k^T$ 近似双侧投影 $P_kW_kP_k$，不近似 $P_kW_k$，不能期望 (18.62)。把 (18.62) 拆为

\lim\Big[\frac{P_k(B_k-W_*)P_k(x_{k+1}-x_k)}{\|x_{k+1}-x_k\|}+\frac{P_k(B_k-W_*)(I-P_k)(x_{k+1}-x_k)}{\|x_{k+1}-x_k\|}\Big]=0.\tag{18.63}

令 $B_k=Z_kM_kZ_k^T$。 定理 18.7：假设 18.2(a)，$B_k$ 有界，$x_k\to x^*$ 且

\lim_{k\to\infty}\frac{\|P_k(B_k-W_*)P_k(x_{k+1}-x_k)\|}{\|x_{k+1}-x_k\|}=0,\tag{18.64}

则两步超线性收敛：$\lim\|x_{k+2}-x^*\|/\|x_k-x^*\|=0$。若存在切向收敛（$\|(I-P_k)(x_{k+1}-x_k)\|/\|x_{k+1}-x_k\|\to0$），由 (18.63)、(18.64) 实际为一步超线性，即使交叉项 $P_k(B_k-W_*)(I-P_k)$ 不小。局部约化 Hessian BFGS 方法：$x_{k+1}=x_k+Y_kp_Y+Z_kp_Z$（(18.27)），$M_k$ 用 (18.30) 的 BFGS 更新，$M_0$ 对称正定；假设零空间基光滑变化

\|Z_k-Z_*\|=O(\|x_k-x^*\|).\tag{18.65}

定理 18.8：假设 18.2(a)，若 $\{x_k\}$ R-线性收敛到 $x^*$，则 $\{M_k\}$、$\{M_k^{-1}\}$ 一致有界且 $x_k$ 两步超线性收敛。 (18.65) 必要的原因：零空间基有很多选择，若迭代间变化太大，修正向量 $s_k,y_k$ 有跳变，阻碍超线性收敛；事实上任何只依赖 $A_k$ 的 $Z_k$ 计算过程即使 $A_k$ 满秩也常不连续。两种办法：QR 分解中的任意选择（如符号）在解附近与上一步保持一致；或把 $A_{k-1}$ 的 QR 正交因子作用于 $A_k$，再对 $Q_{k-1}^TA_k$ 做 QR 得 $Q_k$ 进而 $Z_k$。两者都满足 (18.65)。

18.11 Maratos 效应（The Maratos Effect）（PDF p.583–589）

某些价值函数会拒绝向解推进良好的步，阻碍 SQP 快速收敛——由 Maratos [156] 首先观察到。

例 18.1（Powell [209]）：

\min f(x_1,x_2)=2(x_1^2+x_2^2-1)-x_1\quad\text{s.t. }x_1^2+x_2^2-1=0.

解 $x^*=(1,0)^T$，$\lambda^*=\tfrac32$，$\nabla^2_{xx}\mathcal L(x^*,\lambda^*)=I$。取可行点 $x_k=(\cos\theta,\sin\theta)^T$，$B_k=I$。$f(x_k)=-\cos\theta$，$\nabla f(x_k)=(4\cos\theta-1,4\sin\theta)^T$，$A(x_k)^T=(2\cos\theta,2\sin\theta)^T$。子问题：$\min -\cos\theta+(4\cos\theta-1)p_1+4\sin\theta\,p_2+\frac12p_1^2+\frac12p_2^2$ s.t. $p_2=-\cot\theta\,p_1$，解

p_k=\begin{bmatrix}\sin^2\theta\\-\sin\theta\cos\theta\end{bmatrix},\tag{18.66}\qquad x_k+p_k=\begin{bmatrix}\cos\theta+\sin^2\theta\\\sin\theta(1-\cos\theta)\end{bmatrix}.

$\sin\theta\ne0$ 时 $\|x_k+p_k-x^*\|_2=2\sin^2(\theta/2)$，$\|x_k-x^*\|_2=2|\sin(\theta/2)|$，比值 $\|x_k+p_k-x^*\|/\|x_k-x^*\|^2=\frac12$——符合 Q-二次收敛。但

f(x_k+p_k)=\sin^2\theta-\cos\theta>f(x_k),\qquad c(x_k+p_k)=\sin^2\theta>c(x_k)=0,

目标和约束违反都增加。图 18.4 取 $\theta=\pi/2$（为清晰起见取了大角度），SQP 从 $x^{(0)}$ 移到 $x^{(1)}=(1,1)$（原文写 $x^{(0)}=(1,0)$，按 $\theta=\pi/2$ 应为 $(0,1)$）。任何非零 $\theta$ 下该步都会被拒绝。所以任何形如 $\phi(x;\mu)=f(x)+\frac1\mu h(c(x))$（$h\ge0$，$h(0)=0$）的价值函数都会拒绝 (18.66)，包括光滑 $f+\mu^{-1}\|c\|_2^2$ 与不可微 $f+\mu^{-1}\|c\|_1$。不处理时会显著拖慢 SQP，不仅干扰远离解的好步，还会阻止超线性收敛。

对策：

用不受 Maratos 效应影响的价值函数，如 Fletcher 增广拉格朗日 (18.36)：在满足二阶充分条件的解附近，算法 18.1 的步都会被接受。
二阶校正：给 $p_k$ 加一个在 $c(x_k+p_k)$ 处计算、能充分降低约束的步 $p_k'$（如 S$\ell_1$QP 的 (18.56)）。
非单调策略：允许价值函数在某些迭代上升，如 watchdog。

线搜索中的二阶校正（$\ell_1$ 价值函数）：

w_k=-A_k^T(A_kA_k^T)^{-1}c(x_k+p_k),\tag{18.67}

满足 $x_k+p_k$ 处约束的线性化 $A_kw_k+c(x_k+p_k)=0$，且是其最小范数解。这个法向校正把 $\|c(x)\|$ 降到 $O(\|x_k-x^*\|^3)$，保证（至少在解附近）$x_k\to x_k+p_k+w_k$ 使价值函数下降；代价是在 $x_k+p_k$ 多求一次约束。

算法 18.7（带二阶校正的 SQP）：

选 η ∈ (0, 0.5)，0 < τ1 < τ2 < 1；选 x0, B0；
for k = 0,1,2,...
    计算 fk, ∇fk, ck, Ak；若满足终止测试：STOP；
    计算 SQP 步 pk；αk = 1；newpoint = false；
    while not newpoint
        if φ1(xk + αk pk) ≤ φ1(xk) + η αk Dφ1(xk; pk)
            x_{k+1} = xk + αk pk；newpoint = true；
        else if αk = 1
            由 (18.67) 计算 wk；
            if φ1(xk + pk + wk) ≤ φ1(xk) + η Dφ1(xk; pk)
                x_{k+1} = xk + pk + wk；newpoint = true；
            在 [τ1 αk, τ2 αk] 中选新 αk；
        else
            在 [τ1 αk, τ2 αk] 中选新 αk；
    end
    用拟牛顿公式更新 Bk 得 B_{k+1}；
end

（罚参数在找到成功步前保持不变。）可证有限步后 $\alpha_k=1$ 总能产生新迭代点（$x_k+p_k$ 或 $x_k+p_k+w_k$），价值函数不再干扰，获得与局部算法相同的超线性收敛。$w_k$ 也可用任何列张成 $A_k^T$ 列空间的 $Y_k$ 定义。实践中有效，额外约束求值的代价被稳健性和效率的提升抵消。

Watchdog（非单调）策略：偶尔接受使价值函数上升的步（"松弛步 relaxed steps"），但若在 $\hat t$ 步内未获得充分下降，则回到松弛步之前的点做正常步（线搜索强制 $\ell_1$ 价值函数下降）。松弛步之后的那一步起到类似二阶校正的作用。下面取 $\hat t=1$。

算法 18.8（Watchdog）：

选 η ∈ (0, 0.5)；选 x0, B0；k = 0，S = {0}；
repeat
    计算 fk, ∇fk, ck, Ak；若满足终止测试：STOP；
    计算 SQP 步 pk；x_{k+1} = xk + pk；更新 B_{k+1}；
    if φ1(x_{k+1}) ≤ φ1(xk) + η Dφ1(xk; pk)            （充分下降，正常接受）
        k = k+1；S = S ∪ {k}；
    else                                                （松弛步：暂时接受）
        计算 SQP 步 p_{k+1}；线搜索求 α_{k+1} 使 φ1(x_{k+2}) ≤ φ1(x_{k+1}) + η α_{k+1} Dφ1(x_{k+1}; p_{k+1})；
        x_{k+2} = x_{k+1} + α_{k+1} p_{k+1}；更新 B_{k+2}；
        if φ1(x_{k+1}) ≤ φ1(xk) 或 φ1(x_{k+2}) ≤ φ1(xk) + η Dφ1(xk; pk)
            k = k+2；S = S ∪ {k}；
        else if φ1(x_{k+2}) > φ1(xk)                    （失败：回到 xk 做线搜索）
            求 αk 使 φ1(x_{k+3}) ≤ φ1(xk) + η αk Dφ1(xk; pk)；x_{k+3} = xk + αk pk；
        else                                            （再走一步）
            计算 SQP 步 p_{k+2}；线搜索得 x_{k+3} = x_{k+2} + α_{k+2} p_{k+2}；更新 B_{k+3}；
            k = k+3；S = S ∪ {k}；
end

拟牛顿更新总用紧邻前一步的信息。$S$ 只用于标记获得充分下降的迭代，至少三分之一的迭代在 $S$ 中；据此可证局部收敛、足够大的 $k$ 时 $\alpha_k=1$、超线性收敛。实践中常允许上升 $\hat t=5$ 或 10 步；对将被拒绝的迭代点不更新矩阵可能更好。实现有一定复杂度但值得，实践表现好。相对二阶校正的潜在优势：约束求值可能更少（最好情况下几乎都是完整 SQP 步、很少回退）；两者相对优劣尚缺乏足够数值经验。

注记与文献：SQP 由 Wilson [245] 于 1963 年提出，1970 年代发展（Garcia-Palomares & Mangasarian [97]、Han [131,132]、Powell [202,204,205]），综述见 Boggs & Tolle [23]；SLP 方法见 Fletcher & Sainz de la Maza [89]；SQP 与增广拉格朗日的关系见 Tapia [234]。另一种只依赖 $x$ 的方法：对约化 KKT 方程

F(x)=\begin{bmatrix}Z(x)^Tg(x)\\c(x)\end{bmatrix}=0\tag{18.68}

（$n$ 个方程、$n$ 个未知数，无乘子）用牛顿法；雅可比需 $Z'(x)$，去掉相关项后得到与 SQP 相关的格式（Goodman [117]）。不相容线性化约束的另一处理见 Powell [202]。约化 Hessian SQP 可能最早由 Murray & Wright 和 Coleman & Conn 提出，在化工过程控制和轨迹优化中有用。阻尼 BFGS 保留了 BFGS 的部分（非全部）好性质，其弱点的数值实验见 Powell [208]。多数 SQP 是不可行方法（初始点和迭代点都不必可行），对强非线性约束有利；但若函数在可行域外无定义，需要可行 SQP（Panier & Tits [189]）。许多 SQP 代码（NPSOL [111]、SNOPT [108]）区别对待线性约束：先使迭代点满足所有线性约束并保持；对不相容或近相关约束使用放松约束的"弹性模式（elastic mode）"。Byrd–Hribar–Nocedal [34] 的 NLP 内点法用算法 18.6 解障碍法中的等式子问题。二阶校正：Coleman & Conn [44]、Fletcher [82]、Gabay [96]、Mayne & Polak [161]；watchdog：Chamberlain 等 [40]。光滑变化的零空间基：Coleman & Sorensen [50]、Gill 等 [109]；约化 Hessian 拟牛顿更现实的收敛结果：Byrd & Nocedal [36]。

第 18 章习题概括（PDF p.589–591）

18.1：证明定理 18.4（牛顿 SQP 二次收敛）。
18.2：编程实现算法 18.1，求解 $\min e^{x_1x_2x_3x_4x_5}-\frac12(x_1^3+x_2^3+1)^2$，s.t. $\sum x_i^2=10$，$x_2x_3=5x_4x_5$，$x_1^3+x_2^3=-1$；起点 $(-1.71,1.59,1.82,-0.763,-0.763)$，解 $\approx(-1.8,1.7,1.9,-0.8,-0.8)$。
18.3：证明阻尼 BFGS 满足 (18.24)。
18.4：(18.30a)+(18.32) 定义下解附近 $y_k^Ts_k>0$，并说明对乘子估计需要什么假设。
18.5：证明 (18.38)。
18.6：写出约束 $x_1^2+x_2^2=1$ 在 $(0,0)$、$(0,1)$、$(0.1,0.02)$、$-(0.1,0.02)$ 处的线性化（体会线性化退化/不相容）。
18.7：编程实现约化 Hessian 方法求解给定问题。
18.8：法向问题 (18.47) 总有位于 $A_k^T$ 值空间的解。
18.9：把 (18.51) 改写成 QP。
18.10：用 CG 解切向问题时，$Z_k$ 只以 $Z_k(Z_k^TZ_k)^{-1}Z_k^Tw$ 形式出现，可改算为 $w-A_k^T(A_kA_k^T)^{-1}A_kw$（原文 (18.69) 写的是 $A_k^T(A_kA_k^T)^{-1}A_kw$，即投影到值空间的部分，零空间投影为 $w$ 减去它），也可通过解增广系统 $\begin{bmatrix}I&A_k^T\\A_k&0\end{bmatrix}$ 实现——无需显式计算 $Z_k$。

第 18 章本章要点

SQP = 对 KKT 方程的牛顿法 = 在线性化约束下极小化拉格朗日二次模型；纯牛顿 SQP 二次收敛，乘子即 QP 乘子。
不等式：子问题线性化全部约束（IQP），接近解时有效集稳定（定理 18.1）；或 EQP（工作集 + 等式子问题，如 SLP-EQP）。
步计算：$LDL^T$ 增广系统、值空间法、零空间法；最小二乘乘子；约化 Hessian 方法去掉交叉项（切向收敛使之合理）。
Hessian：精确拉格朗日 Hessian、阻尼 BFGS（保证正定）、SR1（信赖域）、增广拉格朗日 Hessian、约化 Hessian BFGS（Coleman–Conn 曲率、更新–跳过规则）。
价值函数：$\ell_1$（罚权 $>\|\lambda\|_\infty$ 即下降）与 Fletcher 函数（条件 (18.39)）；罚参数更新 (18.40)。
线性化不相容：SNOPT 弹性松弛 (18.19)；信赖域法用约束平移（法向步 + 切向步）、双椭球约束或 S$\ell_1$QP。
收敛速度：Boggs–Tolle–Wang 条件（投影 Dennis–Moré）；约化 Hessian 两步超线性，切向收敛时一步超线性；零空间基需光滑变化。
Maratos 效应：任何 $f+h(c)/\mu$ 型价值函数都可能拒绝二次收敛的步；对策为 Fletcher 函数、二阶校正 $w_k=-A^T(AA^T)^{-1}c(x_k+p_k)$、watchdog 非单调策略。

与量化交易的关联

非线性约束组合优化：当约束本身非线性时——风险预算（各资产风险贡献等于目标值）、波动率目标 $\sqrt{w^T\Sigma w}=\sigma^*$、带市场冲击的非线性交易成本、CVaR/下行风险约束——问题不再是 QP，常用 SQP 求解（如 SNOPT、scipy.optimize.minimize(method='SLSQP')，后者就是带 BFGS 的线搜索 SQP，正对应本章算法 18.3 与阻尼 BFGS）。理解本章能解释 SLSQP 常见报错：线性化约束不相容（"Inequality constraints incompatible"）、Hessian 近似不正定、线搜索失败（Maratos 效应等）。
模型校准：Heston/SABR 等模型参数校准带非线性约束（Feller 条件 $2\kappa\theta>\sigma^2$）时可用 SQP；精确 Hessian 往往拿不到，拟牛顿 + 阻尼更新是标准选择。
最优执行：Almgren–Chriss 等执行轨迹问题在加入非线性冲击或风险约束后是带结构的 NLP；本章指出最优控制类问题适合约化 Hessian SQP（自由度少）或内点法（带状结构）。
乘子解读：SQP 返回的 QP 乘子是约束的影子价格，可用于约束敏感性分析（例如放宽风险预算能换来多少收益）。
热启动：日频再平衡时，以前一日解与有效集热启动 SQP/QP 子问题，能显著提速——这正是本章强调的 hot-start。

附录 A 背景材料（Background Material）（PDF p.592–626）

PDF p.592 为附录标题页。附录汇集全书用到的分析、几何、拓扑与线性代数基础，编写教材时可作为"预备知识"章节的素材。

A.1 分析、几何与拓扑要素（Elements of Analysis, Geometry, Topology）（PDF p.593–609）

$\mathbb R^n$ 的拓扑：

收敛：$\lim x_k=x$ 指 $\forall\epsilon>0,\ \exists K$，$k\ge K$ 时 $\|x_k-x\|\le\epsilon$。例：$x_k=(1-2^{-k},1/k^2)^T\to(1,0)^T$。
聚点 / 极限点（accumulation / limit point）：存在子列收敛到 $\hat x$；等价地，$\forall\epsilon>0$ 与任意 $K$，存在 $k\ge K$ 使 $\|x_k-\hat x\|\le\epsilon$。例 (A.1)：$(1,1),(\frac12,\frac12),(1,1),(\frac14,\frac14),\dots$ 恰有两个极限点 $(0,0)$、$(1,1)$；$x_k=\sin k$ 以 $[-1,1]$ 中每一点为极限点。
实数列的 $\liminf$/$\limsup$：最小/最大聚点。例 $1,\frac12,1,\frac14,1,\frac18,\dots$：$\liminf=0$，$\limsup=1$。
有界：$\|x\|\le M$；开集：每点有含于集合的小球；闭集：任意序列的极限点都在集合内。例：$(0,1)\cup(2,10)$ 开，$[0,1]\cup[2,5]$ 闭，$(0,1]$ 既不开也不闭。
内部 $\mathrm{int}F$（最大开子集）与闭包 $\mathrm{cl}F$（最小闭超集）。例 $F=(-1,1]\cup[2,4)$：$\mathrm{cl}F=[-1,1]\cup[2,4]$，$\mathrm{int}F=(-1,1)\cup(2,4)$。
紧（compact）：每个序列都有极限点且极限点都在集合内；$\mathbb R^n$ 中闭且有界 ⇒ 紧。
邻域：含 $x$ 的开集；开球 $B(x,\epsilon)=\{y:\|y-x\|<\epsilon\}$。
锥（cone）：$x\in F\Rightarrow\alpha x\in F,\ \forall\alpha\ge0$ (A.2)。例 $\{x_1>0,x_2\ge0\}$。
仿射包 $\mathrm{aff}F$（含 $F$ 的最小仿射集）(A.3)，相对内部 $\mathrm{ri}F$（相对于 $\mathrm{aff}F$ 的内部）：$x\in\mathrm{ri}F$ 若 $\exists\epsilon$，$(x+\epsilon B)\cap\mathrm{aff}F\subset F$。例：冰淇淋锥 (A.26) 的 $\mathrm{aff}=\mathbb R^3$，$\mathrm{ri}=\{x_3>2\sqrt{x_1^2+x_2^2}\}$；两点集 $\{(1,0,0),(0,2,0)\}$ 的仿射包为 $\{(x_1,x_2,0)\}$，相对内部为空；$\{x_1,x_2\in[0,1],x_3=0\}$ 的相对内部为 $\{x_1,x_2\in(0,1),x_3=0\}$。

连续与极限：$\lim_{x\to x_0}f(x)=f_0$ 的 $\epsilon$–$\delta$ 定义 (A.4)；$x_0\in D$ 且 $f_0=f(x_0)$ 时连续。例 (A.5)：$f(x)=-x$（$x\in[-1,1]$，$x\ne0$），其余 $x\in[-10,10]$ 取 5：在 0 处极限为 0 但 $f(0)=5$，不连续；在 $\pm1$ 处极限不存在。单侧极限 (A.6)(A.7)：$\lim_{x\downarrow1}f=5$，$\lim_{x\uparrow1}f=-1$（原文写 1，应为 $-1$）。Lipschitz 连续：$\|f(x_1)-f(x_0)\|\le M\|x_1-x_0\|$ (A.8)；局部 Lipschitz：在某邻域内成立。

导数：一元导数 (A.9)、二阶导 (A.10)、链式法则 (A.11)；梯度 (A.12)；Hessian（二阶连续可微时对称）；多元链式法则 $\nabla_tf(x(t))=\sum_i\frac{\partial f}{\partial x_i}\nabla x_i(t)$ (A.13)。 方向导数：$D(f(x);p)=\lim_{\epsilon\to0}\frac{f(x+\epsilon p)-f(x)}\epsilon=\nabla f(x)^Tp$ (A.14)，用 $\phi(\alpha)=f(x+\alpha p)$ 与链式法则证明 (A.15–A.16)。不可微函数也可有方向导数，如

D(\|x\|_1;p)=-\sum_{x_i<0}p_i+\sum_{x_i>0}p_i+\sum_{x_i=0}|p_i|,

任何 $x,p$ 都存在，但有分量为零时梯度不存在（这正是 18.5 节 $\ell_1$ 价值函数分析所需）。 例 A.1：$f=x_1^2+x_1x_2$，$x_1=\sin t_1+t_2^2$，$x_2=(t_1+t_2)^2$，用链式法则求 $\nabla_tf$ 并与直接代入求导比较。

中值定理：一元 $\phi(\alpha_1)=\phi(\alpha_0)+\phi'(\xi)(\alpha_1-\alpha_0)$ (A.17)；多元 $f(x+p)=f(x)+\nabla f(x+\alpha p)^Tp$，$\alpha\in(0,1)$ (A.18)。例 A.2：$f=x_1^3+3x_1x_2^2$，$x=0$，$p=(1,2)$，$f(x+p)=13$，$\nabla f(x+\alpha p)^Tp=39\alpha^2$，取 $\alpha=1/\sqrt{13}$ 成立。二阶形式 $f(x+p)=f(x)+\nabla f(x)^Tp+\frac12p^T\nabla^2f(x+\alpha p)p$ (A.19)（Taylor 定理的一种形式）。

隐函数定理（定理 A.1，参照 Lang [147]）：$h:\mathbb R^n\times\mathbb R^m\to\mathbb R^n$，(i) $h(z^*,0)=0$；(ii) 在 $(z^*,0)$ 邻域 Lipschitz 连续可微；(iii) $\nabla_zh(z^*,0)$ 非奇异。则 $h(z(t),t)=0$ 隐式定义的 $z(t)$ 在原点附近良定义且 Lipschitz 连续。常用于参数化线性系统 $M(t)z=g(t)$（$M(0)$ 非奇异）：$z(t)=M(t)^{-1}g(t)$ 在 0 附近 Lipschitz 连续。

可行集的几何：可行集 $\Omega=\{x:c_i(x)=0,\ i\in\mathcal E;\ c_i(x)\ge0,\ i\in\mathcal I\}$ (A.20)。纯几何视角 $\min f$ s.t. $x\in\Omega$ (A.21)（$\Omega$ 闭）可避免冗余、线性相关、不光滑约束带来的理论麻烦和尺度问题，但多数理论、算法、软件假设代数描述；几何工具在最优控制等中有成功应用（Clarke [42]、Dunn [77]）。

定义 A.1（切向量，Clarke [42, Thm 2.4.5]）：$w$ 是 $\Omega$ 在 $x$ 处的切向量，若对所有 $x_i\to x$（$x_i\in\Omega$）和所有 $t_i\downarrow0$，存在 $w_i\to w$ 使 $x_i+t_iw_i\in\Omega$。切锥 $T_\Omega(x)$：全体切向量；法锥 $N_\Omega(x)=\{v:v^Tw\le0,\ \forall w\in T_\Omega(x)\}$ (A.22)。零向量属于两者；书中证明了 $T$ 确实是锥（令 $\bar t_i=t_i/\alpha$）。
例 1：单个等式 $\Omega=\{h(x)=0\}$ (A.23)，$\nabla h(x)\ne0$：由 Taylor 展开 $w^T\nabla h(x)=0$，反向由隐函数定理，故 $T=\mathrm{Null}(\nabla h(x)^T)$ (A.24)，$N=\mathrm{Range}(\nabla h(x))$ (A.25)。
例 2：$\Omega=\{x_1\ge x_2^2,\ x_2\ge x_1^2\}$（图 A.1），原点处 $T=\{w\ge0\}$，$N=\{v\le0\}$；验证 $(0,1)$ 为切向量：取 $x_i=(1/i^2,1/i)$，$t_i=1/i$，$w_i=(\frac1{3i},1)$。
例 3：冰淇淋锥 $\Omega=\{x_3\ge2\sqrt{x_1^2+x_2^2}\}$ (A.26)（图 A.2），原点处 $T=\Omega$，$N=\{v_3\le-\frac12\sqrt{v_1^2+v_2^2}\}$；用 Cauchy–Schwarz 型不等式验证 $v^Tw\le0$。
例 4：$\Omega=\{x_2\ge0,\ x_2\le x_1^3\}$ (A.27)（图 A.3），原点处 $T=\{(w_1,0):w_1\ge0\}$ (A.28)，$N=\{v:v_1\le0\}$ (A.29)；$\mathrm{ri}\,\Omega=\{x_2>0,x_2<x_1^3\}$，$\mathrm{ri}\,T=\{(w_1,0):w_1>0\}$，$\mathrm{ri}\,N=\{v_1<0\}$。（这是一个 LICQ 不成立、切锥与线性化锥不同的典型例子。）

阶记号（Order Notation）：对非负序列，$\eta_k=O(\nu_k)$：$|\eta_k|\le C|\nu_k|$（$k$ 充分大）；$\eta_k=o(\nu_k)$：$\eta_k/\nu_k\to0$；$\eta_k=\Theta(\nu_k)$：$C_0|\nu_k|\le|\eta_k|\le C_1|\nu_k|$（等价于互为 $O$）。函数版本 $\eta(\nu)=O(\nu)$、$o(\nu)$ (A.30)（$\nu\to0$ 或 $\infty$ 由上下文定）；$O(1)$ 表有界，$o(1)$ 表趋零；向量/矩阵用范数。

标量方程求根：牛顿 $p_k=-F(x_k)/F'(x_k)$，$x_{k+1}=x_k+p_k$ (A.31)（切线与 $x$ 轴交点，图 A.4）；割线法（Broyden 方法的 $n=1$ 特例，割线方程完全确定 $B_k$）：

B_k=\frac{F(x_k)-F(x_{k-1})}{x_k-x_{k-1}},\qquad p_k=-F(x_k)/B_k,\ x_{k+1}=x_k+p_k\tag{A.32}

（图 A.5）。第 4 章信赖域算法中需用到标量求根。

A.2 线性代数要素（Elements of Linear Algebra）（PDF p.609–626）

向量与矩阵：对称 $A=A^T$；正定：$\exists\alpha>0$，$x^TAx\ge\alpha\|x\|^2$ (A.33)；半正定：$\alpha=0$。

范数：$\|x\|_1=\sum|x_i|$，$\|x\|_2=(x^Tx)^{1/2}$，$\|x\|_\infty=\max|x_i|$ (A.34)；等价性 $\|x\|_\infty\le\|x\|_2\le\sqrt n\|x\|_\infty$，$\|x\|_\infty\le\|x\|_1\le n\|x\|_\infty$ (A.35)。范数公理：三角不等式、正定性、齐次性 (A.36)。Euclid 范数的 Cauchy–Schwarz 不等式（原书称 Hölder）$|x^Tz|\le\|x\|\|z\|$ (A.37)，证明：$\|\alpha x+z\|^2\ge0$ 对 $\alpha$ 的二次式判别式非正。诱导矩阵范数 $\|A\|=\sup\|Ax\|/\|x\|$ (A.38)：$\|A\|_1=\max_j\sum_i|A_{ij}|$（列和），$\|A\|_2=\lambda_1(A^TA)^{1/2}$，$\|A\|_\infty=\max_i\sum_j|A_{ij}|$（行和）(A.39)；Frobenius 范数 $\|A\|_F=(\sum a_{ij}^2)^{1/2}$ (A.40)（不与任何向量范数相容）；$\|AB\|\le\|A\|\|B\|$ (A.41)。条件数 $\kappa(A)=\|A\|\|A^{-1}\|$ (A.42)。函数空间范数：$\|\int_a^bF(t)dt\|\le\int_a^b\|F(t)\|dt$（牛顿法分析中用）。

子空间：对线性组合封闭。$\{w:a_i^Tw=0\}$ (A.43) 是子空间，$\{w:a_i^Tw\ge0\}$ (A.44) 一般不是（例 $a_1=(1,0)$）。线性无关、张成集、基、维数 $\dim(S)$。零空间 $\mathrm{Null}(A)$、值空间 $\mathrm{Range}(A)$；线性代数基本定理 $\mathrm{Null}(A)\oplus\mathrm{Range}(A^T)=\mathbb R^n$。

特征值与 SVD：$Aq=\lambda q$；无零特征值 ⇔ 非奇异；对称矩阵特征值为实数，对称正定则全为正。奇异值分解 $A=USV^T$ (A.45)，$U,V$ 正交，$S$ 对角 $\sigma_1\ge\dots\ge\sigma_{\min(m,n)}\ge0$。对称矩阵谱分解 $A=\sum\lambda_iq_iq_i^T=Q\Lambda Q^T$ (A.46)；对称正定时谱分解与 SVD 一致，$\|A\|_2=\sigma_1$ = 最大特征值，$\|A^{-1}\|_2=1/\sigma_n$，且 $\sigma_n\|x\|^2\le x^TAx\le\sigma_1\|x\|^2$。正交矩阵 $\|Qx\|=\|x\|$，奇异值全为 1。

行列式与迹：$\mathrm{trace}(A)=\sum A_{ii}=\sum\lambda_i$ (A.47–A.48)；$\det A=\prod\lambda_i$ (A.49)；$\det A=0$ ⇔ 奇异，$\det AB=\det A\det B$，$\det A^{-1}=1/\det A$，正交阵 $\det Q=\pm1$（用于第 6、8 章分析）。

矩阵分解：

置换矩阵：交换单位阵相应行（例：$5\times5$ 交换第 1、4 行）。
LU：$PA=LU$ (A.50)；解 $Ax=b$：$\tilde b=Pb$，前代 $Lz=\tilde b$，回代 $Ux=z$。稠密时约 $2n^3/3$ flops（LAPACK [4]）。 算法 A.1（带行部分主元的高斯消去）：对 $i=1..n$：在第 $i$ 列 $i..n$ 行中找绝对值最大元 $A_{ji}$；若为 0 则奇异；必要时交换 $A$、$L$ 的第 $i,j$ 行；$L_{ii}=1$，$L_{ki}=A_{ki}/A_{ii}$，$A_{kl}\leftarrow A_{kl}-L_{ki}A_{il}$；最后 $U$ 取 $A$ 的上三角。列主元不增加实际稳定性，但稀疏时可保持因子稀疏。非方阵：$m>n$ 得 $L\in\mathbb R^{m\times n}$；$m<n$ 时对 $A^T$ 分解 $PA^T=\begin{bmatrix}L_1\\L_2\end{bmatrix}U$ (A.51)，若 $A$ 行满秩则零空间由 $M=P^T\begin{bmatrix}L_1^{-T}L_2^T\\-I\end{bmatrix}U^{-T}$ 的列张成 (A.52)。
Cholesky：对称正定 $A=LL^T$ (A.53)，约 $n^3/3$ flops，对角为正时唯一。算法 A.2：对 $i$：$L_{ii}=\sqrt{A_{ii}}$；$L_{ji}=A_{ji}/L_{ii}$；$A_{jk}\leftarrow A_{jk}-L_{ji}L_{ki}$。只用下三角；无需换行即稳定；对称置换 $P^TAP=LL^T$ 可改善稀疏性。
QR：$AP=QR$ (A.54)，$P$ 列置换，$Q$ 正交（原文误写为 "$A$ is $m\times m$ orthogonal"），$R$ 上三角。方阵解方程：$\tilde b=Q^Tb$，回代 $Rz=\tilde b$，$x=Pz$（原文写 $P^Tz$，按 $AP=QR$ 应为 $Pz$）。稠密成本约 $4m^2n/3$，方阵时约为 LU 的两倍；无论如何选置换，稀疏情形 $Q,R$ 一般稠密。用 Householder 变换或 Givens 旋转实现（Golub & Van Loan [115, Ch.5]）。$m<n$ 时对 $A^T$ 做 QR：$A^TP=[Q_1\ Q_2]R$，$Q_2$ 的列张成 $A$ 的零空间，正交规范，优于 (A.52)，但可能更贵（尤其稀疏）。$A$ 列满秩时 $P^TA^TAP=R^TR$，即 $R^T$ 是 $P^TA^TAP$ 的 Cholesky 因子，规定对角为正时 $R$、$Q$ 唯一。$\|A\|_2=\|R\|_2$，方阵时 $\|A^{-1}\|=\|R^{-1}\|$，故可用三角阵 $R$ 估计 $A$ 的条件数（Golub & Van Loan [115, pp.128–130]）。

Sherman–Morrison–Woodbury 公式：秩一更新 $\bar A=A+ab^T$，

\bar A^{-1}=A^{-1}-\frac{A^{-1}ab^TA^{-1}}{1+b^TA^{-1}a};\tag{A.55}

秩 $p$ 更新 $\hat A=A+UV^T$（$U,V\in\mathbb R^{n\times p}$），

\hat A^{-1}=A^{-1}-A^{-1}U(I+V^TA^{-1}U)^{-1}V^TA^{-1}.\tag{A.56}

解 $\hat Ax=d$ 只需用 $A$ 解 $p+1$ 个系统（$A^{-1}d$、$A^{-1}U$）并求 $p\times p$ 矩阵的逆，$p\ll n$ 时便宜。

特征值交错定理（定理 A.2，Golub & Van Loan [115, Thm 8.1.8]）：$A$ 对称，特征值 $\lambda_1\ge\dots\ge\lambda_n$，$\|z\|=1$，$A+\alpha zz^T$ 的特征值 $\xi_1\ge\dots\ge\xi_n$。$\alpha>0$ 时 $\xi_1\ge\lambda_1\ge\xi_2\ge\lambda_2\ge\dots\ge\xi_n\ge\lambda_n$；$\alpha<0$ 时 $\lambda_1\ge\xi_1\ge\lambda_2\ge\dots\ge\lambda_n\ge\xi_n$；两种情况都有 $\sum_i(\xi_i-\lambda_i)=\alpha$ (A.57)。即秩一修正后特征值与原特征值交错，总调整量等于 $\alpha$（$=\pm\|\alpha zz^T\|_2$）。

误差分析与浮点运算：绝对误差 $\|x-\tilde x\|$，相对误差 $\|x-\tilde x\|/\|x\|$（小时分母可换成 $\|\tilde x\|$）。双精度 64 位，尾数 $.d_1d_2\dots d_t$，值 $\sum_{i=1}^td_i2^{-i}\times2^e$；单位舍入（unit roundoff） $u=2^{-t}$，双精度约 $10^{-15}$（实际约 $1.1\times10^{-16}$）。$\mathrm{fl}(x)=x(1+\epsilon)$，$|\epsilon|\le u$ (A.58)；$|\mathrm{fl}(x*y)-x*y|\le u|x*y|$ (A.59)。抵消（cancellation）：两个相近的大数相减，结果误差上界 $u(|x|+|y|+|x-y|)$，相对误差约 $2u|x|/|x-y|$，可能很大；若两数各有 $k$ 位精度、前 $\bar k$ 位相同，差只剩约 $k-\bar k$ 位有效数字——应尽量避免相近数相减（参见 15.2 节简单消去的数值抵消）。参考 Golub & Van Loan [115, §2.4]、Higham [136]。

条件与稳定性：**条件（conditioning）**是问题本身的性质：数据小扰动是否导致解大变化。例：$\begin{bmatrix}1&2\\1&1\end{bmatrix}x=\begin{bmatrix}3\\2\end{bmatrix}$，解 $(1,1)$，右端第一元改为 3.00001 解变为 $(0.99999,1.00001)$，良态；$\begin{bmatrix}1.00001&1\\1&1\end{bmatrix}x=\begin{bmatrix}2.00001\\2\end{bmatrix}$，解 $(1,1)$，右端改为 2 后解变为 $(0,2)$，病态。线性系统扰动界

\frac{\|x-\tilde x\|}{\|x\|}\approx\kappa(A)\Big(\frac{\|A-\tilde A\|}{\|A\|}+\frac{\|b-\tilde b\|}{\|b\|}\Big).

**稳定性（stability）**是算法的性质：对类中所有良态问题在浮点运算下都给出准确答案。算法 A.1 + 三角代换的相对误差约 $\kappa(A)\frac{\mathrm{growth}(A)}{\|A\|}u$ (A.60)，最坏情况 $\mathrm{growth}/\|A\|\sim2^{n-1}$（理论上不稳定），但实际很少出现大增长因子，实用上视为稳定。不选主元的高斯消去肯定不稳定，连良态的 $\begin{bmatrix}0&1\\1&2\end{bmatrix}$ 都分解不了。对称正定系统用 Cholesky + 三角代换是稳定的。

参考文献（References）（PDF p.627–639）

共 259 条，按作者字母排序（[1] Ahuja–Magnanti–Orlin《Network Flows》到 [259] Zhu–Byrd–Lu–Nocedal《L-BFGS-B》）。本块各章引用的关键文献包括：Bertsekas [8]《Constrained Optimization and Lagrange Multiplier Methods》、[9]《Nonlinear Programming》；Boggs & Tolle [23]（SQP 综述，Acta Numerica 1996）；Boggs–Tolle–Wang [24]（拟牛顿约束优化局部收敛）；Byrd–Hribar–Nocedal [34]（大规模内点算法）；Chamberlain 等 [40]（watchdog 技术）；Fiacco & McCormick [79]（SUMT，障碍法经典）；Fletcher [83]《Practical Methods of Optimization》；Freund & Nachtigal [94]（QMR）；Gill–Murray–Saunders 等 [108]（SNOPT）、[111]（NPSOL）、[112]（约束非线性规划综述）；Golub & Van Loan [115]《Matrix Computations》；Higham [136]《Accuracy and Stability of Numerical Algorithms》；Markowitz [157]《Portfolio Selection》(J. Finance 1952)、[159] 专著；Murtagh & Saunders [175]（MINOS）；Murty & Kabadi [176]（非凸 QP 的 NP-hard 性）；Paige & Saunders [188]（LSQR）；Powell 系列 [195]–[209]；Conn–Gould–Toint [53]（LANCELOT）；M. Wright [250]–[252]、S. Wright [253]–[256]（内点法、模型预测控制）。另有自动微分（Bischof、Griewank 等）、最小二乘（Björck、Lawson–Hanson）、随机规划（Birge–Louveaux、Kall–Wallace）、LP 复杂性（Khachiyan、Karmarkar、Nesterov–Nemirovskii）等前面各章引用的文献。

索引（Index）（PDF p.640–651）

按字母排序的全书主题索引（原书页码 619–634 左右），从 "Accumulation point"、"Active set"、"Affine scaling" 到 "Watchdog technique"、"Weakly active"、"Wolfe conditions"（含强 Wolfe 条件、尺度不变性）、"Zoutendijk condition"。条目覆盖无约束优化（线搜索、信赖域子问题的精确/近似解、hard case、Steihaug 方法、二维子空间极小化、拟牛顿/有限内存方法）、约束优化（二阶条件、势函数下降算法、预测步、QP 内点法等）以及数值线性代数概念（unit roundoff 等）。编写教材时可用于术语对照，无需单独成章。

本块总体说明

覆盖 PDF p.445–651：第 15 章后半（15.2 变量消去中段起、15.3 价值函数、习题）、第 16 章二次规划全章、第 17 章罚函数/障碍/增广拉格朗日全章、第 18 章 SQP 全章、附录 A、参考文献、索引。
文本为 PDF 自动抽取，矩阵与公式大量错位，笔记中的公式均按上下文还原；原文中发现的若干笔误（符号、下标、"linearly dependent/independent" 等）已在相应位置注明。
章节结构与第 1 版一致（第 17 章含对数障碍法与 SLC 方法；第 18 章含约化 Hessian SQP、Maratos 效应、watchdog），与 Springer 第 2 版编号存在差异，编写者引用时请以内容为准。

第 15 章 约束优化算法基础（Fundamentals of Constrained Algorithms）（接上一块）

15.2 变量消去（Elimination of Variables）（接上一块，PDF p.445–451）

线性约束的简单消去（Simple Elimination for Linear Constraints）

线性约束的一般约化策略（General Reduction Strategies）

不等式约束的影响（The Effect of Inequality Constraints）

15.3 度量进展：价值函数（Measuring Progress: Merit Functions）（PDF p.451–455）

第 15 章习题概括（PDF p.455–456）

第 15 章（本块部分）本章要点

与量化交易的关联

推荐习题

第 16 章 二次规划（Quadratic Programming）（PDF p.457–505）

引例：组合优化（Portfolio Optimization）（PDF p.459–460）

16.1 等式约束 QP（Equality-Constrained Quadratic Programs）（PDF p.460–464）

16.2 求解 KKT 系统（Solving the KKT System）（PDF p.464–470）

直接解法（Direct Solution of the KKT System）

值空间法（Range-Space Method）

零空间法（Null-Space Method）

基于共轭性的方法（A Method Based on Conjugacy）

16.3 不等式约束问题（Inequality-Constrained Problems）（PDF p.470–473）

16.4 凸 QP 的有效集方法（Active-Set Methods for Convex QP）（PDF p.474–487）

16.5 不定 QP 的有效集方法（Active-Set Methods for Indefinite QP）（PDF p.487–493）

16.6 梯度投影法（The Gradient-Projection Method）（PDF p.493–498）

16.7 内点法（Interior-Point Methods）（PDF p.498–501）

16.8 对偶（Duality）（PDF p.501–502）

第 16 章习题概括（PDF p.503–505）

第 16 章本章要点

与量化交易的关联

推荐习题

第 17 章 罚函数、障碍函数与增广拉格朗日方法（Penalty, Barrier, and Augmented Lagrangian Methods）（PDF p.506–543）

17.1 二次罚函数法（The Quadratic Penalty Method）（PDF p.508–516）

17.2 对数障碍法（The Logarithmic Barrier Method）（PDF p.516–528）

17.3 精确罚函数（Exact Penalty Functions）（PDF p.528–529）

17.4 增广拉格朗日法（Augmented Lagrangian Method）（PDF p.529–540）

17.5 序列线性约束方法（Sequential Linearly Constrained Methods）（PDF p.540–541）

第 17 章习题概括（PDF p.542–543）

第 17 章本章要点

与量化交易的关联

推荐习题

第 18 章 序列二次规划（Sequential Quadratic Programming）（PDF p.544–591）

18.1 局部 SQP 方法（Local SQP Method）（PDF p.546–550）

18.2 实用 SQP 方法预览（Preview of Practical SQP Methods）（PDF p.550–551）

18.3 步的计算（Step Computation）（PDF p.552–555）

18.4 二次模型的 Hessian（The Hessian of the Quadratic Model）（PDF p.555–560）

18.5 价值函数与下降性（Merit Functions and Descent）（PDF p.560–563）

18.6 线搜索 SQP 方法（A Line Search SQP Method）（PDF p.563–564）

18.7 约化 Hessian SQP 方法（Reduced-Hessian SQP Methods）（PDF p.564–569）

18.8 信赖域 SQP 方法（Trust-Region SQP Methods）（PDF p.569–576）

18.9 一个实用的信赖域 SQP 算法（A Practical Trust-Region SQP Algorithm）（PDF p.576–579）

18.10 收敛速度（Rate of Convergence）（PDF p.579–583）

18.11 Maratos 效应（The Maratos Effect）（PDF p.583–589）

第 18 章习题概括（PDF p.589–591）

第 18 章本章要点

与量化交易的关联

推荐习题

附录 A 背景材料（Background Material）（PDF p.592–626）

A.1 分析、几何与拓扑要素（Elements of Analysis, Geometry, Topology）（PDF p.593–609）

A.2 线性代数要素（Elements of Linear Algebra）（PDF p.609–626）

参考文献（References）（PDF p.627–639）

索引（Index）（PDF p.640–651）

本块总体说明

第 15 章约束优化算法基础（Fundamentals of Constrained Algorithms）（接上一块）

第 16 章二次规划（Quadratic Programming）（PDF p.457–505）

第 17 章罚函数、障碍函数与增广拉格朗日方法（Penalty, Barrier, and Augmented Lagrangian Methods）（PDF p.506–543）

第 18 章序列二次规划（Sequential Quadratic Programming）（PDF p.544–591）