Golden-section Search: 단봉 함수 최적화

Golden-section search, 황금 분할 탐색, 삼분 탐색

정의

단봉 (unimodal) 함수 위에서 최소/최대를 찾는 탐색. 이분 탐색을 단봉 함수용으로 확장.

삼분 탐색 (Ternary Search)

구간 [l, r] 을 세 등분하여 두 내부점 m1 = l + (r-l)/3, m2 = r - (r-l)/3 비교. 불량한 쪽 1/3 을 버림. O(log₃ range).

double ternary(double l, double r) {
    for (int iter = 0; iter < 200; iter++) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (f(m1) < f(m2)) r = m2;   // 최대화 가정
        else l = m1;
    }
    return (l + r) / 2;
}

Golden-section

두 내부점을 황금비 (φ = (1 + √5) / 2) 로 나누면 매 반복마다 이전 계산 재사용 가능 → 함수 호출 절반.

정수 삼분 탐색

이산 단봉 함수에서 세 등분 점을 정수화. while (r - l > 2).

참고

• 이분 탐색
• Convex Hull Trick