Метод наискорейшего спуска

В методе наискорейшего спуска минимизирующая последовательность также строится по правилу . Однако величина шага находится в результате решения следующей вспомогательной задачи. На луче , выходящем из точки и направленным по антиградиенту, введем функцию одной переменной и определим из условия

(6.10)

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

Опишем алгоритм метода наискорейшего спуска.

Шаг 0. Задать параметр точности , выбрать , положить .

Шаг 1. Найти и проверить условие достижения заданной точности . Если оно выполняется, то перейти к шагу 3, иначе - к шагу 2.

Шаг 2. Определить шаг , решив вспомогательную задачу с использованием алгоритма поразрядного поиска. Найти очередную точку положить и перейти к шагу 1.

Шаг 3. Завершить вычисления, положив .

Замечание. Градиентный метод имеет простой геометрический смысл. Оказывается, очередная точка минимизирующей последовательности лежит на луче . Причем, если определяется из условия (6.10), т.е. когда по лучу осуществляется исчерпывающий спуск, то находится в точке касания луча с линией уровня, проходящей через эту точку (см. теорему 4.1 и рис. 4.1). Далее можно понять, что чем ближе линии уровня к окружности, тем быстрее сходится градиентный метод. В тех же случаях, когда линии (поверхности) уровня функции сильно вытянуты и функция имеет так называемый «овражный» характер, процедура градиентного спуска сходится очень медленно. Это означает, что малое изменение некоторых переменных приводит к резкому изменению значения функции. Эта группа методов характеризует «склон оврага». По остальным переменным, задающим направление «дна оврага», функция меняется незначительно. Если точка лежит на «склоне оврага», то направление спуска из этой точки будет почти перпендикулярным к направлению «дна оврага», и в результате точки последовательности , полученные градиентным методом, будут поочередно находиться то на одном, то на другом «склоне оврага». Если «склоны оврага» достаточно круты, то такие скачки «со склона на склон» точек могут сильно замедлить сходимость градиентного метода. Для ускорения сходимости итерационной процедуры при поиске минимума «овражной» функции можно предложить следующий эвристический прием, называемый овражным методом.

Дата добавления: 2014-01-06