Реферат: Теорема о линейной сходимости градиентного метода с постоянным шагом
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">Доклад поматематическим методам в экономике
<span Courier New"">“Теорема олинейной сходимости градиентного метода с постоянным шагом”
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">
<span Courier New"">ДВГУ
<span Courier New""><span Courier New"">
Теорема о линейной сходимости градиентногометода с постоянным шагом.
Пусть выполнены условия: функция fограничена снизу, непрерывнодифференцируема и f’ удовлетворяет условию Липшица и, кроме того, fдважды непрерывно дифференцируема и сильно выпукла с константойl. Тогда приaÎ(0, 2/L) градиентныйметод с шагом aсходится со скоростью геометрической прогрессиисо знаменателем q = max{|1 -al|, |1-aL|}:
<table cellpadding=«0» ">||xn -x*|| £qn||x0-x*||.
Д о к а з а т е л ь с т в о.Решение x* = argmin f(x) существует иединственно в силу теорем 1) и 2)<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;color:black;mso-ansi-language:RU;mso-fareast-language:RU; mso-bidi-language:AR-SA">[1]. Дляфункции F(x) = f
¢(x) воспользуемся аналогомформулы Ньютона — Лейбница <table cellpadding=«0» ">F(y) = F(x) +
ò
1
0
F ¢[x + s(y -x)](y-x) ds,
или, для x = x* и y = xn, учитывая, что f ¢(x*) = Q,
<table cellpadding=«0» ">
f ¢(xn) =
ò
1
0
f ¢¢[x* + s(xn -x*)](xn -x*) ds
(здесь воспользовались 3)<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;color:black;mso-ansi-language:RU;mso-fareast-language:RU; mso-bidi-language:AR-SA">[2]).Далее, в силу утверждения 4)<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;color:black;mso-ansi-language:RU;mso-fareast-language:RU; mso-bidi-language:AR-SA">[3]
f ¢¢(x) £Lпривсех x ÎRm. Кроме того (в силу 5)<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;color:black;mso-ansi-language:RU;mso-fareast-language:RU; mso-bidi-language:AR-SA">[4]), поусловию f ¢¢(x) ³lпритех же x. Поэтому, так как <table cellpadding=«0» ">l||h||2 £(f ¢¢[x* + s(xn -x*)]h, h) £L||h||2,
выполнено неравенство
<table cellpadding=«0» ">
l||h||2 £
æ
è
æ
è
ò
1
0
f ¢¢[x* + s(xn -x*)] ds
ö
ø
h, h
ö
ø
£L||h||2.
(10)
Интеграл, стоящий в этом неравенстве, определяет линейный (симметричный в силу симметричности f) оператор на Rm, обозначим его <span Script MT Bold";color:black">Ln
. Неравенство (10) означает, что l£<span Script MT Bold";color:black">Ln£L. Всилу (9) градиентный метод (4) записывается в виде <table cellpadding=«0» ">xn+1= xn -a<span Script MT Bold";color:black">Ln
(xn -x*).Но тогда
<table cellpadding=«0» ">||xn+1 -xn|| = ||xn -x* -a<span Script MT Bold";color:black">Ln
(xn -x*)|| == ||(I -a<span Script MT Bold";color:black">Ln)(xn -x*)|| £||I -a<span Script MT Bold";color:black">Ln|| · ||xn -x*||.
Спектр s(I-a<span Script MT Bold";color:black">Ln
) оператора I-a<span Script MT Bold";color:black">Lnсостоит из чиселвида si= 1 -ali, где liÎs(<span Script MT Bold";color:black">Ln). В силу (10) и неравенства l£li£L, <table cellpadding=«0» ">1 -al³si³1 -aL,
и следовательно
<table cellpadding=«0» ">||I -a<span Script MT Bold";color:black">Ln||
£max{|1 -al|, |1 -aL|} = q.Таким образом,
<table cellpadding=«0» ">||xn+1 -xn|| £q||xn -x*||.
Из этого неравенства вытекает утверждение данной теоремы.
Оптимальный выбор шага.
Константа q,характеризующая скорость сходимости метода, зависит от шага a. Нетрудно видеть, что величина
<table cellpadding=«0» ">q= q(a) = max{|1 -al|, |1 -aL|}
минимальна, если шаг aвыбирается из условия |1 -al| =|1 -aL| (см. рис. 1), т. е. если a= a* =2/(l+ L). При таком выборе шага оценка сходимости будет наилучшейи будет характеризоваться величиной
<table cellpadding=«0» ">q= q* =
L-l
L+ l
.
<img src="/cache/referats/21651/image002.jpg" v:shapes="_x0000_i1026">
Рис. 1.
В качестве lи Lмогут выступать равномерные по xоценки сверху и снизу собственных значений оператора f ¢¢(x). Если l<< L, то q* »1 иметод сходится очень медленно. Геометрически случай l<< Lсоответствует функциям с сильно вытянутыми линиями уровня (см. рис. 2). Простейшим примером такой функции можетслужить функция на R2, задаваемаяформулой
<table cellpadding=«0» ">f(x1, x2) = lx21+ Lx22с l<< L.
<img src="/cache/referats/21651/image003.gif" v:shapes="_x0000_i1027">
Рис. 2.
Поведение итераций градиентного метода для этой функцииизображено на рис. 2 — они, быстро спустившись на «днооврага», затем медленно «зигзагообразно» приближаются к точкеминимума. Число m= L/l(характеризующее разброс собственных значений оператора f ¢¢(x)) называют числомобусловленности функцииf. Если m>> 1, то функции называют плохообусловленными или овражными. Для такихфункций градиентный метод сходится медленно.
Но даже для хорошо обусловленных функций проблема выборашага нетривиальна в силу отсутствия априорной информации о минимизируемойфункции. Если шаг выбирается малым (чтобы гарантировать сходимость), то методсходится медленно. Увеличение же шага (с целью ускорения сходимости) можетпривести к расходимости метода.
<span Courier New"">
<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">[1]
1) Теоремаединственности для строго выпуклой функции.Задача f(x) ®min, со строго выпуклой функциейне может иметь более одного решения.
2) Теорема оразрешимости для сильно выпуклой функции.
Задача f(x) ®min, сдифференцируемой сильно выпуклойфункцией разрешима.
<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;color:black;mso-ansi-language:RU;mso-fareast-language:RU; mso-bidi-language:AR-SA">[2]
3)[f ¢(x)]¢= f ¢¢(x).Поясним: здесь [f ¢(x)]¢— производная функции x®f ¢(x),действующей из Rm в Rm, а f ¢¢(x) —вторая производная функции f: Rm ®Rm.<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">[3]
4) Пусть F: Rm®Rkдифференцируема. Тогда F удовлетворяетусловию Липшица с константой L,в том и только том случае, если ||F ¢(x)|| £Lпри всех x ( существует и обратное утверждение).<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;color:black;mso-ansi-language:RU;mso-fareast-language:RU; mso-bidi-language:AR-SA">[4]
5)f ÎC2 сильно выпукла сконстантой c в том и только том случае, если f ¢¢(x) ³c привсех x ÎRm.