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

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

Ниже мы рассмотрим классический метод Ньютона и семейство квазиньютоновских методов, обсудим, как за счёт учёта второй производной достигается ускорение сходимости, а затем перейдём к основам выпуклой оптимизации.

Мы введём понятия выпуклых функций и множеств, опишем ключевые свойства выпуклых задач (в частности, почему для них методы оптимизации гарантированно находят глобальный минимум) и приведём примеры таких задач — например, обучение метода опорных векторов (англ. — Support Vector Machine, SVM) и решение регрессии LASSO, которые формулируются как выпуклые оптимизационные проблемы.

Методы второго порядка

Начнём с классического — метода Ньютона.

Метод Ньютона

Это базовый алгоритм второго порядка для поиска минимума гладкой функции. Идея метода состоит в том, чтобы в каждой точке приближать целевую функцию при помощи квадратичной зависимости с использованием градиента и матрицы вторых производных. Формула шага Ньютона для безусловной оптимизации такая:

где — градиент, а — матрица Гессе функции .

Важно. Шаг метода Ньютона вычисляется не посредством явного обращения матрицы Гессе, а как решение системы линейных уравнений:

где

• — матрица вторых производных (матрица Гессе);
• — градиент функции в текущей точке.

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

Такая формулировка эквивалентна записи шага Ньютона с использованием обратной матрицы, но является более устойчивой и предпочтительной с вычислительной точки зрения.

Интуитивно метод Ньютона заглядывает во вторую производную, т. е. учитывает кривизну функции в текущей точке, и потому способен более точно спрогнозировать, где находится минимум. Это как спускаться в долину не вслепую: если градиентный метод сообщает только направление спуска, то метод Ньютона благодаря Гессиану оценивает, насколько изогнута чаша функции, и подбирает оптимальный шаг с учётом этой информации.

Главное достоинство метода Ньютона — быстрая локальная сходимость. Для хорошо обусловленных задач в окрестности минимума алгоритм демонстрирует квадратичную скорость сходимости (ошибка уменьшается пропорционально квадрату числа итераций). На практике это означает, что метод Ньютона часто требует на порядок меньше итераций, чем метод градиентного спуска, для достижения той же точности решения.

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

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

Такое драматическое ускорение обусловлено тем, что для квадратичных функций аппроксимация Ньютона точно совпадает с самой функцией, поскольку метод Ньютона, по сути, строит квадратичную аппроксимацию функции — а квадратичная функция является квадратичной аппроксимацией самой себя. Соответственно, шаг сразу приводит в стационарную точку — другими словами, решение системы достигается напрямую.

Однако у метода Ньютона есть и недостатки:

• Во-первых, для каждой итерации требуется вычислить матрицу Гессе и решить систему линейных уравнений размерности (где — число переменных). Если использовать подход с прямым обращением матрицы, то это операция порядка , что становится узким местом для задач большой размерности.
• Во-вторых, метод Ньютона требует, чтобы матрица Гессе в окрестности минимума была положительно определённой (хотя для выпуклых функций это обычно так). Если функция не выпуклая или начальная точка далека от минимума, шаг Ньютона может увести в сторону, приводя к расходимости алгоритма.

На практике часто применяют демпфированный метод Ньютона (англ. — Damped Newton Method) — то есть используют уменьшение шага или ограничение шага, чтобы гарантировать снижение значения функции на каждой итерации.

Также распространена стратегия сначала выполнить несколько шагов градиентного спуска (устраняющих грубые ошибки позиции), а затем перейти к методу Ньютона, когда мы находимся уже достаточно близко к оптимуму, — это сочетает стабильность первого порядка и скорость второго.

Квазиньютоновские методы

Полноценный метод Ньютона требует вычисления и хранения Гессиана, что для больших задач накладно по времени и памяти. Квазиньютоновские методы предлагают компромисс: они приближённо восстанавливают информацию о второй производной, используя только вычисляемые градиенты функции.

Идея этих методов — на каждой итерации обновлять некоторую матрицу , которая служит аппроксимацией либо самой матрицы Гессе, либо её обратной (как в популярных реализациях).

Самым известным алгоритмом этого семейства является метод Бройдена — Флетчера — Гольдфарба — Шанно (BFGS).

Мы не будем углубляться в формулы и детали метода, но дадим общее описание для понимания сути происходящего. В методе BFGS происходит следующее.

