7.123 신뢰 영역법

1. 기본 원리

신뢰 영역법(trust-region method)은 현재 점 $\mathbf{x}_k$ 주위에서 목적 함수의 모델(통상 2차 모델)이 신뢰할 수 있는 영역을 명시적으로 제한하고, 그 영역 내에서 모델을 최소화하여 다음 반복점을 결정하는 최적화 방법이다. 직선 탐색법이 먼저 방향을 결정하고 스텝 크기를 선택하는 반면, 신뢰 영역법은 방향과 크기를 동시에 결정한다.

2. 신뢰 영역 하위 문제

각 반복에서 다음의 제약된 이차 최소화 문제를 풀어야 한다.

$\min_{\mathbf{d}} \quad m_k(\mathbf{d}) = f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^T\mathbf{d} + \frac{1}{2}\mathbf{d}^T\mathbf{B}_k\mathbf{d}$

$\text{s.t.} \quad \lVert \mathbf{d} \rVert \leq \Delta_k$

여기서 $\mathbf{B}_k$ 는 헤시안 또는 그 근사, $\Delta_k > 0$ 은 신뢰 영역의 반지름이다. 이 하위 문제의 해 $\mathbf{d}_k^*$ 는 코시 점(Cauchy point)과 뉴턴 점 사이에 놓이며, 신뢰 영역의 경계에 위치할 수 있다.

3. 실제 감소와 예측 감소

실제 감소(actual reduction)와 예측 감소(predicted reduction)의 비율이 갱신의 수용 여부와 신뢰 영역의 크기 조절에 사용된다.

$\rho_k = \frac{f(\mathbf{x}_k) - f(\mathbf{x}_k + \mathbf{d}_k)}{m_k(\mathbf{0}) - m_k(\mathbf{d}_k)}$

$\rho_k \approx 1$ : 모델이 정확하므로 $\Delta_k$ 를 증가시킨다.
$\rho_k > 0$ 충분히 큼: 스텝을 수용하고 $\Delta_k$ 를 유지하거나 증가시킨다.
$\rho_k$ 작음 또는 음수: 모델이 부정확하므로 스텝을 기각하고 $\Delta_k$ 를 축소한다.

4. 알고리즘

초기점 $\mathbf{x}_0$ , 초기 반지름 $\Delta_0$ , 매개변수 $0 < \eta_1 < \eta_2 < 1$ , $0 < \gamma_1 < 1 < \gamma_2$
$k = 0, 1, 2, \ldots$ 에 대해:
$\quad$ 신뢰 영역 하위 문제를 풀어 $\mathbf{d}_k$ 를 구한다.
$\quad$ $\rho_k$ 를 계산한다.
$\quad$ if $\rho_k \geq \eta_1$ : $\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{d}_k$ (수용)
$\quad$ else: $\mathbf{x}_{k+1} = \mathbf{x}_k$ (기각)
$\quad$ 반지름 갱신:

$\rho_k < \eta_1$ : $\Delta_{k+1} = \gamma_1 \Delta_k$ (축소)
$\eta_1 \leq \rho_k < \eta_2$ : $\Delta_{k+1} = \Delta_k$ (유지)
$\rho_k \geq \eta_2$ and $\lVert \mathbf{d}_k \rVert = \Delta_k$ : $\Delta_{k+1} = \gamma_2 \Delta_k$ (확대)

통상적 매개변수: $\eta_1 = 0.1$ , $\eta_2 = 0.75$ , $\gamma_1 = 0.25$ , $\gamma_2 = 2$ .

5. 하위 문제의 해법

5.1 정확 해: 모레-소렌센 방법

신뢰 영역 하위 문제의 전역 최적해는 다음의 조건을 만족하는 $(\mathbf{d}^*, \mu^*)$ 이다.

$(\mathbf{B}_k + \mu^*\mathbf{I})\mathbf{d}^* = -\nabla f(\mathbf{x}_k)$

$\mu^* \geq 0, \quad \mu^*(\lVert \mathbf{d}^* \rVert - \Delta_k) = 0$

$\mathbf{B}_k + \mu^*\mathbf{I} \succeq 0$

$\lVert \mathbf{d}^* \rVert < \Delta_k$ 이면 $\mu^* = 0$ 이고 비제약 뉴턴 스텝이 된다. $\lVert \mathbf{d}^* \rVert = \Delta_k$ 이면 $\mu^* > 0$ 이며, 이는 대각 정규화된 뉴턴 방정식을 풀어야 한다. 모레-소렌센(Moré-Sorensen) 알고리즘은 $\mu$ 에 대한 세속 방정식(secular equation) $1/\lVert \mathbf{d}(\mu) \rVert = 1/\Delta_k$ 를 뉴턴 반복으로 풀어 정밀한 해를 산출한다.

5.2 근사 해: 코시 점과 도그레그

코시 점(Cauchy point): 최급경사 방향 $-\nabla f(\mathbf{x}_k)$ 를 따라 신뢰 영역 내에서 모델을 최소화하는 점이다. 계산 비용이 $O(n)$ 이며, 전역 수렴을 보장하기 위한 최소한의 조건을 만족한다.

도그레그 방법(Dogleg method): 코시 점과 뉴턴 점을 잇는 절선 경로를 따라 신뢰 영역 경계와의 교점을 구한다. $\mathbf{B}_k \succ 0$ 일 때 적용 가능하며, 정밀 해에 비해 계산이 단순하면서도 양호한 성능을 제공한다.

슈타이하우그-토인트 방법(Steihaug-Toint method): 켤레 그래디언트법으로 하위 문제를 근사적으로 풀며, 음의 곡률이 감지되거나 신뢰 영역 경계에 도달하면 즉시 종료한다. 대규모 문제에서 헤시안을 명시적으로 형성할 필요 없이 헤시안-벡터 곱만으로 해를 구할 수 있어 효율적이다.

6. 직선 탐색법과의 비교

특성	신뢰 영역법	직선 탐색법
결정 순서	방향과 크기 동시 결정	방향 결정 후 크기 결정
비양정치 헤시안	자연스럽게 처리	헤시안 수정 필요
수렴 보장	코시 감소 조건으로 전역 수렴	울프 조건으로 전역 수렴
구현 복잡도	하위 문제 해법 필요	상대적으로 단순

7. 수렴 이론

적절한 조건(코시 감소 조건)하에서 신뢰 영역법은 다음의 전역 수렴을 보장한다.

$\liminf_{k \to \infty} \lVert \nabla f(\mathbf{x}_k) \rVert = 0$

정확 헤시안 $\mathbf{B}_k = \nabla^2 f(\mathbf{x}_k)$ 를 사용하고 최적해 근방에서 신뢰 영역이 활성이지 않으면( $\lVert \mathbf{d}_k \rVert < \Delta_k$ ), 이차 수렴이 달성된다.

8. 로봇 공학에서의 응용

신뢰 영역법은 비선형 최소 제곱 문제에서 레벤버그-마쿼트 알고리즘의 이론적 기반을 형성한다. 로봇 캘리브레이션, SLAM 백엔드 최적화, 번들 조정 등의 문제에서 신뢰 영역 기반 비선형 최소 제곱 해법이 핵심적으로 사용된다.

9. 참고 문헌

Conn, A. R., Gould, N. I. M., & Toint, P. L. (2000). Trust-Region Methods. SIAM.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Moré, J. J., & Sorensen, D. C. (1983). “Computing a Trust Region Step.” SIAM Journal on Scientific and Statistical Computing, 4(3), 553–572.

version: 1.0