Градиентный метод с дроблением шага

В этом варианте градиентного метода величина шага α ⁿ на каждой итерации выбирается из условия выполнения неравенства

где ε ∈ (0, 1) — некоторая заранее выбранная константа. Условие (11) гарантирует (если, конечно, такие α ⁿ удастся найти), что получающаяся последовательность будет релаксационной. Процедуру нахождения такого α ⁿ обычно оформляют так. Выбирается число δ ∈ (0, 1) и некоторый начальный шаг α⁰. Теперь для каждого n полагают α ⁿ = α⁰ и делают шаг градиентного метода. Если с таким α ⁿ условие (11) выполняется, то переходят к следующему n. Если же (11) не выполняется, то умножают α ⁿ на δ ("дробят шаг") и повторяют эту процедуру до тех пор пока неравенство (9) не будет выполняться. В условиях теоремы 1. эта процедура для каждого n за конечное число шагов приводит к нужному α ⁿ.

З а д а ч а 8. Докажите (воспользуйтесь неравенством (8)).

З а д а ч а 9. Сходится ли градиентный метод с дроблением шага для функции f (x) = | x | ^p при p ∈ (1, 2)?

Можно показать, что в условиях теоремы 2. градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора α на каждом шаге, заменяя ее на проблему выбора параметров ε, δ и α⁰, к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.

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

Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки xⁿ будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче L = { x ∈ R ^m: x = xⁿ – α f ′(xⁿ); α ≥ 0}:

Рис. 5.

Другими словами, α ⁿ выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис. 5). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны. В самом деле, поскольку функция φ: α → f (xⁿ – α f ′(xⁿ)) достигает минимума при α = α ⁿ, точка α ⁿ является стационарной точкой функции φ:

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

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

З а д а ч а 10. Докажите, что если f (x) = (Ax, x)/2 + (b, x) + c, где A — симметричный оператор в R ^m, а b, c ∈ R ^m, то шаг α ⁿ метода наискорейшего спуска задается явной формулой

З а д а ч а 11. Пусть λ¹,..., λ ^m — собственные числа оператора A. Покажите, что градиентный метод для функции f (x) = (Ax, x)/2 + (b, x) + c с шагами α⁰ = 1/λ¹, α¹ = 1/λ²,..., α ^{m –1} = 1/λ ^m за m шагов дает точное решение: x^m = x *.