А.В. Фурсиков - Курс лекций по вариационному исчислению (1156151), страница 5
Текст из файла (страница 5)
Рассмотрим одномерную задачу(ϕ(λ) = f xb + λh + r(λ) → inf,(90)F (bx + λh + r(λ)) = 0.Ясно, что λ = 0 является локальным минимумом новой задачи (так как xb ∈ locmin), поэтому0 = ϕ′ (0) = hf ′ (bx), hi .Значит,⊥ !!∗!x) = Im F ′ (bx) .f ′ (bx) ∈ (TxbM )⊥ = Ker F ′ (b(91)(92)Здесь переход «!» следует из теоремы о касательном пространстве, а «!!» — из теоремы 1.12. Поэтому найдётсяy ∗ ∈ Y ∗ такой, что∗f ′ (bx) + F ′ (bx) y ∗ = 0,(93)откуда следует, что иИтак,L′x (bx, 1, y ∗ )hf ′ (bx), hi + hF ′ (bx)h, y ∗ i = 0.(94)= 0 и теорема доказана. Пример 2.1. Покажем, что условие замкнутости Im F ′ (x) существенно.
ПустьX = R × ℓ2 = {(α, y) : α ∈ R, y ∈ ℓ2 } , Y = ℓ2 ,(95)y yyn12Λ : (y1 , y2 , . . . , yn , . . .) 7→, ,..., ,... .(96)1 2nЛегко видеть, что Im Λ 6= ℓ2 (например, образ не содержит (1, 12 , 31 , . . .)) и Im Λ = ℓ2 . В частности, образ незамкнут. Возьмем какое-нибудь yb ∈ ℓ2 r Im Λ. Определим отображения f и F :f (α, y) := α, F (α, y) := Λy + αby.(97)Рассмотрим задачу(f (x) → inf,F (x) = 0,(98)Ясно, что из равенства F (α, y) = 0 следует α = 0, откуда y = 0, то есть множество допустимых элементов —это {(0, 0)}. Покажем, что принцип Лагранжа всё же не выполнен. Возьмем 0 6= (λ, z) ∈ (R × ℓ2 )∗ ∼= R × ℓ2 .ИмеемXykL (α, y), λ, z = λα ++ αbyk zk .(99)kkПредположим, что L′x (0, λ, z) = 0. ИмеемL′α = 0 = λ +откуда следует λ = 0, z = 0.
Противоречие.Xkybk zk ,Пример 2.2. Конечномерные задачи вида(f0 (x) → inf,L′yk =zk= 0,kfk (x) = 0, (k = 1, 2, . . . , n),где fj : Rn → R являются частным случаем задачи (87).2 Формула(A, B)′ = (A′ , B ′ ) легко доказывается.15(100)(101)1.3. Выпуклые задачи1.3.1. Выпуклые функцииНам понадобится расширенная вещественная прямая R := R ∪ {−∞} ∪ {+∞}. Пусть X — линейное пространство, и f : X → R.Определение.
Эффективным множеством f называется множество dom f := {x ∈ X : f (x) < ∞}.Определение. Надграфиком f называется множество epi f := {(α, x) ∈ R × X : x ∈ dom f, α > f (x)}.Определение. Функция f называется выпуклой, если epi f — выпуклое множество.Определение. Функция f называется собственной, если dom f 6= ∅ и f > −∞.В основном мы будем рассматривать собственные функции.Утверждение 1.20. Пусть f : X → R — собственная функция. Она является выпуклой тогда и толькотогда, когда выполнено неравенство Йенсена:f (αx1 + (1 − α)x2 ) 6 αf (x1 ) + (1 − α)f (x2 )(102)для любых x1 , x2 ∈ dom f и всех α ∈ [0, 1].
Пусть выполнено неравенство Йенсена. Возьмем (a, x1 ), (b, x2 ) ∈ epi f и α ∈ [0, 1]. Покажем, что α(a, x1 )++ (1 − α)(b, x2 ) ∈ epi f . Действительно,f (αx1 + (1 − α)x2 ) 6 αf (x1 ) + (1 − α)f (x2 ) < ∞,(103)откуда αx1 + (1 − α)x2 ∈ dom f . Далее,αa + (1 − α)b > αf (x1 ) + (1 − α)f (x2 ) > f (αx1 + (1 − α)x2 ),откуда αa + (1 − α)b, αx1 + (1 − α)x2 ∈ epi f .
В обратную сторону — аналогично. (104)Собственные выпуклые функции f : X → R можно отождествить с выпуклыми функциями f : M → R, определенными навыпуклых непустых множествах M ⊂ X, поскольку в силу неравенства Йенсена dom f является выпуклым множеством.1.3.2. Постановка выпуклой задачиОпределение. Пусть X — линейное пространство, fj : X → R — собственные выпуклые функции (j == 0, 1, . . . , n), A ⊂ X — выпуклое множество. Рассмотрим задачу f0 (x) → inf,fj (x) 6 0 (j = 1, . . . , n),(105)x ∈ A.Задачи такого вида называются выпуклыми.Замечание.
Здесь важно, что стоит inf, а не sup, и что стоят неравенства вида f 6 0.Как и раньше, определим множество допустимых элементов:A := {x ∈ A | fj (x) 6 0 при j = 1, . . . , n} .(106)Заметим, что множество A выпукло. В отличие от обычных экстремальных задач, в выпуклом случае не бываетлокальных минимумов (см. лемму ниже).
Поэтому нам достаточно рассматривать абсолютные минимумы: мыпишем xb ∈ absmin, если xb ∈ A и для всех x ∈ A выполнено неравенство f0 (bx) 6 f0 (x).Если на X введена норма, то можно говорить о локальных минимумах задачи (105).Лемма 1.21. Если xb ∈ locmin задачи (105), то xb ∈ absmin задачи (105). Пусть xb ∈ locmin. Возьмем произвольный x ∈ A. Рассмотрим xα = αx + (1 − α)bx для α ∈ [0, 1].
Ясно,что xα ∈ A. Так как при малых α элемент xα близок к xb, а xb — локальный минимум, то при малых αf (bx) 6 f (xα ) = f αx + (1 − α)bx 6 αf (x) + (1 − α)f (bx),(107)откуда f (bx) 6 f (x). Нам понадобится теорема отделимости в следующей форме:Теорема 1.22 (Теорема отделимости для выпуклых множеств). Пусть C ⊂ Rn — выпуклое множество, не содержащее нуля. Тогда найдётся ненулевое λ ∈ Rn , такое что для всех c ∈ C выполнено (λ, c) > 0.16 Для выпуклого множества определено понятие размерности (например, как наименьшее s, при котором множество содержится в некотором аффинном подпространстве размерности s).
Без ограничения общности можно считать, что dim C = n, тогдаC = Int C. Далее, мы можем перейти от C к Int C и считать, что наше множество не только выпукло, но и открыто. Будем строитьподпространства Mk , не пересекающиеся с C, такие что dim Mk = k (в конце мы получим Mn−1 , не пересекающееся с C, и в качестве λ нужно будет взять нормаль к Mn−1 , смотрящую в то полупространство, где лежит C). M0 = {0}.
Пусть мы построилиM0 , M1 , . . . , Mk , k 6 n−2. Построим Mk+1 . Возьмем какое-нибудь двумерное подпространство P так, чтобы P ∩Mk = {0}. ПоложимC ′ := P ∩ (C − Mk ), C ′ выпукло, открыто в P и не содержит нуль. Мы свели задачу к плоскости P : если мы построим прямуюl ⊂ P , такую что l ∩ C ′ = ∅ и 0 ∈ l, то достаточно будет положить Mk+1 := Mk + l (ведь l ∩ (C − Mk ) = ∅ ⇔ (Mk + l) ∩ C = ∅).Но на плоскости все очевидно: конус {kc : c ∈ C ′ , k > 0} есть открытый сектор, соответствующий углу, не большему π, в качестве lможно взять прямую, содержащую один из граничных лучей.
1.3.3. Теорема Куна – ТаккераПусть нам дана выпуклая задача (105). Пусть λ = (λ0 , λ1 , . . . , λn ). Введём функцию Лагранжа:L(x, λ) :=nX(108)λj fj (x).j=0Теорема 1.23 (Кун – Таккер).1◦ Если xb ∈ absmin задачи (105), то найдётся λ 6= 0, такое что:а) λj > 0 при j = 0, . . . , n — условие неотрицательности,б) λj fj (bx) = 0 при j = 1, . . . , n — условие дополняющей нежёсткости,в) L(bx, λ) 6 L(x, λ) для всех x ∈ A.2◦ Если xb и λ таковы, что λ0 > 0 и выполнены условия а), б), в), то xb ∈ absmin задачи (105).3◦ Если в условиях 1◦ выполнено условие Слейтера, то есть найдётся x ∈ A такой, что fj (x) < 0 при всехj = 1, . .
. , n, то для всех λ имеем λ0 6= 0. 1◦ Без ограничения общности считаем f0 (bx) = 0. Рассмотрим множествоC := (α0 , α1 , . . . , αn ) найдётся x ∈ A, такой, что α0 > f0 (x), αj > fj (x) при всех j = 1, . . . , n .(109)Проверим, что к C можно применить конечномерную теорему отделимости.В самом деле, если (0, . .
. , 0) ∈ C, то для некоторого x ∈ A будет f0 (x) < 0 = f0 (bx) — противоречие.Далее, покажем, что C выпукло. Пусть (α0 , . . . , αn ), (β0 , . . . , βn ) ∈ C. Им соответствуют x1 и x2 , для которыхα0 > f0 (x1 ), αj > fj (x1 ), β0 > f0 (x2 ), βj > fj (x2 ). Тогда точка(110)γ(α0 , . . . , αn ) + (1 − γ)(β0 , .
. . , βn )соответствует γx1 + (1 − γ)x2 . Итак, по конечномерной теореме отделимости, найдется ненулевое λ, такое что(λ, c) > 0 для всех c ∈ C. Взяв c в виде c = (δ, 0, . . . , 1, . . . , 0) (единица на j-м месте), получаем неравенствоλ0 δ + λj > 0. Но поскольку δ > 0 произвольно, то λj > 0. Мы получили а).Перейдём к пункту б). Фиксируем j. Если fj (bx) = 0, то тем более λj fj (bx) = 0. Если же fj (bx) < 0, то возьмёмc = (δ, 0, .
. . , fj (bx), . . . , 0) (fj на j-м месте). Так как (λ, c) > 0, то δλ0 + λj fj (bx) > 0, откуда λj fj (bx) > 0. Этонеравенство возможно лишь при λj = 0.Теперь докажем в):nXб) !L(bx, λ) = λ0 f0 (bx) +λj fj (bx) = 0 6 L(x, λ) + δf0 (x),(111)j=1где «!» означает применение неравенства (λ, c) > 0 для c = (f0 (x) + δ, f1 (x), .
. . , fn (x)). В силу произвольности δзаключаем, что L(bx, λ) 6 L(x, λ).2◦ Пусть λ0 > 0 и выполнены условия а), б) и в). Тогдаnв)а)Xб)λ0 f0 (bx) = L(bx, λ) 6 L(x, λ) =λj fj (x) 6 λ0 f0 (x),(112)j=0поэтому xb ∈ absmin.3◦ Пусть xb ∈ absmin, и выполнено условие Слейтера, то есть fj (ex) < 0 (j = 1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
