2020-04-12
101
Изучим сходимость градиентного метода с постоянным шагом на примере функции
| f (x) = | x | p, |
где p > 1 (случай p ≤ 1 мы не рассматриваем, поскольку тогда функция f не будет гладкой, а мы такой случай не исследуем). Очевидно, задача (1) с такой функцией f имеет единственное решение x * = 0. Для этой функции приближения xn градиентного метода имеют вид:
| xn +1 = xn – α p | xn | p –1sign xn. | (6) |
Пределом этой последовательности может быть только 0. Действительно, если x ** = lim n →∞ xn ≠ 0, то, переходя к пределу в (6) при n → ∞, получаем противоречащее предположению x ** ≠ 0 равенство
| x ** = x ** – α p | x **| p –1sign x **, |
откуда x ** = 0. Очевидно также, что если x 0 = 0, то и xn = 0 при всех n.
Покажем, что если p < 2, то при любом шаге α > 0 и любом начальном приближении x 0 (за исключением не более чем счетного числа точек) приближения (6) не являются сходящимися. Для этого заметим, что если 0 < | xn | < (2/α p)1/2(2– p), то
| | xn +1| > | xn |. | (7) |
Поэтому, если xn не обращается в нуль, то она не может сходиться к нулю и, следовательно, не может сходиться вообще.
|
|
|
З а д а ч а 4. Докажите.
Таким образом, осталось доказать (7). В силу (6)
| | xn +1| = | xn – α p | xn | p –1 ·sign xn | = | xn |·| 1 –α p | xn | p –2·sign xn |. |
Остается заметить, что если 0 < | xn | < (2/α p)1/(2– p), то, как нетрудно видеть, |1 – α p | xn | p –2·sign xn | > 1, что и требовалось.
З а д а ч а 5. Покажите, что число начальных точек x 0, для которых xn обращается в нуль при некотором n (и, следовательно, при всех бóльших), не более чем счетно.
Если p = 2, т. е. f (x) = x 2, то (6) переписывается в виде
| | xn +1| = | xn |·|1 – 2α|. |
Поэтому, если α ∈ (0, 1), то |1 – 2α| < 1, а следовательно,
| | xn +1| = |1 – 2α| n +1·| x 0| → 0 при n → ∞. |
Если же α ≥ 1, то
| | xn +1| ≥ | xn |, |
и последовательность { xn }, начинающаяся из ненулевой начальной точки, расходится.
З а д а ч а 6. Докажите, что если p > 2, то градиентный метод (6) сходится при α p | x 0| p –2 < 2 и расходится при α p | x 0| p –2 ≥ 2 для любых начальных точек, за исключением может быть счетного множества.
Таким образом, есть функции, для которых градиентный метод не сходится даже при сколь угодно малом шаге α и есть функции, для которых он сходится только при достаточно малых шагах. В следующих пунктах мы приведем ряд теорем о сходимости градиентного метода.
Теорема об условной сходимости градиентного метода с постоянным шагом.
Теорема 1: Пусть в задаче (1) функция f ограничена снизу, непрерывно дифференцируема и, более того, f ′ удовлетворяет условию Липшица:
| || f ′(x) – f ′(y)|| ≤ Λ || x – y || при всех x, y ∈ R m. |
Тогда при α ∈ (0, 2/Λ) градиентный метод с постоянным шагом условно сходится.
Д о к а з а т е л ь с т в о. Положим zn = –α f ′(xn) и обозначим f (xn + tzn) через φ(t). Тогда, как легко видеть,
|
|
|
| φ′(t) = (f ′(xn + tzn), zn) |
и поэтому по формуле Ньютона — Лейбница для функции φ
| f (xn +1) – f (xn) = f (xn + zn) – f (xn) = φ(1) – φ(0) = |
|
| Добавив и отняв (f ′(xn), zn) = ∫01(f ′(xn), zn) ds и воспользовавшись неравенством (x, y) ≤ || x || · || y ||, получим |
|
|
Учитывая условие Липшица для f ′, эту цепочку можно продолжить:
| (8) |
Поскольку 1 – Λα/2 > 0, последовательность { f (xn)} не возрастает и, следовательно, релаксационность { xn } доказана. А так как в силу условий теоремы f еще и ограничена снизу, последовательность { f (xn)} сходится. Поэтому, в частности, f (xn +1) – f (xn) → 0 при n → ∞. Отсюда и из (8) получаем
|
Замечания о сходимости.
Подчеркнем, что теорема 1 не гарантирует сходимости метода, но лишь его условную сходимость, причем, локальную. Например, для функции f (x) = (1 + x 2)–1 на R последовательность { xn } градиентного метода с постоянным шагом, начинающаяся с произвольного x 0 стремится к ∞.
З а д а ч а 7. Докажите это.
Поскольку в теореме 1 градиент непрерывен, любая предельная точка последовательности { xn } является стационарной. Однако эта точка вовсе не обязана быть точкой минимума, даже локального. Например, рассмотрим для функции f (x) = x 2sign x градиентный метод с шагом α ∈ (0, 1/2). Тогда, как легко видеть, если x 0 > 0, то xn → 0 при n → ∞. Точка же x = 0 не является локальным минимумом функции f.
Заметим также, что описанный метод не различает точек локального и глобального минимумов. Поэтому для того, чтобы сделать заключение о сходимости xn к точке x * = argmin f (x) приходится налагать дополнительные ограничения, гарантирующие, в частности, существование и единственность решения задачи (1). Один вариант таких ограничений описывается ниже.
Теорема о линейной сходимости градиентного метода с постоянным шагом.
Теорема 2: Пусть выполнены условия теоремы 1. и, кроме того, f дважды непрерывно дифференцируема и сильно выпукла с константой λ. Тогда при α ∈ (0, 2/Λ) градиентный метод с шагом α сходится со скоростью геометрической прогрессии со знаменателем q = max{|1 – αλ|, |1 – αΛ |}:
| || xn – x *|| ≤ qn || x 0 – x *||. |
Д о к а з а т е л ь с т в о. Решение x * = argmin f (x) существует и единственно. Для функции F (x) = f ′(x) воспользуемся аналогом формулы Ньютона — Лейбница
|
Далее, f ′′(x) ≤ Λ при всех x ∈ R m. Кроме того, по условию f ′′(x) ≥ λ при тех же x. Поэтому, так как
| λ|| h ||2 ≤ (f ′′[ x * + s (xn – x *)] h, h) ≤ Λ || h ||2, |
выполнено неравенство
| (10) |
Интеграл, стоящий в этом неравенстве, определяет линейный (симметричный в силу симметричности f) оператор на R m, обозначим его L n. Неравенство (10) означает, что λ ≤ L n ≤ Λ. В силу (9) градиентный метод (4) записывается в виде
| xn +1 = xn – αL n (xn – x *). |
Спектр σ(I – αL n) оператора I – αL n состоит из чисел вида σ i = 1 –αλ i, где λ i ∈ σ(L n). В силу (10),
| 1 – αλ ≥ σ i ≥ 1 – αΛ, |
и следовательно
| || I – αL n || ≤ max{|1 –αλ|, |1 – αΛ |} = q. |
Таким образом,
| || xn +1 – xn || ≤ q || xn – x *||. |
Из этого неравенства и задачи 1 вытекает утверждение теоремы.
