Методы многомерной оптимизации: градиентный спуск и метод Ньютона
Поиск наилучшего решения в мире множества вариантов
Задача оптимизации является одной из краеугольных в прикладной математике. Будь то проектирование крыла самолета с минимальным аэродинамическим сопротивлением, подбор параметров химического реактора для получения максимального выхода продукта или обучение глубокой нейронной сети, — математически все эти процессы сводятся к поиску минимума (или максимума) некоторой целевой функции. В реальных задачах эта функция зависит не от одного, а от сотен, тысяч или даже миллиардов параметров.
В случае функций одной переменной мы могли бы просто найти производную, приравнять ее к нулю и найти корни. Однако для многомерных функций со сложной топологией (с множеством локальных минимумов, оврагов и седловых точек) аналитическое решение получить невозможно. В игру вступают итерационные численные алгоритмы оптимизации, которые, подобно путнику в горах, шаг за шагом нащупывают путь в самую глубокую впадину.
Градиентный спуск: движение по наискорейшему склону
Самым известным и концептуально простым алгоритмом является метод градиентного спуска (Gradient Descent), предложенный еще Огюстеном Луи Коши. Градиент — это вектор, указывающий направление наискорейшего возрастания функции. Следовательно, антиградиент (вектор, взятый со знаком минус) указывает направление наискорейшего убывания.
Алгоритм стартует из случайной начальной точки. На каждом шаге мы вычисляем вектор градиента в текущей точке и делаем небольшой шаг в противоположном направлении. Размер этого шага определяется параметром, который называется «скоростью обучения» (learning rate). Главная проблема классического градиентного спуска — сильная зависимость от этого параметра. Если шаг слишком велик, алгоритм начнет перепрыгивать через минимум и расходиться; если слишком мал — сходимость растянется на долгие часы. Кроме того, в так называемых «овражных» функциях градиентный спуск начинает совершать зигзагообразные колебания поперек оврага, крайне медленно продвигаясь к его дну.
Метод Ньютона и учет кривизны пространства
Чтобы ускорить сходимость и избежать зигзагов в оврагах, необходимо использовать информацию не только о наклоне функции (первой производной), но и о ее кривизне. Эту информацию предоставляет матрица вторых производных, называемая матрицей Гессе (или гессианом). Использование гессиана лежит в основе многомерного метода Ньютона.
Метод Ньютона строит на каждом шаге квадратичную аппроксимацию целевой функции (в виде параболоида) и мгновенно прыгает в вершину этого параболоида. В окрестности минимума метод Ньютона обладает фантастической квадратичной скоростью сходимости. Однако вычисление, хранение и, что самое главное, обращение матрицы Гессе на каждом шаге (требующее решения огромной СЛАУ) делает классический метод Ньютона абсолютно неприменимым для задач с большим количеством параметров (например, при обучении нейросетей). Поэтому на практике используют квазиньютоновские методы (такие как популярный BFGS) или метод сопряженных градиентов, которые хитроумными способами оценивают кривизну пространства, не вычисляя сам гессиан в явном виде.