황금분할 탐색

황금분할 탐색(Golden-section search)은 특정 구간 내에서 함수의 극값(최소값 또는 최대값)을 찾는 기술이다. 구간 내부에 극값이 있는 엄격한 단봉 함수의 경우 해당 극값을 찾는 반면, 여러 극값(구간 경계 포함)을 포함하는 구간의 경우 극값 중 하나로 수렴된다. 구간의 유일한 극값이 구간의 경계에 있는 경우 해당 극점은 해당 경계점으로 수렴된다. 이 방법은 지정된 간격에서 값의 범위를 연속적으로 좁히는 방식으로 작동하므로 상대적으로 느리지만 매우 견고한다. 이 기술은 알고리즘이 3개의 간격 너비가 Φ:1:Φ 비율인 4개 점에 대한 함수 값을 유지한다는 사실에서 이름이 유래되었다. 여기서 Φ는 황금비이다. 이러한 비율은 각 반복마다 유지되며 최대로 효율적이다. 경계점을 제외하고, 최소값을 검색할 때 중앙점은 항상 외부점보다 작거나 같으므로 외부점 사이에 최소값이 포함된다. 최대값을 검색할 때는 그 반대가 적용된다. 이 알고리즘은 많은 함수 평가에 대한 피보나치 검색(아래 설명됨)의 한계이다. 피보나치 탐색과 황금분할 탐색은 키퍼(Kiefer, 1953)에 의해 발견되었다(Abriel and Wilde(1966)).

같이 보기

• 이진 검색 알고리즘

출처

• Kiefer, J. (1953), “Sequential minimax search for a maximum”, 《Proceedings of the American Mathematical Society》 4 (3): 502–506, doi:10.2307/2032161, JSTOR 2032161, MR 0055639 
• Avriel, Mordecai; Wilde, Douglass J. (1966), “Optimality proof for the symmetric Fibonacci search technique”, 《Fibonacci Quarterly》 4: 265–269, MR 0208812 

• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), 〈Section 10.2. Golden Section Search in One Dimension〉, 《Numerical Recipes: The Art of Scientific Computing》 3판, New York: Cambridge University Press, ISBN 978-0-521-88068-8, 2011년 8월 11일에 원본 문서에서 보존된 문서, 2023년 10월 21일에 확인함