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

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

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

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

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

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

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

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

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

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

$\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,$

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

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

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

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

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

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

Высшие измерения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

• Авриэль, Мордехай (2003). Нелинейное программирование: анализ и методы . Дуврское издательство. ISBN  0-486-43227-0 .
• Боннан, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастисабал, Клаудия А. (2006). Численная оптимизация: Теоретические и практические аспекты . Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. дои : 10.1007/978-3-540-35447-5 . ISBN  3-540-35445-Х . МР   2265882 .
• Флетчер, Роджер (1987). Практические методы оптимизации (2-е изд.). Нью-Йорк: Джон Уайли и сыновья . ISBN  978-0-471-91547-8 .
• Гивенс, Джефф Х.; Хотинг, Дженнифер А. (2013). Вычислительная статистика . Хобокен, Нью-Джерси: John Wiley & Sons. стр. 24–58. ISBN  978-0-470-53331-4 .
• Носедаль, Хорхе; Райт, Стивен Дж. (1999). Численная оптимизация . Спрингер-Верлаг. ISBN  0-387-98793-2 .
• Ковалев Дмитрий; Мищенко Константин; Рихтарик, Питер (2019). «Стохастические методы Ньютона и кубические методы Ньютона с простыми локальными линейно-квадратичными скоростями». arXiv : 1912.01597 [ cs.LG ].

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

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