置信域方法

置信域方法（Trust-region methods）又称为信赖域方法，它是一种最佳化方法，能够保证最佳化方法总体收敛。

算法发展

置信域方法的历史可以追溯到Levenberg(1944)，Marquardt(1963)，Goldfeld，Quandt and Trotter(1966)，但现代置信域方法由 Michael J. D. Powell 提出 (1970)。他明确提出了置信域子问题，接受方向步$s_k$的准则，校正置信域半径${\mathrm{\Delta }}_k$的准则，及收敛性定理。这些措施使置信域方法比线搜索方法具有更大的优越性。

思想框架

考虑$\underset{x\in R^n}{\min }f(x)$，其中ƒ(x)是定义在Rⁿ上的二阶连续可微函数。 定义当前点的邻域${\mathrm{\Omega }}_k$

${\mathrm{\Omega }}_k=\{x\in R^n|\Vert x-x_k\Vert \le {\mathrm{\Delta }}_k\},$

这里${\mathrm{\Delta }}_k$称为置信域半径。假定在这个邻域中，二次模型是目标函数ƒ(x)的一个合适的近似，则在这个邻域（称为置信域）中极小化二次模型，得到近似极小点$s_k$，并取 ，其中$\Vert s_k\Vert \le {\mathrm{\Delta }}_k$。

置信域方法的模型子问题是

$\{\begin{array}{cc}& \min q^{(k)}(s)=f(x_k)+g_k^{T}s+\frac{1}{2}{s}^T{B}_{k}s\\ & s.t.\Vert s\Vert \le {\mathrm{\Delta }}_k\\ \end{array}$

其中，$s=x-x_k$，$g_k=\mathrm{\nabla }f(x_k)$，$B_k$是一个对称矩阵，它是黑塞矩阵${\mathrm{\nabla }}^{2}f(x_k)$或其近似，${\mathrm{\Delta }}_k>0$为置信域半径，$\Vert \cdot \Vert$为某一范数，通常我们采用$l_2$范数。

选择${\mathrm{\Delta }}_k$的方法：根据模型函数$q^{(k)}(s)$对目标函数ƒ(x)的拟合程度来调整置信域半径${\mathrm{\Delta }}_k$。 对于置信域方法的模型子问题的解$s_k$，设目标函数的下降量

$Are{d}_k=f(x_k)-f(x_k+s_k)$

为实际下降量，设模型函数的下降量

$Pre{d}_k=q^{(k)}(0)-q^{(k)}(s_k)$

为预测下降量。 定义比值

$r_k=\frac{Are{d}_k}{Pre{d}_k}=\frac{f(x_k)-f(x_k+s_k)}{q^{(k)}(0)-q^{(k)}(s_k)}$,

它用来衡量模型函数$q^{(k)}$与目标函数ƒ 的一致性程度。

置信域算法

• 步1. 给出初始点x₀ ，置信域半径的上界$\overline{\mathrm{\Delta }}$，${\mathrm{\Delta }}_0\in (0,\overline{\mathrm{\Delta }})$，$\epsilon \ge 0$，$0<{\eta }_1\le {\eta }_2<1$，$0<{\gamma }_1<1<{\gamma }_2$，$k:=0$
• 步2. 如果$\Vert g_k\Vert \le \epsilon$，停止
• 步3. （近似地）求解置信域方法的模型子问题，得到 s_k
• 步4. 计算ƒ(x_k+s_k) 和 r_k。令

$x_{k+1}=\{\begin{array}{cc}& x_k+s_k,\text{if }{r}_k\ge {\eta }_1\\ & x_k,\text{else}\\ \end{array}$

• 步5. 校正置信域半径，令

$\begin{array}{cc}& {\mathrm{\Delta }}_{k+1}\in (0,{\gamma }_1{\mathrm{\Delta }}_k],\text{if }{r}_k<{\eta }_1;\\ & {\mathrm{\Delta }}_{k+1}\in [{\gamma }_1{\mathrm{\Delta }}_k,{\mathrm{\Delta }}_k],\text{if }{r}_k\in [{\eta }_1,{\eta }_2);\\ & {\mathrm{\Delta }}_{k+1}\in [{\mathrm{\Delta }}_k,\min \{{\gamma }_2{\mathrm{\Delta }}_k,\overline{\mathrm{\Delta }}\}],\text{if }{r}_k\ge {\eta }_2.\\ \end{array}$

• 步6. 产生B_k+1，校正q^(k) ，令k:=k+1 ，转步2。

基于信赖域的优化软件

• Powell 无导数优化求解器 (Michael J. D. Powell)
• LANCELOT Template:Wayback (Andrew Conn, Nick Gould, Philippe Toint)

应用

现今，置信域算法广泛应用于应用数学、物理、化学、工程学、计算机科学、生物学与医学等学科。相信在不远将来，信赖域方法会在更广泛多样的领域有着更深远的发展。

参考文献

1. Andrew R. Conn,Nicholas I. M. Gould,Philippe L. Toint."Trust-region methods".Philadelphia, Pa. : SIAM [u.a.], 2000. ISBN 978-0-898714-60-9