置信域方法

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

算法发展

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

思想框架

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

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

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

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

${\displaystyle \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.}$ 

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

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

${\displaystyle Are{{d}_{k}}=f({{x}_{k}})-f({{x}_{k}}+{{s}_{k}})}$ 

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

${\displaystyle Pre{{d}_{k}}={{q}^{(k)}}(0)-{{q}^{(k)}}({{s}_{k}})}$ 

为预测下降量。 定义比值

${\displaystyle {{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}})}}}$ ,

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

置信域算法

• 步1. 给出初始点x₀ ，置信域半径的上界${\displaystyle {\bar {\Delta }}}$ ，${\displaystyle {{\Delta }_{0}}\in (0,{\bar {\Delta }})}$ ，${\displaystyle \varepsilon \geq 0}$ ，${\displaystyle 0<{{\eta }_{1}}\leq {{\eta }_{2}}<1}$ ，${\displaystyle 0<{{\gamma }_{1}}<1<{{\gamma }_{2}}}$ ，${\displaystyle k\ :=0}$ 
• 步2. 如果${\displaystyle \left\|{{g}_{k}}\right\|\leq \varepsilon }$ ，停止
• 步3. （近似地）求解置信域方法的模型子问题，得到 s_k
• 步4. 计算ƒ(x_k+s_k) 和 r_k。令

${\displaystyle {{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. 校正置信域半径，令

${\displaystyle {\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