Наискорейший спуск и метод Ньютона на языке Python, с нуля Сравнение

Python Сравнение наискорейшего спуска и метода Ньютона с нуля

Изображение автора.

Оглавление

  1. Введение
  2. Постановка задачи и метод наискорейшего спуска
  3. Метод Ньютона
  4. Реализация
  5. Выводы и окончательное сравнение

1. Введение

В предыдущей публикации мы исследовали популярный метод наискорейшего спуска для оптимизации и реализовали его с нуля на Python:

Реализация алгоритма наискорейшего спуска на Python с нуля

Оглавление

towardsdatascience.com

В этой статье мы собираемся представить метод Ньютона и поделиться пошаговой реализацией, сравнивая его с методом наискорейшего спуска.

2. Постановка задачи и метод наискорейшего спуска

Оптимизация – это процесс поиска набора переменных x, которые минимизируют целевую функцию f(x):

Для решения этой задачи мы можем выбрать начальную точку в координатном пространстве и итеративно приближаться к лучшей аппроксимации минимума с помощью направления поиска p:

В этом выражении:

  • x – входная переменная;
  • k – текущая итерация;
  • p – направление поиска;
  • α > 0 – шаг или длина шага; описывает, насколько мы должны двигаться вдоль направления p.

Направление поиска

В методе наискорейшего спуска направление поиска pₖ является отрицательным градиентом -∇f(xₖ), вычисленным в текущей итерации xₖ:

Минимум – это стационарная точка, поэтому разумно остановить алгоритм, когда норма градиента меньше заданной допускаемой погрешности.

Длина шага

Длина шага α в идеале является минимизатором следующей целевой функции φ(α):

Тем не менее, эта дополнительная задача оптимизации может быть непрактичной и дорогостоящей. Ее решение требует множества вычислений f(x) и ∇f(x). Методы приближенного линейного поиска…