第 04 章信赖域方法

学习目标

读完本章，你应当能够：

写出信赖域子问题和基于实际/预测下降比 $\rho_k$ 的半径更新规则（Algorithm 4.1），解释它与线搜索的根本区别。
计算 Cauchy 点，并说明"达到 Cauchy 下降的固定比例即可保证全局收敛"。
实现 dogleg 方法，理解二维子空间极小化和 CG–Steihaug 方法各自的适用场合。
掌握信赖域子问题全局解的刻画（定理 4.3）：$(B+\lambda I)p=-g$、互补条件、$B+\lambda I$ 半正定；会用对 $1/\|p(\lambda)\|$ 的牛顿法求 $\lambda$，知道"困难情形"是怎么回事。
理解 $\eta=0$ 与 $\eta>0$ 两种情形的全局收敛结论，以及信赖域牛顿法能避开鞍点的理论优势。
看清信赖域子问题与岭回归、Levenberg–Marquardt 方法的同构关系，并用于因子回归中的共线性处理。

读前导读

这一章在解决什么问题

Solver 每走一步，都依赖一个"局部近似模型"：在当前权重附近，用斜率和弯曲程度拼出一个二次函数，假装目标函数就长这样。问题是，这个近似只在附近可信，离得越远越不准——就像用久期和凸性估债券价格，收益率变动 10bp 很准，变动 300bp 就明显偏了。

第 3 章的线搜索先按模型定方向，再沿这个方向试步长。本章的信赖域换了一个思路：先划一个圈（半径 $\Delta$），声明"我只在这个圈里相信模型"，然后在圈内找模型的最好点，方向和距离一次定下来。走完后核对"实际改善 ÷ 模型预测的改善"这个比值 $\rho$：比值接近 1，说明模型靠谱，下次把圈放大；比值很低甚至为负，说明模型在这么远的地方已经失真，把圈缩小。这个机制你在风控里一定见过：模型回测表现好，就给它更大的额度；回测频繁失效，就收紧限额。

本章还有一个让金融读者很亲切的结论：在圈内找最好点（信赖域子问题），数学上和岭回归完全相同。圈的半径对应岭惩罚的强度，半径越小，惩罚越重。这给了你一个看待因子回归共线性问题的新角度：岭回归就是"不相信 OLS 能走那么远"。

需要先想起来的数学

二次模型与 $\arg\min$：$m(p)=f+g^Tp+\tfrac12p^TBp$ 是多元的抛物线，$g$ 是斜率，$B$ 是弯曲程度。$\arg\min_p m(p)$ 表示"使 $m$ 最小的那个 $p$"（不是最小值本身）。见第 00 册第 05 章多元微积分与优化。
特征分解：对称矩阵 $B=Q\Lambda Q^T$，$Q$ 的列 $q_j$ 是相互垂直的单位向量（特征向量），$\Lambda$ 是对角线上的特征值。直观上是"把坐标轴转到 $B$ 的主轴方向，在这组坐标下 $B$ 就只是各轴上的伸缩"。这和 PCA 把协方差矩阵分解成主成分一模一样：$q_j$ 是主成分方向，$\lambda_j$ 是该主成分的方差。见第 00 册第 06 章线性代数速成。
拉格朗日乘子：在约束 $\|p\|\le\Delta$ 下求极小时，乘子 $\lambda$ 衡量"放松约束一点点，目标能改善多少"，也就是约束的影子价格。约束不紧（没碰到边界）时影子价格为 0。见第 00 册第 05 章多元微积分与优化。
Cholesky 分解：正定矩阵可以写成 $R^TR$（$R$ 上三角），相当于矩阵的"平方根"。它的存在与否可以当作"矩阵是否正定"的检验：分解失败就说明不正定。在蒙特卡洛模拟中你可能用它生成相关的随机数。见第 00 册第 06 章线性代数速成。
span 与 range：$\mathrm{span}[u,v]$ 是 $u$、$v$ 所有线性组合构成的平面；$\mathrm{range}(B)$ 是所有 $Bx$ 构成的集合（值域）。

怎么读这一章

必读：4.1（框架与 $\rho_k$）、4.2.1（Cauchy 点的含义，公式可以先跳过）、4.2.3（dogleg，配合原书图 4.3）、4.3.1 的定理 4.3 及其解读、4.6 量化实战 B（岭回归）。4.2.5 的 CG–Steihaug 等读完第 5 章再回来看更容易。4.3.3 困难情形、4.3.4 的证明、4.4 的收敛定理第一次可以只看结论和"核心思想"那一句。4.5 读一下椭球信赖域与变量标准化的关系即可。

4.1 基本思想与算法框架

线搜索和信赖域都依靠目标函数的二次模型，但用法不同：

线搜索用模型产生一个方向，再沿方向找步长；
信赖域在当前点周围划出一个区域，在这个区域里"相信模型能充分代表目标函数"，取模型在区域内的（近似）极小点作为一步——同时决定方向和长度。如果这一步不可接受，就缩小区域重新求解，新的步一般不仅更短，方向也不同。

区域大小至关重要：太小，会错失大步前进的机会；太大，模型的极小点可能离目标函数的极小点很远。实践中根据之前迭代的表现调整：模型可靠（预测准、步子好）就逐步放大，允许更大胆的步；某一步失败，说明模型在当前区域内不够准，就缩小。

原书图 4.1 给了一个直观对比：当前点位于一个弯曲山谷的一端，极小点在另一端。基于同一个二次模型，线搜索沿模型极小点的方向搜索，即使用最优步长也只能得到很小的下降；信赖域取一个小圆内的模型极小点，方向会"拐向"山谷，下降更显著。

4.1.1 模型与子问题

模型函数为

m_k(p)=f_k+\nabla f_k^Tp+\tfrac12p^TB_kp,\tag{4.1}

$B_k$ 对称。由 Taylor 定理 $f(x_k+p)=f_k+\nabla f_k^Tp+\tfrac12p^T\nabla^2f(x_k+tp)p$（4.2），模型误差是 $O(\|p\|^2)$；若取 $B_k=\nabla^2f(x_k)$，误差降为 $O(\|p\|^3)$，这就是信赖域牛顿法（第 6 章）。本章只假设 $B_k$ 对称且关于 $k$ 一致有界。

每一步求解信赖域子问题（trust-region subproblem）：

\min_{p\in\mathbb{R}^n}m_k(p)=f_k+\nabla f_k^Tp+\tfrac12p^TB_kp\quad\text{s.t.}\quad\|p\|\le\Delta_k.\tag{4.3}

这里先用欧氏范数。若 $B_k$ 正定且 $\|B_k^{-1}\nabla f_k\|\le\Delta_k$，解就是无约束极小点 $p_k^B=-B_k^{-1}\nabla f_k$，称为完全步（full step）。其他情况需要专门计算，但好消息是：只需近似解就能保证收敛和良好的实际表现。

4.1.2 半径更新

定义实际下降与预测下降之比

\rho_k=\frac{f(x_k)-f(x_k+p_k)}{m_k(0)-m_k(p_k)}.\tag{4.4}

分子是实际下降（actual reduction），分母是预测下降（predicted reduction），后者恒非负（因为 $p=0$ 可行）。解读：

$\rho_k<0$：目标函数反而上升，拒绝这一步；
$\rho_k\approx1$：模型与函数吻合得很好，可以扩大区域；
$\rho_k$ 为正但不接近 1：保持半径；
$\rho_k$ 接近 0 或为负：缩小半径。

Algorithm 4.1（信赖域）　给定 $\hat\Delta>0$（步长总上界）、$\Delta_0\in(0,\hat\Delta)$、$\eta\in[0,\frac14)$：

for k = 0,1,2,...
  （近似）求解 (4.3) 得 p_k；按 (4.4) 计算 ρ_k
  if ρ_k < 1/4:                         Δ_{k+1} = (1/4)·‖p_k‖
  else if ρ_k > 3/4 且 ‖p_k‖ = Δ_k:     Δ_{k+1} = min(2Δ_k, Δ̂)
  else:                                  Δ_{k+1} = Δ_k
  if ρ_k > η:  x_{k+1} = x_k + p_k     else  x_{k+1} = x_k
end

注意：只有当步长真正碰到边界时才放大半径。如果步严格在区域内部，说明当前半径并不妨碍进展，没有必要放大。

白话解释：用一组数字走一遍 Algorithm 4.1。设当前 $f(x_k)=10$，模型预测这一步把 $f$ 降到 $8$（预测下降 2）。实际降到 $8.1$：$\rho=1.9/2=0.95>3/4$，模型很准；若这一步碰到了边界，下次半径翻倍。实际降到 $9.0$：$\rho=0.5$，接受这一步，半径不变。实际升到 $10.5$：$\rho=-0.25<1/4$，拒绝这一步（$x$ 不动），半径缩为这一步长度的 1/4，下次在更小的圈里重新建模求解。 $\eta$ 是"接受门槛"：$\eta=0$ 表示只要函数降了就接受；$\eta=0.1$ 表示实际下降至少要达到预测的 10%。

