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