Метод градиентного спуска с дроблением шага

Как известно из курсов анализа, градиент скалярной функции f(x) в некоторой точке x_k направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня (поверх­ности постоянного значения функции f(x), проходящей через точку x_k). Вектор, противоположный градиенту f’(x_k,), антиградиент, направлен в сторону наискорейшего убывания функции f(x). Выбирая в качестве направления спуска p_k антиградиент функции f(x) в точке x_k, мы приходим к итерационному процессу вида

(6.1)

В координатной форме этот процесс записывается следу­ющим образом:

(6.2)

Все итерационные процессы, в которых направление дви­жения на каждом шаге совпадает с антиградиентом (гра­диентом) функции, называются градиентными методами и отличаются друг от друга способами выбора шага a _k.

Пусть f(х) - выпуклая дифферен­цируемая во всем пространстве Е^п функция и требуется найти ее точку минимума х*. Выбрав произвольное начальное приближение построим последовательность

(6.3)

где величины (параметрические шаги) выбираются достаточно малыми для того, чтобы выполнялось условие:

(6.4)

В качестве условия окончания вычислений обычно используется близость к нулю градиента т. е. выполнение неравенств

или

, (6.5)

где e - заданное достаточно малое число, после чего полагают .

Если при некотором k условие (2.12) нарушается, то шаг в (6.3) уменьшают (дробят) в заданное число раз до выполнения неравен­ства (6.4) и продолжают вычисления.