信赖域二次子问题

$H$ 负责预测不同方向的曲率，球负责限定“这份局部预测允许使用多远”。沿负曲率方向，二次模型希望越走越低；有限半径为这种下降提供一个明确终点。于是无需先把原来的 $H$ 改成正定，才能定义下一步。

乘子 $\lambda$ 把所有特征方向的曲率同时上移。移位之后，$p_{\ast }$ 成为一个凸二次函数的无约束最小点；互补关系再保证这一修正没有改变球内的最优答案。这个证书解释了为何求解线性系统只是工作的一部分：还要检查曲率和半径。

一个必须补上零空间分量的例子 ​

取

于是 $q(p)=-p_1^2+p_2^2/2+p_2$。令 $\lambda =2$，移位方程变成

它确定 $p_2=-1/3$，却没有确定 $p_1$。最小范数解 $(0,-1/3)$ 还在球内；因为 $\lambda >0$，必须补足半径，得到

两个解都满足完整证书。若只解原来的 Newton 方程 $Hp=-g$，会得到 $(0,-1)$，目标为 $-1/2$；它甚至满足乘子为零的普通 KKT 条件，却不是球内全局解，因为 $H$ 仍有负特征值。

本例中对任意 $\lambda >2$，移位方程的唯一解都是 $p(\lambda )=(0,-1/(1+\lambda ))$，长度小于 $1/3$。因此，单靠调节正定移位并寻找 $\Vert p(\lambda )\Vert =1$，永远找不到答案。困难情形的缺失部分恰在最小特征值的特征空间中。

正定、半正定和线性模型 ​

若 $H\succ 0$ 且 $\Vert H^{-1}g\Vert \le \mathrm{\Delta }$，取 $\lambda =0,p_{\ast }=-H^{-1}g$ 即可。等号时最优步虽然位于球面，乘子仍可为零；“在边界上”不能反推“乘子严格为正”。

若 $H=\mathrm{diag}(1,0),g=(-1,0),\mathrm{\Delta }=2$，所有 $(1,t)$、$|t|\le \sqrt{3}$ 都是最优点，目标为 $-1/2$。半正定奇异模型可以同时有内部解与边界解，并不总属于上面的负曲率困难情形。

若 $H=0,g\ne 0$，最优步为 $-\mathrm{\Delta }g/\Vert g\Vert$，对应 $\lambda =\Vert g\Vert /\mathrm{\Delta }$。若连 $g$ 也为零，整个球都是解。这些分支应在任何除法之前识别。

全局证书为什么成立 ​

设 $p_{\ast }$ 满足证书，任取球内 $z$。用移位方程消去 $g$，直接展开得到

第一项由半正定性非负。若 $\lambda =0$，第二项为零；若 $\lambda >0$，互补关系给出 $\Vert p_{\ast }\Vert =\mathrm{\Delta }\ge \Vert z\Vert$。两项均非负，这是一份覆盖整个球的证明，不只是球面切方向上的二阶判断。

必要性可以通过构造一个这样的解看清。由实对称矩阵的有限维谱定理公理库有限维谱定理Finite-dimensional spectral theorem有限维复正规算子存在正交规范特征基；实数情形对应自伴算子。，将 $H$ 按正交特征方向公理库特征值与特征向量Eigenvalue and eigenvector满足 Tv=λv 且 v 非零的标量 λ 与向量 v。写为 $U\mathrm{diag}(d_i)U^T$，令 $\gamma =U^{T}g$。在 $\lambda >max(0,-\underset{i}{min}{d}_i)$ 上，

右侧随 $\lambda$ 减小而增大。若零移位已有半正定、相容且长度不超过半径的解，就采用它；否则，若上式从谱端点右侧的极限大于 ${\mathrm{\Delta }}^2$，连续性给出一个球面根。如果极限不超过 ${\mathrm{\Delta }}^2$，而谱端点是正移位，则 $g$ 必须垂直于该零空间；取端点处的最小范数解，再加入零空间分量补到球面。这样所有情况都有证书。对任意另一个全局最优点，上面的两项之和必须为零，于是它也满足同一移位方程和互补关系。

怎样求解，成本在哪里 ​

小型稠密问题可以先作 $O(n^3)$ 的对称特征分解，再用一维保守求根处理普通分支；谱坐标中每次长度计算为 $O(n)$，映回原坐标为 $O(n^2)$。接近奇异端点时，应单独检查相容性和零空间，不能靠把分母改成一个小正数掩盖困难情形。实际 Moré–Sorensen 方法用受保护的移位及 Cholesky 分解，避免显式计算完整特征分解。

大型问题常只计算 Hessian 的矩阵向量积，采用Steihaug 截断共轭梯度公理库Steihaug 截断共轭梯度Steihaug–Toint truncated CG · Truncated conjugate gradient trust-region method只用对称矩阵的向量积沿 CG 路径降低二次模型，并在负曲率、信赖边界或小模型残差处给出不同退出状态。求足够下降的近似步。它不一定取得本页的全局子问题最小值。外层信赖域法公理库信赖域法的接受与半径更新Trust-region method用实际下降与预测下降的比值接受或拒绝模型步，并调整信赖半径，使局部二次模型服务于真实目标下降。还要检验真实函数下降，二次子问题的全局解也不等于原非线性函数的全局解。