Зоопарк задач оптимизации

Прежде чем выбирать метод, задачу нужно классифицировать — от этого зависит всё.

Классификация — отнесение задачи к типу (непрерывная/дискретная, выпуклая/невыпуклая, с ограничениями/без), который определяет применимые методы и гарантии.

Зачем классифицировать

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

Ось 1: непрерывная или дискретная

Переменные могут жить в $\mathbb{R}^n$ (вес нейрона, цена, температура) — это непрерывная оптимизация, там работают производные. А могут быть целыми или перестановками (сколько станков купить, в каком порядке объехать города) — дискретная (комбинаторная) оптимизация, где понятие производной теряет смысл и нужны другие инструменты.

Ось 2: выпуклая или невыпуклая

Если функция $f$ выпукла (чашеобразна) и множество $X$ выпукло, у задачи ровно один «уровень дна»: любой локальный минимум автоматически глобальный. Это золотой случай — методы спуска гарантированно приходят к лучшему решению. Невыпуклые задачи (типичная нейросеть) утыканы локальными минимумами и сёдлами; глобальный оптимум искать вычислительно тяжело.

Ось 3: с ограничениями или без

$$\min_x f(x)\quad\text{или}\quad \min_x f(x)\ \text{s.t.}\ g_i(x)\le 0,\ h_j(x)=0.$$

Безусловная задача проще: ищем точку, где $\nabla f=0$. Условная требует учитывать границы — тут появляются множители Лагранжа и условия ККТ.

Карта зоопарка

Распознаём тип кодом

Напишем крошечный «классификатор», который по флагам задачи подсказывает класс методов.

def classify(continuous, convex, constrained):
    kind = "непрерывная" if continuous else "дискретная"
    shape = "выпуклая" if convex else "невыпуклая"
    bnd = "с ограничениями" if constrained else "без ограничений"
    if not continuous:
        method = "ветви и границы / метаэвристики"
    elif convex and not constrained:
        method = "градиент / Ньютон (глобальный оптимум гарантирован)"
    elif convex and constrained:
        method = "ККТ / внутренняя точка"
    else:
        method = "SGD / Adam / рестарты (только локальный оптимум)"
    print(f"{kind}, {shape}, {bnd}")
    print("-> рекомендуется:", method)

classify(True, True, False)
classify(False, False, True)

Вывод:

непрерывная, выпуклая, без ограничений
-> рекомендуется: градиент / Ньютон (глобальный оптимум гарантирован)
дискретная, невыпуклая, с ограничениями
-> рекомендуется: ветви и границы / метаэвристики

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

Гарантии метода прямо вытекают из класса задачи. Для выпуклых задач есть теорема: «локальный минимум = глобальный», поэтому достаточно градиентного спуска. Для невыпуклых такой теоремы нет — отсюда рестарты, отжиг, генетика, которые лишь пытаются сбежать из плохих впадин, не гарантируя успеха. Для дискретных задач включается теория сложности: многие из них NP-трудны, то есть точный ответ за разумное время неизвестен.

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

• Применить непрерывный метод к дискретной задаче. «Округлить» дробное решение рюкзака часто даёт недопустимый или плохой план.
• Считать задачу выпуклой по умолчанию. Большинство интересных задач невыпуклы; проверяйте.
• Игнорировать ограничения. Безусловный минимум может лежать вне допустимого множества и быть бессмысленным.

Итоги

• Три главные оси: непрерывная/дискретная, выпуклая/невыпуклая, с ограничениями/без.
• Класс задачи определяет метод и гарантии (глобальный оптимум или только локальный).
• Выпуклость — золотой случай; невыпуклость и дискретность — тяжёлые.