Выбирается число d Î (0, 1) и некоторый начальный шаг a0. Теперь для каждого n полагают an = a0 и делают шаг градиентного метода. Если с таким an условие выполняется, то переходят к следующему n. Если же условие не выполняется, то умножают an на d («дробят шаг») и повторяют эту процедуру до тех пор пока равенство.
Градиентный метод с дроблением шага.
В этом варианте градиентного метода величина шага αn на каждой итерации выбирается из условия выполнения неравенства
где e Î (0, 1) — некоторая заранее выбранная константа. Условие гарантирует (если, конечно, такие an удастся найти), что получающаяся последовательность будет релаксационной. Процедуру нахождения такого an обычно оформляют так.
Выбирается число d Î (0, 1) и некоторый начальный шаг a0. Теперь для каждого n полагают an = a0 и делают шаг градиентного метода. Если с таким an условие выполняется, то переходят к следующему n. Если же условие не выполняется, то умножают an на d («дробят шаг») и повторяют эту процедуру до тех пор пока равенство
не будет выполняться. В условиях теоремы об условной сходимости градиентного метода с постоянным шагом эта процедура для каждого n за конечное число шагов приводит к нужному an.
Можно показать, что в условиях теоремы (о линейной сходимости градиентного метода с постоянным щагом) градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора a на каждом шаге, заменяя ее на проблему выбора параметров e, d и a0, к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.
Метод наискорейшего спуска.
Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки xn будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче L = {x Î Rm: x = xn — af ¢(xn); a ³ 0}: