Fibonacci search, Golden section search 의 비교
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다.
Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다.
이전 글에서 Fibonacci search(링크), Golden section search(링크) 에 대해서 설명했습니다. 핵심 아이디어가 똑같은 두 알고리즘은 충분한 iteration 을 거치면 결과적으로는 같은 성능(Convergence rate, 수렴속도)을 보임을 증명할 수 있습니다.
Wikipedia 의 Golden section search(링크) 에서도 Fibonacci search 를 언급하고 있습니다.
1. Golden section search convergence rate
1) f(x) 의 minimum 을 포함하는 구간의 길이는 황금률(Golden ratio) τ 의 비율로 줄어듭니다. 수식으로 표현하면
2)
3) 따라서 a_k, b_k 모두 τ = 0.618 의 비율로 r-linearly convergent sequence 라고 말 할 수 있습니다.
2. Fibonacci search convergence rate
1) f(x) 의 minimum 을 포함하는 구간의 길이는
2)
3) Fibonacci number 의 일반항은
일반항의 유도 참고자료: https://suhak.tistory.com/81
4) 충분히 큰 k 에 대하여 3) 의 마지막 항은 0에 수렴하므로
5)
6) 따라서 a_k, b_k 모두 τ = 0.618 의 비율로 r-linearly convergent sequence 라고 말 할 수 있습니다.
결과적으로 두 알고리즘은 충분한 iteration 에 대하여 convergence rate 가 0.618 로 같기 때문에 성능이 동일하다고 할 수 있습니다.
참고
www.ing.unitn.it/~bertolaz/2-teaching/2011-2012/AA-2011-2012-OPTIM/lezioni/slides-m1D.pdf
