跳至內容

置信域方法

維基百科,自由的百科全書

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