# 置信域方法

## 思想框架

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

{\displaystyle \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.}

${\displaystyle Are{{d}_{k}}=f({{x}_{k}})-f({{x}_{k}}+{{s}_{k}})}$

${\displaystyle Pre{{d}_{k}}={{q}^{(k)}}(0)-{{q}^{(k)}}({{s}_{k}})}$

${\displaystyle {{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}})}}}$,

## 置信域算法

• 步1. 给出初始点x0 ，置信域半径的上界${\displaystyle {\bar {\Delta }}}$${\displaystyle {{\Delta }_{0}}\in (0,{\bar {\Delta }})}$${\displaystyle \varepsilon \geq 0}$${\displaystyle 0<{{\eta }_{1}}\leq {{\eta }_{2}}<1}$${\displaystyle 0<{{\gamma }_{1}}<1<{{\gamma }_{2}}}$${\displaystyle k\ :=0}$
• 步2. 如果${\displaystyle \left\|{{g}_{k}}\right\|\leq \varepsilon }$，停止
• 步3. （近似地）求解置信域方法的模型子问题，得到 sk
• 步4. 计算ƒ(xk+sk) 和 rk。令

{\displaystyle {{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. 校正置信域半径，令

{\displaystyle {\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. 产生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