На старте выбираем начальную точку и задаём приближение матрицы Гессе (часто единичную).

Далее на каждой итерации:

• Градиент: вычисляем градиент функции в текущей точке .
• Направление шага: определяем, куда двигаться, используя приближённую матрицу Гессе: .
• Шаг: делаем движение в выбранном направлении (иногда с уменьшением длины шага для устойчивости) и попадаем в точку .
• Обновление матрицы: в точке матрица корректируется с использованием разностей градиентов и шага (по некоторой хитрой формуле).

Повтор: мы продолжаем шаги метода до достижения минимума (в котором градиент становится очень малым).

Преимущества квазиньютоновских методов в том, что они сходятся существенно быстрее методов первого порядка и при этом обходятся без явного вычисления Гессиана. Например, алгоритм BFGS и его модификация L-BFGS обычно требуют заметно меньше итераций, чем градиентный спуск, но каждая итерация лишь немногим дороже градиентной.

Квазиньютоновские методы достигают существенного ускорения сходимости по сравнению с простым градиентным методом, приближаясь по эффективности к методу Ньютона, зато они избегают прямого вычисления вторых производных.

Разумеется, цена за это — большее число итераций, чем у классического метода Ньютона, ведь аппроксимация Гессиана на первых итерациях груба. Тем не менее на практике методы вроде L-BFGS часто являются одним из самых эффективных вариантов: каждый шаг сопоставим по стоимости с вычислением градиента, а сходимость значительно лучше, чем у методов первого порядка.

Эти методы могут составить конкуренцию даже самым популярным методам оптимизации, таким как Adam.

Ускорение сходимости и сравнение методов

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

Метод Ньютона же обладает квадратичной сходимостью в окрестности решения: грубо говоря, ошибка на итерации пропорциональна квадрату ошибки на итерации .

Квазиньютоновские методы (такие, как BFGS) обычно достигают суперлинейной сходимости — это скорость между линейной и квадратичной. В таблице ниже мы суммировали различия между методами первого и второго порядка:

Итак, мы увидели, что методы второго порядка выигрывают по числу итераций до сходимости (требуется меньше шагов), но каждый их шаг существенно дороже. В задачах малой или средней размерности метод Ньютона может быть теоретически оптимальным по скорости сходимости, тогда как в задачах большой размерности часто предпочитают квазиньютоновские алгоритмы или специализированные методы, чтобы избежать работы с полноразмерным Гессианом.

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

А как быть с оптимизацией в этом случае? Об этом мы как раз сейчас и поговорим.

Условная оптимизация

В реальных задачах машинного обучения мы редко ищем минимум функции потерь в вакууме. Часто нам нужно соблюдать определённые ограничения. Классический пример — регуляризация.

Мы хотим не просто минимизировать ошибку на обучающих данных, но и сделать это так, чтобы веса модели не становились слишком большими. Это помогает избежать переобучения и улучшить обобщающую способность модели. Такая задача — найти минимум функции при выполнении дополнительных условий — называется задачей условной оптимизации.

Метод множителей Лагранжа

Рассмотрим классическую задачу: требуется найти экстремум функции , если задано ограничение в виде равенства . Метод множителей Лагранжа предлагает элегантный подход к решению таких задач.

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

В точке касания градиенты обеих функций должны быть направлены одинаково. Поскольку градиент всегда перпендикулярен линии уровня, это условие означает, что градиенты и должны быть коллинеарны. Математически это записывается так:

Здесь — некоторое число, называемое множителем Лагранжа.

Чтобы решить задачу с ограничением, мы вводим вспомогательную функцию — функцию Лагранжа (или лагранжиан):

Магия метода Лагранжа заключается в том, что задача условной оптимизации для функции сводится к поиску обычной критической точки, но уже для лагранжиана , без учёта ограничений. Приравнивая градиент лагранжиана по всем переменным (включая и ) к нулю, мы получаем систему уравнений, которая одновременно включает условие коллинеарности градиентов и само уравнение ограничения.

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

Представьте, что ограничение немного изменилось и стало , где — малое число. Тогда оптимальное значение функции тоже изменится. Скорость этого изменения по отношению к и есть .

В экономике величину называют теневой ценой. Например, если — это прибыль, а — ограничение на ресурсы (скажем, количество доступной стали), то показывает, насколько вырастет прибыль, если прибавить ещё одну единицу этого ресурса.

