라인서치

편집 역사 토론
수치해석 마지막 수정: 2026-07-20 04:16:03

1. 개요[편집]

라인서치
Line search
분야수치 최적화
결정 대상탐색 방향 위의 보폭(step length)
대표 조건Armijo · Wolfe · Goldstein
대안 전략신뢰 영역 방법
궁합경사하강법, 준-뉴턴법

라인서치(line search)는 반복 최적화에서 탐색 방향 pk\mathbf{p}_k 가 정해진 뒤, 그 방향으로 얼마나 멀리 갈지(보폭, step length) αk>0\alpha_k > 0 를 결정하는 절차다. 대부분의 하강법은 다음 형태의 반복을 돈다.

xk+1=xk+αk pk\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \, \mathbf{p}_k

여기서 방향 pk\mathbf{p}_k 는 경사하강법이면 −∇f-\nabla f, 뉴턴-랩슨법이면 뉴턴 스텝, 준-뉴턴법이면 근사 헤세 기반 방향이다. 라인서치는 이 방향을 존중하되 보폭만 골라 목적함수를 실제로 충분히 줄이는 역할을 한다. 최적화 알고리즘이 “어디로 갈지”와 “얼마나 갈지”를 분리하는 두 축 중 후자를 담당하는 셈.1

방향이 아무리 좋아도 보폭이 너무 크면 골짜기를 뛰어넘어 발산하고, 너무 작으면 거북이걸음으로 수렴을 못 본다. 라인서치는 이 사이에서 “적당히 좋은” 보폭을 싸게 찾아내는 실용적 타협의 기술이다.

2. 정확 라인서치 vs 비정확 라인서치[편집]

방향 pk\mathbf{p}_k 위에서 목적함수를 1변수 함수로 보면 ϕ(α)=f(xk+αpk)\phi(\alpha) = f(\mathbf{x}_k + \alpha \mathbf{p}_k) 가 된다.

정확 라인서치(exact line search)는 ϕ(α)\phi(\alpha) 를 완전히 최소화하는 α∗=arg⁡min⁡αϕ(α)\alpha^\ast = \arg\min_\alpha \phi(\alpha) 를 찾는다. 이론적으로 깔끔하지만, 매 반복마다 1차원 최소화를 정밀하게 푸는 비용이 배보다 배꼽이 크다. 게다가 방향 자체가 근사인 마당에 보폭만 완벽하게 구해봐야 실익이 적다.

그래서 실무의 국룰은 비정확 라인서치(inexact line search)다. ϕ(α)\phi(\alpha) 를 최소화하는 대신 “충분히 좋으면 통과”시키는 몇 가지 조건만 만족하는 α\alpha 를 값싸게 찾는다. 이때 만족시켜야 할 두 가지 요구는 (1) 함수값이 충분히 줄어들 것, (2) 보폭이 터무니없이 작지는 않을 것이다. 이 둘을 수식으로 못박은 것이 아래의 조건들이다.

3. Armijo · Wolfe · Goldstein 조건[편집]

ϕ′(0)=∇f(xk)⊤pk<0\phi'(0) = \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k < 0 (하강 방향)이라 가정하자.

Armijo 조건(충분한 감소, sufficient decrease). 상수 c1∈(0,1)c_1 \in (0,1) 에 대해

f(xk+αpk)≤f(xk)+c1 α ∇f(xk)⊤pkf(\mathbf{x}_k + \alpha \mathbf{p}_k) \le f(\mathbf{x}_k) + c_1 \, \alpha \, \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k

즉 접선이 예측한 감소량의 최소 c1c_1 배는 실제로 줄어야 한다. 보통 c1=10−4c_1 = 10^{-4} 라는 아주 느슨한 값을 쓴다.

곡률 조건(curvature condition). Armijo만으로는 보폭이 너무 작아도 통과되므로, c2∈(c1,1)c_2 \in (c_1, 1) 에 대해

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

