Метод золотого сечения: поиск минимума функции

Метод золотого сечения - один из классических алгоритмов одномерной оптимизации: он находит минимум унимодальной функции на отрезке, не вычисляя производную и не требуя аналитического выражения. В основе лежит простое наблюдение: на каждом шаге достаточно двух пробных точек, чтобы гарантированно выбросить часть отрезка, где минимума нет. Попробуйте калькулятор ниже - двигайте ползунок шага и смотрите, как синий отрезок сужается к минимуму; дальше разберём каждую формулу строго.

Принцип метода и золотое число

Пусть на отрезке $[a, b]$ задана унимодальная функция $f(x)$ - непрерывная, имеющая ровно один минимум. Мы хотим сузить отрезок неопределённости до заданной точности $\varepsilon$.

Рассчитать для своей задачи

На каждом шаге расставляем две пробные точки:

$$x_1 = b - \varphi(b - a), \quad x_2 = a + \varphi(b - a),$$

где $\varphi = \dfrac{\sqrt{5} - 1}{2} \approx 0{,}618$ - золотое сечение (меньший корень уравнения $\varphi^2 + \varphi = 1$). Дробь $\varphi$ делит отрезок в пропорции $1 : \varphi \approx 0{,}382 : 0{,}618$.

Сравниваем $f(x_1)$ и $f(x_2)$:

• если $f(x_1) < f(x_2)$ - минимум лежит в $[a, x_2]$, поэтому заменяем $b \leftarrow x_2$;
• если $f(x_1) \geq f(x_2)$ - минимум в $[x_1, b]$, заменяем $a \leftarrow x_1$.

Ключевое свойство золотого сечения: после сужения одна из двух новых пробных точек совпадает со старой. Это значит, что на следующем шаге достаточно вычислить $f$ только в одной новой точке - экономия на 50% по сравнению с произвольным разбиением.

Скорость сходимости

После $n$ итераций длина отрезка неопределённости равна

$$|b_n - a_n| = \varphi^n \cdot (b_0 - a_0).$$

Поскольку $\varphi \approx 0{,}618 < 1$, длина убывает геометрически. Чтобы достичь точности $\varepsilon$, достаточно

$$n \geq \frac{\ln(\varepsilon / (b_0 - a_0))}{\ln \varphi}$$

итераций. Например, для отрезка $[0, 1]$ и $\varepsilon = 10^{-5}$ нужно всего $n \approx 26$ шагов.

Это быстрее метода деления пополам только в теоретическом смысле: дихотомия за два вычисления $f$ сужает отрезок в 2 раза, тогда как золотое сечение за два вычисления - в $1/\varphi \approx 1{,}618$ раза. Но за одно вычисление (со второй итерации) - в $1/\varphi$; при дорогостоящих $f$ это решающий довод.

Рассчитать для своей задачи

На логарифмической шкале убывание длины отрезка - прямая линия с наклоном $\ln\varphi \approx -0{,}481$. Именно это свойство делает золотое сечение точно оптимальным для стратегий с одной пробной точкой за шаг.

Шаги алгоритма на примере

Возьмём $f(x) = x^2 - 4x + 5$ на $[0, 5]$, точность $\varepsilon = 0{,}1$.

Шаг 0. $a = 0$, $b = 5$, длина 5.

$$x_1 = 5 - 0{,}618 \cdot 5 = 1{,}910, \quad f(x_1) = 1{,}651$$ $$x_2 = 0 + 0{,}618 \cdot 5 = 3{,}090, \quad f(x_2) = 4{,}549$$

Так как $f(x_1) < f(x_2)$, отбрасываем правую часть: $b \leftarrow 3{,}090$. Длина стала $3{,}090$.

Шаг 1. $a = 0$, $b = 3{,}090$.

$$x_1 = 3{,}090 - 0{,}618 \cdot 3{,}090 = 1{,}180, \quad f(x_1) = 2{,}390$$ $$x_2 = 0 + 0{,}618 \cdot 3{,}090 = 1{,}910, \quad f(x_2) = 1{,}651$$

Теперь $f(x_1) > f(x_2)$, отбрасываем левую часть: $a \leftarrow 1{,}180$.

Так шаг за шагом отрезок сжимается к $x^* = 2$ (истинный минимум $f(2) = 1$). Уже через 10 итераций длина не превысит $5 \cdot 0{,}618^{10} \approx 0{,}036$ - лучше заданной точности $0{,}1$.

