7.83 아르미요 조건과 울프 조건

1. 스텝 크기 수용 기준의 필요성

반복적 최적화 알고리즘에서 갱신 규칙 $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$ 의 스텝 크기 $\alpha_k$ 가 부적절하면 수렴이 보장되지 않는다. 스텝 크기가 지나치게 크면 목적 함수가 오히려 증가하고, 지나치게 작으면 진행이 미미하여 사실상 수렴하지 못한다. 아르미요 조건과 울프 조건은 이러한 문제를 방지하기 위한 수학적으로 엄밀한 스텝 크기 수용 기준이다.

직선 탐색 함수를 $\phi(\alpha) = f(\mathbf{x}_k + \alpha \mathbf{d}_k)$ 로 정의하면, $\phi(0) = f(\mathbf{x}_k)$ 이고 $\phi'(0) = \nabla f(\mathbf{x}_k)^T \mathbf{d}_k < 0$ (하강 방향 가정)이다.

2. 아르미요 조건 (충분 감소 조건)

2.1 정의

아르미요 조건(Armijo condition)은 스텝 크기 $\alpha$ 에 의한 목적 함수의 감소가 1차 근사에 의해 예측되는 감소의 일정 비율 이상이어야 함을 요구한다.

$f(\mathbf{x}_k + \alpha \mathbf{d}_k) \leq f(\mathbf{x}_k) + c_1 \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k$

여기서 $c_1 \in (0, 1)$ 은 충분 감소 매개변수이다. 이 조건은 “충분 감소 조건(sufficient decrease condition)” 또는 “제1 울프 조건“이라고도 불린다.

2.2 기하학적 해석

1차 테일러 전개에 의해 $f(\mathbf{x}_k + \alpha \mathbf{d}_k) \approx f(\mathbf{x}_k) + \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k$ 이다. 아르미요 조건의 우변 $\ell(\alpha) = f(\mathbf{x}_k) + c_1 \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k$ 는 원점에서의 접선의 기울기를 $c_1$ 배 축소한 직선이다. $c_1 < 1$ 이므로 이 직선은 접선보다 완만하며, 아르미요 조건은 $\phi(\alpha)$ 가 이 완만한 직선 아래에 놓여야 함을 의미한다.

$c_1 = 0$ 이면 단순한 감소 조건 $f(\mathbf{x}_{k+1}) \leq f(\mathbf{x}_k)$ 가 되지만, 이것만으로는 수렴이 보장되지 않는다. $c_1 = 1$ 이면 조건이 지나치게 엄격하여 만족시키기 어렵다. 실용적으로 $c_1 = 10^{-4}$ 가 널리 사용되며, 이는 아주 작은 감소만으로도 조건이 만족되므로 상당히 관대한 기준이다.

2.3 아르미요 조건의 한계

아르미요 조건만으로는 스텝 크기가 지나치게 작은 값으로 수용되는 것을 방지할 수 없다. $\alpha \to 0^+$ 일 때 $\phi(\alpha) \to \phi(0)$ 이고 $\ell(\alpha) \to \ell(0) = \phi(0)$ 이므로, 충분히 작은 $\alpha$ 는 항상 아르미요 조건을 만족한다. 이러한 미소 스텝은 알고리즘의 진행을 실질적으로 정체시킨다.

3. 역추적 직선 탐색에서의 아르미요 조건

아르미요 조건은 역추적(backtracking) 절차와 결합하여 사용될 때 효과적이다.

알고리즘: 초기 스텝 크기 $\bar{\alpha} > 0$ , 축소 인자 $\rho \in (0, 1)$ , 충분 감소 매개변수 $c_1 \in (0, 1)$ 이 주어진다.

$\alpha \leftarrow \bar{\alpha}$
while $f(\mathbf{x}_k + \alpha \mathbf{d}_k) > f(\mathbf{x}_k) + c_1 \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k$
$\quad \alpha \leftarrow \rho \alpha$
end while
$\alpha_k \leftarrow \alpha$

이 절차에서 초기 스텝이 크게 시작하고 점진적으로 축소하므로, 아르미요 조건을 만족하면서도 지나치게 작지 않은 스텝 크기를 선택하게 된다. 뉴턴법이나 준뉴턴법에서는 $\bar{\alpha} = 1$ 이 표준 초기값이며, 이는 뉴턴 스텝의 단위 스텝 크기가 최적해 근방에서 수용될 것을 기대하기 때문이다.

4. 울프 조건

4.1 약 울프 조건(Weak Wolfe Conditions)

