4. Trust Region Methods

1. 개요

Trust Region기법은 큰 틀에서 본다면, Line Search와 유사합니다.
다만, Cost Function($f$)를 그대로 사용하는 것이 아니라,
유사한 Model Function($m$)으로 근사하여, 최적화를 수행하며,
동시에 일정한 Bound내에서 Model Function의 최적값을 찾는 다는 점이 차이입니다.
여기서 Bound가 Trust Region이 됩니다.

Bound를 작게하면, 수렴 속도가 당연히 줄어들고, 크게 하면 수렴을 못할 수 있습니다.

1.1. Model Function 정의

먼저, Cost Function을 $f$라고 한다면, 이를 Taylor-series 전개(Expansion)를 통해
2차항까지 적어보면 Model Function($m$)다음과 같습니다.

$m_k(p)=f_k+\nabla f_k^Tp+\dfrac{1}{2}p^TB_kp...............(1)$

2차항까지 정의하면, 이 함수는 Quadric이며, Convex타입이기 때문에
미분을 통해 쉽게 Global Minimum을 구할수 있습니다.
단, $||p||\leq\Delta_k$ 라는 조건이 붙는데 여기서 $\Delta_k$가 Region의 Radius입니다.

일단 Radius를 적용하지 않는다면, 미분을 통해서 정답은 다음과 같습니다.

$p_k^B=-B_k^{-1}\nabla f_k$ 이며, 이때 $p$를 Full Step이라고 부릅니다.

여기까지 하면, Line Search와 정확하게 동일한 형태입니다.

추가적으로, $B_k= \nabla^2 f(x_k)$, 즉 Hesian Matrix로 정의를 하면,
이를 Trust Region Newton Method라고 부릅니다.

1.2. Model Fuction 예제

Line Search예제와 동일하게 아래의 Cost Function을 가정해보겠습니다.
https://velog.io/@mir21c/3.-Line-Search-Methods#11-%EC%98%88%EC%A0%9C

$f(x)=0.01x^4-0.03x^3-0.45x^2+0.3x-1$

그리고 시작점은 10이라고 하고 $B=1$로 가정하겠습니다.

$f(10)=27$

$\nabla f_k=0.04x_k^3-0.09x_k^2-0.9x_k+0.3$
이고
$\nabla f_k(10)=22.3$
이기 때문에

$m = 27 + 22.3p+\dfrac{1}{2}p^2$ 이며 최적값은
$p=-22.3$ 이 됩니다.

이 결과는 Line Search의 경우와도 동일합니다.
사실 이 예제에서는 solution수식이 동일하기 때문에
Line Search와 같은 결과가 나올 수 밖에 없습니다.

그럼 계속해서 Trust Region만의 방식에 대해 설명을 이어가겠습니다.

1.3. Trust Region 기본 동작

Trust Region의 기본은 Region(Radius, $\Delta$)를 매 Iteration마다 갱신하는 것입니다. 이를 위해 먼저, $\rho$를 아래와 같이 정의합니다. 참고로 분자를 actual reduction, 분모를 predicted reduction이라고 합니다.

$\rho_k=\dfrac{f(x_k)-f(x_k+p_k)}{m_k(0)-m_k(p_k)}$

이는 모델($m$)과 실제 함수($f$)의 비율을 의미하며, 이상적으로는 $\rho$가 1이 되면 모델이 실제 함수와 동일하게 근사되었기 때문에 좋은 상태이며, 반대로 $\rho$가 0에 가깝거나 음수가되면, Region을 변경할 필요가 있습니다.

알고리즘 전개 전, 기본 파라미터는 아래와 같이 정의됩니다.
$\overline{\Delta}$은 Step Length 전체에 해당하는 Region값으로 Region의 최대값이 됩니다. $\eta$는 위에서 일종의 Threshold로 $\rho$가 $\eta$보다 클 때, $x$값을 업데이트합니다.

$\overline{\Delta}>0, \Delta_0\in(0,\overline{\Delta}), \eta\in(0, \dfrac{1}{4})$

아래는 pseudo code를 markdown에서 구현하기 어려워 bullet을 사용합니다

• for k=0,1,2,...
  • $p_k$를 (1)번 수식에서 계산
  • $\rho_k$를 계산
  • if $\rho_k<\frac{1}{4}$
    • $\Delta_{k+1}=\frac{1}{4}||p_k||$
  • else
    • if $\rho_k>\frac{3}{4}$ and $||p_k||=\Delta_k$
      • $\Delta_{k+1}=min(2\Delta_k, \overline{\Delta})$
    • else
      • $\Delta_{k+1}=\Delta_{k}$
  • if $\rho_k>\eta$
    • $x_{k+1}=x_k+p_k$
  • else
    • $x_{k+1}=x_k$

위에서 $\rho$가 $\frac{1}{4}$작으면, Region을 줄여주고, 또 너무 큰 값이 되지 않도록 적절히 제어해줍니다. 마지막으로 $\rho$가 $\eta$보다 클 때에만 $x$를 $p$벡터로 업데이트 해줍니다.

여기서 $\rho$의 Reduction을 최대(최적값으로 최대한 이동)로 이동하게 만드는 조건을 Cauchy Point 라고 합니다.

1.4. Trust Region 예제

1.2예제의 수식
$f(x)=0.01x^4-0.03x^3-0.45x^2+0.3x-1$
을 이용해서 전개를 해보겠습니다.

우선 초기값은 다음과 같습니다.
$x_0 =10$,$f(10)=24$, $\nabla f(10)=22.3$, $p_0=-22.3$
이를 토대로 다음 단계를 추정하면 아래와 같습니다.

이 때 $\rho_0=\dfrac{f(10)-f(-12.3)}{m_k(0)-m_k(-22.3)}=\dfrac{27-211.9422}{27-211.9422}=1.0$

이 상태에서는 당연히 굉장히 변동폭이 크기 때문에 제대로 수렴하지 않을 가능성이 있다는 것을 알 수 있습니다.
그렇기에 적절한 Region을 선택할 필요가 있습니다

2. Cauchy Point

2.1. Dogleg Method

2.2. Steihaug's Approach

3. Nearly Exact Solutions

4. Global Convergence