金融直觉：这和模型风险管理的逻辑相同。$\rho_k$ 是一次"回测"：模型预测的损益和实际损益一比。连续准确，额度（半径）逐步放大，但设上限 $\hat\Delta$；一次严重失准，立刻大幅收紧额度并否决这笔交易。求解子问题的近似方法有两类：三种"至少达到 Cauchy 点下降量"的便宜方法——dogleg（$B_k$ 正定时）、二维子空间极小化（$B_k$ 可以不定）、Steihaug 方法（$B_k$ 是大规模稀疏的精确 Hessian 时最合适）；以及 Moré–Sorensen 的"近似精确"解法，它利用解满足 $(B_k+\lambda I)p=-\nabla f_k$ 这一性质，寻找与半径相对应的 $\lambda$。

4.2 Cauchy 点及相关算法

4.2.1 Cauchy 点

与线搜索不需要最优步长类似，信赖域方法的全局收敛只要求近似解位于信赖域内、并使模型"充分下降"。充分下降用 Cauchy 点来量化。

Algorithm 4.2（Cauchy 点）

求线性化子问题的解：$p_k^S=\arg\min_p f_k+\nabla f_k^Tp$ s.t. $\|p\|\le\Delta_k$；（4.5）
沿 $p_k^S$ 方向求模型极小：$\tau_k=\arg\min_{\tau>0}m_k(\tau p_k^S)$ s.t. $\|\tau p_k^S\|\le\Delta_k$；（4.6）
$p_k^C=\tau_kp_k^S$。

闭式解：$p_k^S=-\dfrac{\Delta_k}{\|\nabla f_k\|}\nabla f_k$，

p_k^C=-\tau_k\frac{\Delta_k}{\|\nabla f_k\|}\nabla f_k,\tag{4.7}

\tau_k=\begin{cases}1,&\nabla f_k^TB_k\nabla f_k\le0,\\[4pt]\min\left(\dfrac{\|\nabla f_k\|^3}{\Delta_k\nabla f_k^TB_k\nabla f_k},\ 1\right),&\text{否则}.\end{cases}\tag{4.8}

理解：若沿负梯度方向曲率非正，模型沿该方向单调下降，一直走到边界；若曲率为正，模型沿该方向是一元凸二次函数，取它的无约束极小点和边界中先到的那个。

推导拆解：(4.8) 的第二行怎么来？沿 $p^S$ 方向走 $\tau$ 倍，记 $s=\Delta/\|g\|$，则 $p=-\tau s g$，代入模型：$m(\tau)=f-\tau s\|g\|^2+\tfrac12\tau^2s^2\,g^TBg$。这是 $\tau$ 的一元二次函数。曲率 $g^TBg>0$ 时，对 $\tau$ 求导令其为零：$-s\|g\|^2+\tau s^2g^TBg=0$，得 $\tau=\|g\|^2/(s\,g^TBg)=\|g\|^3/(\Delta\,g^TBg)$。但 $\tau>1$ 会走出信赖域，所以再与 1 取较小者。第一步 $p^S$ 为什么是 $-\Delta g/\|g\|$？只看线性部分 $g^Tp$，在长度 $\le\Delta$ 的向量里让它最小，就是让 $p$ 与 $g$ 方向正好相反、长度用满，即最速下降方向走到边界。 Cauchy 步计算便宜（不需要矩阵分解），是判断近似解是否可接受的标尺：若每一步的模型下降至少是 Cauchy 步下降的固定倍数，信赖域方法就全局收敛（4.4 节）。

4.2.2 改进 Cauchy 点

但总取 Cauchy 点，相当于用一种特殊步长的最速下降，表现很差。Cauchy 点对 $B_k$ 的依赖很弱（只用来定步长）；要想快速（比如超线性）收敛，$B_k$ 必须同时影响方向和长度。所以实用方法都先算 Cauchy 点再加以改进，并且设计成：当 $B_k$ 正定且 $\|p_k^B\|\le\Delta_k$ 时直接取完全步 $p_k^B$——这样在 $B_k$ 是精确 Hessian 或拟牛顿近似时就能期待超线性收敛。

下面省略下标，把子问题写成

\min_p m(p)\overset{\text{def}}{=}f+g^Tp+\tfrac12p^TBp\quad\text{s.t.}\quad\|p\|\le\Delta,\tag{4.9}

解记作 $p^*(\Delta)$，强调它依赖于半径。

4.2.3 Dogleg 方法

先看 $B$ 正定时解 $p^*(\Delta)$ 随 $\Delta$ 怎样变化：

$\Delta\ge\|p^B\|$ 时，$p^*(\Delta)=p^B$；（4.10）
$\Delta$ 很小时二次项几乎不起作用，$p^*(\Delta)\approx-\Delta\dfrac{g}{\|g\|}$；（4.11）
中间值时 $p^*(\Delta)$ 沿一条弯曲的轨迹从负梯度方向过渡到 $p^B$（原书图 4.3）。

Dogleg（狗腿）方法用两段折线代替这条曲线。第一段从原点到最速下降方向上的无约束极小点

p^U=-\frac{g^Tg}{g^TBg}g,\tag{4.12}

第二段从 $p^U$ 到 $p^B$：

\tilde p(\tau)=\begin{cases}\tau p^U,&0\le\tau\le1,\\ p^U+(\tau-1)(p^B-p^U),&1\le\tau\le2.\end{cases}\tag{4.13}

然后在信赖域约束下沿这条折线极小化 $m$。

白话解释：dogleg 里有两个"候选目的地"。$p^U$ 是"只按最速下降方向走、走到模型最低点"的保守步（它的步长公式和第 3 章 (3.25) 的精确步长相同）；$p^B$ 是牛顿步，完全按模型走到最低点的激进步。圈很小时，只能沿最速下降方向走一点；圈足够大时，直接走牛顿步；圈大小居中时，先朝 $p^U$ 走，再拐向 $p^B$，在碰到圈边的地方停下。参数 $\tau\in[0,1]$ 是第一段，$\tau\in[1,2]$ 是第二段。这条折线的形状像狗的后腿弯折，因此得名。它的好处是：只需解一次线性方程组（算 $p^B$）和一个一元二次方程（求与圆的交点），就能得到近似"沿最优曲线走到边界"的步。 引理 4.1　设 $B$ 正定，则 (i) $\|\tilde p(\tau)\|$ 是 $\tau$ 的增函数；(ii) $m(\tilde p(\tau))$ 是 $\tau$ 的减函数。

证明（只需看 $\tau\in[1,2]$ 段，第一段显然）。(i) 令 $h(\alpha)=\frac12\|p^U+\alpha(p^B-p^U)\|^2$，则

h'(\alpha)=-p^{U\,T}(p^U-p^B)+\alpha\|p^U-p^B\|^2\ge-p^{U\,T}(p^U-p^B)=\frac{g^Tg\cdot g^TB^{-1}g}{g^TBg}\left[1-\frac{(g^Tg)^2}{(g^TBg)(g^TB^{-1}g)}\right]\ge0,

最后一步由 Cauchy–Schwarz 不等式（练习 4）。(ii) 令 $\hat h(\alpha)=m(\tilde p(1+\alpha))$，则

\hat h'(\alpha)=(p^B-p^U)^T(g+Bp^U)+\alpha(p^B-p^U)^TB(p^B-p^U)\le(p^B-p^U)^T(g+Bp^B)=0.\qquad\square

推论：若 $\|p^B\|\ge\Delta$，折线与信赖域边界恰好相交一次，否则不相交。由于 $m$ 沿折线递减，选法很简单：$\|p^B\|\le\Delta$ 时取 $p^B$；否则取折线与边界的交点，只需解一个关于 $\tau$ 的标量二次方程 $\|p^U+(\tau-1)(p^B-p^U)\|^2=\Delta^2$，不需要任何搜索。dogleg 也可以改造来处理不定的 $B$，但意义不大，因为那时 $p^B$ 不再是模型的极小点。

4.2.4 二维子空间极小化

$B$ 正定时，可以把搜索范围从折线扩大到 $p^U$ 与 $p^B$ 张成（等价地，$g$ 与 $B^{-1}g$ 张成）的整个二维子空间：

\min_p m(p)=f+g^Tp+\tfrac12p^TBp\quad\text{s.t.}\quad\|p\|\le\Delta,\ p\in\mathrm{span}[g,B^{-1}g].\tag{4.14}

这只是一个两变量问题，容易求解（练习 9）。Cauchy 点在子空间内可行，所以下降量至少与 Cauchy 点一样多，保证全局收敛；整条 dogleg 折线也在这个子空间里，所以它是 dogleg 的推广。

