Градиентный метод с дроблением шага.
В этом варианте градиентного метода величина шага αn на каждой итерации выбирается из условия выполнения неравенства
| f(xn+1) = f(xn – αnf ′(xn)) ≤ f(xn) – εαn||f ′(xn)||2, | (11) |
где ε ∈ (0, 1) — некоторая заранее выбранная константа. Условие (11) гарантирует (если, конечно, такие αn удастся найти), что получающаяся последовательность будет релаксационной. Процедуру нахождения такого αn обычно оформляют так. Выбирается число δ ∈ (0, 1) и некоторый начальный шаг α0. Теперь для каждого n полагают αn = α0 и делают шаг градиентного метода. Если с таким αn условие (11) выполняется, то переходят к следующему n. Если же (11) не выполняется, то умножают αn на δ ("дробят шаг") и повторяют эту процедуру до тех пор пока неравенство (9) не будет выполняться. В условиях теоремы 1. эта процедура для каждого n за конечное число шагов приводит к нужному αn.
З а д а ч а 8. Докажите (воспользуйтесь неравенством (8)).
З а д а ч а 9. Сходится ли градиентный метод с дроблением шага для функции f(x) = |x|p при p ∈ (1, 2)?
Можно показать, что в условиях теоремы 2. градиентный метод с дроблением шага линейно сходится . Описанный алгоритм избавляет нас от проблемы выбора α на каждом шаге, заменяя ее на проблему выбора параметров ε, δ и α0, к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.
|
|
|
Метод наискорейшего спуска.
Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки xn будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче L = {x ∈ Rm: x = xn – αf ′(xn); α ≥ 0}:
| αn = argminα∈[0, ∞)f(xn – αf ′(xn)). | (12) |
Рис. 5.
Другими словами, αn выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис. 5). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны. В самом деле, поскольку функция φ: α → f(xn – αf ′(xn)) достигает минимума при α = αn, точка αn является стационарной точкой функции φ:
|
| = (f ′(xn – αnf ′(xn)), –f ′(xn)) = –(f ′(xn+1), f ′(xn)). |
Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации (12). Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом .
|
|
|
В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.
З а д а ч а 10. Докажите, что если f(x) = (Ax, x)/2 + (b, x) + c, где A — симметричный оператор в Rm, а b, c ∈ Rm, то шаг αn метода наискорейшего спуска задается явной формулой
|
З а д а ч а 11. Пусть λ1, ..., λm — собственные числа оператора A. Покажите, что градиентный метод для функции f(x) = (Ax, x)/2 + (b, x) + c с шагами α0 = 1/λ1, α1 = 1/λ2, ..., αm–1 = 1/λm за m шагов дает точное решение: xm = x*.
Дата добавления: 2022-06-11; просмотров: 24; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!