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

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

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

Теперь от канонических ограничений 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+ ,например, самый меньший:(5)k = min+ j.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.(7)θk = minγiki∈Ik+Опишем теперь непосредственно сам метод. Возможны следующие ситуации.1) Jf+ = ∅. В этом случае v принадлежит множеству U∗ (оптимальна) и мы останавливаемся.172) 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 .

Докажем, что при использованиитакого правила мы действительно получим угловую точку.Для точки w соответствующая ей матрица B будет иметь видB(w) = (Aj1 |· · ·|Ajs−1 |Ak |Ajs+1 |· · ·|Ajr ).Нам необходимо показать, что это есть базис. Сделаем это по определению. Пустьα1 Aj1 + . . . + αs−1 Ajs−1 + αk Ak + αs+1 Ajs+1 + . .

. + αr Ajr = 0.Подставим в это равенство Ak = Bγk = γ1k Aj1 + . . . + γrk Ajr . Тогда так как B(v)есть базис, то необходимо должно выполнятьсяαi + αk γik = 0, ∀i 6= s,αk γsk = 0.Отсюда следует, что все αi равны нулю, то есть B(w) — базис.Таким образом, по Теореме 19 мы получаем, что w действительно угловая точкамножества U.Замечания.1) В случае, когда v вырождена, θk = 0 и v = w. При этом может произойти зацикливание процесса, но правила выбора k и s (правила Блэнда) позволяют избежатьэтого.2) Если угловых точек в множестве U конечное число, то остановка процесса произойдёт через конечное число шагов на случаях 1) или 2).В конце пункта сформулируем обобщающую наши рассуждения теорему.18Теорема 20 (к задаче линейного программирования). В задаче линейного программирования выполняются следующие утверждения:1) если U 6= ∅, то в U существует по крайней мере одна угловая точка;2) если J∗ > −∞, то во множестве U∗ содержится по крайней мере одна точка.Доказательство.Доказательство этой теоремы, по сути, приводится в обосновании симплекс-метода(перебора по угловым точкам).Замечание.

Утверждение 2) справедливо именно для задачи линейного программирования. В противном случае это, вообще говоря, не верно. Например, если J(u) = e−u(это не задача линейного программирования), то U = R1 , J∗ = 0, но U∗ = ∅.6Методы снятия ограниченийВ этой главе рассматриваются задачи минимизации функционаловJ(u) → inf, u ∈ Uс учётом ограничений на множество U.Эти ограничения могут быть “терпимыми”, например, u может принадлежать не всему пространству, а какому-либо подмножеству этого пространства. Такие ограничениямы не рассматриваем и считаем, что их можно обойти простыми методами.Нас же будут интересовать более “функциональные” ограничения на u. Рассмотримконкретный пример:u ∈ U = {u ∈ U0 ⊂ H | g1 (u) 6 0, . .

. , gm (u) 6 0, gm+1 (u) = 0, . . . , gm+s = 0},где gi какие-либо функции.Здесь интересующие нас ограничения это m ограничений типа “неравенство” и s ограничений типа “равенство” (“терпимым” ограничением является принадлежность точкиu множеству U0 ).Естественно, какие-либо из ограничений могут отсутствовать.Метод штрафовВ этом методе рассматривается задача минимизации с ограничениями следующего вида:J(u) → inf, u ∈ U = {u ∈ U0 ⊂ H | g1 (u) 6 0, . . . , gm (u) 6 0,gm+1 (u) = 0, .

. . , gm+s = 0} (1)Рассмотрим функцию (называемую штрафом или штрафной функцией):P (u) =m+sX(gi+ (u))pi ,pi > 1 (обычно pi = 2).i=119Функции gi+ (u) называют индивидуальными штрафами. В качестве конкретного примера можно взятьgi+ (u) = max{gi (u), 0}, i = 1, m,gi+ (u) = |gi (u)| , i = m + 1, m + s.Легко видеть, что условиеP (u) = 0,u ∈ U0выполняется тогда и только тогда, когда точка u принадлежит множеству U.Из штрафной функции P (u) формируются формулы видаΦk (u) = J(u) + Ak P (u),Ak > 0, Ak → ∞ при k → ∞, u ∈ U0 , k = 1, 2, . . .(2)Теперь от задачи (1) мы переходим к последовательности задач (2).

