황금 분할 탐색

두 내부 시험점

최솟값을 포함하는 구간 [a,b]에서 ρ=(√5-1)/2로 두자. 두 내부 시험점을 c=a+(1-ρ)(b-a), d=a+ρ(b-a)로 잡으면 a<c<d<b이다. 함수가 해당 구간에서 한 골짜기 형태라고 가정하면 f(c)와 f(d)의 비교로 최솟값이 없는 쪽을 제외할 수 있다. 여러 골짜기가 있는 임의의 함수에 같은 전역 최적 보장을 적용할 수는 없다.

구간 축소의 예제

f(x)=(x-2)²를 [0,10]에서 살펴보자. 시험점은 약 3.820과 6.180이고 함수값은 앞쪽이 작다. 한 골짜기인 이 함수에서는 구간을 [0,6.180]으로 줄일 수 있다. 새 구간의 오른쪽 내부 시험점은 약 3.820으로 이전의 왼쪽 시험점과 같다. 그 함수값을 재사용하고 새 시험점 한 곳만 추가로 계산할 수 있다.

비율을 유지하는 이유

ρ²=1-ρ라는 관계가 구간을 줄인 뒤에도 내부점 하나를 재사용할 수 있게 한다. 같은 방식으로 반복하면 구간 길이가 일정 비율로 줄어든다. 함수 평가가 비싼 경우 재사용이 도움이 될 수 있지만, 더 정교한 보간을 이용하는 방법보다 항상 빠른 것은 아니다. 함수값의 잡음이나 반올림 오차가 비교에 미치는 영향도 고려한다.

근 찾기와 구분

황금 분할 탐색은 f(x)=0의 해를 찾는 방법이 아니라 f의 값을 작게 만드는 위치를 찾는다. 초기 구간을 정하는 절차와 그 안에서 축소하는 절차도 구분해야 한다. 어떤 도구에서 두 초기점을 받는다는 사실이 그 두 점 사이만 탐색한다는 뜻은 아닐 수 있다. 종료 허용 오차와 구간 조건을 확인하고, 반환한 위치와 최솟값의 수치를 혼동하지 않는다.