Steihaug 截断共轭梯度

形式陈述

给定 $q(p)=g^Tp+p^THp/2$ 、实对称矩阵作用 $v\mapsto Hv$ 和 $\Delta>0$ ，算法为信赖域二次子问题求一个近似步。它从零步启动共轭梯度，但不要求 $H$ 在整个空间正定。下面用模型梯度 $r_j=g+Hz_j$ ，而不是线性系统中常见的负残差记号。

取相对容差 $0<\eta<1$ ，置 $z_0=0,r_0=g,d_0=-g$ 。若 $g=0$ ，返回零步和“一阶残差为零”状态。否则重复：

计算 $w_j=Hd_j$ 与曲率 $\delta_j=d_j^Tw_j$ 。
若 $\delta_j\le0$ ，解 $\|z_j+\tau d_j\|=\Delta$ 的两个根，比较两个端点的模型值，返回较低者及“非正曲率”状态。
若 $\delta_j>0$ ，令 $\alpha_j=r_j^Tr_j/\delta_j$ 。若 $\|z_j+\alpha_jd_j\|\ge\Delta$ ，沿正向射线截到球面，返回及“到达边界”状态。
否则令 $z_{j+1}=z_j+\alpha_jd_j$ 、 $r_{j+1}=r_j+\alpha_jw_j$ 。若 $\|r_{j+1}\|\le\eta\|g\|$ ，返回内部步及“模型残差达到”状态。
令 $\beta_j=\|r_{j+1}\|^2/\|r_j\|^2$ ， $d_{j+1}=-r_{j+1}+\beta_jd_j$ ，继续。

球面交点来自一个标量二次方程：

(d^Td)\tau^2+2(z^Td)\tau+(z^Tz-\Delta^2)=0.

当前点严格在球内时，两根一正一负。正曲率的越界分支取正根；非正曲率时，一维目标是凹函数或线性函数，区间最小值必在某个端点，比较两端即可。实现应另设最大向量积次数，并单独报告非有限计算与预算耗尽。

直觉

普通 CG 期待沿每个方向找到有限的二次谷底。信赖域提供了另一种合法终点：如果模型沿当前方向一直下弯，就走到球面；如果谷底在球外，也只走到球面。非正曲率在这里是可利用的信息，不是给分母加一个小常数后继续除法的理由。

算法只要求对称矩阵作用 $v\mapsto Hv$ ，不必显式存储矩阵。若模型矩阵就是目标的 Hessian，可以调用Hessian–向量积，让自动微分程序提供这一作用；一般曲率近似则需提供自己的乘积接口。算法逐步探索由模型梯度触发的方向，用少量向量构造候选步。

正曲率 CG 折线在第二段触到球面，以及首方向出现负曲率时直接到达边界的两种退出 — 两种边界退出

例子与边界

第二个 CG 步走出了球

取 $H=\operatorname{diag}(1,4)$ 、 $g=(-1,-1)$ 、 $\Delta=4/5$ 。无约束最优步为 $(1,1/4)$ ，长度大于半径。第一轮有

d_0=(1,1),\quad \delta_0=5,\quad\alpha_0=2/5,\quad z_1=(2/5,2/5),\quad r_1=(-3/5,3/5).

第一点长度为 $\sqrt8/5<4/5$ 。取 $\eta=0.1$ 时，残差比例为 $\|r_1\|/\|g\|=3/5$ ，尚未达到要求。接着

\beta_0=9/25,\quad d_1=(24/25,-6/25),\quad \delta_1=144/125,\quad\alpha_1=5/8.

完整 CG 步会到达 $(1,1/4)$ 。现在截取 $z_1+\tau d_1$ ，球面方程化为

153\tau^2+90\tau-50=0,\qquad \tau=\frac{5(\sqrt{43}-3)}{51}<\frac58.

因此输出

p=\left(\frac25+\frac{24}{25}\tau, \frac25-\frac6{25}\tau\right).

可直接核对 $\|p\|=4/5$ 。第一点的模型值为 $-2/5$ ；沿第二个方向走到上述交点时，模型仍继续下降。输出有明确的球面证书，却没有声称模型梯度为零，因为边界最优性本来也不要求 $g+Hp=0$ 。

第一方向就发现负曲率

改取 $H=\operatorname{diag}(-2,1)$ 、 $g=(1,0)$ 、 $\Delta=1$ 。初始方向 $d_0=(-1,0)$ 满足 $d_0^THd_0=-2$ 。两个球面点为 $(-1,0)$ 与 $(1,0)$ ，模型值分别为 $-2$ 与零，于是返回前者。整个过程只用了一个矩阵向量积，没有形成任何正定分解。