В машинном обучении, как мы увидим далее, переменная играет ключевую роль: она количественно выражает компромисс между минимизацией функции потерь и усложнением модели.

Теорема Каруша — Куна — Таккера (KKT): оптимизация при неравенствах

Метод Лагранжа хорошо подходит для задач с ограничениями в виде равенств. Однако на практике мы чаще сталкиваемся с ограничениями-неравенствами, например . В таких случаях используется более общий подход — условия Каруша — Куна — Таккера (ККТ).

Рассмотрим задачу оптимизации

при условиях

Тогда лагранжиан будет задаваться так:

где — множители Лагранжа для ограничений-равенств, а — множители для ограничений-неравенств.

Условия KKT представляют собой систему необходимых условий, которым должна удовлетворять точка, чтобы быть решением задачи с ограничениями-неравенствами.

Интуитивно их можно разбить на четыре основные группы:

1. Стационарность. Градиент лагранжиана по параметрам должен быть равен нулю. Это условие аналогично первому условию из метода Лагранжа.
2. Допустимость по прямой задаче. Точка-решение обязана удовлетворять всем заданным ограничениям — как в форме равенств, так и в форме неравенств.
3. Допустимость по двойственной задаче. Множители Лагранжа, связанные с ограничениями-неравенствами, должны быть неотрицательными.
4. Дополняющая нежёсткость. Это ключевое условие. Для каждого ограничения-неравенства произведение соответствующего множителя на значение ограничения в оптимальной точке должно равняться нулю:

Это означает, что либо ограничение активно (в точности равно нулю), либо соответствующий ему множитель равен нулю.

На первый взгляд условие дополняющей нежёсткости может показаться абстрактным. Однако на деле это изящный и логичный переключатель, выражающий простую идею. Оно утверждает, что для любого ограничения-неравенства в точке оптимума возможно только одно из двух:

• Случай A: ограничение неактивно. Это означает, что оптимальное решение лежит строго внутри допустимой области, то есть . Такое ограничение не влияет на решение, оно неактуально и не мешает нам двигаться в нужном направлении. В этом случае его множитель обязан быть равен нулю, поскольку ни влияния, ни цены у такого ограничения нет.
• Случай B: ограничение активно. Это ситуация, когда решение располагается ровно на границе допустимой области: . Ограничение становится жёстким — оно мешает двигаться дальше. Здесь уже может возникнуть ненулевая «цена» этого ограничения, и множитель может быть больше нуля.

💡 Таким образом, условие дополняющей нежёсткости элегантно кодирует простую идею: ограничение имеет вес только тогда, когда оно активно.

Оптимизация с ограничениями и связь с регуляризацией

Теперь становится ясно, что теория условной оптимизации напрямую связана с одним из ключевых инструментов машинного обучения — регуляризацией. Регуляризация — это инструмент для снижения переобучения моделей, которое опосредованно связано с большими весами.

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

При регуляризации обычно функция потерь имеет вид:

где — исходный лосс, а — регуляризатор.

Ниже перечислим самые популярные виды регуляризаторов.

• -регуляризация (Ridge Regression). При Ridge-регуляризции мы минимизируем функцию потерь с добавлением штрафного слагаемого . Это эквивалентно решению задачи условной оптимизации с ограничением для некоторого значения . Геометрически это означает, что мы ищем минимум не во всём пространстве, а только внутри или на границе гиперсферы. Обычно решение находится в той точке, где линия уровня функции потерь касается этой гиперсферы.
• -регуляризация (Lasso). Аналогично минимизация функции потерь с -штрафом соответствует задаче условной оптимизации с ограничением . В геометрических терминах допустимая область — это гиперромб (в двумерном пространстве — ромб, в трёхмерном — октаэдр).

Ключевое различие между - и -регуляризациями заключается в форме ограничивающих областей. В отличие от гладкой сферы , -область (ромб) имеет острые углы, ориентированные вдоль осей координат.

Если линии уровня функции потерь (представьте расширяющиеся круги) соприкасаются с этой областью, они с большей вероятностью коснутся одного из острых углов, чем гладкой поверхности (окружности или сферы). Такое касание в углу означает, что одна из компонент вектора весов становится равной нулю.

