置信域方法

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

算法发展

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

思想框架

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

${{\Omega }_{k}}=\{x\in {{R}^{n}}|\left\|x-{{x}_{k}}\right\|\leq {{\Delta }_{k}}\},$

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

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

$\left\{{\begin{aligned}&\min \ {{q}^{(k)}}(s)=f({{x}_{k}})+g_{k}^{T}s+{\frac {1}{2}}{{s}^{T}}{{B}_{k}}s\\&s.t.\quad \left\|s\right\|\leq {{\Delta }_{k}}\\\end{aligned}}\right.$

其中，$s=x-x_{k}$，${{g}_{k}}=\nabla f({{x}_{k}})$，$B_{k}$是一个对称矩阵，它是黑塞矩阵${{\nabla }^{2}}f({{x}_{k}})$或其近似，${{\Delta }_{k}}>0$为置信域半径，$\left\|\ \centerdot \ \right\|$为某一范数，通常我们采用$l_{2}$范数。

选择${{\Delta }_{k}}$的方法：根据模型函数${{q}^{(k)}}(s)$对目标函数ƒ(x)的拟合程度来调整置信域半径${{\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₀ ，置信域半径的上界${\bar {\Delta }}$，${{\Delta }_{0}}\in (0,{\bar {\Delta }})$，$\varepsilon \geq 0$，$0<{{\eta }_{1}}\leq {{\eta }_{2}}<1$，$0<{{\gamma }_{1}}<1<{{\gamma }_{2}}$，$k\ :=0$
• 步2. 如果$\left\|{{g}_{k}}\right\|\leq \varepsilon$，停止
• 步3. （近似地）求解置信域方法的模型子问题，得到 s_k
• 步4. 计算ƒ(x_k+s_k) 和 r_k。令

${{x}_{k+1}}=\left\{{\begin{aligned}&{{x}_{k}}+{{s}_{k}},\quad {\text{if }}{{r}_{k}}\geq {{\eta }_{1}}\\&{{x}_{k}},\quad \quad \quad {\text{else}}\\\end{aligned}}\right.$

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

${\begin{aligned}&{{\Delta }_{k+1}}\in (0,{{\gamma }_{1}}{{\Delta }_{k}}],\quad \quad \quad \quad \ \ \ {\text{if }}{{r}_{k}}<{{\eta }_{1}};\\&{{\Delta }_{k+1}}\in [{{\gamma }_{1}}{{\Delta }_{k}},{{\Delta }_{k}}],\quad \quad \quad \quad \ {\text{if }}{{r}_{k}}\in [{{\eta }_{1}},{{\eta }_{2}});\\&{{\Delta }_{k+1}}\in [{{\Delta }_{k}},\min\{{{\gamma }_{2}}{{\Delta }_{k}},{\bar {\Delta }}\}],\ {\text{if }}{{r}_{k}}\geq {{\eta }_{2}}.\\\end{aligned}}$

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

基于信赖域的优化软件

• Powell 无导数优化求解器 (Michael J. D. Powell)
• LANCELOT （页面存档备份，存于互联网档案馆） (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