Условие применимости: унимодальность

Метод гарантирует нахождение глобального минимума только тогда, когда функция унимодальна - имеет ровно один минимум на отрезке. Если у $f$ два и более локальных минимума, алгоритм «выберет» один из них, но какой именно - непредсказуемо.

Проверить унимодальность аналитически: достаточно, чтобы $f'(x) = 0$ имела единственный корень на $[a, b]$ и $f'' > 0$ в нём (строгий минимум). Для гладкой строго выпуклой функции ($f'' > 0$ всюду на $[a, b]$) метод работает безусловно.

Связь с золотым сечением и числом Фибоначчи

Название «золотое сечение» не случайно: $\varphi = (\sqrt{5} - 1)/2$ - то самое иррациональное число, которое с древности описывает деление отрезка в «наиболее гармоничном» соотношении. В математической оптимизации его роль другая: это единственная точка деления, при которой метод после каждого шага оставляет такое же относительное расположение пробных точек на новом, меньшем отрезке.

Числа Фибоначчи $1, 1, 2, 3, 5, 8, 13, 21, \ldots$ связаны с $\varphi$ формулой:

$$\varphi = \lim_{n \to \infty} \frac{F_n}{F_{n+1}},$$

а метод Фибоначчи (предшественник золотого сечения) использует конечное число шагов, заранее известное. Для $n \to \infty$ оба метода совпадают, и коэффициент сужения стремится к $\varphi$.

Частые ошибки

• Забывают проверить унимодальность. Применяют метод к функции с двумя локальными минимумами и удивляются неверному ответу. Сначала убедитесь, что функция унимодальна на выбранном отрезке.
• Путают $x_1$ и $x_2$. Формулы $x_1 = b - \varphi(b - a)$ и $x_2 = a + \varphi(b - a)$ симметричны относительно середины, но $x_1 < x_2$ всегда. Привязка знака к нижней границе ($a + \ldots$) дает $x_2$, к верхней ($b - \ldots$) - $x_1$.
• Неверно обновляют границу. Если $f(x_1) < f(x_2)$, то $b \leftarrow x_2$ (не $x_1$): отрезок $[a, x_2]$ оставляем. Частая ошибка - поставить $b \leftarrow x_1$, выбросив зону, где минимум ещё может быть.
• Используют десятичное $\varphi = 0{,}618$. Округление накапливается за 20-30 итераций. Держите $\varphi = (\sqrt{5} - 1) / 2$ как константу.
• Останавливаются по числу шагов, а не по ширине отрезка. Критерий остановки - $|b - a| \leq \varepsilon$, а не «сделали $n$ шагов». При фиксированном $n$ вы не знаете, достигнута ли нужная точность.

FAQ

Нужна ли производная для метода золотого сечения? Нет. Метод использует только значения $f(x_1)$ и $f(x_2)$ и не требует производной. Это делает его применимым к «чёрным ящикам» - функциям, для которых формулы нет, но значение можно получить экспериментально или численно.

Чем метод золотого сечения отличается от градиентного спуска? Градиентный спуск использует производную $f'(x)$ и может применяться к многомерным функциям, но требует её вычисления и может застрять в локальном минимуме. Золотое сечение - строго одномерный метод, работает без производной и при унимодальности гарантирует глобальный минимум. Для одномерных задач без производной золотое сечение обычно предпочтительнее.

Как выбрать начальный отрезок $[a, b]$? Отрезок должен содержать минимум. Практически: построить грубый график или оценить по физическому смыслу задачи. Если минимум не попал в $[a, b]$, алгоритм найдёт «минимум на краю» - либо $a$, либо $b$. Признак: после сходимости проверьте, что $f(x^*) \leq f(a)$ и $f(x^*) \leq f(b)$.

Коротко

Метод золотого сечения сужает отрезок неопределённости в $\varphi \approx 0{,}618$ раз за каждый шаг при одном вычислении $f$. Формулы пробных точек $x_1 = b - \varphi(b - a)$ и $x_2 = a + \varphi(b - a)$ обеспечивают переиспользование: одна из точек остаётся на следующем шаге. За $n$ шагов длина отрезка составляет $\varphi^n (b - a)$, убывая геометрически. Условие применимости - унимодальность функции на $[a, b]$; без него метод не гарантирует глобального результата.