它的一大优点是能直观、实用且理论上稳妥地处理不定的 $B$（Byrd–Schnabel–Schultz）：当 $B$ 有负特征值时，子空间改为

\mathrm{span}[g,(B+\alpha I)^{-1}g],\qquad\alpha\in(-\lambda_1,-2\lambda_1],\tag{4.15}

$\lambda_1$ 是 $B$ 最负的特征值（保证 $B+\alpha I$ 正定；区间留有余地，使得可以用 Lanczos 等方法近似求 $\alpha$）。若 $\|(B+\alpha I)^{-1}g\|\le\Delta$，就放弃子空间搜索，取

p=-(B+\alpha I)^{-1}g+v,\tag{4.16}

其中 $v$ 满足 $v^T(B+\alpha I)^{-1}g\le0$，让 $p$ 不往回缩、而继续大致沿 $-(B+\alpha I)^{-1}g$ 方向走到更远处（利用负曲率）。若 $B$ 有零特征值但没有负特征值，就用 Cauchy 步。

二维子空间法得到的模型下降常常接近精确解，主要计算量只是一次 $B$ 或 $B+\alpha I$ 的分解，而近似精确方法通常要两三次分解。

4.2.5 Steihaug 方法（CG–Steihaug）

前两种方法都要解一个含 $B$ 的线性方程组，$B$ 很大时代价高。Steihaug 方法基于共轭梯度法（第 5 章），不需要精确解线性方程组，又能在 Cauchy 点的基础上改进。它和标准 CG 的区别只在于：离开信赖域或者遇到 $B$ 的负曲率方向时就停止。

Algorithm 4.3（CG–Steihaug）　给定容差 $\epsilon>0$；令 $p_0=0$，$r_0=g$，$d_0=-r_0$；若 $\|r_0\|<\epsilon$，返回 $p_0$。

for j = 0,1,2,...
  if d_jᵀ B d_j ≤ 0:
     求 τ 使 p = p_j + τ d_j 在 (4.9) 中使 m 最小且 ‖p‖ = Δ；return p
  α_j = r_jᵀ r_j / d_jᵀ B d_j
  p_{j+1} = p_j + α_j d_j
  if ‖p_{j+1}‖ ≥ Δ:
     求 τ ≥ 0 使 p = p_j + τ d_j 满足 ‖p‖ = Δ；return p
  r_{j+1} = r_j + α_j B d_j
  if ‖r_{j+1}‖ < ε‖r_0‖: return p_{j+1}
  β_{j+1} = r_{j+1}ᵀ r_{j+1} / r_jᵀ r_j
  d_{j+1} = −r_{j+1} + β_{j+1} d_j
end

（精读笔记所据的 PDF 文本最后一行印作 $d_{j+1}=r_{j+1}+\beta_{j+1}d_j$；按 $d_0=-r_0$ 的约定和标准 CG，应为 $-r_{j+1}$，此处已更正。）

与线性 CG 的对应关系：$m\leftrightarrow\phi$，$p\leftrightarrow x$，$B\leftrightarrow A$，$-g\leftrightarrow b$。两个额外的停止准则（遇到零/负曲率方向；越出信赖域）都把当前方向与边界的交点作为结果。

初始化 $p_0=0$ 至关重要：第一步之后

p_1=\alpha_0d_0=-\frac{g^Tg}{g^TBg}g,

恰好是 Cauchy 点（若未被边界截断）；之后 CG 每步都降低 $m$，所以全局收敛所需的充分下降自动满足。另一个关键性质也来自 $p_0=0$：迭代点的范数单调增加，因此一碰到边界就可以停——之后不会再有信赖域内模型值更低的点。

定理 4.2　Algorithm 4.3 生成的序列满足

0=\|p_0\|_2<\cdots<\|p_j\|_2<\|p_{j+1}\|_2<\cdots<\|p\|_2\le\Delta.

证明要点：先证 $p_j^Tr_j=0$（$j\ge0$）和 $p_j^Td_j>0$（$j\ge1$）。由 $p_j=\sum_{i<j}\alpha_id_i$ 和 CG 的扩展子空间性质（$r_j\perp d_i$，$i<j$，见第 5 章定理 5.2）得 $p_j^Tr_j=0$。又

p_1^Td_1=(\alpha_0d_0)^T(-r_1+\beta_1d_0)=\alpha_0\beta_1d_0^Td_0>0,\tag{4.17}

归纳地 $p_{j+1}^Td_{j+1}=\beta_{j+1}p_{j+1}^Td_j=\beta_{j+1}(p_j^Td_j+\alpha_jd_j^Td_j)>0$。于是

\|p_{j+1}\|^2=\|p_j\|^2+2\alpha_jp_j^Td_j+\alpha_j^2\|d_j\|^2>\|p_j\|^2.

若因负曲率或越界而停止，最终 $\|p\|=\Delta$，是可能的最大长度。$\square$

直观上，CG–Steihaug 的迭代点沿一条从 Cauchy 点出发、离原点越来越远的路径前进；$B$ 正定时可以与 dogleg 类比——都从 $p^C$ 走向 $p^B$，直到碰到边界。

4.3 子问题的近似精确解

4.3.1 精确解的刻画

上面的方法并不认真追求子问题的精确解，但都利用了 $B$ 的信息，成本低且全局收敛。当 $n$ 不太大时，值得更充分地利用模型：大约用三次分解（dogleg 和二维子空间只需一次）就能得到很好的近似。

定理 4.3　$p^*$ 是

\min_p m(p)=f+g^Tp+\tfrac12p^TBp\quad\text{s.t.}\quad\|p\|\le\Delta\tag{4.18}

的全局解，当且仅当 $p^*$ 可行，且存在标量 $\lambda\ge0$ 使

\begin{aligned} (B+\lambda I)p^*&=-g,&(4.19a)\\ \lambda(\Delta-\|p^*\|)&=0,&(4.19b)\\ B+\lambda I\ &\text{半正定}.&(4.19c) \end{aligned}

解读：

(4.19b) 是互补条件（complementarity）：$\lambda$ 和 $\Delta-\|p^*\|$ 至少有一个为零。解严格在区域内部时 $\lambda=0$，于是 $Bp^*=-g$ 且 $B$ 半正定；解在边界上时 $\lambda$ 可以为正（原书图 4.4）。
由 (4.19a)，$\lambda p^*=-Bp^*-g=-\nabla m(p^*)$：在边界上的解与模型的负梯度共线，即垂直于模型的等高线。
这是非凸二次函数在球上全局最优的充要条件。信赖域子问题是少数"非凸但可以全局求解"的优化问题之一，这是信赖域方法理论上很漂亮的地方。

金融直觉：$\lambda$ 是半径约束的影子价格，和组合优化里约束的拉格朗日乘子含义一样。设想你在做"跟踪误差不超过 2%"约束下的主动组合优化：如果最优组合的跟踪误差只有 1.5%（约束不紧），放宽约束不会带来任何好处，影子价格为 0；如果正好顶到 2%，放宽一点就能多拿收益，影子价格为正。(4.19b) 的"互补条件"说的就是这件事：要么约束不紧（$\|p^*\|<\Delta$）且 $\lambda=0$，要么约束紧且 $\lambda\ge0$。 (4.19a) 可以读成"把模型的弯曲程度人为加上 $\lambda$，再求牛顿步"。$\lambda$ 越大，$B+\lambda I$ 越"硬"，步子越短、越接近最速下降方向（$\lambda$ 极大时 $p\approx-g/\lambda$）。所以信赖域在"牛顿步"和"短的最速下降步"之间连续过渡，过渡的旋钮就是 $\lambda$。 (4.19c) 是信赖域独有的：$B$ 本身可以不定（模型在某些方向向下弯），但加上 $\lambda I$ 后必须半正定，即 $\lambda\ge-\lambda_1$。

4.3.2 计算近似精确解

由定理 4.3，要么 $\lambda=0$ 满足 (4.19a)(4.19c) 且 $\|p\|\le\Delta$；要么定义

p(\lambda)=-(B+\lambda I)^{-1}g

（$\lambda$ 足够大使 $B+\lambda I$ 正定），求 $\lambda>0$ 使

\|p(\lambda)\|=\Delta.\tag{4.20}

这是一个一维求根问题。设 $B=Q\Lambda Q^T$，$\Lambda=\mathrm{diag}(\lambda_1,\dots,\lambda_n)$，$\lambda_1\le\cdots\le\lambda_n$，则

p(\lambda)=-\sum_{j=1}^n\frac{q_j^Tg}{\lambda_j+\lambda}q_j,\tag{4.21}

\|p(\lambda)\|^2=\sum_{j=1}^n\frac{(q_j^Tg)^2}{(\lambda_j+\lambda)^2}.\tag{4.22}

