Скачайте в формате документа WORD

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

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

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






ДВГУ


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

Пусть выполнены словия: функция сильно выпукла с константой сходится со скоростью геометрической прогрессии со знаменателем q = max<{|1 <-

||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]< m. Кроме того (в силу 5)[4]), по условию f ¢¢(x) ³

l<||h||2 £ (f ¢¢[x* + s(xn <-2,

выполнено неравенство


2 £ 

æ
è

æ
è

ò

1

0


f ¢¢[x* + s(xn <- ds

ö
ø

h, h

ö
ø


 £ L ||h||2.


(10)

Интеграл, стоящий в этом неравенстве, определяет линейный (симметричный в силу симметричности f) оператор на Rm, обозначим его Ln. Неравенство (10) означает, что n £ L. В силу (9) градиентный метод (4) записывается в виде

xn+1 = xn <- n(xn <- x*).

Но тогда

||xn+1 <- xn|| = ||xn <- x* <-aLn(xn <- x*)|| =

= ||(I <- n)(xn <- x*)|| £ ||I <- n||  ||xn <- x*||.

Спектр n) оператора I <- n состоит из чисел вида i = 1 <-ali, где i Î n). В силу (10) и неравенств i £ L ,

1 <- i ³ 1 <-

и следовательно

||I <- n|| £ max<{|1 <-al<|, |1 <-

Таким образом,

||xn+1 <- xn|| £ q||xn <- x*||.

Из этого неравенства вытекает тверждение даннойа теоремы.

Оптимальный выбор шага.

Константа q, характеризующая скорость сходимости метода, зависит от шага

q = q(

минимальна, если шаг рис. 1), т. е. если

q = q* = 

L <-


L +

.



Рис. 1.

В качестве рис. 2). Простейшим примером такой функции может служить функция на R2, задаваемая формулой

f(x1, x2) = 21+ L x22с


Рис. 2.

Поведение итераций градиентного метода для этой функции изображено на рис. 2 - они, быстро спустившись на "дно оврага", затем медленно "зигзагообразно" приближаются к точке минимума. Число

Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о минимизируемой функции. Если шаг выбирается малым (чтобы гарантировать сходимость), то метод сходится медленно. величение же шага (с целью скорения сходимости) может привести к расходимости метода.




[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.