Таким образом, -регуляризация естественным образом зануляет веса ненужных признаков, эффективно выполняя их отбор. Зануление весов делает модель более простой, интерпретируемой и устойчивой в силу уменьшения числа её параметров.

Теперь вы знаете не только как оптимизировать функции, но и как решать задачи оптимизации с дополнительными условиями. В этом параграфе хочется ещё обсудить отдельный класс задач оптимизации, с которым мы сталкиваемся в практических кейсах очень часто — это выпуклая оптимизация.

Выпуклая оптимизация

Теперь перейдём к теме выпуклой оптимизации. Это класс оптимизационных задач, в которых целевая функция является выпуклой, и допустимое множество (область допустимых решений) тоже выпуклое. Интерес к выпуклым задачам обусловлен тем, что они обладают весьма приятными математическими свойствами, гарантирующими эффективность и надёжность поиска глобального решения.

Выпуклые функции и множества

Выпуклым множеством называется множество , для которого любой отрезок, соединяющий две произвольные точки из , целиком содержится в . Формально: и точка также принадлежит .

Геометрически это означает отсутствие выемок: фигура без впадин, напоминающая сплошной выпуклый полигон или овал. Например, круг или выпуклый многоугольник — выпуклые множества, тогда как область в форме полумесяца — нет.

Понятие выпуклости множества важно, потому что многие ограничения в оптимизационных задачах образуют выпуклые области (например, системы линейных неравенств задают выпуклый многогранник допустимых решений).

Выпуклая функция — это функция, график которой изгибается вверх, как чаша или буква U. Эквивалентно для любой пары точек и на графике точка на хорде между ними всегда лежит выше графика:

Иными словами, прямая, соединяющая две произвольные точки на графике, не опускается ниже самой кривой. Визуально это заметно на рисунке: для функции на картинке выше любой отрезок между двумя её точками лежит над ней.

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

Для дважды дифференцируемых функций полезным признаком выпуклости служит знак второй производной.

• В одномерном случае функция выпукла тогда и только тогда, когда для всех (вторая производная неотрицательна).
• В многомерном случае выпуклость гладкой функции эквивалентна тому, что её матрица Гессе является положительно полуопределённой на всей области определения (все собственные значения неотрицательны).

💡 Таким образом, положительная (полу)определённость Гессиана — достаточное условие выпуклости функции.

Например, функция с выпукла, поскольку её Гессиан положительно определён. А вот функция с седловой точкой, как , невыпукла, так как Гессиан имеет отрицательное направление.

Свойства выпуклых оптимизационных задач

Оптимизационная задача вида

где — выпуклая функция, а — выпуклое множество допустимых решений, называется выпуклой задачей оптимизации. Такие задачи обладают рядом важных свойств:

• локальные минимумы являются глобальными;
• единственность решения (при строгой выпуклости);
• сильная дуальность;
• эффективные алгоритмы решения.

Рассмотрим их подробнее.

Локальные минимумы являются глобальными

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

Формально для выпуклых дифференцируемых функций справедливо сильное утверждение: условие стационарности является не только необходимым, но и достаточным для оптимальности.

Другими словами, если и , то — точное глобальное решение задачи . Это крайне важное упрощение по сравнению с невыпуклыми задачами, где градиент 0 мог бы означать как минимум, так и максимум или седловую точку.

Единственность решения (при строгой выпуклости)

Выпуклая функция может иметь не одно, а целое множество глобальных минимумов: например, подойдёт любая точка на плато с минимальным значением. Однако если функция строго выпуклая (грубо говоря, график загнут вверх без участков линейности), то глобальный минимум единственный. Строгая выпуклость означает, что неравенство выпуклости строгое для любых двух различных точек, и из этого следует, что контур уровня глобального минимума сводится к одной точке.

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

Если же решение не единственно (например, множество решений выпуклой задачи образует отрезок или площадь), обычно выбирают любое или добавляют небольшую регуляризацию для выбора конкретного решения.

Сильная дуальность

Выпуклые задачи, удовлетворяющие некоторым техническим условиям (условия Слейтера для ограничений), обладают нулевым дуальным разрывом. Это значит, что можно сформулировать двойственную задачу, — решить её часто проще, чем прямую, — и получить тот же оптимум, что и в исходной постановке. Сильная дуальность позволяет эффективно использовать метод множителей Лагранжа и методы прямо-двойственной оптимизации на выпуклых задачах.

