Тогда при a Î (0, 2/L) градиентный метод с шагом a сходится со скоростью геометрической прогрессии со знаменателем q = max{|1 — al|, |1 — aL |}:
Д о к а з а т е л ь с т в о. Решение x* = argmin f(x) существует и единственно в силу теорем 1) и 2)[1]. Для функции F(x) = f ¢(x) воспользуемся аналогом формулы Ньютона — Лейбница
или, для x = x* и y = xn, учитывая, что f ¢(x*) = Q,
(здесь воспользовались 3)[2]). Далее, в силу утверждения 4)[3] f ¢¢(x) £ L при всех x Î Rm. Кроме того (в силу 5)[4]), по условию f ¢¢(x) ³ l при тех же x. Поэтому, так как
выполнено неравенство
æ
è
æ
è
ò
1
0
f ¢¢[x* + s(xn -x*)] ds
ö
ø
h, h
ö
ø
Нужна помощь в написании доклада?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
£ L ||h||2.
(10)
Интеграл, стоящий в этом неравенстве, определяет линейный (симметричный в силу симметричности f) оператор на Rm, обозначим его Ln. Неравенство (10) означает, что l £ Ln £ L. В силу (9) градиентный метод (4) записывается в виде
Но тогда
Спектр s(I — aLn) оператора I — aLn состоит из чисел вида si = 1 -ali, где li Î s(Ln). В силу (10) и неравенства l £ li £ L ,
и следовательно
Таким образом,
Из этого неравенства вытекает утверждение данной теоремы.
Оптимальный выбор шага.
Константа q, характеризующая скорость сходимости метода, зависит от шага a. Нетрудно видеть, что величина
минимальна, если шаг a выбирается из условия |1 — al| = |1 — aL | (см. рис. 1), т. е. если a = a* = 2/(l+ L). При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной
Рис. 1.
В качестве l и L могут выступать равномерные по x оценки сверху и снизу собственных значений оператора f ¢¢(x). Если l << L, то q* » 1 и метод сходится очень медленно. Геометрически случай l << L соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 2). Простейшим примером такой функции может служить функция на R2, задаваемая формулой
Рис. 2.
Нужна помощь в написании доклада?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
Поведение итераций градиентного метода для этой функции изображено на рис. 2 — они, быстро спустившись на «дно оврага», затем медленно «зигзагообразно» приближаются к точке минимума. Число m = L/l (характеризующее разброс собственных значений оператора f ¢¢(x)) называют числом обусловленности функции f. Если m >> 1, то функции называют плохо обусловленными или овражными. Для таких функций градиентный метод сходится медленно.
Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о минимизируемой функции. Если шаг выбирается малым (чтобы гарантировать сходимость), то метод сходится медленно. Увеличение же шага (с целью ускорения сходимости) может привести к расходимости метода.
[1] 1) Теорема единственности для строго выпуклой функции.
Задача f(x) ® min , со строго выпуклой функцией не может иметь более одного решения.
2) Теорема о разрешимости для сильно выпуклой функции.
[2] 3) [f ¢(x)]¢ = f ¢¢(x). Поясним: здесь [f ¢(x)]¢ — производная функции x ® f ¢(x), действующей из Rm в Rm, а f ¢¢(x) — вторая производная функции f: Rm ® Rm.
[3] 4) Пусть F: Rm ®Rk дифференцируема. Тогда F удовлетворяет условию Липшица с константой L, в том и только том случае, если ||F ¢(x)|| £ L при всех x ( существует и обратное утверждение).
[4] 5) f Î C2 сильно выпукла с константой c в том и только том случае, если f ¢¢(x) ³ c при всех x Î Rm.