울프 조건은 아르미요 조건에 곡률 조건(curvature condition)을 추가한 것이다.

충분 감소 조건 (아르미요 조건):

$f(\mathbf{x}_k + \alpha \mathbf{d}_k) \leq f(\mathbf{x}_k) + c_1 \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k$

곡률 조건:

$\nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^T \mathbf{d}_k \geq c_2 \nabla f(\mathbf{x}_k)^T \mathbf{d}_k$

여기서 $0 < c_1 < c_2 < 1$ 이다.

곡률 조건의 좌변 $\phi'(\alpha) = \nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^T \mathbf{d}_k$ 는 직선 탐색 함수의 $\alpha$ 에서의 도함수이다. $\phi'(0) = \nabla f(\mathbf{x}_k)^T \mathbf{d}_k < 0$ 이므로, 곡률 조건은 $\phi'(\alpha_k)$ 가 초기 기울기 $\phi'(0)$ 보다 덜 음수(즉, 기울기의 절대값이 감소)가 되어야 함을 요구한다. 이는 $\alpha_k$ 가 $\phi$ 의 최소점에 충분히 가까움을 의미하며, 스텝 크기가 지나치게 작아지는 것을 방지한다.

4.2 강 울프 조건(Strong Wolfe Conditions)

강 울프 조건은 곡률 조건을 다음과 같이 강화한다.

충분 감소 조건: (동일)

$f(\mathbf{x}_k + \alpha \mathbf{d}_k) \leq f(\mathbf{x}_k) + c_1 \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k$

강 곡률 조건:

$\lvert \nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^T \mathbf{d}_k \rvert \leq c_2 \lvert \nabla f(\mathbf{x}_k)^T \mathbf{d}_k \rvert$

약 울프 조건의 곡률 조건은 $\phi'(\alpha_k)$ 가 양의 큰 값을 가지는 것을 허용하지만(즉, $\phi$ 가 강하게 증가하는 구간도 수용), 강 울프 조건은 $\phi'(\alpha_k)$ 의 절대값이 작을 것을 요구하여 $\phi$ 의 최소점에 더 가까운 스텝을 선택한다.

4.3 매개변수의 선택

$c_1$ 은 충분 감소의 관대함을, $c_2$ 는 곡률 조건의 엄격함을 제어한다.

$c_1 = 10^{-4}$ : 거의 모든 응용에서 표준
$c_2 = 0.9$ : 준뉴턴법(BFGS, L-BFGS)에 적합. 탐색 방향의 품질이 높으므로 관대한 곡률 조건으로 충분하다.
$c_2 = 0.1$ : 켤레 그래디언트법에 적합. 탐색 방향이 이전 그래디언트 정보에 민감하므로 정밀한 직선 탐색이 필요하다.

$c_1 < c_2$ 의 조건은 두 조건이 양립 가능한 구간이 존재하기 위한 필수 요건이다.

5. 울프 조건을 만족하는 스텝 크기의 존재성

다음의 정리가 성립한다. $f: \mathbb{R}^n \to \mathbb{R}$ 이 연속 미분 가능하고, $\mathbf{d}_k$ 가 하강 방향이며, $f$ 가 반직선 $\{\mathbf{x}_k + \alpha \mathbf{d}_k : \alpha > 0\}$ 위에서 하방 유계이면, $0 < c_1 < c_2 < 1$ 인 울프 조건을 만족하는 스텝 크기 $\alpha_k > 0$ 이 반드시 존재한다.

증명 개요: $\phi'(0) < 0$ 이고 $\phi$ 가 하방 유계이면, $\phi$ 는 결국 증가해야 하므로 아르미요 직선 $\ell(\alpha) = \phi(0) + c_1 \alpha \phi'(0)$ 과 $\phi(\alpha)$ 가 교차하는 점 $\alpha'$ 이 존재한다. 평균값 정리에 의해 $(0, \alpha')$ 내에 $\phi'(\hat{\alpha}) = (\phi(\alpha') - \phi(0))/\alpha' = c_1 \phi'(0) + \epsilon$ ( $\epsilon \geq 0$ )을 만족하는 $\hat{\alpha}$ 가 존재한다. $c_2 > c_1$ 이므로 $\phi'(\hat{\alpha}) \geq c_2 \phi'(0)$ 이 성립하여 곡률 조건이 만족된다.

6. 골드스타인 조건

골드스타인(Goldstein) 조건은 울프 조건의 대안으로, 다음의 양면 부등식으로 구성된다.