를 추가로 요구한다. 방향미분이 충분히 완만해질 때까지 가라는 뜻. Armijo + 곡률 조건을 묶은 것이 그 유명한 Wolfe 조건이다. 부등호를 절댓값으로 강화하면 강 Wolfe(strong Wolfe) 조건이 되며, 준-뉴턴법의 BFGS 갱신이 양정치를 유지하려면 이 강 Wolfe가 필요하다.2

Goldstein 조건은 곡률 조건 대신 감소량을 위아래로 동시에 끼워(두 부등식) 보폭이 지나치게 작지 않도록 막는 대안이다. 구현이 간단해 예전엔 많이 썼지만, 하한 부등식이 최소점을 배제해버릴 수 있다는 흠 때문에 지금은 Wolfe가 더 대세다.

4. 백트래킹 알고리즘[편집]

가장 널리 쓰이는 비정확 라인서치 구현은 백트래킹(backtracking)이다. 절차가 눈물 나게 단순하다.

  1. 넉넉한 초기 보폭 α←1\alpha \leftarrow 1 에서 시작한다(뉴턴/준-뉴턴 방향이면 1이 국룰).
  2. Armijo 조건을 만족하면 그 α\alpha 를 채택하고 종료.
  3. 아니면 α←ρ α\alpha \leftarrow \rho\,\alpha (ρ∈(0,1)\rho \in (0,1), 보통 0.5)로 줄이고 2로 돌아간다.

큰 보폭에서 시작해 조건을 만족할 때까지 뒤로 물러나며 줄이기 때문에 “back-tracking”. 곡률 조건을 안 보고 Armijo만 검사하는데도, 시작을 크게 잡고 줄여오는 구조 덕분에 보폭이 너무 작아지는 문제가 자연히 완화된다. 함수 평가만 필요하고 기울기 재평가가 없어 싸다는 것도 큰 장점.

5. 신뢰 영역과의 비교, 그리고 실무[편집]

라인서치와 신뢰 영역 방법은 반복 최적화를 안정화하는 양대 철학이다. 라인서치는 방향을 먼저 정하고 보폭을 조절하고, 신뢰 영역은 믿을 만한 반경을 먼저 정하고 그 안에서 방향·크기를 동시에 정한다. 헤세가 부정치일 때 라인서치는 방향이 하강이 아니면 곤란해지지만, 신뢰 영역은 그런 경우도 자연스럽게 다룬다. 반대로 라인서치는 구현이 간단하고 방향이 잘 잡히는 문제에서 값싸게 잘 돈다.

  • 경사하강법의 학습률(learning rate)은 사실상 고정 보폭이다. 라인서치는 이 학습률을 매 스텝 적응적으로 고르는 것과 같다.3
  • 가우스-뉴턴법이나 레벤버그-마쿼트 방법의 날 스텝이 목적함수를 늘릴 때, 라인서치를 얹어 전역 수렴성을 확보한다.
  • 대규모 문제에서 함수·헤세 행렬 평가가 비싸면, 평가 횟수를 줄이는 백트래킹형이 선호된다.

6. 관련 문서[편집]

7. Footnotes[편집]

  1. “방향은 예술, 보폭은 공학”이라는 말이 있다. 좋은 방향을 찾는 건 기하학적 통찰이 필요하지만, 보폭을 고르는 건 몇 개의 부등식만 만족시키면 되는 기계적 작업이라는 자조 섞인 표현. ↩

  2. BFGS의 헤세 근사가 양정치를 유지하려면 sk⊤yk>0\mathbf{s}_k^\top \mathbf{y}_k > 0(곡률 조건)이 필요한데, 강 Wolfe 라인서치가 이걸 보장해준다. Wolfe를 대충 구현하면 준-뉴턴법이 슬금슬금 발산하는 참사가 벌어진다. ↩

  3. 그럼에도 딥러닝에서 라인서치를 잘 안 쓰는 건, 미니배치마다 목적함수가 요동쳐서 ϕ(α)\phi(\alpha) 자체가 노이즈 범벅이라 라인서치의 전제가 깨지기 때문이다. 그래서 Adam 같은 적응형 옵티마이저가 그 자리를 대신한다. ↩