置信域方法

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

算法发展

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

思想框架

考虑 ,其中ƒ(x)是定义在Rn上的二阶连续可微函数。 定义当前点的邻域 

 

这里 称为置信域半径。假定在这个邻域中,二次模型是目标函数ƒ(x)的一个合适的近似,则在这个邻域(称为置信域)中极小化二次模型,得到近似极小点 ,并取 ,其中 


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

 

其中,   是一个对称矩阵,它是黑塞矩阵 或其近似, 为置信域半径, 为某一范数,通常我们采用 范数


选择 的方法:根据模型函数 对目标函数ƒ(x)的拟合程度来调整置信域半径 。 对于置信域方法的模型子问题的解 ,设目标函数的下降量

 

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

 

为预测下降量。 定义比值

 ,

它用来衡量模型函数 与目标函数ƒ 的一致性程度。

置信域算法

  • 步1. 给出初始点x0 ,置信域半径的上界      
  • 步2. 如果 ,停止
  • 步3. (近似地)求解置信域方法的模型子问题,得到 sk
  • 步4. 计算ƒ(xk+sk) 和 rk。令

 

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

 

  • 步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