Метод Ньютона в оптимизации - Newtons method in optimization

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

llIn исчисление, Метод Ньютона является итерационный метод для поиска корни из дифференцируемая функция F, которые являются решениями уравнение F (Икс) = 0. В оптимизация, Метод Ньютона применяется к производная ж ′ из дважды дифференцируемая функция ж найти корни производной (решения ж ′(Икс) = 0), также известный как стационарные точки из ж. Эти решения могут быть минимумами, максимумами или седловыми точками.^[1]

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

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

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

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

Метод Ньютона пытается решить эту проблему путем построения последовательность ${\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}}$, имеющий такие же уклоны и кривизну, что и поверхность в этой точке, а затем переход к максимуму или минимуму этого параболоида (в более высоких измерениях это также может быть точка перевала ).^[2] Обратите внимание, что если ${\displaystyle f}$ случается с быть квадратичная функция, то точный экстремум находится за один шаг.

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

Вышесказанное итерационная схема можно обобщить на ${\displaystyle d}$ размеров путем замены производной на градиент (разные авторы используют разные обозначения градиента, в том числе ${\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, метод часто называют расслабленным или затухающим методом Ньютона.

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

Если ж является сильно выпуклой функцией с липшицевым гессианом, то при условии, что ${\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 }$. Это приводит к более медленной, но более надежной сходимости, когда гессен не дает полезной информации.

Стохастический метод Ньютона

Многие практические проблемы оптимизации, особенно те, которые возникают в области науки о данных и машинного обучения, связаны с функцией ${\displaystyle f:\mathbb {R} ^{d}\to \mathbb {R} }$ которое возникает как среднее от очень большого числа более простых функций ${\displaystyle f_{i}}$:

${\displaystyle f(x)={\frac {1}{n}}\sum _{i=1}^{n}f_{i}(x).}$

В управляемом машинном обучении ${\displaystyle f_{i}(x)}$ представляет потерю модели, параметризованной вектором ${\displaystyle x\in \mathbb {R} ^{d}}$ на точке обучения данных ${\displaystyle i}$, и ${\displaystyle f(x)}$ таким образом отражает средние потери модели на наборе обучающих данных. К задачам этого типа относятся линейный метод наименьших квадратов, логистическая регрессия и глубокое обучение нейронной сети.

В этой ситуации метод Ньютона для минимизации ${\displaystyle f}$ принимает форму

${\displaystyle x_{k+1}=x_{k}-\left({\frac {1}{n}}\sum _{i=1}^{n}f''_{i}(x_{k})\right)^{-1}\left({\frac {1}{n}}\sum _{i=1}^{n}f_{i}'(x_{k})\right).}$

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

В этом большом ${\displaystyle n}$ режима, вышеупомянутый вопрос может быть решен путем рассмотрения стохастический метод Ньютона (СН) разработан и проанализирован Ковалевым, Мищенко и Рихтариком.^[3] SN - это обобщение метода Ньютона, которое позволяет гибко выбирать множество ${\displaystyle S_{k}}$ функций, для которых необходимо вычисление гессиана и градиента. Этот набор можно выбрать ${\displaystyle S_{k}=\{1,2,\dots ,n\}}$, и в этом случае SN сводится к методу Ньютона. Однако можно также выбрать ${\displaystyle S_{k}=\{i\}}$, куда ${\displaystyle i}$ является случайным элементом ${\displaystyle \{1,2,\dots ,n\}}$.

Метод. В общем, SN - это параметрическое семейство методов с параметром ${\displaystyle \tau \in \{1,2,\dots ,n\}}$ контроль размера партии. Данный ${\displaystyle \tau }$, в итерации ${\displaystyle k}$ мы позволяем ${\displaystyle S_{k}}$ быть случайным подмножеством ${\displaystyle \{1,2,\dots ,n\}}$ выбирается равномерно из всех подмножеств мощности ${\displaystyle \tau }$. То есть все подмножества мощности ${\displaystyle \tau }$ выбираются с вероятностью ${\displaystyle 1/{d \choose \tau }}$. Два описанных выше случая являются частными случаями этого для ${\displaystyle \tau =n}$ и ${\displaystyle \tau =1}$, соответственно.

Метод стохастического Ньютона поддерживает последовательность векторов ${\displaystyle x_{k}^{1},x_{k}^{2},\cdots ,x_{k}^{n}\in \mathbb {R} ^{d}}$ за ${\displaystyle k\geq 0}$. В начале, т.е. при ${\displaystyle k=0}$, эти векторы инициализируются произвольно. Разумный выбор - сделать их равными. Затем метод выполняет следующие шаги:

${\displaystyle Step\;1:\quad x_{k+1}=\left({\frac {1}{n}}\sum _{i=1}^{n}f''_{i}(x_{k}^{i})\right)^{-1}\left({\frac {1}{n}}\sum _{i=1}^{n}f''_{i}(x_{k}^{i})x_{k}^{i}-f_{i}'(x_{k}^{i})\right)}$

${\displaystyle Step\;2:\quad {\text{Sample }}S_{k}\subseteq \{1,2,\dots ,n\}}$

${\displaystyle Step\;3:\quad x_{k+1}^{i}={\begin{cases}x_{k+1}&i\in S_{k}\\x_{k}^{i}&i\notin S_{k}\end{cases}}.}$

Обратите внимание, что если ${\displaystyle x_{0}^{1}=x_{0}^{2}=\cdots =x_{0}^{n}}$ и ${\displaystyle \tau =n}$, SN сводится к описанному выше методу Ньютона. Однако, в отличие от метода Ньютона, при итерации ${\displaystyle k}$, SN необходимо вычислить градиенты и гессианы функций ${\displaystyle f_{i}}$ за ${\displaystyle i\in S_{k}}$ Только. В частности, размер партии ${\displaystyle \tau }$ может быть выбрана постоянной, и в этом случае стоимость каждой итерации SN составляет независимый из ${\displaystyle n}$.

Конвергенция. За ${\displaystyle \tau =n}$, SN имеет локальную квадратичную скорость сходимости, идентичную методу Ньютона. За ${\displaystyle \tau <n}$, SN имеет локальную линейную скорость сходимости, не зависящую от числа обусловленности. В частности, Ковалев, Мищенко и Рихтарик показали, что если ${\displaystyle f}$ является сильно выпуклым и имеет липшицево-гессиан, то, пока начальная итерация ${\displaystyle x_{0}^{1},x_{0}^{2},\cdots ,x_{0}^{n}}$ достаточно близки к (обязательно) единственному минимизатору ${\displaystyle x_{*}}$ из ${\displaystyle f}$, тогда

${\displaystyle {\rm {E}}\left[{\frac {1}{n}}\sum _{i=1}^{n}\|x_{k}^{i}-x_{*}\|^{2}\right]\leq \left(1-{\frac {3\tau }{4n}}\right)^{k}\left[{\frac {1}{n}}\sum _{i=1}^{n}\|x_{0}^{i}-x_{*}\|^{2}\right],}$

куда ${\displaystyle {\rm {E}}[\cdot ]}$ относится к математическому ожиданию относительно случайности, присущей алгоритму.

Это намного лучшая скорость, чем та, которую можно получить любым стохастическим методом первого порядка, таким как стохастический градиентный спуск. Действительно, скорость сходимости всех методов первого порядка зависит от числа обусловленности ${\displaystyle f}$, который обычно определяется как ${\displaystyle \kappa =L/\mu }$, куда ${\displaystyle 0<\mu \leq L}$ такие константы, что

${\displaystyle \mu I\preceq f''(x)\preceq LI,\qquad \forall x\in \mathbb {R} ^{d}.}$

Существуют различные методы, которые в некоторой степени могут уменьшать но который не может полностью устранить эффект кондиционирования ${\displaystyle \kappa }$ о скорости сходимости методов первого порядка. Эти методы включают в себя адаптивные размеры шагов, мини-выборку, выборку по важности, импульс Поляка, импульс Нестерова и уменьшение дисперсии. В отличие от всех этих техник, SN полностью устраняет эффект кондиционирования. Однако, как и метод Ньютона, SN страдает от зависимости от местный только гарантия сходимости.

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

• Квазиньютоновский метод
• Градиентный спуск
• Алгоритм Гаусса – Ньютона
• Алгоритм Левенберга-Марквардта
• Регион доверия
• Оптимизация
• Метод Нелдера – Мида

Примечания

1. «Относительные экстремумы». Ламарский университет. Получено 28 августа 2019.
2. Эдвардс, А. В. Ф. (1992). Вероятность (Расширенная ред.). Балтимор: Издательство Университета Джона Хопкинса. п. 129. ISBN  0-8018-4443-6.
3. Ковалев, Дмитрий; Мищенко, Константин; Richtárik, Питер (2019). «Стохастический Ньютон и кубические методы Ньютона с простыми локальными линейно-квадратичными скоростями». arXiv:1912.01597.

Рекомендации

• Авриэль, Мардохей (2003). Нелинейное программирование: анализ и методы.. Dover Publishing. 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.
• 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.