最速下降法、牛顿法、共轭梯度法均为线搜索法，其一般策略是给定点 $\boldsymbol{x}^{(k)}$ 后，定义搜索方向 $\boldsymbol{d}^{(k)}$ ，并沿着该方向进行一维搜索。而信赖域法的搜索范围是一个以 $\boldsymbol{x}^{(k)}$ 为中心的球域（信赖域），在此域内优化目标函数的二次逼近式，直到满足精度要求。信赖域法稳定性强，收敛性好，既有牛顿法的快速局部收敛性，又有理想的全局收敛性质，且不要求目标函数的 Hessian 矩阵正定。
一、信赖域法
无约束问题
$$
\min\quad f(\boldsymbol{x}),\quad \boldsymbol{x}\in\mathbb{R}^n
$$
二次逼近式
将 $f(\boldsymbol{x})$ 在 $\boldsymbol{x}^{(k)}$ 处进行 Taylor 展开并取二次近似
$$
f(\boldsymbol{x}) \approx f\left(\boldsymbol{x}^{(k)}\right)+\nabla f\left(\boldsymbol{x}^{(k)}\right)^{\mathrm{T}}\left(\boldsymbol{x}-\boldsymbol{x}^{(k)}\right)+\frac{1}{2}\left(\boldsymbol{x}-\boldsymbol{x}^{(k)}\right)^{\mathrm{T}} {\nabla}^{2} f\left(\boldsymbol{x}^{(k)}\right)\left(\boldsymbol{x}-\boldsymbol{x}^{(k)}\right)
$$
记 $\boldsymbol d=\boldsymbol{x}-\boldsymbol{x}^{(k)}$ ，则得到一个二次模型 $\varphi_{k}(\boldsymbol{d})$ ，并且为了在 $\boldsymbol{x}^{(k)}$ 附近用 $\varphi_{k}(\boldsymbol{d})$ 近似 $f\left(\boldsymbol{x}^{(k)}+\boldsymbol{d}\right)$ ，需要限定 $|\boldsymbol{d}| \leqslant r_{k}$ ，$r_{k}$ 是常数，称为信赖域半径。因此原目标优化问题可以归结为求解一系列子问题：
$$
\begin{aligned}
&\min \quad \varphi_{k}(\boldsymbol{d}) \stackrel{\text { def }}{=} f\left(\boldsymbol{x}^{(k)}\right)+\nabla f\left(\boldsymbol{x}^{(k)}\right)^{\mathrm{T}} \boldsymbol{d}+\frac{1}{2} \boldsymbol{d}^{\mathrm{T}} \nabla^{2} f\left(\boldsymbol{x}^{(k)}\right) \boldsymbol{d} \
&\text { s.t. }|\boldsymbol{d}| \leqslant r_{k}
\end{aligned}
$$
其中，范数未作规定，这里讨论取欧式范数，即 $|\cdot|=|\cdot|_{2}$ ，这样约束条件可写为 $(\boldsymbol d^\mathrm{T}\boldsymbol d)^{\frac{1}{2}}\le{r}_k$ 。
搜索方向
该约束子问题可通过对偶法求解（理解KKT条件和对偶问题）。若 $\boldsymbol{d}^{(k)}$ 是该问题的最优解，则存在乘子 $\hat w\ge 0$ ，使得
$$
\begin{aligned}
&\nabla^{2} f\left(\boldsymbol{x}^{(k)}\right) \boldsymbol{d}^{(k)}+\nabla f\left(\boldsymbol{x}^{(k)}\right)+\frac{\hat{w}}{\left(\boldsymbol d^{(k)\mathrm{T}}\boldsymbol d^{(k)}\right)^{\frac{1}{2}}} \boldsymbol{d}^{(k)}=0 \
&\hat{w}\left(|\boldsymbol{d}^{(k)} |-r_{k}\right)=0 .
\end{aligned}
$$
记作
$$
w=\frac{\hat{w}}{\left(\boldsymbol{d}^{(k) \mathrm T} \boldsymbol{d}^{(k)}\right)^{\frac{1}{2}}}
$$
得到 $\boldsymbol{d}^{(k)}$ 是问题最优解的必要条件（KKT条件）
$$
\left{\begin{array}{l}
\nabla^{2} f\left(\boldsymbol{x}^{(k)}\right) \boldsymbol d^{(k)}+w \boldsymbol d^{(k)}=-\nabla f\left(\boldsymbol{x}^{(k)}\right), \
w\left(\left|\boldsymbol{d}^{(k)}\right|-r_{k}\right)=0, \
w \geqslant 0, \
\left|\boldsymbol{d}^{(k)}\right| \leqslant r_{k} .
\end{array}\right.
$$
假设 $\nabla^{2} f\left(\boldsymbol x^{(k)}\right)+w \bold{I}$ 可逆，则由上式可得到
$$
\left|\boldsymbol{d}^{(k)}\right|=\left|\left(\nabla^{2} f\left(\boldsymbol{x}^{(k)}\right)+w \bold{I}\right)^{-1} \nabla f\left(\boldsymbol{x}^{(k)}\right)\right|
$$
可知二次模型的解 $\boldsymbol{d}^{(k)}$ 与信赖域半径 $r_k$ 有关。
当信赖域半径由小到大逐渐增大时，搜索方向在最速下降方向和牛顿方向间连续变化。
- 若 $r_k$ 充分大，则 $w$ 值可能很小，从而搜索方向接近牛顿方向，即
$$
\boldsymbol d^{(k)} \approx-\nabla^{2} f\left(\boldsymbol x^{(k)}\right)^{-1} \nabla f\left(\boldsymbol x^{(k)}\right)
$$
- 若 $r_k\rightarrow0$，则 $\boldsymbol{d}^{(k)}\rightarrow 0,w\rightarrow\infty$ ，此时搜索方向接近最速下降方向
$$
\boldsymbol{d}^{(k)} \approx-\frac{1}{w} \nabla f\left(\boldsymbol{x}^{(k)}\right)
$$
逼近判决
求出最优解 $\boldsymbol{d}^{(k)}$ 后，点 $\boldsymbol{x}^{(k)}+\boldsymbol{d}^{(k)}$ 是否能作为原问题的近似解还需要根据用 $\varphi_{k}(\boldsymbol{d})$ 逼近 $f(\boldsymbol{x})$ 是否成功来确定。用函数实际下降量与预测下降量之比来进行衡量
$$
\rho_k=\frac{f\left(\boldsymbol{x}^{(k)}\right)-f\left(\boldsymbol{x}^{(k)}+\boldsymbol{d}^{(k)}\right)}{f\left(\boldsymbol{x}^{(k)}\right)-\varphi_{k}\left(\boldsymbol{d}^{(k)}\right)}
$$
若 $\rho_k$ 足够大，则认为逼近成功，取 $\boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}+\boldsymbol{d}^{(k)}$ ；否则后继点仍取 $\boldsymbol{x}^{(k)}$ 。
算法步骤
给定可行点 $\boldsymbol{x}^{(1)}$ ，信赖域半径 $r_1$ ，参数 $0<\mu<\eta<1$ （一般取 $\mu=\frac{1}{4},\eta=\frac{3}{4}$）以及精度要求 $\varepsilon$，置 $k=1$ 。
计算 $f\left(\boldsymbol{x}^{(k)}\right), \nabla f\left(\boldsymbol{x}^{(k)}\right)$ ，若 $\left|\nabla f\left(\boldsymbol{x}^{(k)}\right)\right| \leqslant \varepsilon$ ，则停止计算，得解 $\boldsymbol{x}^{(k)}$ ；否则，计算 $\nabla^{2} f\left(\boldsymbol{x}^{(k)}\right)$ 。
求解子问题
$$
\begin{aligned}
&\min \quad \varphi_{k}(\boldsymbol{d}) \stackrel{\text { def }}{=} f\left(\boldsymbol{x}^{(k)}\right)+\nabla f\left(\boldsymbol{x}^{(k)}\right)^{\mathrm{T}} \boldsymbol{d}+\frac{1}{2} \boldsymbol{d}^{\mathrm{T}} \nabla^{2} f\left(\boldsymbol{x}^{(k)}\right) \boldsymbol{d} \
&\text { s.t. }|\boldsymbol{d}| \leqslant r_{k}
\end{aligned}
$$
得到问题的最优解 $\boldsymbol{d}^{(k)}$ ，并计算
$$
\rho_k=\frac{f\left(\boldsymbol{x}^{(k)}\right)-f\left(\boldsymbol{x}^{(k)}+\boldsymbol{d}^{(k)}\right)}{f\left(\boldsymbol{x}^{(k)}\right)-\varphi_{k}\left(\boldsymbol{d}^{(k)}\right)}
$$若 $\rho_k\le\mu$ ，则令 $\boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}$ ；若 $\rho_k>\mu$ ，则令 $\boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}+\boldsymbol{d}^{(k)}$ 。
修改信赖域半径 $r_k$ 。若 $\rho_k\le\mu$ ，令 $r_{k+1}=\frac{1}{2}r_k$；若 $\mu<\rho_k<\eta$ ，令 $r_{k+1}=r_k$；若 $\rho_k\ge\eta$ ，令 $r_{k+1}=2r_k$ 。
置 $k=k+1$ ，转步骤2。
算法特点
- 不要求目标函数的 Hessian 矩阵正定。
- 既有牛顿法的快速局部收敛性，也有理想的全局收敛性。
- 算法利用二次模型来修正步长，使得目标函数的下降比线搜索方法更有效。
- 搜索步长受 Taylor 展开式有效的信赖域的限制，此方法又称为有限步长法。
参考
- 《最优化理论与算法》陈宝林著。
- 理解KKT条件和对偶问题