$f(\mathbf{x}_k) + (1 - c) \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k \leq f(\mathbf{x}_k + \alpha \mathbf{d}_k) \leq f(\mathbf{x}_k) + c \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k$

여기서 $0 < c < 1/2$ 이다. 우측 부등식은 아르미요 조건에 해당하고, 좌측 부등식은 스텝 크기가 지나치게 작아지는 것을 방지한다. 골드스타인 조건은 도함수 정보를 사용하지 않으므로 구현이 단순하지만, 정밀 최소점이 수용 구간 밖에 놓일 수 있다는 단점이 있다. 준뉴턴법에서는 울프 조건이 선호되며, 골드스타인 조건은 주로 뉴턴법과 결합하여 사용된다.

7. 수렴 이론에서의 역할

7.1 조프 조건과의 연계

울프 조건(특히 강 울프 조건)을 만족하는 직선 탐색과 하강 방향의 결합은 조프(Zoutendijk) 조건을 유도한다.

$\sum_{k=0}^{\infty} \cos^2 \theta_k \lVert \nabla f(\mathbf{x}_k) \rVert^2 < \infty$

여기서 $\cos \theta_k = -\frac{\nabla f(\mathbf{x}_k)^T \mathbf{d}_k}{\lVert \nabla f(\mathbf{x}_k) \rVert \lVert \mathbf{d}_k \rVert}$ 는 탐색 방향과 최급경사 방향 사이의 각도의 코사인이다. 이 급수의 수렴은 $\lVert \nabla f(\mathbf{x}_k) \rVert \to 0$ (탐색 방향이 그래디언트와 지나치게 직교하지 않는 경우) 또는 $\cos \theta_k \to 0$ 을 함의하며, 전자가 성립하면 알고리즘이 정류점에 수렴함을 의미한다.

7.2 준뉴턴법에서의 중요성

BFGS 알고리즘의 전역 수렴성은 울프 조건을 만족하는 직선 탐색에 의존한다. 울프 조건은 BFGS 갱신에서 시컨트 조건 $\mathbf{s}_k^T \mathbf{y}_k > 0$ 을 보장하며, 이는 헤시안 근사 행렬의 양정치성 유지에 필수적이다. 여기서 $\mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k$ 이고 $\mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)$ 이다. 곡률 조건에 의해 다음이 보장된다.

$\mathbf{s}_k^T \mathbf{y}_k = \alpha_k (\nabla f(\mathbf{x}_{k+1})^T \mathbf{d}_k - \nabla f(\mathbf{x}_k)^T \mathbf{d}_k) \geq (c_2 - 1) \alpha_k \nabla f(\mathbf{x}_k)^T \mathbf{d}_k > 0$

7.3 켤레 그래디언트법에서의 중요성

켤레 그래디언트법의 수렴을 보장하기 위해서는 강 울프 조건과 함께 $c_2 < 1/2$ 을 선택하는 것이 권장된다. 이는 직선 탐색이 정밀 최소점에 충분히 가깝도록 하여, 켤레 방향의 품질을 유지하는 데 필요하다.

8. 실용적 구현 지침

직선 탐색의 실용적 구현에서는 다음의 지침이 참고된다.

뉴턴법 및 준뉴턴법: 초기 스텝 $\bar{\alpha} = 1$ , 역추적 + 아르미요 조건 또는 울프 조건( $c_2 = 0.9$ ). 단위 스텝이 수용되는 비율이 높을수록 알고리즘 효율이 향상된다.
경사 하강법: 초기 스텝 크기의 선택이 중요하며, 이전 반복의 정보를 활용한 적응적 초기 스텝 설정이 효과적이다.
켤레 그래디언트법: 강 울프 조건( $c_2 = 0.1$ )이 필수적이며, 정밀한 직선 탐색이 알고리즘의 수렴을 좌우한다.

9. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Armijo, L. (1966). “Minimization of Functions Having Lipschitz Continuous First Partial Derivatives.” Pacific Journal of Mathematics, 16(1), 1–3.
Wolfe, P. (1969). “Convergence Conditions for Ascent Methods.” SIAM Review, 11(2), 226–235.
Wolfe, P. (1971). “Convergence Conditions for Ascent Methods. II: Some Corrections.” SIAM Review, 13(2), 185–188.
Moré, J. J., & Thuente, D. J. (1994). “Line Search Algorithms with Guaranteed Sufficient Decrease.” ACM Transactions on Mathematical Software, 20(3), 286–307.

version: 1.0