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

В соответствии с основной идеей градиентного метода минимизирующая последовательность строится по правилу (6.3), т.е. в качестве направления убывания функции выбирается направление антиградиента ( ), которое, как показано выше, обеспечивает в малой окрестности точки наискорейшее убывание функции . В качестве длины шага в этом варианте градиентного метода находится какое-либо число , обеспечивающее условие монотонного убывания функции

. (6.4)

С этой целью задается какое-либо число . При этом для каждого проверяют условие монотонного убывания (6.4), и в случае его нарушения величину дробят до тех пор, пока не восстановится монотонность метода.

Приведем алгоритм одного из вариантов метода градиентного спуска.

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

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

Шаг 2. Найти новую точку в направлении антиградиента и вычислить .

Шаг 3. Проверить неравенство

, (6.5)

где - произвольно выбранная константа, одинаковая для всех итераций.

Шаг 4. Если неравенство (6.5) выполняется, то положить , , и перейти к шагу 1, иначе - перейти к шагу 3.

Шаг 5. Положить , где и перейти к шагу 2.

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

Замечание. Вблизи стационарной точки функции величина становится малой. Это может привести к замедлению сходимости последовательности . Поэтому в (6.3) вместо вектора антиградиента используют вектор единичной длины .

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

Теорема 6.1. Если функция ограничена снизу, ее градиент удовлетворяет условию Липшица, т.е.

(6.6)

с конечной константой при любых , а выбор производится описанным способом, то для процесса (6.3) норма градиента при , какова бы ни была начальная точка .

Д о к а з а т е л ь с т в о. По теореме о среднем

,

где . Тогда учитывая, что в рассматриваемой итерационной процедуре имеем

В силу неравенства Коши-Буняковского

и условия Липшица (6.6) имеют место неравенства

.

Учитывая, что , получаем

.

Из полученного соотношения видно, что существуют , при которых неравенство (6.5) справедливо. Для этого достаточно выбрать значение параметра , удовлетворяющее условию . Поскольку - ограниченная величина, а , то всегда можно это сделать.

Таким образом, если выбирать по указанному способу, то

. (6.7)

Отсюда с учетом того, что правило выбора при любом гарантирует (в качестве можно взять любую константу, не превосходящую )), следует, что при любом , если и что

. (6.8)

Далее поскольку функция ограниченна снизу и при любом , то при

(6.9)

Тогда из (6.8), (6.9) вытекает, что при .