推导拆解：(4.21) 的来历。$B+\lambda I=Q\Lambda Q^T+\lambda QQ^T=Q(\Lambda+\lambda I)Q^T$（用了 $QQ^T=I$），所以 $(B+\lambda I)^{-1}=Q(\Lambda+\lambda I)^{-1}Q^T$，中间是对角矩阵，求逆只需把每个对角元取倒数 $1/(\lambda_j+\lambda)$。于是 $p(\lambda)=-\sum_j\frac{q_j^Tg}{\lambda_j+\lambda}q_j$：把梯度投影到每个主轴上（$q_j^Tg$），在该轴上除以"弯曲程度 + $\lambda$"。 (4.22) 是因为各 $q_j$ 相互垂直且长度为 1，所以长度平方就是各分量平方和（勾股定理）。用 PCA 的语言：梯度在第 $j$ 个主成分上的分量被"除以该主成分方差 + $\lambda$"。方差小的主成分（$\lambda_j$ 小）被放大得最厉害——这正是共线时 OLS 系数不稳定的原因；加上 $\lambda$ 后，这些方向的放大被压住，这就是岭回归的收缩效应。

由此可见：

在 $(-\lambda_1,\infty)$ 上 $\|p(\lambda)\|$ 连续、单调非增，且 $\lim_{\lambda\to\infty}\|p(\lambda)\|=0$；（4.23）
若 $q_1^Tg\ne0$，则 $\lim_{\lambda\downarrow-\lambda_1}\|p(\lambda)\|=\infty$。（4.24）

因此（$q_1^Tg\ne0$ 时）在 $(-\lambda_1,\infty)$ 上恰有一个 $\lambda^*$ 使 $\|p(\lambda^*)\|=\Delta$（原书图 4.5）。三种情形：$B$ 正定且 $\|B^{-1}g\|\le\Delta$，取 $\lambda=0$；$B$ 正定但 $\|B^{-1}g\|>\Delta$，在 $(0,\infty)$ 中找根；$B$ 不定且 $q_1^Tg\ne0$，在 $(-\lambda_1,\infty)$ 中找根。

用什么函数做牛顿迭代？ 直接对 $\phi_1(\lambda)=\|p(\lambda)\|-\Delta$（4.25）用牛顿法效果不好：$\lambda$ 略大于 $-\lambda_1$ 时 $\phi_1\approx\frac{C_1}{\lambda+\lambda_1}+C_2$，高度非线性。改用

\phi_2(\lambda)=\frac1\Delta-\frac{1}{\|p(\lambda)\|},

在该区域 $\phi_2\approx\frac1\Delta-\frac{\lambda+\lambda_1}{C_3}$ 近乎线性，牛顿法表现很好（原书图 4.6）。牛顿迭代 $\lambda^{(\ell+1)}=\lambda^{(\ell)}-\phi_2(\lambda^{(\ell)})/\phi_2'(\lambda^{(\ell)})$（4.26）可以写成只需 Cholesky 分解的形式：

Algorithm 4.4（精确信赖域）　给定 $\lambda^{(0)}$，$\Delta>0$：

for ℓ = 0,1,2,...
  Cholesky 分解 B + λ^(ℓ) I = Rᵀ R
  解 Rᵀ R p_ℓ = −g；解 Rᵀ q_ℓ = p_ℓ
  λ^(ℓ+1) = λ^(ℓ) + (‖p_ℓ‖/‖q_ℓ‖)² · (‖p_ℓ‖ − Δ)/Δ        (4.27)
end

实际使用需要加保护（例如 $\lambda^{(\ell)}<-\lambda_1$ 时 Cholesky 分解不存在）。每次迭代的主要工作是一次 Cholesky 分解；实用版本不追求高精度，两三次迭代得到的近似解就够了。

一个有用的观察：$\phi_2$ 在 $(-\lambda_1,\infty)$ 上是凹的增函数，所以从 $\lambda^*$ 左侧出发的牛顿迭代会单调地从左侧逼近 $\lambda^*$，不会越过；从右侧出发则第一步可能跳得太远（甚至跳到 $-\lambda_1$ 左边），这就是需要保护的原因。

白话解释（原文一处措辞需更正）：上一段说 $\phi_2$ 是"凹的增函数"，方向写反了。随着 $\lambda$ 增大，$\|p(\lambda)\|$ 减小，$1/\|p(\lambda)\|$ 增大，所以 $\phi_2=\frac1\Delta-\frac1{\|p(\lambda)\|}$ 是减函数（这与上文的近似式 $\phi_2\approx\frac1\Delta-\frac{\lambda+\lambda_1}{C_3}$ 一致）；又因为 $1/\|p(\lambda)\|$ 是凹函数（Moré–Sorensen 的结果），$\phi_2$ 是凸函数。可以用两项的小例子验证：$\lambda_1=0,\lambda_2=1$，$q_j^Tg=1$，则 $1/\|p\|$ 在 $\lambda=1,2,3$ 处约为 $0.894,1.664,2.400$，相邻增量 $0.770>0.736$ 在变小，确为凹。结论不受影响：对"凸的减函数"，切线在函数图像下方，从根的左侧（$\phi_2>0$，即 $\|p\|>\Delta$）出发，牛顿步落点不会越过根，迭代单调右移逼近 $\lambda^*$；从右侧出发则可能跳过头。代码中"从 $\lambda^*$ 左侧出发"的初始化正是利用了这一点。

4.3.3 困难情形

若最负特征值是重根（$0>\lambda_1=\lambda_2=\cdots$），只要对某个 $\lambda_j=\lambda_1$ 的 $j$ 有 $q_j^Tg\ne0$，上述方法照样可用。
若对所有 $\lambda_j=\lambda_1$ 的 $j$ 都有 $q_j^Tg=0$，(4.24) 就不成立，$(-\lambda_1,\infty)$ 内可能不存在使 $\|p(\lambda)\|=\Delta$ 的 $\lambda$（原书图 4.7）。Moré 和 Sorensen 称之为困难情形（hard case）。由定理 4.3，$\lambda\in[-\lambda_1,\infty)$，所以只能取 $\lambda=-\lambda_1$。

此时求 $p$ 的方法是：$B-\lambda_1I$ 奇异，取它零空间中的单位向量 $z$（$(B-\lambda_1I)z=0$），令

p=-\sum_{j:\lambda_j\ne\lambda_1}\frac{q_j^Tg}{\lambda_j+\lambda}q_j+\tau z,\tag{4.28}

则 $\|p\|^2=\sum_{j:\lambda_j\ne\lambda_1}\frac{(q_j^Tg)^2}{(\lambda_j+\lambda)^2}+\tau^2$，总能选 $\tau$ 使 $\|p\|=\Delta$，并且在 $\lambda=-\lambda_1$ 时 (4.19) 成立。（PDF 文本中 (4.28) 的求和项前缺少负号，与 (4.21) 不一致，此处已更正。）直观上：梯度在最负曲率方向上没有分量，光靠调 $\lambda$ 走不到边界，于是沿负曲率方向 $z$ "补"一段，这恰好也是降低模型值的方向。

4.3.4 定理 4.3 的证明

先看无约束二次函数何时有极小点。

引理 4.4　设 $m(p)=g^Tp+\frac12p^TBp$（4.29），$B$ 为任意对称矩阵。则 (i) $m$ 有极小点当且仅当 $B$ 半正定且 $g\in\mathrm{range}(B)$；(ii) 极小点唯一当且仅当 $B$ 正定；(iii) $B$ 半正定时，任何满足 $Bp=-g$ 的 $p$ 都是全局极小点。

证明：(i) 充分性：若有 $p$ 使 $Bp=-g$，则对任意 $w$，

m(p+w)=m(p)+g^Tw+(Bp)^Tw+\tfrac12w^TBw=m(p)+\tfrac12w^TBw\ge m(p).

必要性：极小点处 $\nabla m=Bp+g=0$，所以 $g\in\mathrm{range}(B)$；且 $\nabla^2m=B$ 必须半正定。(ii) 正定时 $w\ne0$ 有 $w^TBw>0$，极小唯一；若半正定但不正定，存在 $w\ne0$ 使 $Bw=0$，$m(p+w)=m(p)$，不唯一。(iii) 即 (i) 的证明。$\square$

例：$B=\mathrm{diag}(1,0,2)$。若 $g_2=0$，则 $g\in\mathrm{range}(B)$，有极小点；若 $g_2\ne0$，沿 $\alpha(0,-g_2,0)^T$ 令 $\alpha\to\infty$，$m$ 无限下降。这正是第 2 章提到的"样本协方差奇异时均值–方差问题可能无界"的数学本质。

定理 4.3 的证明

充分性：设存在 $\lambda\ge0$ 满足 (4.19)。由引理 4.4(iii)，$p^*$ 是

