Ю.Н. Киселёв, С.Н. Аввакумов, М.В. Орлов - Оптимальное управление. Линейная теория и приложения, страница 7

Опорная функция c(F, ψ) непрерывнапо второму аргументу:c(F, ψ ) → c(F, ψ),ψ → ψ .Свойство 5◦ (опорная функция линейно преобразованного множества):пусть D – квадратная матрица n-го порядка, тогдаc(DF, ψ) = c(F, D∗ ψ) ∀ψ ∈ E n ,где D∗ – матрица, полученная из матрицы D транспонированием.562 Свойство 5◦ вытекает из определений опорной функции, операции линейного преобразования множества и свойств скалярного произведения{x ∈ DF ⇔ x = Df, f ∈ F }c(DF, ψ) = sup (x, ψ) =x∈DF= sup (Df, ψ) = sup (f, D∗ ψ) = c(F, D∗ ψ) .f ∈Ff ∈FВ частном случае матрицы D = αE, где α – число, E – единичнаяматрица, множествоDF = (αE)F = αF ,и на основании свойства 5◦c(αF, ψ) = c(F, αψ) .Если число α 0, то, привлекая свойство 2◦ , получаемc(αF, ψ) = α · c(F, ψ)∀α 0, ψ ∈ E n .Итак, имеет местоСвойство 6◦ (положительная однородность по первому аргументу):c(αF, ψ) = α · c(F, ψ) ∀α 0, ψ ∈ E n .Свойство 7◦ (аддитивность по первому аргументу):c(F1 + F2 , ψ) = c(F1 , ψ) + c(F2 , ψ) .2 Используя определения опорной функции и операции алгебраического сложения множеств, получаемc(F1 + F2 , ψ) =sup (x, ψ) =x∈F1 +F2{x ∈ F1 + F2 ⇔ x = f1 + f2 , f1 ∈ F1 , f2 ∈ F2 }= sup (f1 + f2 , ψ) = sup (f1 , ψ) + sup (f2 , ψ) =f1 ∈F1f2 ∈F2f1 ∈F1f2 ∈F2= c(F1 , ψ) + c(F2 , ψ) .Свойство 8◦ (опорная функция объединения множеств):57а) c(F1 ∪ F2 , ψ) = max{c(F1 , ψ), c(F2 , ψ)},б) для семейства {Fλ } равномерно ограниченных множеств, зависящих от параметра λ, принадлежащего некоторому множеству Λ(∃R > 0: |Fλ | R ∀λ ∈ Λ), имеет место формула!Fλ , ψ = sup c(Fλ , ψ) .cλ∈Λλ∈Λ2 В случае а) получаемc(F1 ∪ F2 , ψ) =sup (x, ψ) = max{ sup (x, ψ), sup (x, ψ)} =x∈F1 ∪F2x∈F1x∈F2= max{c(F1 , ψ), c(F2 , ψ)} .'В случае б) множествоFλ ограничено (оно принадлежит шаλ∈Λру SR (0)) и'cFλ , ψ =λ∈Λsup(x, ψ) = sup sup (x, ψ) = sup c(Fλ , ψ) .'x∈λ∈Λλ∈Λ x∈FλFλλ∈Λ◦Свойство 9 (опорная функция неотрицательной линейной комбинации множеств):пусть λ1 , λ2 – неотрицательные числа, F1 , F2 – ограниченные множества, лежащие в пространстве E n , тогдаc(λ1 F1 + λ2 F2 , ψ) = λ1 c(F1 , ψ) + λ2 c(F2 , ψ)∀ψ ∈ E n .2 Свойство 9◦ вытекает из свойств 7◦ и 6◦ .Свойство 10◦ (совпадение опорных функций множества и егонаименьшей выпуклой оболочки):∀ψ ∈ E n .'2 В разделе 2.4 доказано, что conv F = H ≡Fm , гдеc(F, ψ) = c(conv F, ψ)F0 = F,Fm+1 =!(4)m0{λFm + (1 − λ)Fm },m = 0, 1, .

. .λ∈[0,1]Привлекая свойство 8◦ б), можно записать⎛⎞!c(conv F, ψ) = c ⎝Fm , ψ ⎠ = sup c(Fm , ψ) .m0m058(5)Покажем, чтоc(Fm , ψ) = c(F, ψ),m = 0, 1, . . .(6)Тогда из (5), (6) вытекает утверждение(4) свойства 10◦ . Ясно, что'{λF0 + (1 − λ)F0 } и, используяc(F0 , ψ) = c(F, ψ). Далее F1 =свойства 8◦ б) и 9◦ , получаемλ∈[0,1]c(F1 , ψ) = sup c(λF0 + (1 − λ)F0 , ψ) =λ∈[0,1]= sup {λc(F0 , ψ) + (1 − λ)c(F0 , ψ)} = sup c(F0 , ψ) = c(F0 , ψ) .λ∈[0,1]λ∈[0,1]Итак, равенство (6) верно при m = 0, 1; его справедливость длялюбого номера m устанавливается индукцией.Мы изучили первую группу свойств (свойства 1◦ – 10◦ ) опорныхфункций.

