置信域方法

维基百科,自由的百科全书
跳转至: 导航搜索

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

算法发展[编辑]

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

思想框架[编辑]

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

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

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


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

\left\{ \begin{align}
  & \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\|\le {{\Delta }_{k}} \\ 
\end{align} \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. 给出初始点x0 ,置信域半径的上界\bar{\Delta }{{\Delta }_{0}}\in (0,\bar{\Delta })\varepsilon \ge 00<{{\eta }_{1}}\le {{\eta }_{2}}<10<{{\gamma }_{1}}<1<{{\gamma }_{2}}k\ :=0
  • 步2. 如果\left\| {{g}_{k}} \right\|\le \varepsilon ,停止
  • 步3. (近似地)求解置信域方法的模型子问题,得到 sk
  • 步4. 计算ƒ(xk+sk) 和 rk。令

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

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

\begin{align}
  & {{\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}}\ge {{\eta }_{2}}. \\ 
\end{align}

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

应用[编辑]

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

参考文献[编辑]

  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