\hat m(p)=g^Tp+\tfrac12p^T(B+\lambda I)p=m(p)+\tfrac\lambda2p^Tp\tag{4.30}

的全局极小点，所以

m(p)\ge m(p^*)+\tfrac\lambda2(p^{*T}p^*-p^Tp).\tag{4.31}

由互补条件 $\lambda(\Delta^2-p^{*T}p^*)=0$，得 $m(p)\ge m(p^*)+\frac\lambda2(\Delta^2-p^Tp)\ge m(p^*)$ 对一切 $\|p\|\le\Delta$ 成立。

必要性：若 $\|p^*\|<\Delta$，则 $p^*$ 是 $m$ 的无约束局部极小点，从而 $\nabla m(p^*)=0$、$\nabla^2m=B$ 半正定，取 $\lambda=0$ 即可。若 $\|p^*\|=\Delta$，$p^*$ 也是 $\min m(p)$ s.t. $\|p\|=\Delta$ 的解，由约束优化的一阶条件（原书第 12 章），拉格朗日函数 $\mathcal{L}(p,\lambda)=m(p)+\frac\lambda2(p^Tp-\Delta^2)$ 在 $p^*$ 处驻定，得 $(B+\lambda I)p^*=-g$（4.32）。对所有 $\|p\|=\Delta$ 有 $m(p)\ge m(p^*)$，代入 $g=-(B+\lambda I)p^*$ 整理得

\tfrac12(p-p^*)^T(B+\lambda I)(p-p^*)\ge0.\tag{4.33}

方向集合 $\{\pm(p-p^*)/\|p-p^*\|:\|p\|=\Delta\}$ 在单位球面上稠密，所以 $B+\lambda I$ 半正定。最后证 $\lambda\ge0$：若只有负的 $\lambda$ 满足 (4.19a)(4.19c)，由 (4.31)，$\|p\|\ge\|p^*\|=\Delta$ 时也有 $m(p)\ge m(p^*)$；结合球内的最优性，$p^*$ 是 $m$ 的无约束全局极小点，由引理 4.4(i)，$Bp^*=-g$ 且 $B$ 半正定，于是 $\lambda=0$ 也满足条件，矛盾。$\square$

4.4 全局收敛

4.4.1 Cauchy 点带来的下降

全局收敛只需要近似解的模型下降达到 Cauchy 下降的固定比例。dogleg、二维子空间、Algorithm 4.3 的近似解都满足

m_k(0)-m_k(p_k)\ge c_1\|\nabla f_k\|\min\left(\Delta_k,\frac{\|\nabla f_k\|}{\|B_k\|}\right),\qquad c_1\in(0,1].\tag{4.34}

"min"中的二选一是信赖域方法的典型特征（源自半径约束）。当 $\Delta_k$ 是较小者时，(4.34) 很像 Wolfe 第一条件：模型下降与梯度大小和步长都成比例。

白话解释：(4.34) 的右边可以读成"坡度 × 能走的距离"。能走多远受两个因素限制，取较紧的那个：一是圈的半径 $\Delta_k$；二是 $\|\nabla f_k\|/\|B_k\|$，它是"坡度 ÷ 弯曲程度"，大约就是沿最速下降方向走到模型谷底的距离（一元时就是 $|f'|/f''$）。圈很小时，半径是瓶颈；圈很大时，模型自身的谷底是瓶颈。只要每一步至少拿到这个下降量的固定比例，就保证全局收敛——不需要把子问题解得很精确。 引理 4.5　Cauchy 点满足 (4.34)，且 $c_1=\frac12$：

m_k(0)-m_k(p_k^C)\ge\tfrac12\|\nabla f_k\|\min\left(\Delta_k,\frac{\|\nabla f_k\|}{\|B_k\|}\right).\tag{4.35}

证明：分三种情况。

$\nabla f_k^TB_k\nabla f_k\le0$：$m_k(p_k^C)-m_k(0)=-\Delta_k\|\nabla f_k\|+\frac12\frac{\Delta_k^2}{\|\nabla f_k\|^2}\nabla f_k^TB_k\nabla f_k\le-\Delta_k\|\nabla f_k\|$。
曲率为正且 $\frac{\|\nabla f_k\|^3}{\Delta_k\nabla f_k^TB_k\nabla f_k}\le1$（4.36）：$\tau$ 取内点， $m_k(p_k^C)-m_k(0)=-\frac12\frac{\|\nabla f_k\|^4}{\nabla f_k^TB_k\nabla f_k}\le-\frac12\frac{\|\nabla f_k\|^4}{\|B_k\|\|\nabla f_k\|^2}=-\frac12\frac{\|\nabla f_k\|^2}{\|B_k\|}.$
否则 $\nabla f_k^TB_k\nabla f_k<\frac{\|\nabla f_k\|^3}{\Delta_k}$（4.37），$\tau=1$： $m_k(p_k^C)-m_k(0)\le-\Delta_k\|\nabla f_k\|+\frac12\frac{\Delta_k^2}{\|\nabla f_k\|^2}\cdot\frac{\|\nabla f_k\|^3}{\Delta_k}=-\frac12\Delta_k\|\nabla f_k\|.\qquad\square$

定理 4.6　若 $\|p_k\|\le\Delta_k$ 且 $m_k(0)-m_k(p_k)\ge c_2[m_k(0)-m_k(p_k^C)]$，则 $p_k$ 满足 (4.34)，$c_1=c_2/2$。特别地，精确解满足 (4.34) 且 $c_1=\frac12$；dogleg、二维子空间、Algorithm 4.3 都有 $m_k(p_k)\le m_k(p_k^C)$，同样 $c_1=\frac12$。

4.4.2 收敛到驻点

两类结果：$\eta=0$（只要 $f$ 下降就接受）时，梯度有一个趋于零的子列；$\eta>0$（实际下降至少是预测下降的某个小比例）时，整个梯度序列趋于零。假设：$B_k$ 一致有界；水平集 $\{x:f(x)\le f(x_0)\}$（4.38）有界；允许近似解略超出半径，$\|p_k\|\le\gamma\Delta_k$，$\gamma\ge1$（4.39）。

定理 4.7（$\eta=0$）　设 $\|B_k\|\le\beta$，$f$ 在水平集上连续可微且有下界，所有近似解满足 (4.34) 和 (4.39)。则

\liminf_{k\to\infty}\|\nabla f_k\|=0.\tag{4.40}

证明要点：

写出 $|\rho_k-1|=\left|\dfrac{m_k(p_k)-f(x_k+p_k)}{m_k(0)-m_k(p_k)}\right|$。由 Taylor 定理，分子 $\le(\beta/2)\|p_k\|^2+C_4(p_k)\|p_k\|$（4.41），其中 $C_4$ 可以通过限制 $\|p_k\|$ 而任意小。
反设 $\|\nabla f_k\|\ge\epsilon$（$k\ge K$）（4.42）。由 (4.34)，分母 $\ge c_1\epsilon\min(\Delta_k,\epsilon/\beta)$（4.43），于是 $|\rho_k-1|\le\frac{\gamma\Delta_k(\beta\gamma\Delta_k/2+C_4)}{c_1\epsilon\min(\Delta_k,\epsilon/\beta)}.\tag{4.44}$
取 $\bar\Delta$ 足够小，使 $\beta\gamma\Delta/2+C_4\le\frac{c_1\epsilon}{2\gamma}$（4.45）且 $\bar\Delta\le\epsilon/\beta$。则 $\Delta_k\le\bar\Delta$ 时 $|\rho_k-1|\le\frac12$，$\rho_k>\frac14$ 半径不会缩小。所以半径只在 $\Delta_k>\bar\Delta$ 时才缩小，$\Delta_k\ge\min(\Delta_K,\bar\Delta/4)$（4.46）。
若有无穷多步 $\rho_k\ge\frac14$，则这些步 $f(x_k)-f(x_{k+1})\ge\frac14c_1\epsilon\min(\Delta_k,\epsilon/\beta)$，$f$ 有下界迫使 $\Delta_k\to0$，与 (4.46) 矛盾；否则最终每步 $\rho_k<\frac14$，$\Delta_k$ 每步缩为四分之一，也趋于零，同样矛盾。$\square$

核心思想：半径足够小时模型一定足够准（$\rho_k\approx1$），所以半径不可能无限缩小；而半径有下界时每一步成功的迭代都带来确定的下降量，函数有下界就不可能有无穷多次。

定理 4.8（$\eta\in(0,\frac14)$）　设 $\|B_k\|\le\beta$，$f$ 在水平集上梯度 Lipschitz 连续且有下界，近似解满足 (4.34)(4.39)。则

\lim_{k\to\infty}\nabla f_k=0.\tag{4.47}

