В исчислении , метод Ньютона является итерационным методом для нахождения корней из в дифференцируемой функции F , которые являются решениями уравнения F ( х ) = 0 . Таким образом , метод Ньютона может быть применен к производной F ' из в дважды дифференцируемой функции F , чтобы найти корни производной (решения F ' ( х ) = 0 ), также известный как критическую точку (математика) S из ж. Эти решения могут быть минимумами, максимумами или седловыми точками, см. Раздел «Несколько переменных» в Критической точке (математика), а также раздел «Геометрическая интерпретация» в этой статье. Это актуально при оптимизации , которая направлена на поиск (глобальных) минимумов функции f .
Метод Ньютона
Центральная проблема оптимизации - это минимизация функций. Давайте сначала рассмотрим случай функций одной переменной, т. Е. Функций одной действительной переменной. Позже мы рассмотрим более общий и более практичный многомерный случай.
Для дважды дифференцируемой функции , мы стремимся решить задачу оптимизации
Метод Ньютона пытается решить эту проблему путем построения последовательности от первоначального предположения (отправная точка) который сходится к минимизатору из используя последовательность Тейлоровских аппроксимаций второго порядка вокруг итерации. Разложение Тейлора второго порядка функции f вокруг является
Следующая итерация определяется так, чтобы минимизировать это квадратичное приближение в , и установка . Если вторая производная положительна, квадратичное приближение является выпуклой функцией от, а его минимум можно найти, установив производную равной нулю. С
минимум достигается для
Собирая все вместе, метод Ньютона выполняет итерацию
Геометрическая интерпретация
Геометрическая интерпретация методы Ньютона является то , что при каждой итерации, она сводится к подгонкам параболы на графику из по пробной стоимости , имеющий тот же наклон и кривизну, что и график в этой точке, а затем переход к максимуму или минимуму этой параболы (в более высоких измерениях это также может быть седловая точка ), см. ниже. Обратите внимание, что еслислучается быть квадратичной функцией, то точная экстремум находится в одном шаге. Применяя это простое наблюдение к простым квадратичным функциям стоимости, мы получаем различное поведение метода Ньютона:
- Для функции , у которого глобальный минимум равен 0, метод Ньютона сходится к 0 после 1 шага.
- Для функции , у которого глобальный максимум равен 0, метод Ньютона сходится к 0 после 1 шага.
Высшие измерения
Приведенную выше итерационную схему можно обобщить наразмеров, заменив производную градиентом (разные авторы используют разные обозначения градиента, в том числе), А также взаимный второй производной с обратным из матрицы Гесса (разные авторы используют различные обозначения для гессиана, в том числе). Таким образом, получается итерационная схема
Часто метод Ньютона модифицируют, чтобы включить небольшой размер шага. вместо :
Это часто делается для того, чтобы гарантировать выполнение условий Вульфа или более простых и эффективных условий Армийо на каждом этапе метода. Для размеров шага, отличных от 1, метод часто называют расслабленным или затухающим методом Ньютона.
Конвергенция
Если f - сильно выпуклая функция с липшицевым гессианом, то при условии, что достаточно близко к , последовательность сгенерированный методом Ньютона будет сходиться к (обязательно уникальному) минимизатору из квадратично быстро. [ необходима цитата ] То есть,
Вычисление направления Ньютона
Нахождение обратной величины гессиана в больших измерениях для вычисления направления Ньютона может быть дорогостоящей операцией. В таких случаях вместо прямого обращения гессиана лучше вычислить векторкак решение системы линейных уравнений
которое может быть решено различными факторизациями или приближенно (но с большой точностью) итерационными методами . Многие из этих методов применимы только к определенным типам уравнений, например, факторизация Холецкого и сопряженный градиент будут работать, только еслиположительно определенная матрица. Хотя это может показаться ограничением, часто это полезный индикатор того, что что-то пошло не так; например, если приближается проблема минимизации ине является положительно определенным, то итерации сходятся к седловой точке, а не к минимуму.
С другой стороны, если выполняется оптимизация с ограничениями (например, с множителями Лагранжа ), проблема может стать проблемой поиска седловой точки, и в этом случае гессиан будет симметричным неопределенным, а решение нужно будет сделать с помощью метода, который будет работать для таких, например, вариант факторизации Холецкого или метод сопряженных остатков .
Также существуют различные квазиньютоновские методы , в которых приближение гессиана (или его обратного напрямую) строится на основе изменений градиента.
Если гессиан близок к необратимой матрице , инвертированный гессиан может быть численно нестабильным, и решение может расходиться. В этом случае в прошлом были испробованы определенные обходные пути, которые с переменным успехом решали определенные проблемы. Например, можно изменить гессиан, добавив матрицу поправок чтобы сделать положительно определенный. Один из подходов состоит в том, чтобы диагонализовать гессен и выбрать чтобы имеет те же собственные векторы, что и гессиан, но каждое отрицательное собственное значение заменено на .
Подход, используемый в алгоритме Левенберга-Марквардта (который использует приближенный гессиан), заключается в добавлении масштабированной единичной матрицы к гессиану,, при необходимости масштабирования на каждой итерации. Для большихи малый гессиан, итерации будут вести себя как градиентный спуск с размером шага. Это приводит к более медленной, но более надежной сходимости, когда гессен не дает полезной информации.
Некоторые предостережения
В исходной версии метода Ньютона есть несколько предостережений:
Во-первых: это не работает, если гессиан не обратим. Это ясно из самого определения метода Ньютона, который требует взятия обратного гессиана.
Во-вторых: он может вообще не сходиться, но может войти в цикл, имеющий более 1 балла. См. Раздел «Анализ отказов» в методе Ньютона .
В-третьих: он может сходиться к седловой точке, а не к локальному минимуму, см. Раздел «Геометрическая интерпретация» в этой статье.
Популярные модификации метода Ньютона, такие как квазиньютоновские методы или алгоритм Левенберга-Марквардта, упомянутые выше, также имеют оговорки:
Например, обычно требуется, чтобы функция стоимости была (сильно) выпуклой, а гессиан был глобально ограниченным или липшицевым, например, это упоминается в разделе «Сходимость» данной статьи. Если посмотреть на статьи Левенберга и Марквардта в справочнике по алгоритму Левенберга-Марквардта , которые являются исходными источниками для упомянутого метода, можно увидеть, что в статье Левенберга практически нет теоретического анализа, а в статье Марквардта анализирует только локальную ситуацию и не доказывает результат глобальной конвергенции. Можно сравнить с методом поиска линии с обратным прослеживанием для градиентного спуска, который имеет хорошую теоретическую гарантию при более общих предположениях, может быть реализован и хорошо работает в практических крупномасштабных задачах, таких как глубокие нейронные сети.
Смотрите также
Заметки
Рекомендации
- Авриэль, Мардохей (2003). Нелинейное программирование: анализ и методы . Dover Publishing. ISBN 0-486-43227-0.
- Боннанс, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастизабал, Клаудиа А. (2006). Численная оптимизация: теоретические и практические аспекты . Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. DOI : 10.1007 / 978-3-540-35447-5 . ISBN 3-540-35445-X. Руководство по ремонту 2265882 .
- Флетчер, Роджер (1987). Практические методы оптимизации (2-е изд.). Нью-Йорк: Джон Вили и сыновья . ISBN 978-0-471-91547-8.
- Givens, Geof H .; Хоинг, Дженнифер А. (2013). Вычислительная статистика . Хобокен, Нью-Джерси: John Wiley & Sons. С. 24–58. ISBN 978-0-470-53331-4.
- Нокедаль, Хорхе; Райт, Стивен Дж. (1999). Численная оптимизация . Springer-Verlag. ISBN 0-387-98793-2.
- Ковалев, Дмитрий; Мищенко, Константин; Richtárik, Питер (2019). «Стохастический Ньютон и кубические методы Ньютона с простыми локальными линейно-квадратичными скоростями». arXiv : 1912.01597 [ cs.LG ].
Внешние ссылки
- Коренблюм, Даниэль (29 августа 2015 г.). «Визуализация Ньютона-Рафсона (1D)» . Bl.ocks . ffe9653768cb80dfc0da.