置信域方法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