Методы оптимизации. Конспект лекций (Буряков) (2003) (1125388), страница 7
Текст из файла (страница 7)
В этом случае uk+1 = uk . Это “классический” методНьютона.Теорема 16. Пусть U ⊂ H — выпуклое, замкнутое множество, причём int U 6= ∅,J(u) ∈ C2 (U) и сильно выпукла с коэффициентом κ > 0, J 00 (u) ∈ Lip(U) с константойLL > 0. Тогда если q = 2κku1 − u0 kH < 1, то метод (2) сходится к u∗ и верна следующаяоценка скорости сходимости:kuk − u∗ kH 62κ 2k k −1·q1 − q2,Lk = 0, 1, 2, .
. .Доказательство.По Теореме 6 u∗ существует и единственна.Применим к Jk (u) Теорему 8 п.(d0 ):Jk0 (u) = J 0 (uk ) + J 00 (uk )(u − uk );Jk00 (u) = J 00 (uk );hJk00 (u)h, hiH = hJ 00 (uk )h, hiH > κkhk2H .Отсюда по Теореме 6 uk также существует и единственна.По Теореме 9 из (2) имеем:hJk0 (uk+1 ), u − uk+1 iH > 0 ∀u ∈ U38(3).hJ 0 (uk ) + J 00 (uk )(uk+1 − uk ), u − uk+1 iH > 0 ∀u ∈ U(4)Подставим в это выражение вместо u uk :hJ 0 (uk ), uk − uk+1 iH > hJ 00 (uk )(uk+1 − uk ), uk+1 − uk iH > κkuk+1 − uk k2H(5)Теперь в качестве u возьмём в (4) uk+1 (k := k − 1) и прибавим к (5):κkuk+1 − uk k2H 6 hJ 0 (uk ) − J 0 (uk−1 ) − J 00 (uk−1 )(uk − uk−1 ), uk − uk+1 iH = {упр.
6} =Z1=hJ 00 (uk−1 + t(uk − uk−1 ))(uk − uk−1 ), uk − uk−1 iH dt−0− hJ 00 (uk−1 )(uk − uk−1 ), uk − uk+1 iH =Z1=h[J 00 (uk−1 + t(uk − uk−1 )) − J 00 (uk−1 )] (uk − uk−1 ), uk − uk+1 iH dt 60Z1kt(uk − uk−1 )kH ·kuk − uk−1 kH ·kuk+1 − uk kH dt =6LLkuk − uk−1 k2H ·kuk+1 − uk kH .20Имеем:L2κ 2kkuk − uk−1 k2H 6 . .
. 6q(6).2κLИз (6) и условия q < 1 получаем, что последовательность {uk }∞k=0 фундаментальная исуществует (в силу полноты H)lim uk = u ∈ H,kuk+1 − uk kH 6k→∞но так как все uk ∈ U, а U замкнуто, то u ∈ U.Перейдём в (4) к пределу при k → ∞, тогда в силу непрерывности J 0 (u) и J 00 (u)получаем, чтоhJ 0 (u) + J 00 (u)(u − u), u − uiH > 0 ∀u ∈ UОтсюда по Теореме 9 u ∈ U∗ , но U∗ состоит из единственной точки u∗ , значит u = u∗ .Таким образом, мы доказали, что процесс сходится. Теперь осталось выяснить скоростьсходимости.kuk − u∗ kH 6 {нер-во 4} 6∞Xkum − um+1 kH 6 {(6)} 6m=k∞2κ 2k X 2m −2kqqLm=kОтсюда получаем (3) и теорема доказана.Замечания.1) Рассмотрим случай, когда uk начинают повторяться, то есть когда uk+1 = uk .
Из(4) следует, чтоhJ 0 (uk ) + J 00 (uk )(uk+1 − uk ), u − uk+1 iH = hJ 0 (uk ), u − uk iH > 0 ∀u ∈ U.Отсюда по Теореме 9 получаем, что uk совпадает с u∗ и процесс останавливается.392) Так как q должно быть меньше 1, то u0 необходимо выбирать не произвольнымобразом, то есть процесс сходится в достаточно малой окрестности u∗ . Но в случае,когда U совпадает со всем H можно предложить априорный вариант выбора u0 .Возьмём в (5) k = 0:κku1 − u0 k2H 6 hJ 0 (u0 ), u0 − u1 iH 6 kJ 0 (u0 )kH ·ku1 − u0 kH .Теперь достаточно выбрать u0 таким, чтоkJ 0 (u0 )kH L·< 1,κ2κи q меньше этой величины.В случае, когда U 6= H это, вообще говоря, сделать не всегда удастся, так как J 0 (u)на U может и не быть столь малым.Метод сопряжённых направлений (градиентов)В этом пункте рассмотрим задачу минимизации для функционалов специального видав конечномерном гильбертовом пространстве:J(u) =1hAu, ui − hf, ui → inf,2u ∈ Rn = U,A∗ = A > 0.(1)Критерием оптимальности для такой задачи является условие J 0 (u∗ ) = 0, котороеэквивалентно условию Au∗ = f.Идея метода сопряжённых градиентов заключается в следующем.
Пусть {pk }n−1k=0 —nnбазис в R . Тогда для любой точки u0 из R выполнено равенствоu∗ − u0 = α0 p0 + α1 p1 + . . . + αn−1 pn−1 .Таким образом, u∗ представимо в видеu∗ = u0 + α0 p0 + α1 p1 + . . . + αn−1 pn−1 .Тогда итерационную последовательность данного метода можно описать какu0 = u0u1 = u0 + α0 p0u2 = u0 + α0 p0 + α1 p1...(точное описание итерации будет дано ниже).Подействовав на вышеприведённое равенство оператором A, получимf − Au0 = α0 Ap0 + α1 Ap1 + .
. . + αn−1 Apn−1 .40Выражение f − Au0 считаем известным, и наша задача состоит в нахождении αi , атакже “правильного” выбора базиса {pk }.Определение. Векторы p и q называются сопряжёнными относительно матрицыR = R∗ > 0, если hRp, qi = 0. По-другому это называют ортогональностью относительноскалярного произведения hp, qiR = hRp, qi .Если {pk }n−1k=0 — базис из сопряжённых относительно A векторов, тоαk =hf − Au0 , pk i,hApk , pk ik = 0, n − 1.(α)Лемма 2. Пусть H = Rn , A = A∗ > 0, {pk }n−1k=0 — базис из сопряжённых относительноA векторов, uk = uk−1 + αk−1 pk−1 , где αk вычисляются по формулам (α). Тогдаαk = αk∗ = argmin J(uk + αpk ) = −−∞<α<+∞hJ 0 (uk ), pk iHhApk , pk iH(2)иhJ 0 (uk+1 ), pk iH = 0 ∀k = 0, n − 1(3)Доказательство.Запишем условие на минимум J(uk + αpk ):hJ 0 (uk + αk∗ pk ), pk i = 0.Тогда,hJ 0 (uk + αk∗ pk ), pk i = hAuk − f + αk∗ Apk , pk i = {uk = u0 + α0 p0 + · · · + αk−1 pk−1 } == hAu0 − f, pk i + αk∗ hApk , pk i = 0.Отсюда с учётом (α) следует, что αk = αk∗ , то есть (2).Теперь из (2) имеем:uk+1 = uk + αk∗ pk ⇒ J 0 (uk+1 ) = 0 ∀k = 0, n − 1, то есть (3).Лемма доказана.Опишем подробнее итерации в рассматриваемом методе.
В качестве первого приближения берём любую точку из Rn , а первый вектор будущего базиса вычисляем какзначение производной функции J(u) в данной точке:∀u0 ∈ Rnp0 = −J 0 (u0 )Теперь пусть требуется вычислить k + 1-ю итерацию, когда предыдущие k уже вычислены, тогда применяем следующие формулы:uk+1 = uk + αk pk ,(4u)0pk+1 = −J (uk+1 ) + βk pk(4p)41αk здесь вычисляются по формулам (α) или (2) (обозначим для однообразия формулы(2) как (4α)). Коэффициенты же βk берутся таким образом, чтобы для pk+1 сохраняласьортогональность (сопряжённость) с pk :βk =hJ 0 (uk+1 ), Apk ihApk , pk i(4β)Теорема 17. Пусть H = Rn — гильбертово пространство, J(u) = 21 hAu, ui − hf, ui ,A∗ = A > 0.
Тогда метод (4) сходится к u∗ за конечное число шагов (не превосходящее n), причём(a) hApk , pm i = 0 ∀k 6= m;(b) hJ 0 (uk ), J 0 (um )i = 0 ∀k 6= m;(c) hJ 0 (uk ), pm i = 0 ∀m = 0, 1, . . . , k − 1.Доказательство.Проведём доказательство по индукции по количеству итераций.Для одной итерации имеем (базис индукции):(a): верно по построению (см.
(4β));(b): hJ 0 (u1 ), J 0 (u0 )i = hJ 0 (u1 ), −p0 i = {Лемма} = 0;(c): в точности совпадает с (3).Пусть теперь (a), (b), (c) верны для k итераций включительно. Докажем, что эти формулы верны для (k + 1)-й итерации.(b): докажем сначала, что hJ 0 (uk+1 ), J 0 (uk )i = 0.
Имеем:J 0 (uk+1 ) = Auk − f + αk Apk = J 0 (uk ) + αk ApkПодставляя это в скалярное произведение получаем, чтоhJ 0 (uk+1 ), J 0 (uk )i = hJ 0 (uk ), J 0 (uk )i + αk hApk , J 0 (uk )i = {4α} == hJ 0 (uk ), J 0 (uk )i −hJ 0 (uk ), pk ihApk , J 0 (uk )ihApk , pk i(∗)По формулам (3) имеемhJ 0 (uk ), pk i = {(4p)} = hJ 0 (uk ), −J 0 (uk ) + βk−1 pk−1 i = − hJ 0 (uk ), J 0 (uk )i .А по предположению индукции (a)hApk , J 0 (uk )i = {(4p)} = hApk , −pk + βk−1 pk−1 i = − hApk , pk i .Подставляя последние два выражения в (∗), получаем, что hJ 0 (uk+1 ), J 0 (uk )i = 0.Покажем теперь, что для m 6 k−1 скалярное произведение hJ 0 (uk+1 ), J 0 (um )i такжеравно 0.hJ 0 (uk+1 ), J 0 (um )i = hJ 0 (uk ), J 0 (um )i + αk hApk , J 0 (um )i = {предп.
инд. (b)} == αk hApk , −pm + βm−1 pm−1 i = {предп. инд. (a)} = 0.42(c): если m = k, то hJ 0 (uk+1 ), pk i = {Лемма} = 0.Если же m 6 k − 1, тоhJ 0 (uk+1 ), pm i = hJ 0 (uk ), pm i + αk hApk , pm i = {предп. инд. (a) и (c)} = 0.(a): рассмотрим m 6 k − 1 (для m = k утверждение верно по построению).hApm , pk+1 i = − hApm , J 0 (uk+1 ) + βk pk i = − hApm , J 0 (uk+1 )i ==−11hαm Apm , J 0 (uk+1 )i =hJ 0 (um ) − J 0 (um+1 ), J 0 (uk+1 )i = {(b)} = 0.αmαmЗдесь мы предполагали, что αm 6= 0.
Покажем, что это действительно так.Возможны ситуации:1) αk = 0. Тогда по формулам (4u) получаем, что uk+1 = uk , то есть процессзацикливается. Но по (4α) αk = 0 тогда и только тогда, когдаhJ 0 (uk ), pk i = 0 = {(4p)} = hJ 0 (uk ), −J 0 (uk ) + βk−1 pk−1 i .В силу леммы получаем, что 0 = −kJ 0 (uk )k2 . Отсюда следует, что J 0 (uk ) = 0и uk = u∗ . Таким образом, найден минимум и процесс можно остановить.2) hApk , pk i = 0. Тогда, так как A > 0, pk = 0 и по формулам (4u) опять получаем,что uk+1 = uk . По формулам (4p) pk = 0 тогда и только тогда, когда−J 0 (uk ) + βk−1 pk−1 = 0⇒−kJ 0 (uk )k2 = 0.То есть uk = u∗ и процесс опять таки можно остановить.Теорема полностью доказана.При реализации метода сопряжённых направлений для функционалов общего видавозникают проблемы из-за наличия матрицы A в формулах (4α) и (4β). Но для такогослучая можно использовать другие способы вычисления этих формул:αk = {Лемма (2)} = argmin J(uk + αpk )−∞<α<∞βk =hJ 0 (uk+1 ), J 0 (uk+1 ) − J 0 (uk )ihJ 0 (uk+1 ), Apk i αk·== {(3), (b), (c)} =hApk , pk iαkhJ 0 (uk+1 ) − J 0 (uk ), pk i=hJ 0 (uk+1 ), J 0 (uk+1 ) − J 0 (uk )ikJ 0 (uk+1 )k2=.kJ 0 (uk )k2kJ 0 (uk )k2Заметим, что эти формулы различны, если функционал не квадратичный.43Метод покоординатного спускаЗдесь мы будем рассматривать экстремальную задачу в конечномерном гильбертовомпространстве H = Rn :J(u) → inf, u ∈ Rn .Пусть {pk }nk=1 — базис в Rn .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
