Минимизация функций: золотое сечение и scipy.minimize

Где функция достигает минимума? Найдём дно «долины» методом золотого сечения, не вычисляя ни одной производной.

Оптимизация — поиск точки, где функция достигает минимума (или максимума). Минимизация без производных особенно ценна, когда производную взять трудно.

Зачем минимизировать

Оптимизация — сердце прикладной науки и машинного обучения. «Подобрать параметры модели так, чтобы ошибка была минимальной», «найти форму детали с минимальным весом», «минимизировать затраты» — всё это минимизация функции. Найти максимум — то же самое: минимизируем −f.

Идея золотого сечения

Если функция на отрезке унимодальна (один минимум, сначала убывает, потом возрастает), можно зажимать минимум, как бисекция зажимает корень. Берём две внутренние пробные точки; та, где значение больше, отсекает «свою» сторону — минимума там быть не может. Точки выбирают в пропорции золотого сечения (≈0.618), чтобы переиспользовать одно вычисление функции на следующем шаге — экономия вызовов.

a───c────d───b      сравниваем f(c) и f(d)
если f(c) < f(d): минимум левее, отсекаем [d, b] -> новый b = d
иначе:           отсекаем [a, c] -> новый a = c

Реализация на чистом Python

Найдём минимум параболы f(x) = (x − 2)² + 1 (очевидно, в x = 2, значение 1):

import math

def f(x):
    return (x - 2) ** 2 + 1

gr = (math.sqrt(5) - 1) / 2     # ~0.618, обратное золотое сечение
a, b = 0.0, 5.0
c = b - gr * (b - a)
d = a + gr * (b - a)
for _ in range(40):
    if f(c) < f(d):
        b = d
    else:
        a = c
    c = b - gr * (b - a)
    d = a + gr * (b - a)

xmin = (a + b) / 2
print("x минимума :", round(xmin, 6))
print("f(min)     :", round(f(xmin), 6))

Вывод:

x минимума : 2.0
f(min)     : 1.0

А в SciPy — одна строка

from scipy.optimize import minimize_scalar, minimize

# одномерный минимум
res = minimize_scalar(lambda x: (x-2)**2 + 1)
print(res.x)        # ~2.0

# многомерный: минимум f(x,y) = (x-1)^2 + (y-3)^2
res2 = minimize(lambda v: (v[0]-1)**2 + (v[1]-3)**2, x0=[0, 0])
print(res2.x)       # ~[1. 3.]

minimize в многомерном случае по умолчанию использует метод BFGS, который оценивает «кривизну» функции и сходится куда быстрее перебора.

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

Почему именно золотое сечение, а не деление пополам? Чтобы зажать минимум, в каждой итерации нужны две внутренние точки (минимума, в отличие от корня, по одному значению не локализуешь). Наивно это два новых вычисления функции на шаг. Но если выбрать точки в пропорции золотого сечения φ, то одна из старых точек идеально подходит на роль новой — её значение уже посчитано. Так на шаг тратится только один новый вызов f. Для дорогих функций (где один вызов — это часовая симуляция) это вдвое экономит время. Многомерные методы (градиентный спуск, BFGS) используют производные/их оценки, чтобы двигаться сразу «под гору» в нужном направлении.

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

Функция не унимодальна. Если минимумов несколько, золотое сечение найдёт какой-то один (локальный), не обязательно глобальный.
Путать минимум и корень. Минимум — где функция самая низкая (f'(x)=0), корень — где она равна нулю; это разные задачи.
Плохой старт в многомерье. minimize находит ближайший локальный минимум; для глобального нужны спец. методы (differential_evolution, basinhopping).

Итог

Минимизация ищет дно «долины»; максимум — это минимум −f.
Золотое сечение зажимает минимум унимодальной функции без производных.
Пропорция φ экономит вызовы функции — важно для дорогих расчётов.
В SciPy: minimize_scalar (1D) и minimize (многомерье, BFGS и др.).