没发现负曲率，不表示不存在

保持同一 $H$ ，改成 $g=(0,1)$ 、 $\Delta=1$ 。所有由 $g,Hg,H^2g,\ldots$ 产生的方向都在第二坐标轴上。算法第一轮沿 $(0,-1)$ 到达球面，得到 $q=-1/2$ 。但完整子问题有

p_*^\pm=(\pm\sqrt8/3,-1/3),\qquad q(p_*^\pm)=-7/6.

负曲率藏在未被梯度激发的第一坐标轴。截断 CG 因而可以返回足够下降的步，却漏掉困难情形中的最优方向。若 $g=0$ ，零启动更是完全没有搜索方向；要求二阶驻性时，需要额外的最小特征值检测或其他负曲率探索。

推论与应用

下降不变量与 Cauchy 保证

精确算术中，只要递推分母非零，方向的 $H$ -共轭性由对称性与上述递推代数地推出。在已探索的正曲率前缀上，令 $P=(d_0,\ldots,d_j)$ ，则 $P^THP=\operatorname{diag}(\delta_0,\ldots,\delta_j)\succ0$ ，所以 $H$ 限制到这些方向的张成空间后确实正定。这是该前缀使用正定 CG 子空间最小化性质的范围，不要求 $H$ 在全空间正定。未截断的递推还给出 $r_j^Td_j=-\|r_j\|^2$ 。因此沿本轮方向，

q(z_j+\alpha d_j)-q(z_j) =-\alpha\|r_j\|^2+\tfrac12\alpha^2\delta_j.

正曲率时，在 $0<\alpha\le\alpha_j$ 内它为负；提前截到球面仍下降。非正曲率时，沿任意正 $\alpha$ 都下降，选择两端较低者至少不会比正端更差。每个已接受的内部 CG 点也最小化已探索子空间中的模型。

第一方向是负梯度方向：若当轮截断，得到沿该方向的球内最小点；若没有截断，第一内部点就是 Cauchy 点。后续模型值继续下降，所以最终输出的模型值不高于 Cauchy 点的模型值。这是它能供外层信赖域法使用的关键保证。它没有承诺任意指定精度的全局子问题误差，边界退出也不能冒充线性系统求解成功。

成本、精度与停止含义

若一次 $Hv$ 的成本为 $T_H$ ，执行 $j$ 次后总工作为 $O(n+j(T_H+n))$ ，其中初始检查与完整向量输出即使在 $j=0$ 时也需 $O(n)$ 工作；只需 $O(n)$ 的附加向量存储。精确算术中，至多探索 $n$ 个独立方向便会内部终止或提前截断；浮点中应使用预算和实际残差，而不把这条代数结论作为固定运行保证。显式稀疏矩阵下，记实际存储槽位数为 $s$ （计入重复项与显式零），若返回完整的 $n$ 维向量，则 $T_H=O(n+s)$ ，包括输出初始化；自动微分接口的成本则取决于原求值图。

长递推后要重新计算 $g+Hp$ ，检查残差漂移与球半径。若因数值误差使步略微越界，可对最终步作可记录的安全缩放，并重新评价模型下降。预条件版本还必须明确采用哪一种信赖域范数；把普通 PCG 公式搬进 Euclidean 球而不调整边界几何，不能直接沿用本页的路径分析。

三个正常退出状态各有用途：内部小残差支持近似 Newton 步；碰到边界说明当前半径限制了步；非正曲率说明模型还存在可利用的弯曲方向。真实目标是否接受这个候选，仍由外层的实际／预测下降比决定。

参考资料

Trond Steihaug, The Conjugate Gradient Method and Trust Regions in Large Scale Optimization, SIAM Journal on Numerical Analysis 20(3), 1983, pp. 626–637；原始论文，出版页摘要可访问。
Jennifer B. Erway, Philip E. Gill and Joshua D. Griffin, Iterative Methods for Finding a Trust-Region Step, 2009，§2，印刷页 1113–1114，CG 路径、非正曲率和边界截断；§1 说明边界精度与矩阵向量积成本。
Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed., 2006，§7.1；作者目录。

形式陈述 ​

第二个 CG 步走出了球 ​

第一方向就发现负曲率 ​

没发现负曲率，不表示不存在 ​

下降不变量与 Cauchy 保证 ​

成本、精度与停止含义 ​