Методы оптимизации. Конспект лекций (Буряков) (2003) (1125388), страница 11
Текст из файла (страница 11)
Сделаем это методом от противного. Предположим, что Jk∗ < 0, тогда найдутся допустимый для (3) вектор v и векторw ∈ Vk+1 такие, чтоhgk0 (u∗ ), vi < 0, hgi0 (u∗ ), vi 6 0 для i = k + 1, m, G0 (u∗ )[v] = 0,60hgk0 (u∗ ), wi < 0, gj0 (u∗ ), w < 0 для j = k + 1, m, G0 (u∗ )[w] = 0.Сдвинувшись на достаточно малое ε из v в направлении w, получимhgk0 (u∗ ), v + εwi < 0,hgi0 (u∗ ), v + εwi 6 0 для i = k + 1, mи, так как G линеен,G0 (u∗ )[v + εw] = 0.Мы получили, что точка v + εw содержится во множестве Vk , которое по предположению пусто.
Полученное противоречие доказывает, что v = 0 — решение.Так как Vk+1 6= ∅ то задача (3) является выпуклой задачей, для которой выполняютсяусловия Слейтера. Применим к (3) Теорему 22.Пусть классическая функция ЛагранжаLk (u, λ) =1· hgk0 (u∗ ), ui+mXλi hgi0 (u∗ ), uii=k+1удовлетворяет принципу минимума из Теоремы 22 при λ = λ0 = (1, λ0k+1 , . . .
, λ0m ) 6= 0.Тогда для любого u ∈ ker G0 (u∗ ) (= U0 ) будет выполняться неравенство0=1· hgk0 (u∗ ), ui+mXλ0i hgi0 (u∗ ), ui 6 Lk (u, λ0 ).i=k+1Так как множество терпимых ограничений и функция Лагранжа линейны, отсюдаполучаем, что Lk (u, λ0 ) = 0 для любого u ∈ ker G0 (u∗ ) (вместо u можно взять −u иполучить аналогичное верное неравенство).Мы получили, что1·gk0 (u∗ )+mX⊥∗λ0i gi0 (u∗ ) ∈ (ker G0 (u∗ )) = im (G0 (u∗ )) ,i=k+1и существует такой набор (λ0m+1 , . . . , λ0m+s ) ∈ Rs , то в качестве искомого вектора можновзятьλ∗ = (λ∗0 = 0, .
. . , λ0k−1 = 0, λ∗k = 1, λ∗k+1 = λ0k+1 , . . . , λ∗m = λ0m ,λ∗m+1 = −λ0m+1 , . . . , λ∗m+s = −λ0m+s ).Теорема полностью доказана.Упражнение 18 (5). Доказать, что в случае, когда A ∈ L(H → F), H, F — гильбертовы пространства, справедливы разложения:F = im A ⊕ ker A∗ ,H = im A∗ ⊕ ker A.(Замечание: в бесконечномерном случае замыкания писать необходимо.)Опишем теперь достаточные условия регулярности в рассматриваемой задаче.
В случае когда im G0 (u∗ ) = Rs и существует такой элемент h ∈ H, что611) G0 (u∗ )[h] = 0;2) hgi0 (u∗ ), hi < 0 ∀i = 1, m,то в любом наборе множителей Лагранжа λ0 6= 0.Для доказательства предположим, что существует набор, в котором λ0 = 0. Тогда изутверждения i) Теоремы 24 имеемm+sXλi gi0 (u∗ ) = 0.i=1Умножим это равенство скалярно на h:mXi=1λi hgi0 (u∗ ), hi +|{z}>0|{z2) ⇒ <0}m+sXi=m+1λi hgi0 (u∗ ), hi = 0.| {z }1) ⇒ =0Получаем, что λi = 0 для любого i = 1, m иm+sXλi gi0 (u∗ ) = 0 ∀u ∈ H.i=m+1Следовательно,∗(G0 (u∗ )) [(λm+1 , .
. . , λm+s )] , u = 0 ∀u ∈ H.А так как im G0 (u∗ ) = Rs , мы получаем, что λm+1 = . . . = λm+s = 0, то есть все λi = 0.Полученное противоречие доказывает наше утверждение.Упражнение 19 (4). Пусть H — гильбертово пространство, A ∈ L(H → H),A = A∗ > 0. Решить с помощью Теоремы 24 задачу минимизации:J(u) = hAu, ui → inf, kuk2H = 1.(В случае бесконечномерного H существование решения предполагается.)Двойственные экстремальные задачиВ этом пункте рассмотрим задачу минимизацииJ(u) → inf,u ∈ U = {u ∈ U0 ⊆ L | g1 (u) 6 0, . .
. , gm (u) 6 0, gm+1 (u) = 0, . . . , gm+s (u) = 0} .(1)Для решения подобных задач иногда легче перейти к решению так называемых двойственных задач. Опишем этот процесс. Строим функцию Лагранжа для задачи (1):L(u, λ) = 1·J(u) +m+sXλi gi (u), u ∈ U0 , λ ∈ Λ0 = λ ∈ Rm+s | λi > 0, i = 1, m .i=162(2)Рассмотрим функциюϕ(u) = sup L(u, λ) =λ∈Λ0J(u), если u ∈ U,.+∞, если u ∈ U0 \U(3)Задача (1) равносильна задаче минимизации на расширенном множестве:ϕ(u) → inf,u ∈ U0 .(4)Вводим функциюψ(λ) = inf L(u, λ).(5)u∈U0Определение. Задачаψ(λ) → sup,λ ∈ Λ0(6)называется двойственной к исходной задаче (1).Теорема 25. Всегда верны неравенства:ψ(λ) 6 ψ ∗ 6 ϕ∗ = J∗ 6 ϕ(u),∀λ ∈ Λ0 , ∀u ∈ U0 .(7)Для того, чтобыψ ∗ = ϕ∗ , U∗ 6= ∅, Λ∗ 6= ∅,(8)необходимо и достаточно, чтобы L(u, λ) имела седловую точку на U0 × Λ0 ; U∗ × Λ∗ —множество всех седловых точек.Доказательство.Утверждение (7) следует непосредственно из определения ϕ(u) и ψ(λ).Докажем, что из (8) следует существование седловой точки.
Возьмём любые u∗ ∈ U∗ ,λ∗ ∈ Λ∗ . Для них верна цепочка неравенств:ψ ∗ = ψ(λ∗ ) = inf L(u, λ∗ ) 6 {U∗ ⊆ U0 } 6 L(u∗ , λ∗ ) 6 sup L(u∗ , λ) = ϕ(u∗ ) = ϕ∗ .u∈U0λ∈Λ0Так как ϕ∗ = ψ ∗ , все неравенства превращаются в равенства и мы имеем:L(u∗ , λ) 6 sup L(u∗ , λ) = L(u∗ , λ∗ ) = inf L(u, λ∗ ) 6 L(u, λ∗ ),u∈U0λ∈Λ0∀λ ∈ Λ0 , ∀u ∈ U0 .То есть (u∗ , λ∗ ) — седловая точка.Итак мы доказали, что U∗ × Λ∗ содержится во множестве седловых точек.Теперь проведём доказательство обратного вложения. Пусть точка (u∗ , λ∗ ) — седловая для функции L.
Докажем, что выполняются условия (8). Нам известно, чтоL(u∗ , λ) 6 L(u∗ , λ∗ ) 6 L(u, λ∗ ) ∀λ ∈ Λ0 , ∀u ∈ U0 .Взяв sup по λ и inf по u, получимϕ∗ 6 {u∗ ∈ U0 } 6 ϕ(u∗ ) 6 L(u∗ , λ∗ ) 6 ψ(λ∗ ) 6 {λ∗ ∈ Λ0 } 6 ψ ∗ 6 {(7)} 6 ϕ∗ .Отсюда имеем, что u∗ — оптимальный элемент и λ∗ — оптимальный элемент, U∗ 6= ∅,Λ 6= ∅, ϕ∗ = ψ ∗ и теорема доказана.∗63Пример. (ψ ∗ < ϕ∗ , седла нет)Рассмотрим функционал J(u) = e−u на множествеU = {u ∈ R1 | g(u) = ue−u = 0} = {0}.Имеем,J∗ = J(0) = 1 = ϕ∗ ,U∗ = {0} =6 ∅,L(u, λ) = 1·e−u + λue−u = e−u (1 + λu), 0, если λ = 0,1−∞, если λ > 0,Λ0 = R , ψ(λ) = −1+ 1λ , если λ < 0.λeТо есть ψ ∗ = 0 = ψ(0), Λ∗ = {0} =6 ∅ и ϕ∗ > ψ ∗ .Пример. (ψ ∗ = ϕ∗ , U∗ 6= ∅, Λ∗ = ∅, седла нет)Рассмотрим функционал J(u) = −u на множествеU = {u ∈ R1 | g(u) = u2 6 0} = {0}.Имеем,ϕ∗ = 0 = J∗ , U∗ = {0} =6 ∅,2L(u, λ) = 1·(−u) + λu , λ ∈ Λ0 = {λ > 0}, ψ(λ) =1− 4λ, если λ > 0,.−∞, если λ = 0То есть ψ ∗ = 0, но множество Λ∗ пусто.Вторая двойственная задачаВведём понятие второй двойственной задачи.
Для этого рассмотрим одинПример.Рассмотрим минимизацию функции J(u) = u2 на множествеU = {g(u) = u2 − 1 6 0} = [−1, 1].Имеем:J∗ = ϕ∗ = 0, U∗ = {0} =6 ∅,L(u, λ) = u2 + λ(u2 − 1)Получаем ψ(λ) = −λ, если λ > −1 (в нашем случае λ > 0).Теперь поставим двойственную задачу к ψ(λ):ψ(λ) = −λ → sup, ψ ∗ = 0 = ψ(0), Λ∗ = {0} =6 ∅.λ>0Перейдём к задаче на минимум (J(v) = −ψ(v)):J(v) = v → inf, v > 0,64(v := λ)v ∈ V = {v ∈ R1 = V0 | g(v) = −v 6 0}Отсюда получаем функцию Лагранжа:L(v, µ) = 1·v + µ(−v), µ > 00, если µ = 1,ψ(µ) =.−∞, если µ 6= 1Определение.
Задача максимизации функции ψ(µ) при µ > 0 называется второйдвойственной задачей.Приведённый пример показывает, что вторая двойственная задача не всегда совпадает с исходной.Упражнение 20 (4). Доказать, что для канонической задачи линейного программирования вторая двойственная задача совпадает с исходной.7Простейшая задача оптимального управления.Принцип максимума ПонтрягинаПостановка задачиВ этой главе мы коснёмся задачи оптимизации, которую принято называть задачей оптимального управления. Более подробно этот вопрос освещается в соответствующемкурсе, мы же рассмотрим его, исходя из наших потребностей.В общем виде рассматриваемая задача выглядит следующим образом:ZTJ(u) =f 0 (x(t), u(t), t) dt + ϕ(x(T )) → inft0x0 (t) = f (x(t), u(t), t) почти всюду для t0 < t < T, x(t0 ) = x0 ,(1)u ∈ U = {u(t) — измерима по Лебегу | u(t) ∈ V ⊆ Rr для почти всех t}Функционал f 0 принято называть интегрантом, а функционал ϕ — терминантом.Заметим, что в такой постановке отсутствуют фазовые ограничения на x(t)(x(t) ∈ G ⊆ Rn ), что облегчает нам исследование задачи.Предположим существование f, fx , f 0 , fx0 , ϕ, ϕx их непрерывность по t, и Липшицнепрерывность по x и u на Rn × V × [t0 ; T ].
(В принципе можно обойтись без Липшицнепрерывности, но при этом многие выкладки значительно усложняются.) В дальнейшембудем ссылаться на подобное существование отметкой (2).Функция Гамильтона-Понтрягина. Принцип максимумаВ этом пункте рассмотрим функцию следующего вида:H(x, u, t, ψ) = f 0 (x, u, t) + hψ, f (x, u, t)iRn ,65называемой функцией Гамильтона-Понтрягина.Введём ряд обозначений:∆J = J(u + h) − J(u),∆x = x(t, u + h) − x(t, h),∆f 0 = f 0 (x(t, u + h), u(t) + h(t), t) − f 0 (x(t, u), u(t), t) .Преобразуем ∆J(u) так, чтобы получить принцип максимума.ZT∆J =∆f 0 dt + ∆ϕ.(3)t0Применяя формулу конечных приращений, имеем∆ϕ = hϕx (x(T ) + θ∆x(T )) ± ϕx (x(T )), ∆x(T )iRn = hϕx (x(T )) , ∆x(T )iRn + Rϕ ,где θ ∈ [0, 1], Rϕ — некоторый остаток.Таким образом, получаемZT∆J =∆f 0 dt + hϕx (x(T )) , ∆x(T )iRn + Rϕ .(4)t0Введём обозначениеψ(T ) = ϕx (x(T )) .(5)Тогдаhϕx (x(T )) , ∆x(T )i = hψ(T ), ∆x(T )i = {∆x(t0 ) = 0} = hψ(T ), ∆x(T )i − hψ(t0 ), ∆x(t0 )i =ZT=dhψ(t), ∆x(t)i dt =dtZThψ 0 (t), ∆x(t)i dt +t0t0ZThψ(t), ∆x0 (t)i dt.t0Таким образом, имеемZT∆J =ZT∆H dt +t0hψ 0 (t), ∆x(t)i dt + Rϕ .(6)t0Теперь, используя формулу конечных приращений и элементарные преобразования,представим ∆H в несколько ином виде:∆H = (H (x(t, u + h), u + h, t, ψ) − H (x(t, u), u + h, t, ψ)) ++ (H (x(t, u), u + h, t, ψ) − H (x(t, u), u, t, ψ)) == hHx (x(t) + θ(t)∆x(t), u + t, t, ψ) , ∆x(t)i + ∆u H,где θ ∈ [0; 1], а через ∆u H обозначено второе слагаемое.66Продолжая цепочку равенств, получаем∆H = hHx (x, u, t, ψ), ∆x(t)i + ∆u H + RH (t),где RH (t) — некий остаток, связанный с H(.
. .). Имеем:ZTZT(7)t0t0t0RH (t) dt + Rϕ .hψ + Hx , ∆xi dt +∆u H dt +∆J =ZT0Потребуем, чтобы выполнялось равенствоψ 0 (t) = −Hx (x(t), u(t), t, ψ(t)).(8)При выполнении этого условия выражение (7) преобразуется вZTZTRH (t) dt + Rϕ .∆u H dt +∆J =t0(9)t0Оценим остатки в этом выражении. Для этого рассмотрим сначала производную приращения x:∆x0 (t) = ∆f (t), t0 < t < T ;∆x(t0 ) = 0.Перейдём к эквивалентной интегральной форме:Zt∆x(t) =∆f (τ ) dτ.t0Тогда из условия Липшица получим:Ztk∆x(t)kRn 6 LZtk∆x(τ )kRn dτ + Lt0t0Zt=∆u(τ )ZTk∆x(τ )kRn dτ + L6Lk h(τ ) kRr dτ 6|{z}t0kh(τ )kRr dτ.t0По лемме Гронуола-Бэллмана имеем:k∆x(t)kRn 6 LkhkL1 (t0 ;T ) exp {L(t − t0 )} .Возьмём максимум по t от обоих частей этого неравенства:k∆x(t)kC[t0 ;T ] 6 constkhkL1 (t0 ;T ) = O (khkL1 ) .67Тогда для остатка Rϕ , используя условия Липшица и применяя неравенство КошиБуняковского, получаем следующую оценку:|Rϕ | = |hϕx (x(T ) + θ∆x(T )) − ϕx (x(T )) , ∆x(T )iRn | 66 {θ ∈ [0; 1]} 6 Lk∆x(T )k2Rn = O khk2L1Оценим остаток RH (t).RH (t) = hHx (x(t) + θ(t)∆x(t), u(t) + h(t), t, ψ(t)) − Hx (x(t), u(t) + h(t), t, ψ(t)) , ∆x(t)iRnВ силу неравенства Коши-Буняковского и условий (2) получаем TZZT RH (t) dt 6 L kθ(t)∆x(t)kRn (1 + kψkC ) k∆x(t)kRn dt.t0t0И так как ψ непрерывна и промежуток ограничен, то TZ RH (t) dt = O khk2 1 .Lt0Из оценок остатков получаем формулуZT∆J =∆u H dt + Okhk2L1 (t0 ;T ).(10)t0Теперь сформулируем основную теорему пункта.Теорема 26 (принцип максимума Понтрягина).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
