황금분할 탐색법

1. 개요[편집]

황금분할 탐색법(golden section search)은 미분을 쓰지 않고 단봉(unimodal) 함수의 최소점을 구간 축소로 찾는 1차원 최적화 기법이다. 도함수 정보 없이 함수값 비교만으로 최소를 가둔 구간(bracket) $[a,b]$를 매 반복 일정 비율씩 줄여 나간다. 기울기를 못 구하거나 신뢰할 수 없는 문제, 예컨대 노이즈가 섞인 실험 함수나 라인서치의 내부 1차원 최소화에 딱 맞는다.

핵심 도구는 이름 그대로 황금비다. $\varphi = \dfrac{\sqrt{5}-1}{2} \approx 0.618$을 써서 구간 안에 두 시험점을 절묘하게 배치하는데, 이 배치 덕분에 매 반복 구간이 일정 비율로 줄고, 무엇보다 이전 반복에서 계산한 함수값 하나를 다음 반복에서 그대로 재사용할 수 있다. 함수 한 번 계산이 비싼 상황에서 이 재사용은 결정적인 이점이다.

2. 알고리즘[편집]

단봉 함수의 최소를 담은 구간 $[a,b]$를 유지하며 다음을 반복한다.

1. 내부 두 점을 배치한다: $$c = b - \varphi(b-a), \qquad d = a + \varphi(b-a)$$ 황금비 성질에 의해 항상 $a < c < d < b$이다.
2. $f(c)$와 $f(d)$를 비교한다.
   • $f(c) < f(d)$이면 최소는 $[a,d]$ 안에 있으므로 $b \leftarrow d$ (오른쪽 잘라냄).
   • 그렇지 않으면 최소는 $[c,b]$ 안에 있으므로 $a \leftarrow c$ (왼쪽 잘라냄).
3. 구간폭 $b-a$가 허용 오차보다 작아질 때까지 1~2를 반복한다.

단봉성이 핵심 가정이다. 구간 안에 최소가 딱 하나여야 “더 나쁜 쪽 바깥을 버려도 최소를 잃지 않는다”가 보장된다. 함수가 다봉이면 엉뚱한 골짜기에 갇힐 수 있다.

3. 왜 하필 황금비인가[편집]

황금비를 쓰는 이유는 함수값 재사용 때문이다. 예를 들어 $f(c) < f(d)$라서 구간을 $[a,d]$로 줄였다고 하자. 새 구간에서 다시 내부 두 점을 계산해야 하는데, 황금비 배치에서는 직전의 $c$가 새 구간의 오른쪽 시험점 위치와 정확히 일치한다. 따라서 $f(c)$를 다시 계산할 필요 없이 재사용하고, 새 시험점 하나만 함수 평가하면 된다.

즉 최적화된 구현에서는 첫 반복만 함수 계산 2번, 이후로는 반복당 1번이면 충분하다. 이것이 황금비가 특별한 이유다. 구간을 $t$배로 줄일 때 남는 시험점 하나가 다음 구간에서도 올바른 황금 위치에 놓이려면 $t^2 = 1 - t$, 즉 $t = \varphi \approx 0.618$이어야 하기 때문이다.¹ 다른 비율을 쓰면 매 반복 두 점을 새로 계산해야 해 효율이 절반으로 떨어진다.²

4. 수렴 속도[편집]

매 반복 구간폭이 정확히 $\varphi \approx 0.618$배로 줄어든다. 따라서 $n$번 반복 후 초기 구간폭의 $\varphi^n$로 축소되는 **선형 수렴(linear convergence)**이다. 오차를 10배 줄이려면 대략 $\log_{1/\varphi} 10 \approx 4.8$, 즉 약 5번의 반복이 필요하다. 도함수를 쓰는 뉴턴-랩슨법류의 2차 수렴에 비하면 느리지만, 미분이 필요 없고 단봉성만 있으면 항상 수렴한다는 견고함이 강점이다. 스텝이 튀거나 발산할 일이 없다.

5. 사촌들과의 비교[편집]

• 피보나치 탐색(Fibonacci search): 구간 축소 비율을 피보나치 수열에서 뽑는 방법. 정해진 함수 평가 횟수 안에서 구간을 최적으로 줄이는 것이 증명돼 있다. 다만 반복 횟수를 미리 정해두어야 비율을 계산할 수 있다는 제약이 있다. 반복 횟수를 무한히 키우면 비율이 황금비로 수렴하므로, 황금분할 탐색은 사실상 “반복 수를 미리 안 정해도 되는 피보나치 탐색”이다.
• 이분법(bisection): 이름이 비슷해 헷갈리지만 용도가 다르다. 이분법은 최소화가 아니라 근찾기(root finding) 방법으로, $f(x)=0$을 푼다. 부호 변화(sign change)를 요구하며 매 반복 구간을 정확히 절반($0.5$배)으로 줄인다. 반면 황금분할은 함수값 크기 비교로 최소를 찾고 단봉성을 요구한다. “구간을 줄인다”는 겉모습만 같을 뿐, 이분법은 부호를, 황금분할은 대소를 본다.³

6. 실무 노트[편집]

황금분할 탐색은 그 자체로 쓰이기도 하지만, 더 자주는 큰 최적화 알고리즘의 부품으로 등장한다. 경사하강법이나 켤레기울기법에서 하강 방향을 정한 뒤 “그 직선 위에서 최적 스텝 $\alpha$“를 찾는 1차원 부분 문제(exact line search)에 쓰이는 것이 대표적이다. 물론 실전 라인서치는 정확한 최소를 굳이 안 찾고 울프 조건 같은 부등식만 만족시키는 부정확 라인서치를 더 선호하지만, 함수가 매끄럽지 않거나 도함수를 못 믿을 때 황금분할은 여전히 든든한 대안이다.

7. 관련 문서[편집]

• 라인서치
• 울프 조건
• 뉴턴-랩슨법
• 경사하강법
• 안장점

8. Footnotes[편집]

1. 위 시뮬레이션도 이 재사용을 그대로 구현했다. 화면의 함수평가 카운터가 첫 반복에 2, 이후 반복마다 1씩만 늘어나는 것이 그 증거다. 살아남은 시험점의 $f$ 값을 물려받고 새 점 하나만 평가하는데, 이것이 가능한 이유가 바로 $\varphi^2 = 1-\varphi$다. ↩

2. 황금비 $\varphi = (\sqrt5 - 1)/2 = 0.6180339\ldots$는 $\varphi^2 = 1 - \varphi$를 만족하는 유일한 양수다. 파르테논 신전과 앵무조개 껍데기에 나온다는 그 비율이 최적화 구간 축소에서도 튀어나오는 건 우연이 아니라 이 자기유사 방정식 때문이다. ↩

3. “이분법으로 최소를 찾으면 되지 않냐”는 흔한 오해. 최솟값 근처에서는 도함수 부호가 바뀌므로 도함수에 이분법을 쓰면 되긴 하는데, 그건 도함수를 안다는 뜻이라 애초에 황금분할이 필요한 상황(미분 불가)이 아니게 된다. ↩