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

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

(6.10)

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

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

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

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

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

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

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

Овражный метод

Пусть в задаче безусловной оптимизации (4.1) функция носит овражный характер. Опишем простейший вариант овражного метода.

В начале поиска минимума «овражной функции» задаются две исходные точки , , из которых производят спуск с помощью какого-либо варианта градиентного метода и получают две точки , на «дне оврага». Затем строят новую точку , где – положительная постоянная, называемая овражным шагом. Вообще говоря, точка будет находиться на “склоне оврага”, поэтому, организовав спуск градиентным методом, получим следующую точку на “дне оврага”. Если таким образом построены точки , , то из точки

совершают спуск в следующую точку на «на дне оврага».

Эффективность овражного метода существенно зависит от выбора шага. Если шаг велик, то на крутых поворотах «оврага» точки могут слишком удаляться от «дна оврага» и спуск из точки в точку может потребовать большого объема вычислений. Кроме того, при больших на крутых поворотах может произойти выброс точки из «оврага», и правильное направление поиска точки минимума будет потеряно. Если же шаг слишком мал, то поиск может замедлиться и эффект от применения овражного метода может стать незначительным.

Скорость сходимости овражного метода может существенно возрасти, если величину овражного шага выбирать переменной, реагирующей на повороты «оврага». При этом желательно за счет увеличения овражного шага по возможности быстрее проходить прямолинейные участки на «дне оврага» на крутых поворотах «оврага» избежать выброса из «оврага» за счет уменьшения овражного шага. Кроме того, желательно добиться по возможности меньшего отклонения точек от «дна оврага» и тем самым сократить объем вычислений, требуемый на градиентный спуск из точки в точку . Интуитивно ясно, что для правильной реакции на поворот «оврага» надо учитывать «кривизну дна оврага», причем информацию о «кривизне» желательно получать из результатов предыдущих итераций овражного метода.

Был предложен следующий способ выбрать овражного шага

, , (6.11)

где - угол между векторами и , определяемый условием

,

а постоянная является параметром алгоритма. Точка тогда определяется так:

.

Разность в равенстве (6.11) связана с «кривизной дна оврага» и, кроме того, указывает направление изменения «кривизны». В самом деле, при переходе с участков «дна оврага» малой «кривизны» на участки с большей «кривизной» будем иметь . Тогда в силу (6.11) , т.е. овражный шаг уменьшается, приспосабливается к повороту «дна оврага», что в свою очередь приводит к уменьшению выброса точки на «склон оврага». При переходе с участков «дна оврага» большой кривизны на участки с меньшей «кривизной», наоборот, , поэтому овражный шаг увеличится и появится возможность сравнительно быстро пройти участок с малой «кривизной», в частности, прямолинейные участки на «дне оврага». Если «кривизна дна оврага» на некоторых участках остается постоянной, то разность будет близка к нулю, и поиск минимума на таких участках будет проводиться с почти постоянным шагом, сформированным с учетом величины «кривизны» при выходе на рассматриваемый участок.

Параметр в равенстве (6.11) регулирует «чувствительность» метода к изменению «кривизны дна оврага». Правильный выбор этого параметра во многом определяет скорость движения по «оврагу».