Далее рассмотрены примеры нахождения опорных функцийнекоторых множеств. При разборе этих примеров привлекаются изученные выше свойства опорных функций.2.5.4 ПримерыПример 1. Найти опорную функцию множестваF1 = S1 (0) = {x ∈ E n : x 1} ∈ Ω(E n )(единичного шара в пространстве E n ). Так как(f, ψ) f · ψ, (f, ψ)ψ = ψ,f = ψтоc(F1 , ψ) = max (f, ψ) = ψ =f 1)ψ12 + . . .

+ ψn2 .Пример 2. Найти опорную функцию множестваF2 = Sr (0) ∈ Ω(E n )(шара радиуса r 0 с центром в начале координат). Замечая, чтоSr (0) = r · S1 (0) и, используя свойство 6◦ и результат примера 1,получаем:c(F2 , ψ) = c(r · S1 (0), ψ) = r · c(S1 (0), ψ) = rψ .59Пример 3. Найти опорную функцию множестваF3 = {a} ∈ Ω(E n ),состоящего из одной точки a ∈ E n . По определению опорной функцииc(F3 , ψ) = (a, ψ) = a1 ψ1 + .

. . + an ψn .Пример 4. Найти опорную функцию множестваF4 = Sr (a) ∈ Ω(E n )(шара радиуса r 0 с центром в точке a ∈ E n ). Привлекая равенствоSr (a) = {a} + Sr (0), свойство 7◦ и результат примеров 2, 3, получаем:c(F4 , ψ) = c({a}, ψ) + c(Sr (0), ψ) =)= (a, ψ) + r ψ = a1 ψ1 + . . . + an ψn + r ψ12 + . . . + ψn2 .Установленное соотношение будет использовано при дальнейшем изложении курса.Пример 5.

Найти опорную функцию множестваF5 = {−v, v}, v ∈ E n ,состоящего из двух точек −v и v. Используя определение опорнойфункции, получаем%&c(F5 , ψ) = max (−v, ψ), (v, ψ) = |(v, ψ)| .Пример 6. Найти опорную функцию множества −11F6 =,∈ Ω(E 2 ),00состоящего из двух точек (−1, 0)∗ и (1, 0)∗ . По определению опорнойфункции находимc(F6 , ψ) = max{−ψ1 , ψ1 } = |ψ1 | .Пример 7. Найти опорную функцию множества%&F7 = x ∈ E 2 : |x1 | 1, x2 = 060(отрезка на плоскости с концами (−1, 0)∗ и (1, 0)∗ ).

Имеем:c(F7 , ψ) = max(x, ψ) = |ψ1 | .x∈F7Мы видим, что c(F7 , ψ) = c(F6 , ψ); это равенство иллюстрируетсвойство 10◦ , так как F7 = conv F6 .Пример 8. Найти опорную функцию множества −1−111F8 =,,,∈ Ω(E 2 ),−11−11состоящего из четырёх точек, расположенных в вершинах квадрата.Имеем:c(F8 , ψ) = max(x, ψ) = |ψ1 | + |ψ2 | .x∈F8Пример 9. Найти опорную функцию множества%&F9 = x ∈ E 2 : |x1 | 1, |x2 | 1 ∈ Ω(E 2 )(квадрата). Имеем:c(F9 , ψ) = max (x1 ψ1 + x2 ψ2 ) = |ψ1 | + |ψ2 | .|x1 |1|x2 |1Совпадение опорных функций множеств F8 и F9 опять иллюстрирует свойство 10◦ , так как F9 = conv F8 .Пример 10.

Найти опорные функции множеств, ограниченных эллипсоидами:2x2nn x1F10 = Эa ≡ x ∈ E : 2 + . . . + 2 1 , ai > 0, i = 1, . . . , n;a1an= Э ≡ {x ∈ E n : (Qx, x) 1},F10здесь Q– симметричная положительно определённая матрица порядка n. Для нахождения опорной функции множества F10 заметим, чтоЭa = A · S1 (0),где A – диагональная матрица с элементами a1 , . . . , an на диагонали,A = A∗ . Используя свойство 5◦ и результат примера 1, получаем:c(Эa , ψ) = c(AS1 (0), ψ) = c(S1 (0), Aψ) = Aψ .61Так как⎛⎜Aψ = ⎝⎞ ⎛⎞ψ1a1 ψ1⎟ ⎜ ..

