Доклад поматематическим методам в экономике
“Теорема олинейной сходимости градиентного метода с постоянным шагом”
ДВГУ
Теорема о линейной сходимости градиентногометода с постоянным шагом.
Пусть выполнены условия: функция 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,
выполнено неравенство
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.
Таким образом,
||xn+1 -xn|| £q||xn -x*||.
Из этого неравенства вытекает утверждение данной теоремы.
Оптимальный выбор шага.
Константа 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
f(x1, x2) = lx21+ Lx22с l
Рис. 2.
Поведение итераций градиентного метода для этой функцииизображено на рис. 2 — они, быстро спустившись на «днооврага», затем медленно «зигзагообразно» приближаются к точкеминимума. Число m= L/l(характеризующее разброс собственных значений оператора f ¢¢(x)) называют числомобусловленности функцииf. Если m>> 1, то функции называют плохообусловленными или овражными. Для такихфункций градиентный метод сходится медленно.
Но даже для хорошо обусловленных функций проблема выборашага нетривиальна в силу отсутствия априорной информации о минимизируемойфункции. Если шаг выбирается малым (чтобы гарантировать сходимость), то методсходится медленно. Увеличение же шага (с целью ускорения сходимости) можетпривести к расходимости метода.
[1] 1) Теоремаединственности для строго выпуклой функции.
Задача f(x) ®min, со строго выпуклой функциейне может иметь более одного решения.
2) Теорема оразрешимости для сильно выпуклой функции.
Задача f(x) ®min, сдифференцируемой сильно выпуклойфункцией разрешима.
[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.