置信域方法

置信域方法（Trust-region methods）又稱為信賴域方法，它是一種最佳化方法，能夠保證最佳化方法總體收斂。

算法發展

置信域方法的歷史可以追溯到Levenberg(1944)，Marquardt(1963)，Goldfeld，Quandt and Trotter(1966)，但現代置信域方法由 Michael J. D. Powell 提出 (1970)。他明確提出了置信域子問題，接受方向步$s_{k}$的準則，校正置信域半徑$\Delta _{k}$的準則，及收斂性定理。這些措施使置信域方法比線搜索方法具有更大的優越性。

思想框架

考慮${\underset {x\in {{R}^{n}}}{\mathop {\min } }}\,f(x)$，其中ƒ(x)是定義在Rⁿ上的二階連續可微函數。 定義當前點的鄰域${{\Omega }_{k}}$

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

這裡${\Delta }_{k}$稱為置信域半徑。假定在這個鄰域中，二次模型是目標函數ƒ(x)的一個合適的近似，則在這個鄰域（稱為置信域）中極小化二次模型，得到近似極小點$s_{k}$，並取 ，其中$\left\|{{s}_{k}}\right\|\leq {{\Delta }_{k}}$。

置信域方法的模型子問題是

$\left\{{\begin{aligned}&\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\|\leq {{\Delta }_{k}}\\\end{aligned}}\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. 給出初始點x₀ ，置信域半徑的上界${\bar {\Delta }}$，${{\Delta }_{0}}\in (0,{\bar {\Delta }})$，$\varepsilon \geq 0$，$0<{{\eta }_{1}}\leq {{\eta }_{2}}<1$，$0<{{\gamma }_{1}}<1<{{\gamma }_{2}}$，$k\ :=0$
• 步2. 如果$\left\|{{g}_{k}}\right\|\leq \varepsilon$，停止
• 步3. （近似地）求解置信域方法的模型子問題，得到 s_k
• 步4. 計算ƒ(x_k+s_k) 和 r_k。令

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

• 步5. 校正置信域半徑，令

${\begin{aligned}&{{\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}}\geq {{\eta }_{2}}.\\\end{aligned}}$

• 步6. 產生B_k+1，校正q^(k) ，令k:=k+1 ，轉步2。

基於信賴域的優化軟體

• Powell 無導數優化求解器 (Michael J. D. Powell)
• LANCELOT （頁面存檔備份，存於網際網路檔案館） (Andrew Conn, Nick Gould, Philippe Toint)

應用

現今，置信域算法廣泛應用於應用數學、物理、化學、工程學、計算機科學、生物學與醫學等學科。相信在不遠將來，信賴域方法會在更廣泛多樣的領域有著更深遠的發展。

參考文獻

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