置信域方法
置信域方法(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。
基於信賴域的優化軟體
編輯- Powell 無導數優化求解器 (Michael J. D. Powell)
- LANCELOT (頁面存檔備份,存於網際網路檔案館) (Andrew Conn, Nick Gould, Philippe Toint)
應用
編輯現今,置信域算法廣泛應用於應用數學、物理、化學、工程學、計算機科學、生物學與醫學等學科。相信在不遠將來,信賴域方法會在更廣泛多樣的領域有著更深遠的發展。
參考文獻
編輯- 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