골짜기가 하나뿐인 함수에서 가장 낮은 곳을, 도함수 없이 함수 값 비교만으로 찾는다. 구간 안에 두 점을 찍어 더 높은 쪽 바깥을 잘라 내고, 남은 구간에서 되풀이한다. 두 점을 황금비 자리에 두면 남은 점 하나를 다음 회차에 그대로 다시 쓸 수 있어, 한 회차에 함수 계산이 한 번뿐이고 구간은 매번 약 0.618배로 준다. 다만 골짜기가 여러 개인 함수에서는 가장 깊은 골짜기가 아닌 곳으로 갈 수 있다.
예시로 보기
함수 값을 한 번 계산하는 데 몇 분씩 걸리는 시뮬레이션이 있다. 도함수는 모른다. 최솟값을 찾으려면 계산 횟수를 아껴야 한다.
\(f(x) = x^2 - \sin x\)를 \([0, 1]\)에서 줄인다.
| \(k\) | \(a_k\) | \(c_k\) | \(d_k\) | \(b_k\) | \(f(c_k)\) | \(f(d_k)\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0.3819660 | 0.6180340 | 1 | −0.22684748 | −0.19746793 |
| 1 | 0 | 0.2360680 | 0.3819660 | 0.6180340 | −0.17815339 | −0.22684748 |
| 2 | 0.2360680 | 0.3819660 | 0.4721360 | 0.6180340 | −0.22684748 | −0.23187724 |
| 3 | 0.3819660 | 0.4721360 | 0.5278640 | 0.6180340 | −0.23187724 | −0.22504882 |
| ⋮ | ||||||
| 22 | 0.4501730 | 0.4501827 | 0.4501886 | 0.4501983 | −0.23246558 | −0.23246558 |
0회차에 \(f(c) < f(d)\)라 \([d, b]\)를 버린다. 1회차의 \(d\)는 0회차의 \(c\)를 그대로 쓴다. 새로 계산하는 점은 \(c_1\) 하나다. 참 최솟값은 \(x \approx 0.4501836\)이다1.
아래 막대가 회차마다 남은 구간이고, 주황 눈금이 안쪽 두 점 \(c\), \(d\)다. 구간이 매번 약 0.618배로 줄며 최솟값 쪽으로 좁혀진다. 각 회차의 눈금 하나는 앞 회차의 눈금 자리를 그대로 쓴다.
정의
입력: 구간 \([a, b]\)에서 단봉인 함수 \(f\). 출력: 최솟값이 있는 작은 구간.
\(f\)가 \([a, b]\)에서 단봉이라는 것은 \(f\)가 \([a, p]\)에서 줄고 \([p, b]\)에서 느는 \(p\)가 하나 있다는 뜻이다. 단봉이면 안쪽 두 점 \(a < c < d < b\)의 값만 비교해 최솟값이 있는 쪽을 안다.
- \(f(c) \le f(d)\)이면 최솟값은 \([a, d]\)에 있다. \(b \leftarrow d\).
- \(f(c) > f(d)\)이면 최솟값은 \([c, b]\)에 있다. \(a \leftarrow c\).
두 경우가 같은 크기로 줄도록 \([a, d]\)와 \([c, b]\)를 대칭으로(\(d - a = b - c\)) 놓는다. 남는 비율을 \(r\)이라 하면 다음과 같다.
\[c = a + (1 - r)(b - a), \qquad d = a + r(b - a), \qquad \tfrac12 < r < 1\]\(r\)이 매 회차 같고, 옛 안쪽 점 하나가 새 안쪽 점이 되려면 \(\frac{r}{1} = \frac{1 - r}{r}\), 곧 \(r^2 + r - 1 = 0\)이어야 한다.
\[r = \frac{-1 + \sqrt5}{2} \approx 0.618 \quad(\text{황금비})\]GOLDEN(f, a, b, n)
r ← (√5 − 1)/2
c ← a + (1 − r)(b − a); d ← a + r(b − a)
repeat n times
if f(c) ≤ f(d) then b ← d; d ← c; c ← a + (1 − r)(b − a) # f(c) 하나만 새로
else a ← c; c ← d; d ← a + r(b − a) # f(d) 하나만 새로
return [a, b]
활용
- 복잡도: 처음 두 번 뒤 한 회차에 함수 계산 1번, 구간은 \(r^n\)배. 폭을 \(\varepsilon\) 이하로 줄이는 데 약 \(\log_{1/r}\frac{b - a}{\varepsilon}\)번이다. 오차 \(10^{-6}\)이면 폭 1에서 약 29번이다1.
- 기계학습의 하이퍼파라미터 하나 고르기, 단변수 탐색과 최급상승법의 직선 탐색에 쓴다.
- 흔한 실수: 단봉인지 확인하지 않는 것. \(\sin5x + 0.05x\)를 \([0, 4]\)에서 줄이면 \(x \approx 2.197\)의 극소로 가는데, 전체 최솟값은 \(x \approx 0.94\)에 있다(검증 코드).
연결
- 선수: 도함수의 활용과 최적화(극값), 이분 탐색(구간을 줄이는 생각)
- 회차마다 비율을 바꿔 회차 수를 미리 정하는 방법: 피보나치 탐색
- 근 찾기의 같은 생각: 이분법(부호로 반 자르기)
확인 문제
C1 황금분할 탐색의 두 안쪽 점 공식과, 값 비교 뒤 구간을 줄이는 규칙을 쓰라.
답: \(c = a + (1 - r)(b - a)\), \(d = a + r(b - a)\), \(r = \frac{\sqrt5 - 1}{2}\). \(f(c) \le f(d)\)이면 \([a, d]\), 아니면 \([c, b]\)를 남긴다(최솟값을 찾을 때).
C2 \([0, 2]\)에서 시작할 때 처음 두 안쪽 점은?
답: \(c = (1 - 0.618034)\cdot2 \approx 0.763932\), \(d = 0.618034\cdot2 \approx 1.236068\).
C3 두 점을 황금비 자리에 두면 왜 회차마다 함수 계산이 한 번이면 되는가?
답: 구간을 줄인 뒤에도 남은 옛 점이 새 구간의 정확히 황금비 자리에 놓인다(\(r^2 = 1 - r\)이기 때문). 그래서 그 점의 값을 다시 쓰고, 반대편 새 점 하나만 계산한다.
C4 표의 2회차에서 \(f(c_2) = -0.22684748 > f(d_2) = -0.23187724\)이다. 3회차의 \(a, c, d, b\)를 쓰라.
답: \(f(c) > f(d)\)라 \([c, b]\)를 남긴다. \(a_3 = 0.3819660\), \(c_3 = d_2 = 0.4721360\), \(b_3 = 0.6180340\), \(d_3 = a_3 + r(b_3 - a_3) = 0.5278640\).