证明思路（Schultz–Schnabel–Byrd）：任取一个 $\nabla f_m\ne0$，记梯度 Lipschitz 常数为 $\beta_1$，令 $\epsilon=\frac12\|\nabla f_m\|$，$R=\epsilon/\beta_1$，则在球 $\mathcal{B}(x_m,R)$ 内 $\|\nabla f(x)\|\ge\epsilon$。由定理 4.7 的推理，迭代点不可能永远留在球内；设 $x_{l+1}$ 是第一个离开的点。对其间实际走过的步求和：要么这些步的 $\Delta_k\le\epsilon/\beta$，则 $f(x_m)-f(x_{l+1})\ge\eta c_1\epsilon\sum\Delta_k\ge\eta c_1\epsilon R=\eta c_1\epsilon^2/\beta_1$（4.48）；要么下降至少 $\eta c_1\epsilon^2/\beta$（4.49）。由于 $f(x_k)\downarrow f^*>-\infty$（4.50），

\|\nabla f_m\|^2\le\left[\tfrac14\eta c_1\min\left(\tfrac1\beta,\tfrac1{\beta_1}\right)\right]^{-1}(f(x_m)-f^*)\to0.\qquad\square

4.4.3 近似精确解的收敛：避开鞍点

Moré–Sorensen 的带保护求根法（包括困难情形的处理）有一个终止准则，保证

m(0)-m(p)\ge c_1(m(0)-m(p^*)),\qquad\|p\|\le\gamma\Delta,\tag{4.51}

$p^*$ 是子问题的精确解（实际不需要知道 $p^*$，(4.51) 由实用终止准则推出）。它与 (4.34) 的主要区别是更好地利用了二阶项 $p^TBp$。例：若 $g=0$ 但 $B$ 有负特征值（当前点是鞍点），(4.34) 的右端为零——前面的算法会停在鞍点；而 (4.51) 的右端为正，迫使算法离开鞍点。

定理 4.9　Algorithm 4.1 取 $B_k=\nabla^2f(x_k)$，$\eta\in(0,\frac14)$，近似解满足 (4.51)。则 $\lim\|\nabla f_k\|=0$。若水平集紧，则要么算法在满足二阶必要条件的点终止，要么 $\{x_k\}$ 在水平集中有满足二阶必要条件的极限点。

这就是说，信赖域牛顿法能避开鞍点——这是它相对线搜索方法（第 3 章只保证收敛到驻点）的一个重要理论优势。

白话解释：鞍点像马鞍中心：前后方向是谷底，左右方向是山脊，梯度为零。只看梯度的方法（Cauchy 步、最速下降）在这里"看不到坡"，会停下。近似精确解看的是整个二次模型：只要 $B$ 有负特征值，就存在一个方向沿它走模型会下降（$p^TBp<0$），子问题的最优解自然会沿这个方向走到圈的边界，于是离开鞍点。 "紧集"（compact）在 $\mathbb{R}^n$ 中就是"有界且闭"的集合，这里用它保证迭代点不会跑到无穷远，从而一定有极限点。"二阶必要条件"即第 2 章定理 2.3：梯度为零且 Hessian 半正定。

4.5 其他改进

4.5.1 尺度

病态尺度在几何上的表现是：$x^*$ 位于一条狭长的山谷中，附近等高线是非常扁的椭圆。此时球形信赖域不合适：沿敏感方向模型只在很短距离内可信，沿不敏感方向可信距离长得多。信赖域的形状应该让边界上各点"对模型的信心大致相同"，即采用椭球信赖域：

\|Dp\|\le\Delta,\tag{4.52}

$D$ 为正对角矩阵，子问题变为

\min_p m_k(p)=f_k+\nabla f_k^Tp+\tfrac12p^TB_kp\quad\text{s.t.}\quad\|Dp\|\le\Delta_k.\tag{4.53}

$f$ 对 $x_i$ 敏感时 $d_{ii}$ 取大，不敏感时取小。$D$ 可由二阶导数 $\partial^2f/\partial x_i^2$ 构造，可以逐步变化，只要 $d_{ii}$ 保持在 $[d_{lo},d_{hi}]$（$0<d_{lo}\le d_{hi}<\infty$）内即可，不必精确。

本章所有算法都可改为椭球信赖域，收敛理论只需表面修改。例如广义 Cauchy 点（Algorithm 4.5）的闭式为

p_k^S=-\frac{\Delta_k}{\|D^{-1}\nabla f_k\|}D^{-2}\nabla f_k,\tag{4.56}

\tau_k=\begin{cases}1,&\nabla f_k^TD^{-2}B_kD^{-2}\nabla f_k\le0,\\ \min\left(\dfrac{\|D^{-1}\nabla f_k\|^3}{\Delta_k\nabla f_k^TD^{-2}B_kD^{-2}\nabla f_k},1\right),&\text{否则}.\end{cases}\tag{4.57}

更简单的做法是变量代换 $\tilde p=Dp$：子问题变为 $\min_{\tilde p}f_k+(D^{-1}\nabla f_k)^T\tilde p+\frac12\tilde p^T(D^{-1}B_kD^{-1})\tilde p$ s.t. $\|\tilde p\|\le\Delta_k$，于是只需用 $D^{-1}\nabla f_k$ 代替梯度、$D^{-1}B_kD^{-1}$ 代替 $B_k$，就能直接套用球形信赖域的理论和算法。

4.5.2 非欧氏信赖域

信赖域也可以用 $\|p\|_1\le\Delta_k$、$\|p\|_\infty\le\Delta_k$ 或它们的尺度化版本。无约束优化中它们没有明显优势，但对约束问题有用。例如界约束问题 $\min f(x)$ s.t. $x\ge0$，子问题是

\min_p m_k(p)\quad\text{s.t.}\quad x_k+p\ge0,\ \|p\|\le\Delta_k.\tag{4.58}

欧氏范数下可行域是球与非负象限的交，几何上很别扭；改用 $\infty$-范数后变成一个盒子：$x_k+p\ge0$，$-\Delta_ke\le p\le\Delta_ke$，可以用标准二次规划技术求解。组合权重的上下界约束 $l\le w\le u$ 正是这种结构，SciPy 中 least_squares(method='trf')（信赖域反射法）、L-BFGS-B 等处理界约束的方法都利用了类似的思路。

4.6 量化实战：信赖域与岭回归

本节做两个实验。

A：dogleg 信赖域　用精确 Hessian 的 dogleg 方法（原书习题 4.2）求解 Rosenbrock 函数，打印每一步的半径、$\rho_k$、步的类型以及是否接受，直观看到半径如何自适应调整。

B：信赖域子问题就是岭回归　截面因子回归 $\min_\beta\frac12\|y-X\beta\|^2$ 中，若两个风格因子（如价值与盈利收益率）高度共线，OLS 估计会出现"一正一负、互相抵消"的不稳定因子收益。给系数加范数约束 $\|\beta\|\le\Delta$：

\min_\beta\ \underbrace{-(X^Ty)^T\beta}_{g^T\beta}+\tfrac12\beta^T\underbrace{X^TX}_{B}\beta\quad\text{s.t.}\quad\|\beta\|\le\Delta,

这恰好是信赖域子问题 (4.18)。由定理 4.3，解满足 $(X^TX+\lambda I)\beta=X^Ty$——这就是岭回归的正规方程，$\lambda$ 就是岭惩罚系数。图 4.5 中 $\|p(\lambda)\|$ 关于 $\lambda$ 的单调关系，保证了"范数约束 $\Delta$"和"岭惩罚 $\lambda$"一一对应。我们用 Algorithm 4.4 对给定的 $\Delta$ 求出 $\lambda$，再与同一 $\lambda$ 下的岭回归闭式解比对。

import numpy as np

# ---------- Part A: Algorithm 4.1 + dogleg，精确 Hessian，Rosenbrock ----------
def rosen(x):  return 100 * (x[1] - x[0]**2)**2 + (1 - x[0])**2
def rosen_g(x): return np.array([-400 * x[0] * (x[1] - x[0]**2) - 2 * (1 - x[0]), 200 * (x[1] - x[0]**2)])
def rosen_h(x): return np.array([[1200 * x[0]**2 - 400 * x[1] + 2, -400 * x[0]], [-400 * x[0], 200.0]])

def cauchy_point(g, B, D):                       # (4.7)(4.8)
    gBg = g @ B @ g; gn = np.linalg.norm(g)
    tau = 1.0 if gBg <= 0 else min(gn**3 / (D * gBg), 1.0)
    return -tau * D / gn * g

def dogleg(g, B, D):
    try:
        np.linalg.cholesky(B)
    except np.linalg.LinAlgError:                # B 不定：dogleg 不适用，退回 Cauchy 点
        return cauchy_point(g, B, D), "Cauchy"
    pB = -np.linalg.solve(B, g)
    if np.linalg.norm(pB) <= D: return pB, "全牛顿步"
    pU = -(g @ g) / (g @ B @ g) * g              # (4.12)
    if np.linalg.norm(pU) >= D: return D * pU / np.linalg.norm(pU), "沿负梯度到边界"
    d = pB - pU                                  # 解 ||pU + t d|| = D, t in [0,1]
    a, b, c = d @ d, 2 * pU @ d, pU @ pU - D**2
    t = (-b + np.sqrt(b * b - 4 * a * c)) / (2 * a)
    return pU + t * d, "狗腿折线"

