信赖域法

信赖域法（trust-region method）先在当前点附近建立局部目标模型，只在一个受限邻域内优化这个模型，再用实际下降与预测下降的一致程度决定是否接受步骤及调整邻域。它在子问题中同时选择方向和长度，与先选方向再作线搜索的结构不同。

模型很远处可能失真

取 $f(x)=x^4-3x^2$，在 $x_0=1/2$ 处有 $f=-11/16$、$g=f^{\prime }=-5/2$、$B=f^{″}=-3$。二次模型是 $$m(p)=-\frac{11}{16}-\frac{5}{2}p-\frac{3}{2}{p}^2.$$ 因为二次系数为负，无约束模型没有下界，但原四次函数有下界。限制 $|p|\le \Delta$ 后，连续模型在紧区间内必有最小点；这里比较两个端点，选正端 $p=\Delta$。

大步长处模型向下、原目标向上，局部模型不能在远处直接使用。

若先取 $\Delta =2$，候选点为 $2.5$，模型预测下降十一，实际下降却是 $-21$，即原目标大幅上升。将半径缩为 $0.5$ 后，候选点为一，预测下降为 $13/8$，实际下降为 $21/16$，二者的比值为 $21/26\approx 0.807692$。同一个局部模型，在不同范围内的可信程度明显不同。

一般子问题及充分最优性条件

对光滑 $f:{ℝ}^n\to ℝ$，令 $g=\mathrm{\nabla }f(x)$，取实对称矩阵 $B$ 近似 Hessian。欧氏信赖域子问题为 $$\underset{\Vert p\Vert \le \Delta }{min}m(p)=f(x)+g^{𝖳}p+\frac{1}{2}{p}^{𝖳}Bp,\Delta >0.$$ 即使 $B$ 不定，闭球的紧性也保证解存在。一个能直接验证的充分最优性证书是存在 $\lambda \ge 0$，使 $$(B+\lambda I)p^{\ast }=-g,B+\lambda I⪰0,\Vert p^{\ast }\Vert \le \Delta ,\lambda (\Vert p^{\ast }\Vert -\Delta )=0.$$ 证明时对任意可行 $p$，令 $d=p-p^{\ast }$。展开二次型并代入驻点式，得到 $$m(p)-m(p^{\ast })=\frac{1}{2}{d}^{𝖳}(B+\lambda I)d+\frac{\lambda }{2}(\Vert p^{\ast }{\Vert }^2-\Vert p{\Vert }^2).$$ 第一项非负。若 $\lambda =0$，第二项为零；若 $\lambda >0$，互补条件给出 $\Vert p^{\ast }\Vert =\Delta \ge \Vert p\Vert$，第二项也非负。因此该点全局最小化局部模型。这并未证明它全局最小化原函数。

接受比值与半径调整

对预测下降 $\mathrm{pred}=m(0)-m(p)>0$ 的步骤，定义 $$\rho =\frac{f(x)-f(x+p)}{m(0)-m(p)}.$$ 分子必须重新评价原目标，不能用模型代替。比值负表示原目标上升；很小的正比值表示模型过于乐观；接近一表示两者吻合。常见实现将很差的比值对应到缩小半径，只在比值超过接受阈值时移动；比值较好且步骤达到边界时才考虑放大半径。阈值是算法参数，不是唯一固定常数。

点值分别对应半径 1/2 与二；连接线只帮助比较两个已评价步骤。

下面演示使用接受阈值 $0.1$：$\rho <0.25$ 时将半径乘 $1/4$，$\rho >0.75$ 且步在边界时将半径加倍，上限为二。这使主例先拒绝半径二的步骤，再在半径二分之一时接受；其他参数可产生不同轨迹。

变式、停止条件与实现

若目标改为 $f(x)=(x-2{)}^2$，二次模型完全等于原函数，任何非零预测下降的步骤都有 $\rho =1$。从零、半径一出发，先到一，再取牛顿步到二；这给出了可手算的模型精确变式。

在非凸主例的 $x=0$ 处，梯度恰为零但 Hessian 为负，零点是局部极大点。只查梯度便可能提前停住；需要检查负曲率或声明只求一阶驻点。半径很小也可能来自反复拒绝和模型失真，本身不证明最优。标准收敛结论需要模型精度、足够模型下降和半径更新规则等条件，不适用于任意取步。

下例只用标准库，针对一维四次函数，在端点、零点及内部凸驻点中精确选择二次子问题最小点；返回每次试步及接受结果，不改写输入。每步成本为常数，历史空间 $O(K)$。高维子问题可用截断共轭梯度等近似求解，计算成本由矩阵结构和求解精度决定。

Python 3

def trust_quartic(initial=0.5, radius=2.0, count=5):
    if radius <= 0 or count < 0:
        raise ValueError("positive radius required")
    x,delta,trace = float(initial),float(radius),[]
    f = lambda z:z**4-3*z*z
    for k in range(count):
        g,B = 4*x**3-6*x,12*x*x-6
        candidates = [-delta,0.0,delta]
        if B > 0 and abs(g/B) <= delta:
            candidates.append(-g/B)
        p = min(candidates,key=lambda p:g*p+B*p*p/2)
        predicted = -g*p-B*p*p/2
        if predicted <= 1e-15:
            break
        ratio = (f(x)-f(x+p))/predicted
        accepted = ratio > 0.1
        trace.append((k,x,delta,p,predicted,ratio,accepted))
        if ratio < 0.25:
            delta *= 0.25
        elif ratio > 0.75 and abs(abs(p)-delta) < 1e-12:
            delta = min(2*delta,2.0)
        if accepted:
            x += p
    return trace

for row in trust_quartic():
    print(row)
assert not trust_quartic()[0][-1]
assert abs(trust_quartic()[1][-2]-21/26) < 1e-12