Как выбрать метод оптимизации

Правильный метод выбирается не по моде, а по свойствам задачи: выпуклость, размерность, ограничения, доступность градиента.

Выбор метода — сопоставление структуры задачи (выпуклость, гладкость, размерность, тип ограничений) с подходящим классом алгоритмов и их гарантиями.

Зачем об этом думать

За курс мы собрали целый арсенал: золотое сечение, градиентный спуск, Adam, Ньютон, BFGS, симплекс, ККТ, отжиг, ГА. Применить мощный молоток не к тому гвоздю — частая ошибка. Ньютон на нейросети с миллионом параметров захлебнётся; отжиг на выпуклой квадратичной — пустая трата времени; градиент на коммивояжёре бессмыслен. Хорошая новость: задача почти всегда сама подсказывает метод.

Четыре вопроса-маршрутизатора

Переменные непрерывны или дискретны? Дискретны — ДП / ветви и границы / метаэвристики. Непрерывны — дальше.
Задача линейна? Да (линейные цель и ограничения) — симплекс / внутренняя точка.
Выпукла? Да — градиентные/Ньютон надёжно дают глобум; с ограничениями — ККТ / внутренняя точка.
Есть ли градиент и какова размерность? Невыпукла, градиент есть, большое $n$ — SGD/Adam. Малое $n$, нужна скорость — Ньютон/BFGS. Градиента нет — золотое сечение (1D), отжиг/ГА.

Дерево решений в коде

def recommend(continuous, linear, convex, has_grad, big):
    if not continuous:
        return "ДП / ветви и границы / метаэвристики (отжиг, ГА)"
    if linear:
        return "симплекс или метод внутренней точки"
    if convex:
        if big:
            return "градиентный спуск / L-BFGS (глобум гарантирован)"
        return "Ньютон / BFGS (быстрая сходимость)"
    # невыпуклая непрерывная
    if not has_grad:
        return "производных нет -> отжиг / ГА / Нелдер-Мид"
    if big:
        return "SGD / Adam (только локальный оптимум)"
    return "BFGS с рестартами"

cases = [
    ("Линейная регрессия",   dict(continuous=True, linear=False, convex=True,  has_grad=True,  big=False)),
    ("Обучение нейросети",   dict(continuous=True, linear=False, convex=False, has_grad=True,  big=True)),
    ("План производства",    dict(continuous=True, linear=True,  convex=True,  has_grad=True,  big=False)),
    ("Коммивояжёр",          dict(continuous=False, linear=False, convex=False, has_grad=False, big=True)),
]
for name, kw in cases:
    print(f"{name:22s}-> {recommend(**kw)}")

Вывод:

Линейная регрессия    -> Ньютон / BFGS (быстрая сходимость)
Обучение нейросети    -> SGD / Adam (только локальный оптимум)
План производства     -> симплекс или метод внутренней точки
Коммивояжёр           -> ДП / ветви и границы / метаэвристики (отжиг, ГА)

Один маленький маршрутизатор отправил каждую задачу к верному классу методов — ровно так рассуждает опытный практик, прежде чем писать код.

Обусловленность и масштабирование

Отдельный практический совет, не зависящий от метода: нормируйте переменные. Признаки разного масштаба создают искусственные овраги (большое число обусловленности $\kappa$), от которых страдают все первопорядковые методы. Приведение к нулевому среднему и единичной дисперсии часто ускоряет сходимость в разы — дешевле любой смены алгоритма.

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

За выбором стоит баланс трёх ресурсов: информация (есть ли градиент, гессиан), вычисления (можем ли позволить $O(n^2)$, $O(n^3)$), гарантии (нужен ли доказанный глобум). Второй порядок (Ньютон) тратит больше информации и вычислений, но сходится быстрее; нулевой порядок (отжиг) почти не требует информации, но медленный и без гарантий. Грамотный инженер выбирает точку на этом компромиссе под бюджет задачи, а не «самый модный» метод.

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

Сразу хвататься за нейросеть/метаэвристику. Если задача выпуклая или линейная, классический солвер быстрее и надёжнее.
Игнорировать масштаб данных. Без нормировки любой градиентный метод буксует в искусственном овраге.
Не проверять выпуклость. От неё зависит, гарантирован ли глобальный оптимум.

Итоги

Метод выбирают по структуре: дискретность → линейность → выпуклость → размерность/градиент.
Дискретно — ДП/ветви/метаэвристики; линейно — симплекс; выпукло — градиент/Ньютон; невыпукло+большое — SGD/Adam.
Нормировка переменных лечит обусловленность дешевле смены метода; помните о балансе информация/вычисления/гарантии.