def trust_region(x, D=1.0, Dmax=10.0, eta=0.1, tol=1e-8, verbose=True):
    for k in range(200):
        g, B = rosen_g(x), rosen_h(x)
        if np.linalg.norm(g) < tol: return x, k
        p, kind = dogleg(g, B, D)
        pred = -(g @ p + 0.5 * p @ B @ p)        # m(0) - m(p)
        rho = (rosen(x) - rosen(x + p)) / pred   # (4.4)
        if verbose and k < 12:
            print("k=%2d  Δ=%.4f  ρ=%7.3f  %-8s  %s" % (k, D, rho, kind, "接受" if rho > eta else "拒绝"))
        if rho < 0.25: D = 0.25 * np.linalg.norm(p)
        elif rho > 0.75 and np.isclose(np.linalg.norm(p), D): D = min(2 * D, Dmax)
        if rho > eta: x = x + p
    return x, k
x, k = trust_region(np.array([-1.2, 1.0]))
print("信赖域 dogleg：%d 次迭代收敛到 %s\n" % (k, np.round(x, 8)))

# ---------- Part B: 信赖域子问题 = 范数约束最小二乘 = 岭回归（Algorithm 4.4） ----------
rng = np.random.default_rng(3)
N, K = 300, 6                                         # 300 只股票的截面，6 个风格因子
X = rng.standard_normal((N, K))
X[:, 1] = 0.99 * X[:, 0] + 0.14 * rng.standard_normal(N)   # 价值与盈利收益率因子高度共线
f_true = np.array([0.010, 0.002, -0.004, 0.003, 0.0, 0.006])
y = X @ f_true + 0.03 * rng.standard_normal(N)          # 当期截面收益
B, g = X.T @ X, -X.T @ y                                # m(p) = g'p + 1/2 p'Bp（差一个常数）

def tr_exact(B, g, Delta, tol=1e-10, maxit=50):
    """Algorithm 4.4：对 phi2(λ)=1/Δ-1/||p(λ)|| 做牛顿迭代，返回 p, λ, 迭代次数"""
    lam1 = np.linalg.eigvalsh(B)[0]
    if lam1 > 0:
        p = -np.linalg.solve(B, g)
        if np.linalg.norm(p) <= Delta: return p, 0.0, 0
    lam = max(0.0, -lam1) + 1e-12 * np.abs(B).max()      # 从 λ* 左侧出发，牛顿迭代单调右移
    for it in range(1, maxit + 1):
        R = np.linalg.cholesky(B + lam * np.eye(len(g))).T   # B + λI = R'R
        p = -np.linalg.solve(R, np.linalg.solve(R.T, g))
        q = np.linalg.solve(R.T, p)
        pn, qn = np.linalg.norm(p), np.linalg.norm(q)
        if abs(pn - Delta) < tol * Delta: break
        lam += (pn / qn)**2 * (pn - Delta) / Delta          # (4.27)
    return p, lam, it

beta_ols = np.linalg.solve(B, -g)
print("条件数 κ(X'X) = %.0f" % np.linalg.cond(B))
print("OLS 因子收益:", np.round(beta_ols, 4), " ||β|| = %.4f" % np.linalg.norm(beta_ols))
for Delta in [0.020, 0.013, 0.010]:
    p, lam, it = tr_exact(B, g, Delta)
    ridge = np.linalg.solve(B + lam * np.eye(K), X.T @ y)   # 同一 λ 的岭回归闭式解
    kkt = np.linalg.norm((B + lam * np.eye(K)) @ p + g)
    print("Δ=%.3f: λ=%8.3f 迭代%d次 ||p||=%.4f  β=%s  与岭回归差 %.1e  KKT残差 %.1e" %
          (Delta, lam, it, np.linalg.norm(p), np.round(p, 4), np.abs(p - ridge).max(), kkt))

运行输出：

k= 0  Δ=1.0000  ρ=  1.003  全牛顿步      接受
k= 1  Δ=1.0000  ρ= -0.414  狗腿折线      拒绝
k= 2  Δ=0.2500  ρ=  1.020  狗腿折线      接受
k= 3  Δ=0.5000  ρ=  0.850  狗腿折线      接受
k= 4  Δ=1.0000  ρ=  1.250  全牛顿步      接受
k= 5  Δ=1.0000  ρ=  1.359  全牛顿步      接受
k= 6  Δ=1.0000  ρ=  0.860  全牛顿步      接受
k= 7  Δ=1.0000  ρ=  1.208  全牛顿步      接受
k= 8  Δ=1.0000  ρ= -4.250  全牛顿步      拒绝
k= 9  Δ=0.1058  ρ=  1.133  狗腿折线      接受
k=10  Δ=0.2116  ρ=  1.263  狗腿折线      接受
k=11  Δ=0.4233  ρ=  0.797  全牛顿步      接受
信赖域 dogleg：25 次迭代收敛到 [1. 1.]

