Метод Ньютона
Конструктор
Newton(; alphaguess = LineSearches.InitialStatic(),
linesearch = LineSearches.HagerZhang())Конструктор принимает два ключевых слова:
-
linesearch = a(d, x, p, x_new, g_new, phi0, dphi0, c), функция, выполняющая линейный поиск. См. раздел о линейном поиске. -
alphaguess = a(state, dphi0, d), функция для задания начального предположения для алгоритма линейного поиска. См. раздел о линейном поиске.
Описание
Метод Ньютона для оптимизации имеет долгую историю и в некотором смысле является золотым стандартом в оптимизации гладких функций без ограничений, по крайней мере с теоретической точки зрения. Его главное преимущество — квадратичная скорость сходимости вблизи локального оптимума. Его основным недостатком является то, что пользователь должен предоставить гессиан. Это может быть трудной, сложной или просто раздражающей задачей. Кроме того, его вычисление может потребовать больших вычислительных затрат.
Метод Ньютона для оптимизации заключается в применении метода Ньютона для решения систем уравнений, где в качестве уравнений выступают условия первого порядка, информирующие о том, что градиент должен быть равен нулевому вектору.
Разложение второго порядка по Тейлору левой части приводит к итеративной схеме
где обратная величина не вычисляется напрямую, а размер шага вычисляется путем решения
Это эквивалентно минимизации квадратичной модели вокруг текущего
Для функций, где получение является трудным или дорогостоящим, можно заменить гессиан другой положительно определенной матрицей, которая аппроксимирует его. Такие методы называются квазиньютоновскими. См. описание (L-)BFGS и градиентного спуска.
В незначительном окружении минимизатора метод Ньютона имеет квадратичную сходимость, но в глобальном масштабе он может сходиться медленнее или даже расходиться. Для обеспечения сходимости выполняется линейный поиск для каждого . Это равносильно замене приведенной выше формуле шага на
и поиску такого скаляра , чтобы получить достаточный спуск. Более подробную информацию см. в разделе о линейном поиске.
Кроме того, если функция локально вогнута, то шаг в приведенных выше формулах будет направлен по возрастанию, так как гессиан не будет положительно (полу-) определенным. Чтобы избежать этого, мы используем специализированный метод для расчета направления шага. Если гессиан является положительно полуопределенным, используется стандартный метод, если же нет, выполняется корректировка с помощью функций в PositiveFactorizations.jl.