울프 조건

편집 역사 토론
수치해석 최적설계 마지막 수정: 2026-07-23 04:09:47

1. 개요[편집]

울프 조건(Wolfe conditions)은 반복 최적화의 라인서치에서 한 스텝의 이동 거리 α\alpha(step length)를 받아들일지 판정하는 두 개의 부등식이다. 하강 방향 d\mathbf{d}가 정해진 뒤 “그 방향으로 얼마나 갈까”를 정할 때, 너무 조금 가도(비효율) 너무 많이 가도(발산·진동) 곤란한데, 울프 조건은 “충분히 줄어들면서도 너무 소심하지 않은” α\alpha의 구간을 정의한다. 경사하강법부터 준-뉴턴법(BFGS/L-BFGS)까지 거의 모든 실전 최적화기가 내부에서 이 조건을 쓴다.

두 조건은 각각 충분 감소(Armijo) 조건과 곡률(curvature) 조건이다. 앞의 것은 함수값이 실제로 충분히 줄었는지를, 뒤의 것은 스텝이 너무 짧아 아직 더 갈 수 있는 상태로 멈추지 않았는지를 본다. 둘이 짝을 이뤄야 라인서치가 이론적으로 수렴을 보장받는다.

스텝 길이 α에 대한 1차원 단면 φ(α)=f(x+αp)를 직접 계산해 그린다. 파란 직선이 충분 감소 기준선 φ(0)+c₁αφ′(0)이고, 아래 세 색띠는 차례로 아르미조를 만족하는 α, 곡률 조건을 만족하는 α(진한 색이 강 울프, 옅은 색이 약 울프), 둘의 교집합인 울프 구간이다. c₁을 키우면 기준선이 가팔라져 수용 구간이 잘려 나가고, c₂를 줄이면 곡률 띠가 단면의 최소점 주위로 조여든다. 마커는 백트래킹 α ← 0.5α가 첫 통과점을 찾는 과정이며, 채택되면 실제로 그만큼 전진해 다음 단면을 새로 계산한다.

2. 충분 감소(Armijo) 조건[편집]

현재 점 x\mathbf{x}, 하강 방향 d\mathbf{d}(즉 ∇f(x)⊤d<0\nabla f(\mathbf{x})^\top \mathbf{d} < 0)에서 스텝 α\alpha가 만족해야 할 첫 조건:

f(x+αd)≤f(x)+c1 α ∇f(x)⊤df(\mathbf{x} + \alpha \mathbf{d}) \le f(\mathbf{x}) + c_1\, \alpha\, \nabla f(\mathbf{x})^\top \mathbf{d}

우변은 현재 점에서 그은 접선을 c1c_1만큼 완만하게 눕힌 기준선이다. 함수값이 이 기준선 아래로 내려와야 “충분히 줄었다”고 인정한다. 상수 c1c_1은 보통 아주 작게 10−410^{-4}로 둔다. c1c_1이 크면 기준이 빡빡해 스텝을 잡기 어렵고, 작으면 거의 아무 감소나 통과시킨다. 문제는 아르미조 조건만으로는 α→0\alpha \to 0인 아주 작은 스텝도 항상 통과한다는 것 — 조금만 움직이면 접선 근사가 정확해져 부등식이 성립하기 때문이다. 그래서 “감소는 했지만 진도가 안 나가는” 상황을 막을 두 번째 조건이 필요하다.

3. 곡률 조건[편집]

두 번째 조건은 이동 후 점에서의 방향 미분이 충분히 완만해졌는지를 본다(약한 울프, weak Wolfe):

∇f(x+αd)⊤d≥c2 ∇f(x)⊤d\nabla f(\mathbf{x} + \alpha \mathbf{d})^\top \mathbf{d} \ge c_2\, \nabla f(\mathbf{x})^\top \mathbf{d}

시작점의 방향 미분은 음수이고, 잘 내려가면 그 값이 0에 가까워지거나 부호가 바뀐다. 곡률 조건은 “아직 방향 미분이 시작값의 c2c_2배보다 가파른 상태(=더 내려갈 여지가 뻔한 상태)로 멈추지 마라”는 뜻이다. 이게 스텝이 너무 짧아지는 것을 막는다. c2c_2는 방법에 따라 다른데, 준-뉴턴법에서는 c2=0.9c_2 = 0.9(느슨하게, 스텝을 크게), 켤레기울기(CG)에서는 c2=0.1c_2 = 0.1(빡빡하게)로 쓴다. 항상 0<c1<c2<10 < c_1 < c_2 < 1을 지킨다.

