Оптимизация вокруг нас

Оптимизация — это математически строгий поиск наилучшего варианта среди всех допустимых.

Оптимизация — нахождение такой точки $x^*$, в которой целевая функция $f(x)$ достигает минимума (или максимума) на заданном допустимом множестве.

Зачем это нужно

Почти любая инженерная или научная задача в какой-то момент сводится к фразе «сделай как можно лучше». Нейросеть учится, минимизируя ошибку на данных. Логистическая компания строит маршруты, минимизируя пробег. Инвестор собирает портфель, максимизируя доходность при ограниченном риске. Завод планирует выпуск, максимизируя прибыль при ограниченных ресурсах. Все эти задачи имеют одну общую форму, и именно её изучает теория оптимизации.

Универсальная запись такова:

$$\min_{x\in X} f(x),$$

где $x$ — то, что мы выбираем (вектор параметров, план, маршрут), $f$ — целевая функция (что мы хотим сделать меньше), а $X$ — допустимое множество (что вообще разрешено выбирать). Максимизация сводится к минимизации тривиально: $\max f(x) = -\min(-f(x))$, поэтому весь курс мы говорим про минимум, не теряя общности.

Три кита любой задачи

Чтобы корректно поставить задачу оптимизации, нужно ответить на три вопроса.

Что мы выбираем? Это переменные решения $x\in\mathbb{R}^n$. Для нейросети — миллионы весов, для маршрута — порядок городов, для диеты — граммы продуктов.
Что хотим оптимизировать? Это целевая функция $f(x)$. Ошибка, стоимость, время, риск.
Что разрешено? Это ограничения, задающие $X$: бюджет, физические законы, неотрицательность, целочисленность.

Маленький пример: лучшая цена

Магазин продаёт товар. При цене $p$ спрос примерно равен $d(p)=100-2p$ штук, себестоимость одной штуки — $20$. Прибыль:

$$f(p) = (p-20)\cdot d(p) = (p-20)(100-2p).$$

Найти лучшую цену — это решить $\max_p f(p)$. Переберём цены и увидим, где прибыль максимальна.

def profit(p):
    demand = 100 - 2 * p
    return (p - 20) * demand

best_p, best_val = None, -1e9
for p10 in range(200, 501):   # цена от 20.0 до 50.0 с шагом 0.1
    p = p10 / 10
    v = profit(p)
    if v > best_val:
        best_val, best_p = v, p

print("Лучшая цена:", best_p)
print("Прибыль:", round(best_val, 2))

Вывод:

Лучшая цена: 35.0
Прибыль: 450.0

Перебор — самый честный, но самый медленный способ. Если бы переменных было не одна, а тысяча, перебор стал бы невозможен: на сетке из $10$ значений по каждой из $1000$ осей получилось бы $10^{1000}$ точек. Весь курс — про то, как находить минимум умно, не перебирая всё.

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

Большинство методов оптимизации устроены как итеративный спуск: стартуем из точки $x_0$, и пока не достигли «дна», делаем шаг $x_{k+1}=x_k+\Delta_k$, где направление $\Delta_k$ выбрано так, чтобы $f$ уменьшилась. Различаются методы тем, как они выбирают направление: по наклону (градиент), по кривизне (Ньютон), случайно с умом (отжиг). Перебор из примера выше — вырожденный случай: «направление» там — просто следующая точка сетки.

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

Путать переменную и параметр. Цена $p$ — переменная (мы её выбираем), а себестоимость $20$ — параметр (задан извне). Оптимизируем только по переменным.
Забыть про допустимое множество. Формально «лучшая цена» = $+\infty$ даёт бесконечную прибыль на штуку, но спрос становится отрицательным — это недопустимо. Ограничения существенны.
Считать, что максимум всегда внутри. Иногда оптимум — на границе допустимого множества, и производная там не равна нулю.

Итоги

Оптимизация — поиск $\min_{x\in X} f(x)$: лучшего $x$ по критерию $f$ при ограничениях $X$.
Три кита: переменные, целевая функция, ограничения.
Максимизация = минимизация со знаком минус.
Перебор честен, но экспоненциально дорог — нужны умные методы.