Теорема о линейной сходимости градиентного метода с постоянным шагом

  • Вид работы:
    Доклад
  • Предмет:
    Математика
  • Язык:
    Русский
    ,
    Формат файла:
    MS Word
    28,25 kb
  • Опубликовано:
    2008-12-09
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

Теорема о линейной сходимости градиентного метода с постоянным шагом

 

 

 

 

 

 

 

 

 

Доклад по математическим методам в экономике

“Теорема о линейной сходимости градиентного метода с постоянным шагом”

 

 

 

 

 

 

 

 

 

ДВГУ

 

 Теорема о линейной сходимости градиентного метода с постоянным шагом.

Пусть выполнены условия: функция 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.


Не нашли материал для своей работы?
Поможем написать уникальную работу
Без плагиата!