강한 울프(strong Wolfe) 조건은 절댓값으로 양쪽을 조인다:

∣∇f(x+αd)⊤d∣≤c2∣∇f(x)⊤d∣\left| \nabla f(\mathbf{x} + \alpha \mathbf{d})^\top \mathbf{d} \right| \le c_2 \left| \nabla f(\mathbf{x})^\top \mathbf{d} \right|

약한 울프는 방향 미분이 너무 큰 양수(반대편으로 훌쩍 넘어간 상태)여도 통과시킬 수 있지만, 강한 울프는 그것마저 막아 최소 근방에 더 촘촘히 붙게 한다. BFGS 계열에서 표준으로 쓰인다.

4. 왜 둘 다 필요한가[편집]

한쪽만으로는 반드시 구멍이 난다.

  • 아르미조만: 앞서 봤듯 무한히 작은 스텝도 통과한다. 매 반복이 찔끔찔끔 움직여 사실상 수렴하지 못한다.
  • 곡률만: 방향 미분만 보므로 함수값이 실제로 줄었다는 보장이 없다. 능선을 넘어 반대편 벽을 타고 올라가도 곡률 조건은 만족할 수 있다.

두 조건을 함께 걸면 α\alpha의 허용 구간이 유한한 폭으로 존재함이 보장되고(연속 미분 가능 & 하한 유계 가정), 이것이 Zoutendijk 조건을 통한 전역 수렴 증명의 핵심 재료가 된다.1

5. 백트래킹 라인서치[편집]

실전에서 가장 흔한 구현은 **백트래킹(backtracking)**이다. 곡률 조건을 명시적으로 검사하지 않고도, 큰 스텝에서 시작해 줄여 나가는 절차 자체가 “너무 작지 않은 첫 통과 스텝”을 고르게 만든다.

  1. 초기 스텝 α←α0\alpha \leftarrow \alpha_0 (보통 1, 뉴턴 계열은 특히 1로 시작).
  2. 아르미조 조건을 검사한다.
  3. 만족하지 않으면 α←ρ α\alpha \leftarrow \rho\,\alpha (보통 ρ=0.5\rho = 0.5, 즉 절반)로 줄이고 2로.
  4. 만족하면 그 α\alpha를 채택.

큰 값에서 감소시키므로 “충분히 크면서 아르미조를 통과하는” 첫 스텝을 잡게 되어, 곡률 조건을 직접 안 봐도 지나치게 작은 스텝을 자연히 피한다.2 이 단순함 덕에 백트래킹은 경사하강법, 준-뉴턴법, 레벤버그-마쿼트 방법의 신뢰도 조절 등 도처에서 쓰인다. 다만 스텝 상한을 관리하는 관점이 더 자연스러운 문제에서는 신뢰 영역 방법이 라인서치의 대안이 된다.3

6. BFGS 안에서의 역할[편집]

준-뉴턴법인 BFGS/L-BFGS는 매 반복 근사 헤세 행렬을 갱신하는데, 이 갱신이 양정치(positive definite)를 유지하려면 곡률 조건 s⊤y>0\mathbf{s}^\top \mathbf{y} > 0이 성립해야 한다(s\mathbf{s}는 스텝, y\mathbf{y}는 기울기 변화). 울프의 곡률 조건이 정확히 이 부등식을 보장한다. 즉 울프 조건은 단순한 스텝 채택 규칙을 넘어, 준-뉴턴 근사 행렬의 건전성을 지키는 안전장치 역할까지 한다.

7. 관련 문서[편집]

8. Footnotes[편집]

  1. 이름은 Philip Wolfe(1969, 1971)에서 왔다. 참고로 “약한/강한”은 얼마나 봐주느냐의 문제지 성능 서열이 아니다. 강한 게 무조건 좋은 게 아니라, CG처럼 강한 울프를 요구하는 방법이 따로 있는 것. ↩

  2. 백트래킹의 미학은 “곡률 조건을 검사 안 해도 곡률 조건의 취지를 절차가 대신한다”는 데 있다. 게으름이 이론을 대체하는 몇 안 되는 사례. ↩

  3. 라인서치 대 신뢰 영역은 “방향 먼저 정하고 거리 조절 vs. 거리(반경) 먼저 정하고 방향 결정”의 차이다. 둘 다 결국 “너무 욕심내지 마라”는 같은 잔소리를 다른 순서로 한다. ↩