Зачем уметь искать минимум по одной переменной

Минимум по одной переменной — фундаментальная подзадача, которую многомерные методы решают на каждом шаге.

Линейный поиск (line search) — поиск наилучшей длины шага $\alpha$ вдоль выбранного направления $p$: $\min_{\alpha>0} f(x_k+\alpha p)$.

Где прячется одномерная задача

Кажется, что поиск минимума по одной переменной — игрушка. На деле это рабочая лошадка всей непрерывной оптимизации. Когда многомерный метод выбрал направление спуска $p$ (например, $p=-\nabla f$), остаётся вопрос: на сколько шагнуть? Слишком мало — медленно; слишком много — перелетим минимум. Ответ — решить одномерную задачу $\varphi(\alpha)=f(x_k+\alpha p)\to\min$ по скаляру $\alpha>0$. Это и есть line search, встроенный почти в каждый солвер.

Унимодальность

Чтобы одномерный поиск был надёжным, функцию полезно считать унимодальной на отрезке: она строго убывает до некоторой точки $x^*$, а затем строго возрастает. У такой функции ровно один минимум, и его можно находить, последовательно сужая интервал неопределённости — без производных, только по значениям.

Наивный перебор

Самый простой способ — сетка. Разобьём отрезок на $N$ точек и выберем минимальную. Точность $\sim$ длина отрезка $/N$.

import math

def phi(x):
    return (x - 2) ** 2 + math.sin(3 * x)

a, b, N = 0.0, 4.0, 40
best_x, best_v = a, phi(a)
for i in range(N + 1):
    x = a + (b - a) * i / N
    v = phi(x)
    if v < best_v:
        best_v, best_x = v, x

print("Перебор: x* ≈", round(best_x, 3), " f* ≈", round(best_v, 4))

Вывод:

Перебор: x* ≈ 1.6  f* ≈ -0.8362

Сетка из $41$ точки даёт грубую оценку. Чтобы улучшить точность вдвое, нужно вдвое больше вычислений — это расточительно. Метод золотого сечения сужает интервал гораздо умнее.

Интервал неопределённости

Идея методов сужения: держим отрезок $[a,b]$, про который знаем, что минимум внутри. Берём две внутренние пробные точки, сравниваем значения и отбрасываем ту часть, где минимума точно нет. Отрезок сжимается, мы повторяем. Через несколько итераций интервал становится крошечным, а его середина — ответом.

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

В реальных солверах редко ищут $\alpha$ точно — это дорого. Чаще берут неточный line search: подбирают $\alpha$, лишь бы функция «достаточно» уменьшилась (условия Армихо и Вольфе). Но понимание точного одномерного поиска (золотое сечение, парабола) важно: оно объясняет, почему слишком большой или слишком малый шаг вредят, и лежит в основе быстрых эвристик подбора шага.

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

Применять сужение к неунимодальной функции. Если минимумов несколько, метод найдёт какой-то один, возможно не лучший.
Слишком мелкая сетка. Перебор с огромным $N$ точен, но крайне медленен — для этого и придуманы умные методы.
Искать $\alpha$ слишком точно. В многомерных методах это пустая трата — хватает приближённого шага.

Итоги

Одномерная оптимизация — подбор длины шага $\alpha$ вдоль направления; встроена в многомерные методы.
Унимодальность гарантирует один минимум и позволяет сужать интервал.
Перебор прост, но дорог; умные методы (золотое сечение) сужают интервал быстро.