Методы оптимизации. Конспект лекций (Буряков) (2003) (1125388), страница 8
Текст из файла (страница 8)
Положим 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→∞Доказательство.Так как M (u0 ) ограничено и замкнуто (то есть компакт в Rn ), а функция J(u) непрерывна, то по Теореме 1 J∗ > −∞, U 6= ∅.Далее, по построениюJ(uk ) > J(uk+1 ) > .
. . > J∗ ,то есть последовательность {J(uk )} сходится и существует пределlim J(uk ) = J > J∗ .k→∞Заметим, что αk → 0 при k → ∞. Это следует из бесконечности числа дроблений.Рассмотрим подпоследовательности с индексами km — моментами дробления.αkm → 0;m→∞ukm → u ∈ M (u0 )m→∞Моменту km предшествует n неудач:J(ukm ± αkm pi ) > J(ukm ) ∀i = 1, n.По формуле конечных приращений имеем: 0iJ (ukm ± θmαkm pi ), ±αkm pi > 0,44iθm∈ [0, 1].Разделим это выражение на αkm и устремим m к бесконечности, тогда в силу непрерывности J 0 (u) получим:hJ 0 (u), ±pi i > 0 ∀i = 1, n, т.е. hJ 0 (u), pi i = 0 ∀i = 1, nОтсюда в силу того, что {pi } — базис следует, что J 0 (u) = 0.
Так как J(u) выпукла, тоu ∈ U∗ , а в силу непрерывности J(u) J(ukm ) → J(u) = J∗ при m → ∞, то естьlim J(uk ) = J∗ ,k→∞и сходимость по функции доказана.Сходимость же по аргументу вытекает непосредственно из Теоремы 1.Рассмотрим пример, когда первая производная функции J(u) не существует, вследствие чего данный метод не сходится.Возьмём в пространстве R2 функцию J(u) = (x − 1)2 + (y − 1)2 + 2|x − y| − 2. Этафункция сильно выпукла, непрерывна, но не дифференцируема при x = y.
Легко видеть,что U∗ = {(1, 1)}, J∗ = −2. Если стартовать из точки u0 = (0, 0), то получим, что всеuk = u0 = (0, 0), то есть при базисе p1 = (1, 0), p2 = (0, 1), J(u0 +αpi ) = α2 −2α+2|α| > 0 —все шаги неудачные.Задачи линейного программированияВ этом пункте мы рассмотрим задачу минимизации функционала J(u) = hc, ui в гильбертовом пространстве H = Rn , где c фиксировано из Rn .Общая задача линейного программирования рассматривается на множествеU = {u ∈ Rn | hai , ui = bi , hai , ui 6 bj ,Если ввести ряд обозначений:a1 a2 , A = A= ··· ama1a2 ,··· asi = 1, m, j = 1, s}b1 b2 b= ··· ,bm(1)b1 b2 b= ··· ,bsто множество U можно описать в более компактной матричной форме:U = {u ∈ Rn |Au = b, Au 6 b}.Наряду с общей задачей (1) мы будем рассматривать каноническую задачу линейногопрограммирования на множествеU = {u ∈ Rn |Au = b, u > 0}.(2)Заметим, что задача (1) сводится к задаче (2). Действительно, положим в (1)wi = max{0, ui } > 0,vi = max{0, −ui } > 0,45y = b − Au > 0.Тогда можно рассмотреть задачу (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.
Если v = 0, то в (3) можно взятьлюбые базисные столбцы матрицы A. Рассмотрим случай, когда v 6= 0. Пустьvj1 > 0, vj2 > 0, . . . , vjk > 0,а остальные vj = 0.Покажем, что столбцы Aj1 , Aj2 , . . . , Ajk линейно независимы. Необходимо доказать,что равенствоγj1 Aj1 + γj2 Aj2 + · · · + γjk Ajk = 0(∗)выполняется только тогда, когдаγj1 = γj2 = · · · = γjk = 0.Введём вектор γ = (γ1 , .
. . , γn ) так, что γj = γji , если j = ji , и γj = 0, если j 6= ji ни длякакого i. Равенство (∗) выполняется тогда и только тогда, когда Aγ = 0.Рассмотрим точку v±ε = v ±εγ. Для достаточно малых ε > 0 будет выполнено v±ε > 0+ v−ε,и Av±ε = Av ± εAγ = Av = b.
Отсюда следует, что v±ε ∈ U. В то же время v = v+ε22а так как v — угловая точка, то v+ε = v−ε = v. Но ε 6= 0 и, значит, γ = 0, то естьAj1 , Aj2 , . . . , Ajk линейно независимы.Теперь достаточно заметить, что (3) выполняется после дополнения Aj1 , Aj2 , . . . , Ajkдо базисного набора в случае, когда k < r. Необходимость доказана.Достаточность.Пусть для точки v выполнены условия (3).
Значит, v > 0, Av = b, то есть v ∈ U.Требуется доказать, что из условияv = αx + (1 − α)y,α ∈ (0, 1), x, y ∈ U46следует, что v = x = y.Если vj = 0 = αxj + (1 − α)yj , то vj = xj = yj = 0, так как α > 0, а xj > 0 и yj > 0.Выделим все vj1 > 0, . . . , vjk > 0 (остальные координаты равны нулю). Тогда, так какv, x, y ∈ U, то Aj1 vj1 + Aj2 vj2 + · · · + Ajk vjk = bAj xj + Aj2 xj2 + · · · + Ajk xjk = b 1 1Aj1 yj1 + Aj2 yj2 + · · · + Ajk yjk = bУчитывая, что Aj1 , Aj2 , . . . , Ajk линейно независимы, получаем, что vji = xji = yji > 0для любого i = 1, k.
Теорема доказана.Определение. Угловая точка v канонического множества U называется невырожденной, если существует такой набор Jb , что vj > 0 для всех j ∈ Jb . Эти координаты (j)называются базисными для точки v:B = (Aj1 |Aj2 | . . . |Ajr ) — базис v.Определение. Если у множества U все угловые точки невырожденные, то задачаминимизации (2) называется невырожденной.Упражнение 14 (3). ПустьU = {u ∈ R4 | u > 0, Au = b}, 1 1 3 13A=, b=.1 −1 1 21Найти все угловые точки U и исследовать их на невырожденность.Симплекс-методЗдесь мы применим аппарат угловых точек для рассмотрения оптимизационной задачиследующего вида: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.47В этом случае для ub в (1) справедливо равенство ub = B −1 b − B −1 F uf , а так как Av = bтогда и только тогда, когда Bvb + F vf = Bvb = b, то это равенство можно переписатькак ub = vb − B −1 F uf . Теперь от канонических ограничений u > 0 можно перейти кнеканонической форме:uf > 0,B −1 F uf 6 vb .Для функции J(u), используя те же рассуждения, можно написать:J(u) = hc, uiRn = hcb , ub iRr + hcf , uf iRn−r == hcb , vb iRn + cf − (B −1 F )T cb , uf Rn−r = J(v) − h∆, uf i , (2)где J(v) = hc, vi , −∆ = cf − (B −1 F )T cb .Введём обозначениеg(uf ) = J(v) − h∆, uf iRn−r .(3)Заметим, что в этом случае J(v) = C ≡ const. Тогда задача (1) сводится к задаче сменьшим количеством переменных, но с неканоническими ограничениями:P(g(uf ) = J(v) −∆j uj → inf,j∈Jf(4)uf ∈ Uf = {uf > 0, (B −1 F )uf 6 vb }.Обозначим через Jf+ множество тех j ∈ Jf , для которых ∆j > 0.
И пусть k ∈ Jf+ ,например, самый меньший:k = min+ j.(5)j∈JfРассмотрим для (4) подзадачу минимизации функции от одной переменнойuf = (0, . . . , 0, uk , 0, . . . , 0):gk (uk ) = J(v) − ∆k uk → inf,uk ∈ Uk = {uk > 0, (B −1 F )k uk 6 vb }.Обозначим через γk вектор (B −1 F )k = B −1 Ak , и пустьγ1k γ2k γk = .. , Ik+ = {i = 1, r | γik > 0}, .
γrk(6)(Ik+ есть множество “реальных” ограничений сверху на uk ). Тогда в качестве решенияподзадачи можно взять vjiθk = min.(7)γiki∈Ik+Опишем теперь непосредственно сам метод. Возможны следующие ситуации.1) Jf+ = ∅. В этом случае v принадлежит множеству U∗ (оптимальна) и мы останавливаемся.482) Jf+ 6= ∅, и существует такой номер k ∈ Jf+ , что Ik+ = ∅. Но тогда нет “реальных”ограничений на uk , которые могут бесконечно возрастать. Откуда J∗ = −∞, U∗ = ∅и процесс итерирования следует остановить.3) Множество Jf+ не пусто и для любого k из Jf+ соответствующее множество Ik+ такжене пусто. (Этот случай представляет собой непосредственно “шаг” метода.)Берём k по правилу (5), uk = θk по правилу (7).В (7) минимум может достигаться на нескольких номерах, поэтому введём супермега-множествоvji++= θk ,Ik ∗ = i ∈ Ik |γikи из него выберем, например, наименьший элемент s = min i.i∈(Ik+ )∗После этого переходим к рассмотрению следующей угловой точки w ∈ U, котораявычисляется по правилу wb = vb − B −1 Ak uk .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
