Одномерная оптимизация: золотое сечение и парабол

Урок про поиск минимума функции одной переменной — без производных (золотое сечение) и с использованием формы кривой (параболический метод).

Одномерная оптимизация ищет точку минимума функции f(x) на отрезке. Метод золотого сечения гарантированно сужает интервал, где лежит минимум, на постоянную долю за шаг.

Минимизация как «бисекция для оптимума»

Оптимизация — нахождение минимума (или максимума) функции — лежит в основе машинного обучения, инженерного проектирования, экономики. Одномерный случай (одна переменная) и важен сам по себе, и служит кирпичиком многомерных методов (поиск вдоль направления). Если функция унимодальна на отрезке (один минимум, без локальных ловушек), его можно найти, надёжно сужая интервал — это аналог бисекции, только для минимума.

Но у минимума, в отличие от корня, нельзя по знаку одной точки понять, с какой он стороны — нужны две внутренние пробы. Метод золотого сечения ставит две пробные точки так, чтобы при сужении одну из них можно было переиспользовать на следующем шаге, экономя вычисления функции. Магическая пропорция, дающая такое переиспользование, — золотое сечение φ.

import math

def золотое_сечение(f, a, b, tol=1e-6):
    gr = (math.sqrt(5) - 1) / 2          # ≈ 0.618, обратное золотое сечение
    c = b - gr * (b - a)
    d = a + gr * (b - a)
    while abs(b - a) > tol:
        if f(c) < f(d):
            b = d                         # минимум левее d
        else:
            a = c                         # минимум правее c
        c = b - gr * (b - a)
        d = a + gr * (b - a)
    return (a + b) / 2

# f(x) = (x - 2)^2 + 1, минимум в x = 2
минимум = золотое_сечение(lambda x: (x - 2)**2 + 1, 0.0, 5.0)
print(f"найденный минимум: x ≈ {минимум:.6f}  (истина 2)")
print(f"значение функции:  f = {(минимум - 2)**2 + 1:.6f}  (истина 1)")

Вывод:

найденный минимум: x ≈ 2.000000  (истина 2)
значение функции:  f = 1.000000  (истина 1)

Метод уверенно нашёл минимум параболы в x=2. Каждый шаг сужает интервал в 1/φ ≈ 0.618 раза — это надёжная линейная сходимость, не требующая ни производной, ни гладкости (лишь унимодальности).

Параболический метод: использовать форму

Золотое сечение надёжно, но не использует форму функции — работает одинаково и для гладкой параболы, и для излома. Вблизи минимума гладкая функция похожа на параболу, поэтому можно ускориться: провести параболу через три точки и прыгнуть сразу в её вершину. Это параболическая интерполяция — аналог метода секущих для оптимизации, со сверхлинейной сходимостью на гладких функциях.

def параболический_шаг(x1, x2, x3, f1, f2, f3):
    # вершина параболы через три точки (формула квадратичной интерполяции)
    числитель = (x2 - x1)**2 * (f2 - f3) - (x2 - x3)**2 * (f2 - f1)
    знаменатель = (x2 - x1) * (f2 - f3) - (x2 - x3) * (f2 - f1)
    return x2 - 0.5 * числитель / знаменатель

f = lambda x: (x - 2)**2 + 1
x1, x2, x3 = 0.0, 1.0, 4.0           # три стартовые точки
x_new = параболический_шаг(x1, x2, x3, f(x1), f(x2), f(x3))
print(f"вершина параболы за ОДИН шаг: x ≈ {x_new:.6f}  (истина 2)")

Вывод:

вершина параболы за ОДИН шаг: x ≈ 2.000000  (истина 2)

Для параболы метод попал в минимум за один шаг — ведь функция и есть парабола, а интерполяция точна. На произвольной гладкой функции так быстро не выйдет, но вблизи минимума параболический метод обгоняет золотое сечение.

Как работает под капотом

Лучшее из двух подходов объединяет метод Брента для оптимизации (за ним стоит scipy.optimize.minimize_scalar): он использует параболическую интерполяцию, когда та ведёт себя разумно (быстрый прыжок к вершине), и откатывается к золотому сечению, когда параболический шаг подозрителен (вылетел за интервал, функция негладкая). Так получают и скорость, и надёжность — ровно как метод Брента для корней сочетает секущие с бисекцией. Важная оговорка: всё это ищет локальный минимум и предполагает унимодальность; при нескольких минимумах нужен глобальный поиск (мультистарт, эволюционные методы).

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

Применять к мультимодальной функции. Эти методы находят один минимум в предположении унимодальности; при многих ловушках попадёте в локальный, а не глобальный.
Доверять только параболическому шагу. На негладких участках он может вылететь за интервал; страхуйте золотым сечением (метод Брента).
Путать минимизацию с поиском корня. Минимум — где производная ноль (а не функция); требует двух проб, а не знака одной точки.

Итоги

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