Пусть точкиuk ∈ U0 таковы, чтоΦk∗ ≡ inf Φk 6 Φk (uk ) 6 Φk∗ + εk(3)U0(их можно получить, например, методами, изложенными в предыдущей главе). Используя эту последовательность точек, сформулируем основную теорему в этом пункте.Теорема 21. Пусть H — гильбертово пространство, множество U0 слабо замкнуто;J(u), gi+ (u) слабо полунепрерывны снизу на U0 ; точкаJ0 = inf J(u)U0конечна; множествоU(δ) = {u ∈ U0 : gi+ (u) 6 δ, i = 1, m + s}ограничено в H для некоторого δ > 0; Ak → +∞, εk → +0, тогда последовательностьJ(uk ) стремится к минимуму J(u):J(uk ) → inf(J(uk ) → J∗ ),и все слабые предельные точки последовательности {uk } содержатся во множестве U∗ .20Правило множителей Лагранжа для выпуклых задачВ этом пункте рассматриваем следующую задачу минимизации:J(u) → inf,u ∈ U = {u ∈ U0 ⊂ L | g1 (u) 6 0, . .

. , gm (u) 6 0}(1)Можно рассмотреть и случай, когда есть ограничения типа “равенство”, но при этомони обязаны быть линейными (в предыдущем методе на такие ограничения также накладываются жёсткие условия в виде слабой полунепрерывности снизу, так что они “почти”линейны).Назовём задачу (1) выпуклой, если множество U0 выпукло, L представляет собойлинейное пространство, функции gi выпуклы.Построим функцию Лагранжа:L(u, λ) = λ0 J(u) +mXλi gi (u) (λ ∈ Rm+1 ).i=1Числа λi называют множителями Лагранжа.Теорема 22 (теорема Ку́на-Та́ккера). Пусть задача (1) выпукла в указанном смысле. Тогда1) если точка u∗ является оптимальной (u∗ ∈ U∗ ), то существует набор множителей Лагранжа λ∗ 6= 0 такой, чтоi)min L(u, λ∗ ) = L(u∗ , λ∗ ) — принцип минимума;u∈U0ii)λ∗i > 0,i = 0, m — условия неотрицательности множителей Лагранжа;iii)λ∗i gi (u∗ ) = 0,i = 1, m — условия, дополняющие нежёсткости.2) если для некоторой пары (u∗ , λ∗ ) выполняются условия i)-iii) и, кроме того,u∗ ∈ U и λ∗0 6= 0, то u∗ — оптимальная точка (u∗ ∈ U∗ ).Замечание о регулярностиРассмотрим пример, в котором λ∗0 = 0.

Пусть H = R1 , J(u) = −u → inf, U0 = R1 ,g1 (u) = u2 , U = {u ∈ R1 | u2 6 0} = {0} = U∗ . Докажем, что в любом наборе λ∗ = (λ∗0 , λ∗1 )обязательно λ∗0 = 0. По Теореме 22 найдётся неотрицательный набор (λ∗0 , λ∗1 ) такой, чтобудет выполняться условие i): −λ∗0 u + λ∗1 u2 > 0 ∀u ∈ R1 .Разделим это неравенство на u > 0: −λ∗0 + λ∗1 u > 0 ∀u > 0, и устремим u к нулю.Получим −λ∗0 > 0.Отсюда с учётом условия неотрицательности множителей Лагранжа имеем λ∗0 = 0.21Достаточные условия регулярности (условия Сле́йтера)Достаточным условием на регулярность является существование точки u0 ∈ U0 такой, что g1 (u0 ) < 0, .

. . , gm (u0 ) < 0. Для доказательства этого факта предположим, чтов некотором (ненулевом) наборе λ∗ первая координата λ∗0 равна нулю, тогда функцияЛагранжа на этом наборе равна:mXλ∗i gi (u0 ) < 0 = L(u∗ , λ∗ ),L(u0 , λ∗ ) =i=1и мы приходим к противоречию с принципом минимума.Приведём аналог теоремы Куна-Таккера в несколько иной формулировке. Для этогосначала введём одноОпределение. Пусть X, Y — множества произвольной природы. f : X × Y → R1 .Точка (x∗ , y ∗ ) называется седловой точкой функции f на множестве X × Y, еслиf (x∗ , y) 6 f (x∗ , y ∗ ) 6 f (x, y ∗ ) ∀x ∈ X, ∀y ∈ Y.Теорема 23 (седловая форма теоремы Куна-Таккера).

Пусть выполняются условия Теоремы 22 и условия регулярности Слейтера. Тогда точка u∗ принадлежит множеству U∗ (u∗ — оптимальная точка) тогда и только тогда, когда классическая функция Лагранжа (с λ0 = 1) имеет седловую точку (u∗ , λ∗ ) на множестве U0 × Rm+.J(u∗ ) +mXλ∗i gi (u∗ )6 J(u) +mXλ∗i gi (u) ∀u ∈ U0(b)i=1i=1Правило множителей Лагранжа для гладких задачВ этом пункте рассматривается задача минимизации с ограничениями:J(u) → infu ∈ U = {u ∈ H | g1 (u) 6 0, .

. . , gm (u) 6 0,gm+1 (u) = 0, . . . , gm+s (u) = 0}, (1)где H — гильбертово пространство, с дополнительными требованиями на гладкостьфункций. Здесь мы кратко рассмотрим лишь необходимое условие локального минимума.Для начала введём несколько понятий (некоторые из них приведены лишь в качественапоминания).Определение. Точка u∗ называется точкой локального минимума функции J(u),если существует такое положительное число ε, что для любой точки u ∈ Uε ∩ U, гдеUε = {u : ku − u∗ k < ε}, выполняется условие J(u∗ ) 6 J(u).Определение. Пусть X — нормированное пространство, M ⊂ X, x0 ∈ M. Векторh ∈ X называют касательным ко множеству M в точке x0 , если существует отображениеϕ(t) : R1 → X, обладающее свойствами:1) x0 + th + ϕ(t) ∈ M ;X→ 0 при t → 0.2) ϕ(t) = o(t), то есть kϕ(t)ktВообще говоря, для наших целей достаточно существования отображения переводящегов X не всю действительную ось R1 , а лишь какой-либо интервал (−ε; ε) для некоторогоε > 0.Обозначим через Tx0 M все касательные векторы ко множеству M в точке x0 .22Теорема (Люсте́рник).

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

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