最速下降法、牛顿法、共轭梯度法均为线搜索法，其一般策略是给定点 \(\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\) 值可能很小，从而搜索方向接近牛顿方向，即
- 若 \(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条件和对偶问题