Теормин (extended) (2003) (1125525), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

. .(2)При этом необходимо учитывать, что на каждом шаге приближения все точки uk должныпринадлежать U. Для простоты будем считать, чтоαk = α ≡ const(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Метод условного градиентаВ этом пункте рассматривается задача минимизации следующего вида: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).(2)u∈UТогда итерационная последовательность рассматриваемого метода описывается как(3)uk+1 = uk + αk (uk − uk ),гдеαk = argmin J (uk + α (uk − uk ))(4)06α61Лемма 1 (оценка скорости сходимости числовой последовательности).Пусть для монотонной числовой последовательности {ak }∞k=0 :a0 > a1 > . . .

> an > . . . > 0выполняется условиеak − ak+1 > C·a2kk = 0, 1, 2, . . .a0m = 0, 1, 2, . . .(∗).1 + a0 CmТеорема 15. Пусть U ⊂ H — выпуклое, замкнутое, ограниченное множество,J(u) ∈ C1 (U) и выпукла, J 0 (u) ∈ Lip(U) с константой L > 0, D = diamU. Тогда 1J(u0 ) − J∗=OJ(uk ) − J∗ 6(5).J(u0 )−J∗kk1+Тогда верна оценка:am 62LDЕсли J(u) сильно выпукла, то, кроме этого, выполнено условиеκkuk − u∗ k2H 6 J(uk ) − J∗ .2Метод НьютонаРассматриваем задачу минимизации функции 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α6112Но мы будем рассматривать метод в более простом варианте, когда αk не минимизируются и принимаются равными 1.

В этом случае uk+1 = uk . Это “классический” методНьютона.Теорема 16. Пусть U ⊂ H — выпуклое, замкнутое множество, причём int U 6= ∅,J(u) ∈ C2 (U) и сильно выпукла с коэффициентом κ > 0, J 00 (u) ∈ Lip(U) с константойLku1 − u0 kH < 1, то метод (2) сходится к u∗ и верна следующаяL > 0. Тогда если q = 2κоценка скорости сходимости:−12κ 2k 2k,1−q·qkuk − u∗ kH 6Lk = 0, 1, 2, . . .(3).Метод сопряжённых направлений (градиентов)В этом пункте рассмотрим задачу минимизации для функционалов специального видав конечномерном гильбертовом пространстве:J(u) =1hAu, ui − hf, ui → inf,2u ∈ Rn = U,A∗ = A > 0.(1)Критерием оптимальности для такой задачи является условие J 0 (u∗ ) = 0, котороеэквивалентно условию Au∗ = f.Идея метода сопряжённых градиентов заключается в следующем.

Пусть {pk }n−1k=0 —базис в Rn . Тогда для любой точки u0 из Rn выполнено равенство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 .Выражение f − Au0 считаем известным, и наша задача состоит в нахождении αi , атакже “правильного” выбора базиса {pk }.13Определение.

Векторы 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)Опишем подробнее итерации в рассматриваемом методе. В качестве первого приближения берём любую точку из 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)αk здесь вычисляются по формулам (α) или (2) (обозначим для однообразия формулы(2) как (4α)).

Коэффициенты же βk берутся таким образом, чтобы для pk+1 сохраняласьортогональность (сопряжённость) с pk :βk =hJ 0 (uk+1 ), Apk ihApk , pk i(4β)Теорема 17. Пусть H = Rn — гильбертово пространство, J(u) = 12 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.14Метод покоординатного спускаЗдесь мы будем рассматривать экстремальную задачу в конечномерном гильбертовомпространстве H = Rn :J(u) → inf, u ∈ Rn .Пусть {pk }nk=1 — базис в Rn . Положим pn+1 = p1 , pn+2 = p2 , . . . Пусть также u0 ∈ Rn —некое начальное приближение. Предположим, что уже построены k приближений uk имы находимся на k + 1-ом шаге итерации.Назовём (k + 1)-й шаг итерации удачным, еслиJ(uk − αk pk+1 ) < J(uk ),J(uk + αk pk+1 ) < J(uk ).В противном случае назовём шаг неудачным.Если шаг удачный, то обновляем uk (берём то значение, где меньше J(uk+1 )) и неменяем αk : αk+1 = αk . Если же шаг неудачный, то переходим к обработке pk+2 .Кроме того, ведётся подсчёт неудачных шагов “подряд”. Если это число становитсяравным размерности пространства, то происходит дробление α: uk+1 оставляем равнойuk , переходим к обработке вектора pk+2 , и полагаем αk+1 = λαk , где λ ∈ (0, 1) — наперёдзаданный коэффициент дробления (обычно его берут равным 1/2).Теорема 18.

