Метод Ньютона в оптимизации

Метод нахождения стационарных точек функции

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

В исчислении метод Ньютона (также называемый Ньютоном–Рафсоном ) — это итерационный метод нахождения корней дифференцируемой функции , которые являются решениями уравнения . Однако для оптимизации дважды дифференцируемой наша цель — найти корни . Поэтому мы можем использовать метод Ньютона на ее производной, чтобы найти решения для , также известные как критические точки . Эти решения могут быть минимумами, максимумами или седловыми точками; см. раздел «Несколько переменных» в Критическая точка (математика) , а также раздел «Геометрическая интерпретация» в этой статье. Это актуально в оптимизации , которая направлена ​​на поиск (глобальных) минимумов функции . ${\displaystyle f}$ ${\displaystyle f(x)=0}$ ${\displaystyle f}$ ${\displaystyle f'}$ ${\displaystyle f'}$ ${\displaystyle f'(x)=0}$ ${\displaystyle f}$ ${\displaystyle f}$

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

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

Имея дважды дифференцируемую функцию , мы стремимся решить задачу оптимизации ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$

${\displaystyle \min _{x\in \mathbb {R} }f(x).}$

Метод Ньютона пытается решить эту проблему, строя последовательность из начального предположения (начальной точки) , которая сходится к минимизатору с помощью последовательности приближений Тейлора второго порядка вокруг итераций. Разложение Тейлора второго порядка для f вокруг есть ${\displaystyle \{x_{k}\}}$ ${\displaystyle x_{0}\in \mathbb {R} }$ ${\displaystyle x_{*}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle x_{k}}$

${\displaystyle f(x_{k}+t)\approx f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}.}$

Следующая итерация определяется так, чтобы минимизировать это квадратичное приближение в , и устанавливая . Если вторая производная положительна, квадратичное приближение является выпуклой функцией , и ее минимум можно найти, установив производную в ноль. Так как ${\displaystyle x_{k+1}}$ ${\displaystyle t}$ ${\displaystyle x_{k+1}=x_{k}+t}$ ${\displaystyle t}$

${\displaystyle \displaystyle 0={\frac {\rm {d}}{{\rm {d}}t}}\left(f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}\right)=f'(x_{k})+f''(x_{k})t,}$

минимум достигается для