条件数 κ(X'X) = 196
OLS 因子收益: [-0.0063  0.0164 -0.0089  0.0036 -0.0004  0.0046]  ||β|| = 0.0206
Δ=0.020: λ=   0.140 迭代4次 ||p||=0.0200  β=[-0.0057  0.0159 -0.0089  0.0036 -0.0004  0.0046]  与岭回归差 3.1e-17  KKT残差 1.4e-15
Δ=0.013: λ=   9.691 迭代8次 ||p||=0.0130  β=[ 0.0025  0.0076 -0.0086  0.0034 -0.0005  0.0044]  与岭回归差 1.3e-17  KKT残差 1.2e-15
Δ=0.010: λ=  93.584 迭代7次 ||p||=0.0100  β=[ 0.004   0.0047 -0.0066  0.0026 -0.0002  0.0033]  与岭回归差 1.7e-18  KKT残差 1.0e-15

解读

A：第 1 步和第 8 步的 $\rho_k$ 为负，被拒绝，半径随即缩小到被拒步长的 1/4；随后几步 $\rho_k\approx1$ 且步长碰到边界，半径逐步加倍；在解附近都是"全牛顿步"，信赖域约束不再起作用，恢复牛顿法的快速收敛（第 6 章定理 6.4 会严格证明这一点）。
B：真实的价值、盈利因子收益是 $(0.010, 0.002)$，两者合计 0.012。由于共线（相关系数约 0.99），OLS 给出 $(-0.0063, 0.0164)$——合计仍约 0.010，但如何在两个因子之间分配完全被噪声主导，而且符号都可能是错的。加上范数约束后，Algorithm 4.4 用 4–8 次 Cholesky 分解就找到了对应的 $\lambda$；它与同一 $\lambda$ 的岭回归解差异在 $10^{-17}$ 量级，KKT 残差在 $10^{-15}$ 量级，验证了定理 4.3。随着 $\Delta$ 收紧，两个共线因子的收益被"拉到一起"，估计更稳定，其余因子几乎不受影响。

更多量化联系

Levenberg–Marquardt：非线性最小二乘 $\min\frac12\|r(x)\|^2$ 的 LM 方法每步解 $(J^TJ+\lambda I)p=-J^Tr$，正是 $B=J^TJ$ 的信赖域子问题（本册第 10 章）。期权模型校准（Heston、SABR 拟合隐含波动率曲面）普遍用 LM 或 scipy.optimize.least_squares(method='trf')，理解 $\lambda$ 与半径的对应关系有助于调参。
非凸目标：风险平价的某些表述、含非线性冲击成本的执行优化，Hessian 可能不定。信赖域方法不需要修正 Hessian 就能处理负曲率，且（用近似精确解时）能避开鞍点。SciPy 中 minimize(method='trust-ncg' / 'trust-exact' / 'trust-krylov') 分别对应本章的 Steihaug、Moré–Sorensen 精确解法和其 Lanczos 版本。
尺度：资产或因子量级差别大时，椭球信赖域（对角缩放）等价于先对变量标准化。

本章小结

信赖域方法在当前点周围的区域内极小化二次模型，用实际下降与预测下降之比 $\rho_k$ 判断模型好坏、自适应调整区域大小。全局收敛只要求每步达到 Cauchy 下降的固定比例，所以子问题可以近似求解：dogleg 适合 $B$ 正定，二维子空间可以处理不定的 $B$，CG–Steihaug 适合大规模问题（它的第一步就是 Cauchy 点，迭代范数单调增）。子问题的全局解由 $(B+\lambda I)p=-g$、互补条件和 $B+\lambda I$ 半正定刻画，可用对 $1/\|p(\lambda)\|$ 的牛顿法求解，"困难情形"要沿最负曲率方向补一段。$\eta>0$ 时梯度整体趋于零；精确 Hessian 加近似精确解还能保证收敛到满足二阶必要条件的点。信赖域子问题与岭回归、Levenberg–Marquardt 是同一个数学结构。

概念	公式/要点
子问题	$\min_p f_k+\nabla f_k^Tp+\frac12p^TB_kp$，$\Vert p\Vert \le\Delta_k$
下降比	$\rho_k=\dfrac{f(x_k)-f(x_k+p_k)}{m_k(0)-m_k(p_k)}$；$<\frac14$ 缩小，$>\frac34$ 且触边界放大
Cauchy 点	$p^C=-\tau\frac{\Delta}{\Vert g\Vert }g$，$\tau=\min\left(\frac{\Vert g\Vert ^3}{\Delta g^TBg},1\right)$（曲率为正时）
Cauchy 下降	$m(0)-m(p^C)\ge\frac12\Vert g\Vert \min(\Delta,\Vert g\Vert /\Vert B\Vert )$
Dogleg	原点 → $p^U=-\frac{g^Tg}{g^TBg}g$ → $p^B=-B^{-1}g$ 的折线与边界交点
精确解刻画	$(B+\lambda I)p^=-g$，$\lambda(\Delta-\Vert p^\Vert )=0$，$B+\lambda I\succeq0$，$\lambda\ge0$
$\lambda$ 的牛顿迭代	$\lambda\leftarrow\lambda+\left(\frac{\Vert p\Vert }{\Vert q\Vert }\right)^2\frac{\Vert p\Vert -\Delta}{\Delta}$，$R^TRp=-g$，$R^Tq=p$
全局收敛	$\eta=0$：$\liminf\Vert \nabla f_k\Vert =0$；$\eta>0$：$\lim\nabla f_k=0$
与岭回归	$\Vert \beta\Vert \le\Delta\ \Leftrightarrow\ (X^TX+\lambda I)\beta=X^Ty$

练习

基础

（原书 4.5）验证 Cauchy 点的闭式 (4.7)(4.8)。
设 $B=\mathrm{diag}(2,1)$，$g=(4,1)^T$，$\Delta=1$。分别计算 Cauchy 点、$p^U$、$p^B$ 和 dogleg 步，比较它们的模型值。提示：$p^B=(-2,-1)$，$\|p^B\|=\sqrt5>1$；$p^U=-\frac{17}{33}(4,1)$，$\|p^U\|\approx2.12>1$，所以 dogleg 步就是沿负梯度走到边界，与 Cauchy 点相同。
说明 Algorithm 4.1 中"只有当 $\|p_k\|=\Delta_k$ 时才放大半径"的理由。如果去掉这个条件，会有什么后果？
（原书 4.6）用 Cauchy–Schwarz 不等式证明 $B$ 正定时 $\gamma=\dfrac{\|g\|^4}{(g^TBg)(g^TB^{-1}g)}\le1$，从而完成引理 4.1 的证明。提示：$g^Tg=(B^{1/2}g)^T(B^{-1/2}g)$。
（原书 4.10）证明对任意对称矩阵 $B$，存在 $\lambda\ge0$ 使 $B+\lambda I$ 正定。

进阶

（原书 4.8）证明 Algorithm 4.4 中的迭代公式 (4.27) 就是对 $\phi_2(\lambda)=\frac1\Delta-\frac1{\|p(\lambda)\|}$ 的牛顿迭代 (4.26)。提示：$\frac{d}{d\lambda}\|p\|^2=-2p^T(B+\lambda I)^{-1}p=-2\|q\|^2$。
构造一个 $2\times2$ 的困难情形例子：$B=\mathrm{diag}(-1,1)$，$g=(0,1)^T$，$\Delta=2$。求子问题的全局解。提示：$\lambda=1$，$p=(\pm\tau,-\frac12)$，$\tau^2+\frac14=4$。
（原书 4.12）设 $g=(-1/\epsilon,-1,-\epsilon^2)^T$，$B=\mathrm{diag}(1/\epsilon^3,1,\epsilon^3)$，$\Delta=0.5$。说明精确解的模型下降为 $\frac38+O(\epsilon)$，而二维子空间法只有 $O(\epsilon)$。这说明了什么？
（原书 4.9）$B$ 正定时，把二维子空间问题 (4.14) 化为一个关于两个系数的小规模信赖域问题，写出求解步骤。
在本章实战 B 中，用 5 折交叉验证在一组 $\Delta$ 中挑选最优值，并与直接在 $\lambda$ 上做交叉验证的结果比较，说明两种参数化的等价性。

原书推荐习题：4.2、4.3（实现 dogleg 与 CG–Steihaug，前者在 Rosenbrock 上试验半径更新规则，后者在扩展 Rosenbrock 函数上报告每步是负曲率、触边界还是满足停止准则）、4.6 与 4.7（Cauchy–Schwarz 与 dogleg/双狗腿路径的单调性）、4.8（推导 $\lambda$ 的牛顿迭代）、4.10 与 4.12（$B+\lambda I$ 的正定化与二维子空间法的局限）。

原书对照

本章内容	原书位置	PDF 页码
4.1 基本思想、模型、子问题、Algorithm 4.1	Ch.4 引言，(4.1)–(4.4)，图 4.1	PDF p.85–89
4.2.1–4.2.2 Cauchy 点及其改进	§4.1 The Cauchy Point，Improving on the Cauchy Point	PDF p.89–91
4.2.3 Dogleg，引理 4.1	The Dogleg Method，图 4.3	PDF p.91–93
4.2.4 二维子空间极小化	Two-Dimensional Subspace Minimization	PDF p.94
4.2.5 CG–Steihaug，定理 4.2	Steihaug's Approach，Algorithm 4.3	PDF p.95–97
4.3.1–4.3.2 精确解刻画与计算，定理 4.3，Algorithm 4.4	§4.2 Characterizing/Calculating Nearly Exact Solutions	PDF p.97–102
4.3.3 困难情形	The Hard Case，图 4.7	PDF p.102–104
4.3.4 引理 4.4 与定理 4.3 的证明	Proof of Theorem 4.3	PDF p.104–107
4.4.1 Cauchy 下降，引理 4.5，定理 4.6	§4.3 Reduction Obtained by the Cauchy Point	PDF p.107–109
4.4.2 定理 4.7、4.8	Convergence to Stationary Points	PDF p.109–113
4.4.3 定理 4.9（避开鞍点）	Convergence of Algorithms Based on Nearly Exact Solutions	PDF p.113–114
4.5 尺度、非欧氏信赖域	§4.4 Other Enhancements	PDF p.114–117
注释与参考、习题	Notes and References，Exercises 4.1–4.12	PDF p.117–119

页码换算：原书正文页码 = PDF 页码减 20（已用 PDF 页眉核对；第 1–2 章减 21，第 3–11 章减 20，第 12–16 章减 19，第 17 章至附录减 18）。

概念	公式/要点
子问题	\(\min_p f_k+\nabla f_k^Tp+\frac12p^TB_kp\)，\(\Vert p\Vert \le\Delta_k\)
下降比	\(\rho_k=\dfrac{f(x_k)-f(x_k+p_k)}{m_k(0)-m_k(p_k)}\)；\(<\frac14\) 缩小，\(>\frac34\) 且触边界放大
Cauchy 点	\(p^C=-\tau\frac{\Delta}{\Vert g\Vert }g\)，\(\tau=\min\left(\frac{\Vert g\Vert ^3}{\Delta g^TBg},1\right)\)（曲率为正时）
Cauchy 下降	\(m(0)-m(p^C)\ge\frac12\Vert g\Vert \min(\Delta,\Vert g\Vert /\Vert B\Vert )\)
Dogleg	原点 → \(p^U=-\frac{g^Tg}{g^TBg}g\) → \(p^B=-B^{-1}g\) 的折线与边界交点
精确解刻画	\((B+\lambda I)p^=-g\)，\(\lambda(\Delta-\Vert p^\Vert )=0\)，\(B+\lambda I\succeq0\)，\(\lambda\ge0\)
\(\lambda\) 的牛顿迭代	\(\lambda\leftarrow\lambda+\left(\frac{\Vert p\Vert }{\Vert q\Vert }\right)^2\frac{\Vert p\Vert -\Delta}{\Delta}\)，\(R^TRp=-g\)，\(R^Tq=p\)
全局收敛	\(\eta=0\)：\(\liminf\Vert \nabla f_k\Vert =0\)；\(\eta>0\)：\(\lim\nabla f_k=0\)
与岭回归	\(\Vert \beta\Vert \le\Delta\ \Leftrightarrow\ (X^TX+\lambda I)\beta=X^Ty\)

第 04 章 信赖域方法