Trust-Region Methods

Line search에서는 방향과 step을 정해서 이동하면서 minimum인지 아닌지 확인하는 반면에 trust region methods에서는 radius를 정해서 그 안에서 approximated function의 minimum을 찾고 그 minimum으로 이동하여 다시 더 큰 radius의 region을 그리고 그 안에서 minimum을 찾는 행위를 반복한다. 최적값으로 수렴하기 전에는 항상 boundary에서 minimum 값을 갖지만 수렴하게되면 radius를 더 크게 해도 boundary 내의 특정 위치를 minimum 값으로 얻고 계산을 반복해도 minimum 값이 바뀌지 않는다. 이를 정리하면 trust-region methods는 아래와 같은 과정으로 진행되고 3번에서 1번으로 반복된다.

1. 현재 위치에서 approximation model을 만든다.
2. trust-region 내에서 모델을 최소화 한다.
3. 새로운 위치로 이동하고 trust-region의 size를 조절한다.

1번에서 말하는 approximation model이 quadratic form 일때 trust-region을 수학적으로 쓰면 아래와 같은 subproblem을 푸는 것과 같다.

$$\begin{aligned} \underset{s}{\text{minimize}} \quad & \tilde{f}(s) = f_{k} + \nabla f_{k}^{T}s + \frac{1}{2} s^{T} \tilde{H}_{k}s \newline \text{subject to} \quad & ||s||_2 \leq \Delta_k \end{aligned}$$

여기서 $\tilde{H}_k$ 는 approximated Hessian 이고 variable $s$는 $s=-\tilde{H}(k)^{-1} \nabla f_k$이다. $\Delta$ 는 trust region의 크기이며 아래의 matric $r$에 의해서 업데이트된다.

$$r=\frac{\text{actual decrease}}{\text{expected decrease}}=\frac{f(x)-f(x+s)}{\tilde{f}(0)-\tilde{f}(s)}$$

여기서 $r\approx1$이면 우리의 approximated model $\tilde{f}$이 실제와 잘 매칭된다는 것이다. 근데 $r>1$이면 expected 보다 actual decrease가 더 크다는 거니까 trust region이 더 커져도 된다. $r<0$이면 trust resion이 너무 크다는 것! 그래서 아래와 같은 알고리즘으로 움직인다.

1 if r ≤ 0.05:  
2    \Delta^{(k+1)} = \Delta^{(k)}/4 
3    s^{(k)} \quad = 0
4 elif r \geq 0.9 and ||s^{(k)}||=\Delta^{(k)}: #(boundary에서 minimum이 나오면)
5    \Delta^{(k+1)}=\min(2 \Delta, \Delta_{\max}) #(maximum radius보다 작으면 radius를 2배로 키운다.)
6 else
7     $\Delta^{(k+1)}=\Delta^{(k)}$  

Trust-region method의 특징은 아래와 같다.

• Trust-region은 Hessian에 민감하기 때문에 정확한 Hessian을 추정하는 것이 중요하다.
• Trust-region이 line search에 비해서 iteration 수가 적지만 각각의 iteration 계산에 드는 비용이 더 비싸다.
• 대부분의 optimization 문제들이 변수들의 scaling에 민감하긴 하지만, Trust-region은 특히 더 scaling에 민감하다.