⎟ ⎜ .. ⎟⎠ ⎝ . ⎠ = ⎝ . ⎠,anψnan ψn0a1..0Aψ =.)⎞⎛a21 ψ12 + . . . + a2n ψn2 ,)a21 ψ12 + . . . + a2n ψn2 .*Доказать самостоятельно, что c(Э, ψ) = (Q−1 ψ, ψ). Указание:использовать вспомогательную переменную y = Q1/2 x ∈ S1 (0).Пример 11. Опорная функция множестватоc(Эa , ψ) =F11 ≡ [a, b] ⊂ E n(отрезка с концами a, b ∈ E n ) определяется формулойc(F11 , ψ) =1(a + b, ψ) +21 (a − b, ψ) .22.5.5 Теорема о представлении наименьшей выпуклой оболочки компакта в форме пересечения полупространств. Свойства 11◦ − 14◦ опорной функции, вытекающие из этой теоремыРассматриваемая теорема, содержащая основной теоретический результат раздела 2.5, показывает в какой степени множество определяется своей опорной функцией. Как мы видели в примерах 5.1-5.3,различные множества могут иметь одну и ту же опорную функцию.В свойстве 10◦ утверждается, что опорные функции множества и егонаименьшей выпуклой оболочки совпадают.Теорема 5.1. Пусть F ∈ Ω(E n ); c(F, ψ) – опорная функция множества F ; ψ ∈ E n .

Тогда(%&x ∈ E n : (x, ψ) c(F, ψ) .(7)conv F =ψ∈SВведём обозначения:62Πψ = {x ∈ E n : (x, ψ) c(F, ψ)} – замкнутое полупространство, ограниченное гиперплоскостью Γψ = {x ∈ E n : (x, ψ) = c(F, ψ)} свекторомнормали ψ ∈ S;"Πψ – пересечение полупространств Πψ по всем векторамΠ =ψ∈Sψ ∈ S, где S – единичная сфера;H = conv F – наименьшая выпуклая оболочка множества F .Тогда утверждение (7) теоремы 5.1 можно кратко записать в формеравенстваH = Π.(8)Теорема утверждает, что наименьшая выпуклая оболочка H компакта F представляется в форме пересечения по векторам ψ ∈ S полупространств Πψ , определяемых опорной функцией компакта F , т.е.conv F определяется опорной функцией c(F, ψ) компакта F .Это значит, что по опорной функции c(F, ψ) компакта F можетбыть однозначно восстановлен не сам компакт F , а только его наименьшая выпуклая оболочка conv F .2 Обратимся к доказательству теоремы. Нужно установить равенство (8) – совпадение множеств H и Π.1.

Докажем сначала, что H ⊂ Π. Используя определение опорнойфункции и свойство 10◦ , получаем, что для любой точки x ∈ H10◦(x, ψ) max(h, ψ) = c(H, ψ) = c(F, ψ)h∈Hследовательно, x ∈ Πψ∀ψ ∈ S, поэтому x ∈ Π =∀ψ ,"Πψ . Это дока-ψ∈Sзывает включениеH ⊂ Π.(9)2. Докажем теперь включениеH⊃Π(10)(методом от противного). Отметим, что множество Π = ∅, так какF = ∅ и F ⊂ Π (почему?). Допустим, что (10) неверно, тогда существует точка x0 ∈ Π, x0 ∈/ H.

Так как H выпуклый компакт и x0 ∈/ H,то по лемме об отделимости ∃ψ0 ∈ S: (h − x0 , ψ0 ) < 0 ∀h ∈ H, т.е.(h, ψ0 ) < (x0 , ψ0 )63∀h ∈ H.Отсюда следует, чтоc(H, ψ0 ) = max(h, ψ0 ) < (x0 , ψ0 ),h∈Hпричём неравенство здесь строгое, так как H – компакт. Отсюда,привлекая свойство 10◦ , получаемc(F, ψ0 ) = c(H, ψ0 ) < (x0 , ψ0 ) ,т.е.(x0 , ψ0 ) > c(F, ψ0 ).(11)"С другой стороны, x0 ∈ Π =Πψ , поэтому x0 ∈ Πψ0 , следоваψ∈Sтельно,(x0 , ψ0 ) c(F, ψ0 ).(12)Сравнение неравенств (11) и (12) приводит к противоречию, котороедоказывает включение (10).3. Из включений (9) и (10) следует равенство (8), которое являетсякраткой записью представления (7).Теорема доказана.Следствие из доказанной теоремы о представлении выпуклых компактов в форме пересечения полупространств.

Пусть F ∈ conv Ω(E n ),тогда({x ∈ E n : (x, ψ) c(F, ψ)}.(13)F =ψ∈SПредставление (13) показывает, что выпуклый компакт однозначноопределяется своей опорной функцией, т.е. при F1 , F2 ∈ conv Ω(E n )имеемF1 = F2 ⇐⇒ c(F1 , ψ) = c(F2 , ψ)∀ψ ∈ E n ⇐⇒⇐⇒ c(F1 , ψ) = c(F2 , ψ)∀ψ ∈ S(14)Упражнение 5.2. Найти алгебраическую сумму F двух шаровF1 = Sr1 (a1 ), F2 = Sr2 (a2 );r1 , r2 0,a1 , a2 ∈ E n .Ясно, что F1 , F2 , F ∈ Ω(E n ). Найдём опорную функцию множества F = F1 + F2 .