Методы оптимизации. Конспект лекций (Буряков) (2003) (1125388), страница 10
Текст из файла (страница 10)
В этом случае, не ограничивая общности, можно считать,что λ∗0 = 1, так как функцию Лагранжа можно делить/умножать на положительноечисло. Тогда имеем:J(u∗ ) = 1·J(u∗ ) +nXi=1λ∗i gi (u∗ ) = L(u∗ , λ∗ ) 6 {i)} 6 L(u, λ∗ ).| {z }=054Последнее неравенство верно для любого u из U0 и, в частности для любого u из U.Далее.∗L(u, λ ) = 1·J(u) +nXλ∗i gi (u) 6 {λ∗i > 0 (утв. ii)) , gi (u) 6 0 (u ∈ U)} 6 J(u) ∀u ∈ U.i=1Так как u∗ содержится в допустимом множестве U, то отсюда получаем, что u∗ —оптимальная точка и достаточность доказана.Упражнение 16 (5).
Доказать теорему об отделимости точки от выпуклого множества в пространстве Rn .Замечание о регулярностиРассмотрим пример, в котором λ∗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.Достаточные условия регулярности (условия Сле́йтера)Достаточным условием на регулярность является существование точки u0 ∈ U0 такой, что g1 (u0 ) < 0, .
. . , gm (u0 ) < 0. Для доказательства этого факта предположим, чтов некотором (ненулевом) наборе λ∗ первая координата λ∗0 равна нулю, тогда функцияЛагранжа на этом наборе равна:L(u0 , λ∗ ) =mXλ∗i gi (u0 ) < 0 = L(u∗ , λ∗ ),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+.Доказательство.Для начала перепишем определение седловой точки (u∗ , λ∗ ) для функции Лагранжа:J(u∗ ) +mXλi gi (u∗ ) 6 J(u∗ ) +i=1mXi=155λ∗i gi (u∗ ) ∀λ ∈ Rm+(a)J(u∗ ) +mXλ∗i gi (u∗ ) 6 J(u) +i=1mXλ∗i gi (u) ∀u ∈ U0(b)i=11) Необходимость.Пусть точка u∗ ∈ U∗ . Тогда по Теореме 22 с учётом условий Слейтера существуеттакой набор λ∗ = (1, λ∗1 , λ∗2 , .
. . , λ∗m ) > 0, что условие (b) непосредственно вытекает изусловия i) этой теоремы, а условие (a) следует из следующего неравенства:mXi=1λi gi (u∗ ) 6 0 = {iii)} = J(u∗ ) +|{z}| {z }>060mXλ∗i gi (u∗ ).i=12) Достаточность.Пусть в точке u∗ ∈ U0 выполняются неравенства (a) и (b).Из (a) следует, чтоmX(λi − λ∗i )gi (u∗ ) 6 0 ∀λi > 0.i=1Подставив в это выражение λ = (λ∗0 , λ∗1 , . . . , λ∗i−1 , λ∗i + ε, λ∗i+1 , .
. . , λ∗m ) (ε > 0), мыполучим, что εgi (u∗ ) 6 0, то есть gi (u∗ ) 6 0. Поскольку это верно для любого i, тоотсюда следует, что u∗ ∈ U.Если подставить в это выражение λ = (λ∗0 , λ∗1 , . . . , λ∗i−1 , 0, λ∗i+1 , . . . , λ∗m ), то будем иметь−λ∗i gi (u∗ ) 6 0, но λ∗i > 0, а gi (u∗ ) 6 0, то есть λ∗i gi (u∗ ) = 0.
Опять же из того, что этоверно для любого i, получаем условие iii) Теоремы 22.Из (b) непосредственно следует условие i).Теперь осталось применить утверждение Теоремы 22 относительно достаточности итеорема доказана.Правило множителей Лагранжа для гладких задачВ этом пункте рассматривается задача минимизации с ограничениями: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, обладающее свойствами:561) x0 + th + ϕ(t) ∈ M ;2) ϕ(t) = o(t), то естьkϕ(t)kXt→ 0 при t → 0.Вообще говоря, для наших целей достаточно существования отображения переводящегов X не всю действительную ось R1 , а лишь какой-либо интервал (−ε; ε) для некоторогоε > 0.uv0 qMОбозначим через Tx0 M все касательные векторы ко множеству M в точке x0 .Tx0 M F (x) = 0x0 qMПриведём без доказательства одну теорему, которой мы в последствии воспользуемся.Теорема (Люсте́рник).
[АТФ, стр. 171-174]Пусть X, Y — банаховы пространства, отображение F : X → Y дифференцируемопо Фреше, M = {x ∈ X | F (x) = 0}, x0 ∈ M, im F 0 (x0 ) = Y. Тогда Tx0 M = ker F 0 (x0 ).Упражнение 17 (4). Пусть X = R2 , Y = R1 , F (x1 , x2 ) = x21 − x42 , множество Mимеет вид M = {(x1 , x2 ) | F (x1 , x2 ) = 0}, x0 = (0, 0).1) Найти Tx0 M ;2) найти ker F 0 (0, 0);3) выяснить, совпадают они или нет и почему.Теперь сформулируем и докажем основную теорему этого пункта.Теорема 24. Пусть u∗ — точка локального минимума в задаче (1); J(u), gi (u) ∈ C1 (Uε )для некоторого положительного ε. Тогда существует ненулевой набор множителейЛагранжа λ∗ = (λ∗0 , . . .
, λ∗m+s ), обладающий следующими свойствами:57i)L0u (u∗ , λ∗ )=λ∗0 J 0 (u∗ )+m+sXλ∗i gi0 (u∗ ) = 0i=1— условие стационарности функции Лагранжа;ii)λ∗i > 0 ∀i = 0, m — условия неотрицательности множителей Лагранжа;iii)λ∗i gi (u∗ ) = 0 ∀i = 1, m — условия, дополняющие нежёсткости.Доказательство.Для начала договоримся о некоторых соглашениях.Во-первых, как и в доказательстве Теоремы 22, не ограничивая общности, будемсчитать, чтоJ(u∗ ) = 0(d1).Во-вторых, будем считать, чтоgi (u∗ ) = 0 ∀i = 1, m(d2).На самом деле, это не столь сильное ограничение, как может показаться, так какпри невыполнении этого условия, можно рассмотреть другую окрестность Uε , что иллюстрирует рисунок.
Поэтому мы рассматриваем лишь задачу на границе. Заметим, что,принимая это соглашение, мы автоматически избавляем себя от доказательства пунктаiii), так как он, очевидно, выполняется.gi (u) = 0u∗Uεgi (u) 6 0В-третьих, для удобства обозначим через g0 (u) саму функцию J(u):g0 (u) = J(u)(d3).Далее, пусть G(u) = (gm+1 (u), .
. . , gm+s (u)) : H → Rs . По условию теоремы в точке u∗эта функция дифференцируема по Фреше, то есть существует линейный ограниченный00оператор G0 (u∗ ) = (gm+1(u∗ ), . . . , gm+s(u∗ )) ∈ L(H → Rs ).Возможны три случая:581) im G0 (u∗ ) 6= Rs ;2) im G0 (u∗ ) = Rs , ker G0 (u∗ ) = {0} (состоит из одного нуля);3) im G0 (u∗ ) = Rs , ker G0 (u∗ ) 6= {0}.Рассмотрим все три этих случая.1) Вырожденный случай: im G0 (u∗ ) 6= RsВ этом случае пространство Rs раскладывается на прямую сумму подпространств(см. Упражнение 18):Rs = im G0 (u∗ ) ⊕ ker(G0 (u∗ ))∗ = {Rs конечномерно} = im G0 (u∗ ) ⊕ ker(G0 (u∗ ))∗ .Таким образом, найдётся ненулевой вектор λ0 ∈ ker(G0 (u∗ ))∗ , для которого справедливо выражение:m+sX0∗ 00 = (G (u∗ )) [λ ] =λ0i gi0 (u∗ ).i=mТеперь в качестве искомого набора множителей Лагранжа достаточно взять:λ∗ = (λ∗0 = 0, . .
. , λ∗m = 0, λ∗m+1 = −λ0m+1 , . . . , λ∗m+s = −λ0m+s ) 6= 0.Как нетрудно видеть, для этого набора все утверждения теоремы выполняются.2) “Полувырожденный” случай: im G0 (u∗ ) = Rs , ker G0 (u∗ ) = {0}Аналогично предыдущему случаю, имеем разложение пространства H = im(G0 (u∗ ))∗(dim H 6 s). То есть найдётся такой вектор λ0 ∈ RS , чтоJ 0 (u∗ ) = (G0 (u∗ ))∗ [λ0 ] =m+sXλ0i gi0 (u∗ ).i=m+1В качестве искомого набора λ∗ берём следующий:λ∗ = (λ∗0 = 1, λ∗1 = 0, . .
. , λ∗m = 0, λ∗m+1 = −λ0m+1 , . . . , λ∗m+s = −λ0m+s ) 6= 0.3) Невырожденный случай: im G0 (u∗ ) = Rs , dim(ker G0 (u∗ )) > 1Обозначим через Vk множества следующего вида:k = 0, m.Vk = u ∈ H | G0 (u∗ )[u] = 0, hgi0 (u∗ ), ui < 0, i = k, mЗаметим, что условие dim(ker G0 (u∗ )) > 1 в этом случае важно, так как иначе все Vkбыли бы пустыми.Очевидно, что справедлива цепочка вложений:V0 ⊆ V1 ⊆ .
. . ⊆ Vm .Докажем, что V0 = ∅. Предположим обратное, то есть, что существует некий элемент v ∈ V0 . Это означает, что v ∈ ker G0 (u∗ ) и hgi (u∗ ), vi < 0 для i = 0, m. Так как59im G0 (u∗ ) = Rs , то по Теореме Люстерника получаем, что ker G0 (u∗ ) = Tu∗ {u | G(u) = 0}и существует отображение ϕ(t): (−ε, ε) → H такое, что u∗ + tv + ϕ(t) ∈ {u | G(u) = 0},то есть G(u∗ + tv + ϕ(t)) = 0 для любого t из интервала (−ε, ε).Таким образом, все точки вида u∗ + tv + ϕ(t) ≡ u(t) удовлетворяют ограничениямтипа “равенство”.Теперь для всех i = 0, m разложим функции gi в окрестности точки u∗ :gi (u(t)) = gi (u∗ ) + hgi0 (u∗ ), tv + ϕ(t)i + o(tv + ϕ(t)) == {(d1), (d2)} = t hgi0 (u∗ ), vi + o(t) < 0 ∀t ∈ (0, ε)Мы получили, что для t из интервала (0, ε) точки u(t) принадлежат допустимомумножеству U, и в тоже время J(u(t)) < 0, что противоречит с (d1).
Значит наше предположение неверно и V0 = ∅.Рассмотрим случай, когда все Vi не содержат элементов, то есть когда0(u∗ ), ui < 0} = ∅.Vm = {u ∈ H | G0 (u∗ )[u] = 0, hgmПоставим задачу минимизации функционала на ядре:0Jm (u) = hgm(u∗ ), ui → inf,u ∈ ker G0 (u∗ )(2)Если Vm = ∅, то u = 0 — решение (2).
Разложим градиент в ортогональную сумму:⊥01212gm(u∗ ) = gm+ gm, где gm∈ ker G0 (u∗ ), gm∈ (ker(G0 (u∗ )) 1 1Jm (u) = gm, u ⇒ {min = 0} ⇒ gm=00(u∗ ) ∈ im(G0 (u∗ ))0 , и существует такой векторТаким образом, получаем, что gmsλ ∈ R , чтоm+sX01·gm(u∗ ) =λ0i gi0 (u∗ ).0i=mТогда в качестве искомого набора множителей Лагранжа можно взятьλ∗ = (λ∗0 = 0, λ∗1 = 0, .
. . , λ∗m−1 = 0, λ∗m = 1, λ∗m+1 = −λ0m+1 , . . . , λ∗m+s = −λ0m+s ).Остаётся рассмотреть случай, когда∅ = V0 = V1 = . . . = Vk ⊂ Vk+1 ⊆ Vk+1 ⊆ . . . ⊆ Vm .Аналогично предыдущим рассуждениям поставим задачу минимизации:Jk (u) = hgk0 (u∗ ), ui → inf,u ∈ {u ∈ ker G0 (u∗ ) | hgi0 (u∗ ), ui 6 0, i = k + 1, m}(3)и покажем, что u = 0 — решение задачи (3).Необходимо доказать, что inf в (3) неотрицателен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
