Обобщенный градиентный спуск
Пусть – выпуклая функция, определенная на евклидовом пространстве , – множество минимумов (оно может быть и пустым), – точка минимума; ; – субградиент функции в точке . Субградиент функции в точке есть вектор такой, что для всех . Из определения субградиента следует, что если , то (1) Геометрически формула (1) означает, что антисубградиент в точке образует острый угол с произвольным направлением, проведенным из в сторону точки с меньшим значением . Отсюда, если непусто, , то при движении из в направлении с достаточно малым шагом расстояние до убывает. Этот простой факт лежит в основе субградиентного метода или метода обобщенного градиентного спуска (ОГС), впервые предложенного в [1] в связи с решением сетевой транспортной задачи. Методом обобщенного градиентного спуска (ОГС) называется процедура построения минимизирующей последовательности , где – начальное приближение, а строятся по следующей рекуррентной формуле: (2) здесь – произвольный субградиент функции в точке , – шаговый множитель. Если , то – есть точкой минимума функции и процесс останавливается. В Институте кибернетики, начиная с 1962 года, были разработаны несколько вариантов ОГС, использующих соотношение (2). Эти результаты получены в период с 1962 по 1968 год и наиболее полно отражены в монографии [2], материал которой составила докторская диссертация Н.З.Шора 1970 года.
Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.
Чтобы численно решить уравнение методом простой итерации, его необходимо привести к следующей форме: , где — сжимающее отображение.
Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:
В предположении, что точка приближения «достаточно близка» к корню , и что заданная функциянепрерывна , окончательная формула для такова:
С учётом этого функция определяется выражением:
Эта функция в окрестности корня осуществляет сжимающее отображение[1], и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:
По теореме Банаха последовательность приближений стремится к корню уравнения .
Метод Ньютона — Рафсона
Метод Ньютона — Рафсона является улучшением метода Ньютона нахождения экстремума, описанного выше. Основное отличие заключается в том, что на очередной итерации каким-либо из методов одномерной оптимизации выбирается оптимальный шаг:
где Для оптимизации вычислений применяют следующее улучшение: вместо того, чтобы на каждой итерации заново вычислять гессиан целевой функции, ограничиваются начальным приближением и обновляют его лишь раз в шагов, либо не обновляют вовсе.