Методы оптимизации. Конспект лекций (Буряков) (2003) (1125388), страница 4
Текст из файла (страница 4)
5: к определению выпуклости функцииИмеем:J(u∗ ) 6 J(u∗ + α(v − u∗ )) 6 {опр. выпуклой функции} 6 (1 − α)J(u∗ ) + αJ(v).Отсюда следует, что αJ(u∗ ) 6 αJ(v), причём α > 0, таким образом, доказано первоеутверждение теоремы.Доказательство второго утверждения теоремы предоставляется читателю.Для доказательства третьего утверждения, предположим, что в U∗ существует элемент v∗ 6= u∗ , тогда для любого α из интервала (0, 1) будем иметь:J∗ = J(αu∗ + (1 − α)v∗ ) < {т.к. J строго выпукла} <{z}|∈U∗ (по п.2)< αJ(u∗ ) + (1 − α)J(v∗ ) = {v∗ , u∗ ∈ U} = J(v∗ ) = J∗ .Получили противоречие и теорема полностью доказана.Теорема 6 (сильно выпуклый вариант теоремы Вейерштрасса). Пусть H —гильбертово пространство, множество U ⊂ H выпукло и замкнуто (не обязательноограничено!), функция J(u) сильно выпукла с коэффициентом κ и полунепрерывна снизуна U (т.е. и слабо полунепрерывна снизу) тогда:1) J∗ > −∞;2) U∗ = {u∗ } =6 ∅;193) ∀u ∈ U κ2 ku − u∗ k2H 6 J(u) − J(u∗ ).Доказательство.Зафиксируем любую точку u0 из U и рассмотрим множествоM(u0 ) = {u ∈ U|J(u) 6 J(u0 )}.Докажем, что M(u0 ) выпукло, замкнуто и ограничено.Выпуклость следует из выпуклости U и J(u).Для доказательства замкнутости рассмотрим любую последовательность{uk }∞k=1 ⊂ M(u0 ), сходящуюся к некоторой точке u.
Необходимо доказать, что точкаu принадлежит множеству M(u0 ). Так как U замкнуто, то точка u ∈ U, иJ(u) 6 {J п.н. снизу} 6 lim J(uk ) 6 {J(uk ) 6 J(u0 )∀k} 6 J(u0 ).k→∞Таким образом, замкнутость доказана.Теперь докажем, что M(u0 ) ограничено. Для этого разобьём это множество на два(см. рис. 6):M(u0 ) = (M(u0 ) ∩ {ku − u0 k 6 2}) ∪ (M(u0 ) \ M1 ).{z}{z}||M1M2M (u0 ) == M1 ∪ M 2M2puM1pu0R=2Рис. 6: множество MМножество M1 ограничено (по построению), то есть нам необходимо доказать ограниченность множества M2 .Для любой точки u из M2 u ∈ U, J(u) 6 J(u0 ), ku − u0 k > 2.
Возьмём число1∈ (0, 21 ), 1 − α ∈ ( 12 , 1), тогда для точки v = u0 + α(u − u0 ) ∈ M1 выполα = ku−u0k| {z }k·k=1<2няется неравенствоκJ(v) 6 {J(u) сильно выпукла} 6 (1 − α)J(u0 ) + αJ(u) − α(1 − α)ku − u0 k2 .2Отсюда, перегруппировав слагаемые и учтя ограничения на α, получаем, чтоκku − u0 k 6 J(u0 ) − J(v).4Но v ∈ M1 , а для этого множества (так как оно выпукло, замкнуто и ограничено)выполнена Теорема 2: J1∗ = inf J(u) > −∞ — и мы имеем ku − u0 k 6 4(J(u0κ)−J1∗ ) .u∈M120Таким образом, множество M2 (а значит и всё множество M) ограничено и первоеутверждение теоремы полностью доказано.Второе утверждение теоремы следует непосредственно из Теоремы 5.Докажем третье утверждение. ИмеемJ(u∗ ) 6 J(u∗ + α(u − u∗ )) 6 {J(u) сильно выпукла} 6{z}|∈Uκ6 αJ(u) + (1 − α)J(u∗ ) − α(1 − α)ku − u∗ k22Отсюда следует, чтоκα(1 − α)ku − u∗ k2 6 αJ(u) + (1 − α)J(u∗ ) − J(u∗ ) = α[J(u) − J(u∗ )]2то есть, κ2 (1 − α)ku − u∗ k2 6 J(u) − J(u∗ ).
Устремляя α к нулю, получаем третье утверждение.Теорема 7 (критерий выпуклости для дифференцируемых функций). ПустьH — гильбертово пространство, множество U ⊂ H выпукло, J(u) ∈ C1 (U). Тогдаследующие утверждения эквивалентны:(a) J(u) выпукла;(b) J(u) > J(v) + hJ 0 (v), u − viH∀u, v ∈ U;(c) hJ 0 (u) − J 0 (v), u − viH > 0 ∀u, v ∈ U.Если, кроме того, J(u) ∈ C2 (U) и intU 6= ∅, то эквивалентны утверждения (a)−(c)и утверждение(d) hJ 00 (u)·h, hiH > 0 ∀u ∈ U, ∀h ∈ H.Доказательство.Для начала проведём цепочку доказательств по схеме (a) ⇒ (b) ⇒ (c) ⇒ (a).1) (a) ⇒ (b)По определению выпуклой функции:J(αu + (1 − α)v) 6 αJ(u) + (1 − α)J(v).Перегруппируем слагаемые и получим:αJ(u) > αJ(v) + [J(v + α(u − v)) − J(v)].Применим к выражению в квадратных скобках формулу конечных приращений:αJ(u) > αJ(v) + hJ 0 (v + θα(u − v)), α(u − v)iH , θ ∈ [0, 1].Теперь разделим обе части неравенства на α > 0 и устремим α к нулю.
Так какJ 0 (u) непрерывна по условию, мы получим, что для любых u, v ∈ U:J(u) > J(v) + hJ 0 (v), u − viH ,т.е. утверждение (b).212) (b) ⇒ (c)Запишем условие (b) для любых двух точек u, v ∈ U:J(u) > J(v) + hJ 0 (v), u − viHJ(v) > J(u) + hJ 0 (u), v − uiH ,и сложим два этих неравенства:J(u) + J(v) > J(v) + J(u) + hJ 0 (v) − J 0 (u), u − viHОтсюда непосредственно следует утверждение (c).3) (c) ⇒ (a)Обозначим через w выражение αu + (1 − α)v.
Тогда:αJ(u) + (1 − α)J(v) − J(αu + (1 − α)v) = αJ(u) + (1 − α)J(v) − [αJ(w) + (1 − α)J(w)] == α(J(u) − J(w)) + (1 − α)(J(v) − J(w)) = {формула конечных приращений} =Z1Z10hJ (w + t(u − w)), u − wiH dt + (1 − α)=α0hJ 0 (w + t(v − w)), v − wiH dt.0Заметим, что u−w = (1−α)(u−v), v −w = α(v −u) и, продолжая цепочку равенств,получим, что предыдущее выражение равноZ1α(1 − α)hJ 0 (w + t(u − w)) − J 0 (w + t(v − w)), u − viH dt.0Если обозначить через x выражение w + t(u − w), а через y выражение w + t(v − w),то u−v будет равняться (x−y)/t, где t > 0. Тогда в этих обозначениях предыдущийинтеграл равенZ11 0hJ (x) − J 0 (y), x − yiH dt > 0.t0Таким образом, импликация (c) ⇒ (a) доказана.Докажем теперь, что из утверждения (c) с дополнительными ограничениями следуетутверждение (d).Фиксируем любое u ∈ intU и любое h ∈ H.
Тогда существует такое ε0 > 0, что длялюбого ε ∈ [0, ε0 ] точка u + εh ∈ U. ИмеемhJ 0 (u + εh) − J 0 (u), εhiH > 0.Применим к первому аргументу скалярного произведения формулу конечных приращений (здесь учитывается, что J(u) ∈ C2 (U)):hJ 00 (u + θεh)εh, εhiH > 0 θ = θ(ε) ∈ [0, 1].22Разделим это неравенство на ε2 и устремим ε к нулю.
Тогда, учтя, что J 00 (u) непрерывна,получим, что утверждение (d) выполнено для всех u ∈ intU.Теперь применим свойство выпуклых множеств: intU = intU (здесь оно приводитсябез доказательства, см., например, [АТФ, стр.216-217]). Имеем, что (d) выполняется длявсех u ∈ U ∩ intU = U ∩ U = U.Для завершение доказательства теоремы докажем, что выполнение условия (d) влечёт за собой (c), а это следует из того, чтоhJ 0 (u) − J 0 (v), u − viH = {Упражнение 6} = hJ 00 (v + θ(u − v))(u − v), u − viH > 0.Таким образом, теорема полностью доказана.Аналогичным образом можно доказать подобную теорему для случая сильной выпуклости. Приведём её формулировку.Теорема 8 (критерий сильной выпуклости для дифференцируемых функций).Пусть H — гильбертово пространство, множество U ⊂ H выпукло, J(u) ∈ C1 (U).Тогда следующие утверждения эквивалентны:(a0 ) J(u) сильно выпукла с коэффициентом κ > 0;(b0 ) J(u) > J(v) + hJ 0 (v), u − viH + κ2 ku − vk2H(c0 ) hJ 0 (u) − J 0 (v), u − viH > κku − vk2H∀u, v ∈ U;∀u, v ∈ U.Если, кроме того, J(u) ∈ C2 (U) и intU 6= ∅, то эквивалентны утверждения (a0 ) −(c ) и утверждение0(d0 ) hJ 00 (u)·h, hiH > κkhk2H∀u ∈ U, ∀h ∈ H.Доказательство.По сути, необходимо повторить доказательство Теоремы 7, учитывая сильную выпуклость.
Предоставим это читателю.Приведём пример, показывающий, что условие intU 6= ∅ в пунктах (d) и (d0 ) Теорем 7и 8 важно.Рассмотрим множество U = {y = 0} в пространстве R2 (u = (x, y), U выпукло,intU = ∅) и функцию J(u) = x2 − y 2 . J(u) ∈ C2 и сильно выпукла, однако очевидно, чтоеё вторая производная2000J (u) =0 −2не удовлетворяет ни условию (d), ни условию (d0 ).Примеры применения Теорем 7 и 8.1) J(u) = hc, ui — линейная функция, выпуклая, но не сильно.
J 00 (u) = 0, т.е. неравенство (d) выполняется, но при этом неравенство (d0 ) не выполняется.232) J(u) = kAu − f k2F , A ∈ L(H → F), f ∈ F — квадратичный функционал, какизвестно выпуклый (доказано выше). Докажем это по-другому — применяя Теорему 7.J 00 (u) = 2A∗ A ∈ L(H → H)hJ 00 (u)h, hiH = h2A∗ Ah, hiH = 2kAhk2F > 0 ∀h ∈ H.То есть условие (d) выполняется.В то же время J(u) — сильно выпуклый с коэффициентом κ > 0 тогда и толькотогда, когда2 hA∗ Ah, hiH > κkhk2H ∀h ∈ H.На алгебраическом языке это означает существование обратного оператора(A∗ A)−1 ∈ L(H → H).То есть, если det(A∗ A) 6= 0, то сильная выпуклость есть, а в противном случаесильной выпуклости нет.Докажем теперь одну из основных теорем курса.Теорема 9 (условия оптимальности в форме вариационного неравенства).Пусть множество U — выпукло, J(u) ∈ C1 (U). Тогда1) если u∗ = argmin J(u), то hJ 0 (u∗ ), u − u∗ i > 0 ∀u ∈ U (1);u∈U2) если u∗ ∈ intU, то J 0 (u∗ ) = 0;3) если выполняется (1), а J(u) выпукла, то u∗ = argmin J(u).u∈UДоказательство.1) Так как U выпукло, то для любой точки u из U найдётся такое число α0 ∈ [0, 1],что для любого α ∈ [0, α0 ] точка u∗ + α(u − u∗ ) будет принадлежать U.
Для этойточки по условию выполнено неравенство:J(u∗ + α(u − u∗ )) − J(u∗ ) > 0.Применяя формулу конечных приращений, получаем:hJ 0 (u∗ + θα(u − u∗ ), α(u − u∗ )i > 0.Разделим это неравенство на α и устремим α к нулю. Тогда в силу непрерывности J 0 (u) получаем первое утверждение утверждение теоремы.2) Для достаточно малых α > 0 точка ua = u∗ − αJ 0 (u∗ ) принадлежит U. Подставимточку ua в (1) и получим:hJ 0 (u∗ ), −αJ 0 (u∗ )i > 0,то есть kJ 0 (u∗ )k2 6 0, а это означает, что J 0 (u∗ ) = 0.243) Последнее утверждение теоремы следует из пункта (b) Теоремы 7:J(u) − J(u∗ ) > hJ 0 (u∗ ), u − u∗ i > 0.Теорема доказана.Примеры применения Теоремы 9.1) Рассмотрим следующую тривиальную задачу минимизации на одномерном пространстве H = R1 :J(u) = u2 → inf, u = x, U = [1, 2].Очевидно, что u∗ = 1. Получим этот результат с помощью (1).
Для нашего случаяскалярное произведение есть просто “естественное” умножение, поэтому необходимым условием оптимальности вследствие (1) является неравенство 2u∗ (u − u∗ ) > 0,которое должно выполняться для любого u из отрезка [1, 2]. Так как u∗ можетбыть только из [1, 2], то необходимо должно выполняться u − u∗ > 0 опять же длялюбого u из отрезка [1, 2]. Отсюда получаем, что u∗ = 1.2) Решим следующую задачу оптимального управления в пространстве L2 (0, 4):Z4J(u) =x(t) + u2 (t) dt → inf ,UU = {u ∈ L2 (0, 4) |u(t)| 6 1 почти всюду},0x0 (t) = u(t),x(0) = 0.0<t<4Для начала заметим, что множество U выпукло замкнуто и ограничено и, следовательно, является слабым компактом в L2 (0, 4).Разобьём функционал J(u) на два интеграла:Z4J(u) =Z4x(t) dt +0u2 (t) dt ≡ J1 (u) + J2 (u)0Функция J1 (u) выпукла как линейная по u.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
