Методы оптимизации. Конспект лекций (Буряков) (2003) (1125388), страница 5
Текст из файла (страница 5)
Функция J2 (u) = kuk2L2 (0,2) сильновыпукла с коэффициентом κ = 2. Отсюда получаем, что J(u) является сильновыпуклым и по Теореме 6 существует единственно оптимальное управление.Воспользуемся необходимым условием (1) для нахождения оптимального управления.hJ 0 (u∗ ), u − u∗ iL2 ≥ 0 ∀u ∈ U(∗)J 0 (u∗ ) в наших обозначениях представимо как J10 (u∗ ) + J20 (u∗ ), при этом J20 (u∗ ) =2u∗ . Если бы мы представили J1 (u) в каноническом виде J1 = hc, ui (виде Рисса),то J10 (u) = c.Z4J1 (u) =Z4x(t, u) dt =0Z4c(t)u(t) dt =0x(t)·1 dt =025Z40x(t)(t − 4)0 dt =Z4= {инт. по частям} = −x0 (t)(t − 4) dt =0Z4u(t)(t − 4) dt.0Таким образом, получаем, что J10 (t) = c(t) = 4−t.
Тогда условие (∗) переписываетсяв видеZ4((4 − t) + 2u∗ (t)) · (u(t) − u∗ (t)) dt > 0 ∀u ∈ U.0Воспользуемся тем, что это неравенство должно выполняться для любых u из U ирассмотрим следующее семейство функций, принадлежащих U:u∗ (t), t ∈ [0, 4]\(t0 − ε, t0 + ε)u(t) =v, t ∈ (t0 − ε, t0 + ε)где v любое число из отрезка [−1, 1], ε > 0Таким образом, мы заменили оптимальное управление функцией, отличной от оптимальной, лишь на интервале (t0 − ε, t0 + ε), на котором она принимается равнойдопустимой константе. Этот метод называют методом игольчатых вариаций.Тогда для любого положительного ε и любого v ∈ [−1, 1] условие (∗) переписывается в видеtZ0 +ε((4 − t) + 2u∗ (t)) · (u(t) − u∗ (t)) dt > 0t0 −εТеперь воспользуемся теоремой о дифференцируемости интеграла Лебега (см., например, [КФ, гл.VI, §6]).
Разделим полученное неравенство на 2ε и устремим ε к 0.Для почти всех t0 из интервала (0, 4) получим (4 − t0 + 2u∗ (t0 )) · (v − u∗ (t0 )) > 0.Возможны несколько вариантов.i) Предположим, что 4 − t0 + 2u∗ (t0 ) > 0. Так как u∗ (t0 ) ∈ [−1, 1], то при t0 изинтервала [0, 2) это неравенство будет выполнено. Тогда необходимо должновыполняться условие v − u∗ > 0 ⇔ v > u∗ для любого v ∈ [−1, 1]. Отсюда приt0 ∈ [0, 2) оптимальным является управление u∗ (t) ≡ −1.ii) Если 4 − t0 + 2u∗ (t0 ) < 0, то v − u∗ (t) 6 0 ∀v ∈ [−1, 1] и мы получаем, чтоu∗ (t) ≡ 1, но это противоречит тому, что 4 − t0 + 2u∗ (t0 ) < 0.
Значит этотвариант исключён.iii) Осталось рассмотреть случай, когда 4 − t0 + 2u∗ (t0 ) ≡ 0. Тогда получаем, чтопри t0 ∈ [2, 4] u∗ (t) = t−4.2Задача полностью решена.26u62q4q-−1 qtu∗ (t)Рис. 7: u∗ (t)Метрическая проекцияВ этом пункте M — метрическое пространство, ρ(x, y) — метрика, U ⊂ M.Определение. Проекцией prU (v) точки v на множество U называется argmin ρ(u, v)u∈U(в некоторых случаях выгоднее рассматривать проекцию как argmin ρ2 (u, v)).u∈UЗаметим, что в случае, когда U не выпукло, проекция точки, вообще говоря, можетбыть не единственной (см. рис.
8).p P1VpUp P2Рис. 8: пример проекции на невыпуклое множествоДля некоторых множеств проекции точки на них вообще не существует. Например,если рассмотреть открытый шар U = {kuk < 1} и точку вне этого шара, то она не будетиметь проекцию на это множество (см. рис. 9).Vp∈UРис. 9: пример отсутствия проекцииТеорема 10 (существование и единственность проекции и её свойства).Пусть H — гильбертово пространство, U — выпуклое замкнутое множество, тогда271) для любого элемента h из H существует единственная prU (h);p ∈ U,2) p = prU (h) ⇔(см. рис.
10);hp − h, u − piH > 0 ∀u ∈ U3) k prU (f ) − prU (g)kH 6 kf − gkH ∀f, g ∈ H. Это свойство называют нестрогойсжимаемостью оператора проектирования (см. рис. 11).Доказательство.1) Рассмотрим функцию J(u) = ku − hk2H . Она сильно выпукла (κ = 2). Множество Uвыпукло и замкнуто по условию. Отсюда по Теореме 6 следует, что J∗ конечно иU∗ = {u∗ } =6 ∅, то есть первое утверждение теоремы.2) Второе утверждение является следствием применения Теоремы 9 к этой же функции.3) Пусть pf = prU (f ), pg = prU (g). Тогда, применяя второе утверждение два раза,имеем:hpf − f, u − pf iH > 0hpg − g, u − pg iH > 0Примем за u в первом неравенстве pg , а во втором pf и сложим ихhpf − f − pg + g, pg − pf iH > 0или по-другомуhpf − pg , pg − pf iH + hg − f, pg − pf iH > 0.Тогда в силу неравенства Коши-Буняковского:kg − f kH ·kpg − pf kH > hg − f, pg − pf iH > hpf − pg , pg − pf iH > kpg − pf k2H .Разделим это неравенство на kpg − pf kH 6= 0 (если pg = pf доказываемое неравенство, очевидно, выполняется) и получим третье утверждение теоремы.Теорема полностью доказана.uαU*phРис.
10: к п. 2 Теоремы 1028fpppfgpppgUpf = pgfgРис. 11: к п. 3 Теоремы 10Упражнение 10 (5). Пусть H — гильбертово пространство, L — замкнутое линейное подпространство из H. Доказать, что prL есть линейный ограниченный самосопряжённый оператор (оператор ортогонального проектирования).Упражнение 11 (4). Пусть H — гильбертово пространство, L — замкнутое линейное подпространство из H, x0 ∈ H — фиксированная точка. Доказать, что (см. утв. 2Теоремы 10)p ∈ x0 + Lp = prx0 +L h ⇔hp − h, li = 0 ∀l ∈ L.Примеры на вычисление проекций.1) Пусть U — шар в H: U = {u ∈ H | ku − u0 kH 6 R, u0 ∈ H}.
Не ограничиваяобщности рассуждений, можно считать, что u0 = 0. Рассмотрим точку h 6∈ U. Тогдапо аналогии с геометрическим пространством R3 предположим, что проекция этойточки на множество U равна:prU (h) = Rh.khkHДокажем это, используя утверждение 2) Теоремы 10.
Для этого рассмотрим скалярное произведение hhRkhk2H− h, u − R=− 1 × hh, uiH − RRkhkHkhkH HkhkHkhkHТак как h 6∈ U, то khkH > R, а значит первый множитель этого произведения отрицателен. Во втором множителе распишем скалярное произведение по неравенствуКоши-Буняковского:hh, uiH 6 khkH ·kukH 6 R·khkH .Отсюда следует, что он неположителен, то есть всё скалярное произведение оказывается неотрицательным и выполняется второе условие Теоремы 10. Таким образом, наше предположение оказалось верным.292) Рассмотрим U = {u(t) ∈ L2 (a, b) | α(t) 6 u(t) 6 β(t); α(t), β(t) ∈ L2 } — “параллелепипед” в L2 . Для нахождения проекции функции h(t) (не принадлежащей U,так как в противном случае проекция просто будет равна h(t)) на U необходимоминимизировать норму:ku(t) − h(t)k2L2 =Zb|u(t) − h(t)|2 dt → inf .u∈UaПроекция в этом случае, как нетрудно видеть, будет равна: h(t), t : α(t) 6 h(t) 6 β(t),β(t), t : h(t) > β(t),[prU (h(t))] (t) =α(t), t : h(t) < α(t).Упражнение 12 (3).
Найти проекции1) в гильбертовом пространстве H на гиперплоскость U = {u ∈ H : hc, uiH = β};2) в пространстве Rn на “параллелепипед” U = {u ∈ Rn : αi 6 ui 6 βi , i = 1, n}.Теорема 11 (проекционная форма критерия оптимальности). Пусть H — гильбертово пространство, U — выпуклое замкнутое множество, J(u) ∈ C1 (U), J(u) выпукла. Тогдаu∗ = argmin J(u) ⇔ ∀α > 0 u∗ = prU (u∗ − αJ 0 (u∗ )).u∈UДоказательство.По Теореме 9 имеем, что u∗ является точкой минимума тогда и только тогда, когдаhJ 0 (u∗ ), u − u∗ i > 0 ∀u ∈ U.Умножим это неравенство на α > 0 и в первом аргументе скалярного произведенияприбавим и вычтем u∗ :hu∗ − (u∗ − αJ 0 (u∗ )), u − u∗ i > 0.Это неравенство по п.2 Теоремы 10 выполнено тогда и только тогда, когдаu∗ = prU (u∗ − αJ 0 (u∗ )).Теорема доказана.5Итерационные методы минимизацииМетод скорейшего спускаРассмотрим достаточно общую задачу минимизации:J(u) → inf,30u ∈ H.(1)Для её решения в данном методе строится следующая итерационная последовательность:uk+1 = uk − αk J 0 (uk ), k = 0, 1, 2, .
. . ; α > 0(2)Для начала процесса итерирования необходимо задать u0 ∈ H. Способов, для выбораu0 в общем случае не существует и в основном здесь исходят из каких-либо эмпирическихданных и полагаются на опыт.Критерии остановки процесса приближенного нахождения минимума могут бытьоснованы на различных соображениях. Приведём некоторые из них:1) kuk+1 − uk k 6 ε1 ;2) kJ(uk+1 ) − J(uk )k 6 ε2 ;3) kJ 0 (uk )k 6 ε3 .(εi выбираются, исходя из требований к решению). Обычно на практике применяюткомбинации этих оценок.Выбор шага спуска αk в общем случае также не единственен (причём на каждом шагеон может быть взят по-разному). Иногда αk берут не зависящим от k: αk = α ≡ const > 0.В методе скорейшего спуска αk определяется конкретным образом:αk = argmin J(uk − αJ 0 (uk )).(3)α>0Обозначим через fk (α) выражение J(uk − αJ 0 (uk )).Заметим, что в при таком выборе αk , если uk+1 = uk , то либо αk = 0, либо J 0 (uk ) = 0.Случай J 0 (uk ) = 0 является необходимым условием минимума и процесс итерированияможно остановить.
А в случае, когда αk = 0 из (3) имеем(fk0 (0) > 0fk0 (0) = hJ 0 (uk ), J 0 (uk )i 6 0.Откуда fk0 (0) = 0 и мы опять получили необходимое условие минимума.Теорема 12. Пусть H — гильбертово пространство, J(u) ∈ C1 (H), J(u) сильно выпукла с коэффициентом κ > 0, J 0 (u) ∈ Lip(H) с константой L > 0.
Тогда при любомвыборе начальной точки u0 из H метод (2)–(3) сходится к точке минимума u∗ задачи(1), причём для скорости сходимости справедлива оценка:κκkuk − u∗ k2 6 J(uk ) − J(u∗ ) 6 q k (J(u0 ) − J(u∗ )), где q = 1 − ∈ [0, 1)2L(4)Доказательство.Для начала заметим, что по Теореме 6 точка u∗ для функции J(u) существует иединственна.По Теореме 8 п.
(c0 ) (условие сильной монотонности градиента) имеем:κku − vk2H 6 hJ 0 (u) − J 0 (v), u − viH31∀u, v ∈ H.Учитывая, что J 0 (u) ∈ Lip(H) и применяя неравенство Коши-Буняковского такжеполучаем, чтоhJ 0 (u) − J 0 (v), u − viH 6 Lku − vk2H .Из этих неравенств следует, что κ 6 L, и выражение для q в (4) верно.Теперь обозначим через ak разность между J(uk ) и J(u∗ ). Очевидно, что ak > 0. Всвою очередьak+1 = J(uk+1 ) − J(uk ) + ak 6 {(2), (3); ∀α} 6 [J(uk − αJ 0 (uk )) − J(uk )] + akПрименим к разности в квадратных скобках формулу конечных приращений в интегральной форме:0Z1J(uk − αJ (uk )) − J(uk ) =hJ 0 (uk − αtJ 0 (uk )), −αJ 0 (uk )iH dt0Добавим и вычтем к левому аргументу скалярного произведения J 0 (uk ), тогда по неравенству Коши-Буняковского и в силу Липшиц-непрерывности J 0 (u) это выражение непревосходит−αkJ 0 (uk )k2H +Z11Lk − αtJ 0 (uk )kH ·k − αJ 0 (uk )kH dt = −αkJ 0 (uk )k2H + Lα2 kJ 0 (uk )k2H .20Таким образом,1ak+1 6 ak − αkJ 0 (uk )k2H + Lα2 kJ 0 (uk )k2H2∀α > 0.В правой части этого неравенства стоит квадратный трёхчлен относительно α, которыйдостигает своего минимума в точке 1/L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