Например, в задачах SVM и LASSO составляются двойственные формулировки для более эффективного решения или для теоретического анализа — эти двойственные задачи проще, поскольку тоже выпуклы.

Эффективные алгоритмы решения

Для многих классов выпуклых задач разработаны полиномиальные алгоритмы, гарантирующие нахождение оптимума за разумное время.

Также для больших безусловных выпуклых задач существуют градиентные методы оптимизации, чью скорость сходимости можно строго проанализировать (например, метод Нестерова с ускорением градиента обеспечивает оптимальный порядок для гладких выпуклых функций).

Таким образом, выпуклость не только упрощает теорию (гарантируя глобальный минимум), но и на практике означает, что у нас есть надёжные методы для поиска решения.

Гарантия глобального минимума

Итак, выше мы выяснили, что одно из главных следствий выпуклости — гарантия нахождения глобального оптимума при использовании любых корректных методов оптимизации.

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

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

Представьте, что мы бегаем с завязанными глазами по ландшафту в поисках самой низкой точки. Если ландшафт выпуклый, то спускаясь всегда вниз по склону, мы непременно окажемся в абсолютном минимуме, из которого уже никуда не спуститься. В невыпуклом «холмистом» ландшафте такой гарантии нет: можно спуститься в локальную впадину и не узнать, что за соседним холмом есть куда более глубокая яма (более лучший минимум).

В машинном обучении и прикладной статистике многие важные задачи ставятся именно как задачи выпуклой оптимизации, что обеспечивает алгоритмам обучения гарантированное нахождение наилучшего решения на обучающих данных. Рассмотрим два известных примера.

Метод опорных векторов (Support Vector Machine, SVM)

Классический SVM для линейной классификации требует решить задачу минимизации выпуклого функционала:

Здесь:

• — вектор весов модели;
• — смещение (англ. — bias);
• — вектор признаков -го объекта;
• — метка класса -го объекта;
• — число объектов в обучающей выборке;
• — коэффициент регуляризации.

По сути (это можно доказать или почитать здесь), при решении задачи SVM мы ищем веса, которые одновременно:

• максимизируют ширину разделяющей полосы;
• минимизируют количество нарушений разделения данных.

Эта задача является задачей выпуклого квадратичного программирования и, в частности, строго выпуклой, имеющей единственное решение. Функционал SVM — сумма квадратичного регуляризационного члена и кусочно-линейной функции потерь (англ. — hinge-loss), которая, несмотря на негладкость, выпукла. Ограничения линейны.

Благодаря выпуклости существуют эффективные алгоритмы для нахождения оптимальной разделяющей гиперплоскости. На практике это означает, что обучение SVM на любом фиксированном наборе данных всегда придёт к одному и тому же оптимальному классификатору (при фиксированных параметрах регуляризации ), вне зависимости от начальных условий алгоритма.

Регрессия Lasso

Задача Lasso (англ. — Least Absolute Shrinkage and Selection Operator) — это минимизация функции ошибки (обычно суммы квадратов отклонений) с L1-регуляризатором. Эта задача оптимизации также является выпуклой: квадратичная функция ошибки выпукла, норма — выпуклый (хоть и негладкий) функционал, а ограничение задаёт выпуклое множество (ромб в пространстве коэффициентов).

Таким образом, Lasso — типичный пример выпуклой, но негладкой задачи. Выпуклость гарантирует, что методы оптимизации смогут найти глобальный минимум функции потерь.

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

---

Подводя итог, выпуклая оптимизация предоставляет мощный инструментарий для теории и практики.

С одной стороны, выпуклые задачи имеют строгие гарантии сходимости алгоритмов (включая оценку скорости сходимости) и единственности решения.

С другой стороны, множество реальных задач сводится к выпуклым формулировкам — от классических методов машинного обучения (SVM, логистическая регрессия, LASSO, Ridge) до задач управления, экономики и инженерии.

Когда задача выпукла, мы можем быть уверены, что, выбрав подходящий метод (градиентный спуск, метод Ньютона или аналог), мы найдём глобально оптимальное решение эффективно и надёжно.

На этом мы замыкаем главную линию этой главы: от поведения функций и локальных приближений — к оптимизации и строгим гарантиям. В следующем, заключительном параграфе подведём итоги и соберём ключевые идеи в одну цельную картину.