Методы оптимизации. Конспект лекций (Буряков) (2003) (1125388), страница 6
Текст из файла (страница 6)
Отсюда следует, чтоak+1 6 ak −1kJ 0 (uk )k2H2L(5)Первая часть неравенства (4) следует из Теоремы 6.Докажем вторую часть неравенства. По Теореме 8 п. (b0 ) имеемκκak = J(uk ) − J(u∗ ) 6 hJ 0 (uk ), uk − u∗ i − kuk − u∗ k2 6 kJ 0 (uk )k·kuk − u∗ k − kuk − u∗ k2 .22Обозначим kuk − u∗ k = y, тогдаκak 6 kuk − u∗ k·y − y 2 .2Эта квадратичная функция от переменной y достигает максимума в точке y0 =Поэтому1ak 6kJ 0 (uk )k2H .2κ32kJ 0 (uk )k.κВыражая отсюда норму kJ 0 (uk )kH и подставляя её в (5), получим:κ= ak q.ak+1 6 ak 1 −LПрименяя это неравенство k, раз получаем второе неравенство в (4), и теорема полностью доказана.Наилучшие результаты, как нетрудно видеть, метод (2)–(3) даёт в случае, когда κ = L(например, для квадратичных функционалов вида J(u) = kuk2H − hb, uiH ).
При этомсогласно (4) мы получаем точный результат уже после первого шага процесса.Заметим, что для квадратичного функционала J(u) = kAu − f k2F задача (3) решаетсяявным образом. Если обозначить через fk (α) выражение J(uk − αJ 0 (uk )), то для случаяквадратичного функционала имеем:fk (α) = kA(uk − αJ 0 (uk )) − f k2F = kAuk − f k2F + α2 kAJ 0 (uk )k2F − 2 hAuk − f, αAJ 0 (uk )iF .В случае, когда kAJ 0 (uk )kF 6= 0, имеем в правой части квадратный трёхчлен относительно α, который достигает минимума в точкеhAuk − f, AJ 0 (uk )iF1 hAuk − f, AA∗ (Auk − f )iF0∗={J(u)=2A(Au−f)}=·=kAJ 0 (uk )k2F2kAA∗ (Auk − f )k2F1 hA∗ (Auk − f ), A∗ (Auk − f )iF1 kA∗ (Auk − f )k2F1 kJ 0 (uk )k2F= ·= ·= ·2kAA∗ (Auk − f )k2F2 kAA∗ (Auk − f )k2F2 kAJ 0 (uk )k2Fαk =Случай же, когда AJ 0 (uk ) = 0 означает, что AA∗ (Auk − f ) = 0. Если обозначитьразность Auk − f через vk , то будем иметь, что vk ∈ ker AA∗ .
А из этого следует, чтоvk ∈ ker A∗ , действительно:AA∗ vk = 0 ⇒ hAA∗ vk , vk i = 0 ⇒ hA∗ vk , A∗ vk i = 0 ⇒ A∗ vk = 0.Отсюда получаем, что J 0 (uk ) = 0, то есть процесс останавливается.Упражнение 13 (3). Найти явное выражение для αk из (3) для функционалаJ(u) =1hAu, ui − hb, ui ,2A∗ = A > 0.Непрерывный аналог метода скорейшего спускаКак и в предыдущем методе, здесь мы рассматриваем задачу минимизации функцииJ(u) на множестве без ограничений U = H:J(u) → inf, u ∈ H(1)Приведём некоторые формальные рассуждения, которые позволят нам получитьнепрерывный аналог метода скорейшего спуска. Рассмотрим шаг процесса для этогометода:uk+1 = uk − αJ 0 (uk ).33Если рассматривать ∆tk как некий временной шаг, то разделив это равенство на ∆tkполучим:uk+1 − ukαk 0=−J (uk ).∆tk∆tkЕсли теперь задать значение u(t) в начальный момент времени t = 0, то мы придём(исходя из здравого смысла) к системе 0u (t) = −β(t)J 0 [u(t)], t > 0(2)u(0) = u0Теорема 13.
Пусть J(u) сильно выпукла на H с коэффициентом κ > 0, J 0 (u) ∈ Lip(H),β(t) > β0 > 0 непрерывна по t. Тогда для любого начального приближения u0 ∈ H метод(2) сходится к u∗ и для скорости сходимости справедлива оценка:ku(t) − u∗ kH 6 ku0 − u∗ kH ·e−κβ0 t , t > 0(3)Доказательство.Как и в предыдущей теореме заметим, что по Теореме 6 точка u∗ существует и единственна.Введём функцию Ляпунова:V (τ ) = ku(τ ) − u∗ k2H .V 0 (τ ) = 2 hu0 (τ ) − u0∗ , u(τ ) − u∗ iH = 2 h−β(τ )J 0 [u(τ )], u(τ ) − u∗ iH 66 {Теорема 8 п.(c0 )} 6 −2β0 κku(τ ) − u∗ k2H = −2β0 κV (τ ).Домножим обе части этого неравенства на e2βκτ и перенесём всё в левую часть:0e2βκτ V 0 (τ ) + 2β0 κe2βκτ V (τ ) 6 0, то есть V (τ )e2βκτ 6 0.Проинтегрируем обе части по τ от 0 до t:ku(t) − u∗ k2H ·e2βκt − ku0 − u∗ k2H ·1 6 0.Перенося второе слагаемое в правую часть, деля на e2βκt и взяв корень, получаем (3).Теорема доказана.Метод проекции градиентаВ этом пункте рассмотрим задачу минимизации функции J(u) на множестве, уже несовпадающем со всем пространством H (задачу на условный минимум):J(u) → inf,u∈U⊂H(1).В данном методе рассматривается итерационная последовательностьuk+1 = prU (uk − αk J 0 (uk )),k = 0, 1, 2, .
. .(2)При этом необходимо учитывать, что на каждом шаге приближения все точки uk должныпринадлежать U. Для простоты будем считать, чтоαk = α ≡ const34(3)Теорема 14. Пусть U ⊂ H — выпуклое, замкнутое множество, J(u) ∈ C1 (U) исильно выпукла с коэффициентом κ > 0, J 0 (u) ∈ Lip(U) с константой L > 0. Пустьтакже α ∈ 0, L2κ2 . Тогда для любого начального приближения u0 ∈ U метод (2), (3)сходится:√kuk − u∗ kH 6 ku0 − u∗ kH ·q k (α), где 0 < q(α) = 1 − 2κα + α2 L2 < 1.(4)Доказательство.По Теореме 11 точка u∗ является решением задачи (1) тогда и только тогда, когдаu∗ = prU (u∗ − αJ 0 (u∗ )),∀α > 0.Введём оператор A : U → U такой, чтоAu = prU (u − αJ 0 (u)).Тогда точка u∗ будет неподвижной для этого оператора.Подберём теперь такие α, при которых оператор A будет сжимающим.kAu − Avk2H 6 {Теорема 10 п.3} 6 k[u − αJ 0 (u)] − [v − αJ 0 (v)]k2H == ku − vk2H + α2 kJ 0 (u) − J 0 (v)k2H − 2α hu − v, J 0 (u) − J 0 (v)iHВторое слагаемое в этом выражении не превосходит в силу Липшиц-непрерывности первой производной J 0 (u) величины L2 ku − vk2H .
Последнее же слагаемое не больше, чемκku − vk2H , так как J(u) сильно выпукла. Из этого получаем:kAu − Avk2H 6 (1 − 2κα + α2 L2 )ku0 − u∗ k2H = q 2 (α)ku0 − u∗ k2H .Теперь, применяя принцип сжимающих отображений (см., например, [КФ, гл. II, §4]),получаем (4) и теорема доказана.Метод условного градиентаВ этом пункте рассматривается задача минимизации следующего вида:J(u) → inf,u ∈ U ⊂ H.(1)Идея метода условного градиента основана на том, что в окрестности точки uk функционал J(u) можно приближенно представить какJ(u) ' J(uk ) + hJ 0 (uk ), u − uk i .Так как J(uk ) близко к J(u), то мы стараемся минимизировать скалярное произведение Jk (u) = hJ 0 (uk ), u − uk i . Введём обозначениеuk = argmin Jk (u).u∈U35(2)Тогда итерационная последовательность рассматриваемого метода описывается какuk+1 = uk + αk (uk − uk ),(3)αk = argmin J (uk + α (uk − uk ))(4)где06α61Для обоснования сходимости метода докажем сначала одну небольшую лемму.Лемма 1 (оценка скорости сходимости числовой последовательности).Пусть для монотонной числовой последовательности {ak }∞k=0 :a0 > a1 > .
. . > an > . . . > 0выполняется условиеak − ak+1 > C·a2kТогда верна оценка:am 6a01 + a0 Cmk = 0, 1, 2, . . .m = 0, 1, 2, . . .(∗).Доказательство.Прежде всего заметим, что последовательность сходится как монотонно убывающаяи ограниченная снизу. Оценим разность величин, обратных элементам последовательности:11ak − ak+1C·a2−=> 2 k = C.ak+1 akak ·ak+1akПросуммировав эти неравенства по k от 0 до m, получим11−> C·m.am a0Отсюда непосредственно следует (∗).Теорема 15. Пусть U ⊂ H — выпуклое, замкнутое, ограниченное множество,J(u) ∈ C1 (U) и выпукла, J 0 (u) ∈ Lip(U) с константой L > 0, D = diamU.
Тогда J(u0 ) − J∗1J(uk ) − J∗ 6=O(5).J(u0 )−J∗k1+k2LDЕсли J(u) сильно выпукла, то, кроме этого, выполнено условиеκkuk − u∗ k2H 6 J(uk ) − J∗ .2Доказательство.J(u) выпукла и непрерывна, следовательно, и слабо полунепрерывна снизу. U выпукло, замкнуто и ограничено, следовательно, является слабым компактом. Отсюда поТеореме 2 имеем, чтоJ∗ > −∞, U∗ 6= ∅.36Обозначим через ak разность между J(uk ) и J∗ , тогдаak+1 = ak + J(uk+1 ) − J(uk ) 6 ak + J(uk + α(uk − uk )) − J(uk ) =Z1= {ф-ла конечных приращений} = ak +hJ 0 (uk + tα(uk − uk )), α(uk − uk )iH dt0Прибавим и вычтем к первому аргументу скалярного произведения под интегралом величину J 0 (uk ) и, применив неравенство Коши-Буняковского и учтя Липшиц-непрерывностьфункции J 0 (u), получимZ10ak+1 = ak + α hJ (uk ), uk − uk iH +L·ktα(uk − uk )kH ·kα(uk − uk )kH dt 606 ak + α hJ 0 (uk ), uk − uk iH +LL 2 2α D 6 ak + α hJ 0 (uk ), u∗ − uk iH + α2 D222По Теореме 7 п.
(b) отсюда получаем:ak+1 6 ak +L 2 2Lα D + α(J(u∗ ) − J(uk )) = (1 − α)ak + α2 D222∀α ∈ [0, 1](6)Подставим в эту оценку α = 0 и получим, что ak+1 6 ak , но при этом все ak > 0, то естьпоследовательность {ak } имеет предел a > 0.Перейдём в (6) к пределу при k → ∞:a 6 (1 − α)a +L 2 2α D2Разделим на α и устремим α к 0. Имеем оценку a 6 0. Таким образом, a = 0.Рассмотрим теперь минимум правой части (6) по ααверш = αk =ak→ 0.LD2Значит, начиная с некоторого k, αk ∈ [0, 1].Берём в (6) α = αk и получаем оценкуak+1 6 ak −a2k.2LD2Отсюда с учётом Леммы 1 получаем первое утверждение теоремы.Осталось заметить, что если J(u) сильно выпукла, то второе утверждение следуетнепосредственно из Теоремы 6 п.
2. Теорема полностью доказана.37Метод НьютонаРассматриваем задачу минимизации функции J(u):J(u) → inf,u∈U⊆H(1)Идея метода Ньютона похожа на метод условного градиента, но здесь мы будем использовать не линейную, а квадратичную аппроксимацию функции J(u) в окрестноститочки uk :1 000J(u) ' J(uk ) + hJ (uk ), u − uk i + hJ (uk )(u − uk ), u − uk i .2Обозначим выражение в квадратных скобках через Jk (u) (квадратично по u).На каждом шаге процесса находится минимумuk = argmin Jk (u).(2)u∈UИ вычисляется следующее приближение по формулам (в общем случае):uk+1 = uk + αk (uk − uk ),αk = argmin J(uk + α(uk − uk )).06α61Но мы будем рассматривать метод в более простом варианте, когда αk не минимизируются и принимаются равными 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