${\displaystyle t=-{\frac {f'(x_{k})}{f''(x_{k})}}.}$

Собирая все вместе, метод Ньютона выполняет итерацию

${\displaystyle x_{k+1}=x_{k}+t=x_{k}-{\frac {f'(x_{k})}{f''(x_{k})}}.}$

Геометрическая интерпретация

Геометрическая интерпретация метода Ньютона заключается в том, что на каждой итерации он сводится к подгонке параболы к графику в пробном значении , имеющему тот же наклон и кривизну, что и график в этой точке, а затем переходу к максимуму или минимуму этой параболы (в более высоких измерениях это также может быть седловой точкой ), см. ниже. Обратите внимание, что если это квадратичная функция, то точный экстремум находится за один шаг. ${\displaystyle f(x)}$ ${\displaystyle x_{k}}$ ${\displaystyle f}$

Более высокие измерения

Приведенную выше итеративную схему можно обобщить на размерности, заменив производную градиентом ( разные авторы используют разные обозначения для градиента, включая ), а обратную величину второй производной — обратной матрицей Гессе (разные авторы используют разные обозначения для Гессе, включая ). Таким образом, получается итеративная схема ${\displaystyle d>1}$ ${\displaystyle f'(x)=\nabla f(x)=g_{f}(x)\in \mathbb {R} ^{d}}$ ${\displaystyle f''(x)=\nabla ^{2}f(x)=H_{f}(x)\in \mathbb {R} ^{d\times d}}$

${\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k}),\qquad k\geq 0.}$

Часто метод Ньютона модифицируют, чтобы включить небольшой размер шага вместо : ${\displaystyle 0<\gamma \leq 1}$ ${\displaystyle \gamma =1}$

${\displaystyle x_{k+1}=x_{k}-\gamma [f''(x_{k})]^{-1}f'(x_{k}).}$

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

Конвергенция

Если f — сильно выпуклая функция с липшицевым гессианом, то при условии, что достаточно близко к , последовательность , сгенерированная методом Ньютона, будет сходиться к (обязательно единственному) минимизатору квадратично быстро. ^[1] То есть, ${\displaystyle x_{0}}$ ${\displaystyle x_{*}=\arg \min f(x)}$ ${\displaystyle x_{0},x_{1},x_{2},\dots }$ ${\displaystyle x_{*}}$ ${\displaystyle f}$

${\displaystyle \|x_{k+1}-x_{*}\|\leq {\frac {1}{2}}\|x_{k}-x_{*}\|^{2},\qquad \forall k\geq 0.}$

Вычисление направления Ньютона

Нахождение инверсии гессиана в больших размерностях для вычисления направления Ньютона может быть дорогостоящей операцией. В таких случаях вместо прямого инвертирования гессиана лучше вычислить вектор как решение системы линейных уравнений ${\displaystyle h=-(f''(x_{k}))^{-1}f'(x_{k})}$ ${\displaystyle h}$

${\displaystyle [f''(x_{k})]h=-f'(x_{k})}$

которые могут быть решены различными факторизациями или приближенно (но с большой точностью) с использованием итерационных методов . Многие из этих методов применимы только к определенным типам уравнений, например, факторизация Холецкого и сопряженный градиент будут работать только если — положительно определенная матрица. Хотя это может показаться ограничением, это часто является полезным индикатором того, что что-то пошло не так; например, если приближается задача минимизации, и она не является положительно определенной, то итерации сходятся к седловой точке , а не к минимуму. ${\displaystyle f''(x_{k})}$ ${\displaystyle f''(x_{k})}$

С другой стороны, если выполняется ограниченная оптимизация (например, с использованием множителей Лагранжа ), то задача может стать задачей нахождения седловой точки, в этом случае гессиан будет симметричным неопределенным, и решение необходимо будет выполнять с помощью метода, который будет работать для таких задач, например, варианта факторизации Холецкого или метода сопряженных остатков . ${\displaystyle x_{k+1}}$ ${\displaystyle LDL^{\top }}$

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

Если гессиан близок к необратимой матрице , то инвертированный гессиан может быть численно нестабилен, а решение может расходиться. В этом случае в прошлом были испробованы некоторые обходные пути, которые имели разный успех с определенными проблемами. Например, можно изменить гессиан, добавив матрицу коррекции, чтобы сделать его положительно определенным. Один из подходов заключается в диагонализации гессиана и выборе так, чтобы он имел те же собственные векторы, что и гессиан, но с заменой каждого отрицательного собственного значения на . ${\displaystyle B_{k}}$ ${\displaystyle f''(x_{k})+B_{k}}$ ${\displaystyle B_{k}}$ ${\displaystyle f''(x_{k})+B_{k}}$ ${\displaystyle \epsilon >0}$

Подход, используемый в алгоритме Левенберга–Марквардта (который использует приближенный гессиан), заключается в добавлении к гессиану масштабированной единичной матрицы, с масштабом, корректируемым на каждой итерации по мере необходимости. Для больших и малых гессианов итерации будут вести себя как градиентный спуск с размером шага . Это приводит к более медленной, но более надежной сходимости, когда гессиан не предоставляет полезной информации. ${\displaystyle \mu I}$ ${\displaystyle \mu }$ ${\displaystyle 1/\mu }$

Некоторые предостережения

Метод Ньютона в его первоначальной версии имеет несколько оговорок:

1. Это не работает, если гессиан необратим. Это ясно из самого определения метода Ньютона, который требует взять обратный гессиан.
2. Он может вообще не сходиться, но может войти в цикл, имеющий более 1 точки. См. метод Ньютона § Анализ отказов .
3. Он может сходиться к седловой точке вместо локального минимума, см. раздел «Геометрическая интерпретация» в этой статье.

Популярные модификации метода Ньютона, такие как квазиньютоновские методы или алгоритм Левенберга-Марквардта, упомянутые выше, также имеют оговорки:

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

Смотрите также

• Квази-Ньютоновский метод
• Градиентный спуск
• Алгоритм Гаусса–Ньютона
• Алгоритм Левенберга–Марквардта
• Доверительный регион
• Оптимизация
• Метод Нелдера–Мида
• Самосогласованная функция — функция, для которой метод Ньютона имеет очень хорошую глобальную скорость сходимости. ^{[2] : Раздел 6.2}

Примечания

1. Нокедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Нью-Йорк: Springer. С. 44. ISBN 0387303030.
2. Немировски и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .

Ссылки

• Avriel, Mordecai (2003). Нелинейное программирование: анализ и методы . Dover Publishing. ISBN 0-486-43227-0.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Численная оптимизация: теоретические и практические аспекты . Universitext (Второе пересмотренное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. doi :10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. МР  2265882.
• Флетчер, Роджер (1987). Практические методы оптимизации (2-е изд.). Нью-Йорк: John Wiley & Sons . ISBN 978-0-471-91547-8.
• Гивенс, Джеф Х.; Хоетинг, Дженнифер А. (2013). Вычислительная статистика . Хобокен, Нью-Джерси: John Wiley & Sons. стр. 24–58. ISBN 978-0-470-53331-4.
• Нокедаль, Хорхе; Райт, Стивен Дж. (1999). Численная оптимизация . Springer-Verlag. ISBN 0-387-98793-2.
• Ковалёв, Дмитрий; Мищенко, Константин; Рихтарик, Питер (2019). «Стохастические методы Ньютона и кубические методы Ньютона с простыми локальными линейно-квадратичными скоростями». arXiv : 1912.01597 [cs.LG].

Внешние ссылки

• Коренблюм, Дэниел (29 августа 2015 г.). «Визуализация Ньютона-Рафсона (1D)». Блоки . ffe9653768cb80dfc0da.