Пусть функция J(u) ∈ C1 (Rn ) и выпукла, множество ЛебегаM (u0 ) = {u ∈ Rn |J(u) 6 J(u0 )} ограничено. Тогда описанный выше процесс сходится и по функции и по аргументу:J(uk ) → J∗ ;k→∞ρ(uk , U∗ ) → 0.k→∞Задачи линейного программированияВ этом пункте мы рассмотрим задачу минимизации функционала J(u) = hc, ui в гильбертовом пространстве H = Rn , где c фиксировано из Rn .Общая задача линейного программирования рассматривается на множестве(1)U = {u ∈ Rn | hai , ui = bi , hai , ui 6 bj , i = 1, m, j = 1, s}Если ввести ряд обозначений:b1a1b1a1 a2  b2  b2  a2 A= ··· , A =  ··· , b =  ··· , b =  ··· ,bmasambsто множество U можно описать в более компактной матричной форме:U = {u ∈ Rn |Au = b, Au 6 b}.Наряду с общей задачей (1) мы будем рассматривать каноническую задачу линейногопрограммирования на множествеU = {u ∈ Rn |Au = b, u > 0}.Заметим, что задача (1) сводится к задаче (2).

Действительно, положим в (1)wi = max{0, ui } > 0,vi = max{0, −ui } > 0,15y = b − Au > 0.(2)Тогда можно рассмотреть задачу (2) относительно новой переменной z:z = (y, v, w) ∈ R2n+s , z > 0J(u) = hc, ui = hc, w − vi — линейна по z (не зависит от y),а ограничения задаются равенством A(w − v) = b.Определение.

Точка v выпуклого множества U называется угловой точкой этогомножества, если из соотношения v = αx + (1 − α)y, где x, y ∈ U, α ∈ (0, 1), следует, чтоv = x = y.Теорема 19 (критерий угловой точки для канонического U). Пусть матрицаA = (A1 |A2 |· · ·|An ) (расписано по столбцам). Точка v является угловой точкой канонического множества U тогда и только тогда, когда существует набор столбцовAj1 , Aj2 , .

. . , Ajr (j1 < j2 < · · · < jr ), r = rank A, причёмAj1 vj1 + Aj2 vj2 + · · · + Ajr vjr = b,(3)/ Jb = {j1 , j2 , . . . , jr } vj = 0.где vji > 0 (i = 1, r), а ∀j ∈Определение. Угловая точка v канонического множества U называется невырожденной, если существует такой набор Jb , что vj > 0 для всех j ∈ Jb . Эти координаты (j)называются базисными для точки v:B = (Aj1 |Aj2 | . . . |Ajr ) — базис v.Определение. Если у множества U все угловые точки невырожденные, то задачаминимизации (2) называется невырожденной.Симплекс-методЗдесь мы применим аппарат угловых точек для рассмотрения оптимизационной задачиследующего вида:J(u) = hc, ui → infu ∈ U = {u > 0, Au = b}(1)Идея метода лежит в переборе лишь только угловых точек множества U.

Часто этопозволяет найти оптимальное решение быстрее рассмотренных выше методов. Перейдемк описанию симплекс-метода.Пусть имеется угловая точка v множества U (каким образом она находится, намсейчас не важно). Будем считать также, что из матрицы A выкинуты все линейно зависимые строки (в системе нет линейно зависимых уравнений), то есть r = rank A = m.Находясь в условиях Теоремы 19, можно записать, что vb = (vj1 , . . . , vjr ) — базисныедля v, vjr > 0, а остальные vj равны нулю.

Обозначим через Jb множество {j1 , . . . , jr },а через Jf — множество {1, . . . , n}\Jb . Пусть далее для соответствующих Aji матрицаB = (Aj1 |Aj2 |· · ·|Ajr ), а остальные столбцы матрицы A образую некую матрицу Fr×(n−r) .По определению B и Теореме 19 det B 6= 0, и существует обратная матрица B −1 .Разобьём вектор u = (u1 , . . . , un ) на базисные переменные ub = (uj1 , . . . , ujn ) и насвободные переменные uf . Тогда условие Au = b можно записать как Bub + F uf = b.16В этом случае для ub в (1) справедливо равенство ub = B −1 b − B −1 F uf , а так как Av = bтогда и только тогда, когда Bvb + F vf = Bvb = b, то это равенство можно переписатькак ub = vb − B −1 F uf .

Характеристики

Список файлов ответов (шпаргалок)