Елементи опуклого аналізу

Вступ

Екстремальні задачі.

Як виникають екстремальні задачі? Цілком природнім прагненням є пошук кращого рішення, оптимального в певному розумінні. Слово “оптимальний” походить від латинського optimus, що означає найкращий, досконалий. Оптимальність задається умовами задачі і, як правило, визначається значенням певного параметру. Тому для того щоб знайти оптимальне рішення доводиться розв’язувати ціле параметризоване сімейство задач та шукати розв’язки, що відповідають мінімуму або максимуму. Обидва ці поняття - мінімум та максимум - об’єднуються терміном екстремум (від латинського extremum, що означає “крайній”). Тому задачі на пошук максимуму або мінімуму також називають екстремальними задачами.

Характерна особливість екстремальних задач - необхідність вибору кращого, в певному заданому розумінні, рішення з існуючих - формує нову область математики, яка, однак, тісно пов’язана з математичним і функціональним аналізом, варіаційним численням і диференціальними рівняннями. Несподіваним є те, що надзвичайно багато практичних задач може бути формалізовано в рамках теорії екстремальних задач. Варіаційне числення, оптимальне керування, теорія ігор (конфліктних керованих процесів) - все це етапи розвитку основної ідеї, спрямовані вимогами практичних проблем. Цей процес продовжується і сьогодні, зокрема в області комп’ютерних наук, де виникають нові проблеми, які, тим не менше, зводяться до задач теорії екстремуму.

Можна нагадати слова Ейлера: «У світі не відбувається нічого, у чому б не було видно сенсу якогось мінімуму або максимуму». Як формалізуються екстремальні задачі? Точно поставлена екстремальна задача містить наступні елементи: функціонал \(f\,:\,X\rightarrow R\) та обмеження, тобто деяку підмножину \(C\subset X\). Задача формулюється наступним чином: знайти екстремум функціонала \(f(\cdotp)\) за умови, що \(x\in C\)

\[\begin{align} & f(x)\rightarrow extr\\ & \:x\in C\\ \end{align} \]

Ідея – лінійна апроксимація у точці екстремуму. Ідея Кеплера (розвинута Ферма) про те, що в точці екстремуму функція майже не змінюється - похідна дорівнює нулю.

Задача з обмеженнями типу рівність і нерівність (математичне програмування) \[\begin{align} & f(x) \rightarrow extr,\\ &\:x\in C\\ &G_{0}(x)\leq0\\ &\:G_{1}(x)=0\\ \end{align}\]

Проблема - наявність обмежень. Екстремум може досягатися на границі обмежень і тому ідея Ферма (Кеплера) не працює. Ідея – метод множників Лагранжа, що дозволяє “включити” обмеження в новому цільовому функціоналу і звести задачу до попереднього випадку.

Варіаційне числення. Досить часто необхідно шукати не точку а функцію. Виникає купа проблем. Ідеї: Перша друга варіація, простір функцій. Перехід у відповідний функціональний простір. Окіл функції.

Оптимальне керування. Задача оптимального керування відрізняється наявністю спеціального параметру \(u\), який впливає на стан системи та динамікою - зміною стану системи у часі (як правило, диференційне рівняння).

\[\begin{align} &z=(x(\cdotp),u(\cdotp))\in C^{1}(\Delta,\,X)\times C^{1}(\Delta,\,Y)\\ & f(z)\rightarrow extr\\ &\:x\in R^{n}\\ &G_{0}(z)\leq0\\ &\:G_{1}(z)=0\\ & \:u\in U \\ & \dot{x}-\phi(z,t)=0,\:t\in\Delta\\ \end{align}\]

Проблема - наявність динаміки. Шукати треба не точку а функцію. Наявність функціональних обмежень не дозволяє напряму застосувати ідею Лагранжа. Ідея – узагальнення методу Лагранжа – принцип максимуму (Понтрягіна і інших).

Теорія диференційних ігор. Поява іншого гравця.

Конфліктно керована система

\[\begin{align} &z=(x(\cdotp),u(\cdotp),v(\cdotp))\in C^{1}(\Delta,\,X)\times C^{1}(\Delta,\,U)\times C^{1}(\Delta,\,V)\\ &f(z)\underset{u(\cdotp)}{\rightarrow}min,\;f(z)\underset{v(\cdotp)}{\rightarrow}max\\ &G_{0}(z)\leq0,\:G_{1}(z)=0,\:u\in U,\:v\in V\\ &\dot{x}-\phi(z,t)=0,\:t\in\Delta\\ \end{align}\]

Ігрова постановка зв’язує дві різні області математики - теорію ігор і оптимальне керування. Теорія ігор описує стратегічну поведінку раціональних учасників. Необхідні елементи ігрової задачі та базові поняття теорії ігор. Основні ідеї розв’язку ігрових задач.

Література

  1. Петров, Н. Н. “Введение в выпуклый анализ.” Ижевск. Удмуртский государственный университет (2009)
  2. Благодатских, В. И. “Введение в оптимальное управление (линейная теория): Учебник.” М.: Высш. шк (2001).

Лекція 1. Основні визначення

Вводяться основні визначення, операції над множинами у \(R^{n}\). Розглядається простір опуклих компактних множин \(K(R^{n})\). Визначається метрика Хаусдорфа.

Операції над множинами

Будемо розглядати \(n\)-вимірний векторний простір \(R^{n}\), який складається з елементів \(x=(x_{1},...,x_{n})\). Простір \(R^{n}\) є лінійним простором зі звичайними операціями додавання і множення на число. Скалярний добуток визначається формулою \((x,y)=x_{1}y_{1}+...+x_{n}y_{n}\). Норма \(\left\Vert x\right\Vert =\sqrt{(x,\,x)}\), метрика \(\rho(x,y)=\left\Vert x-y\right\Vert\) зі звичайними властивостями.

Будемо розглядати множини точок з простору \(R^{n}\). При цьому буде використовуватися звичайний набір операцій: \(\subset,\,=,\,\neq,\,\in,\,\notin,\,\bigcap,\,\bigcup\). Символом \(\oslash\) будемо позначати порожню множину. В просторі \(R^{n}\) природнім чином визначається \(\varepsilon\)-окіл точки \(x\) – всі точки \(y\), такі, що \(\left\Vert x-y\right\Vert <\varepsilon\). Точку \(x\in R^{n}\) називають граничною точкою множини \(X\), якщо будь-якому її околу належить хоча б одна точка множини \(X\). Множина називається замкнутою, якщо вона містить всі свої граничні точки. Замиканням \(\bar{X}\) або \(cl\,X\) множини \(X\) називається найменша замкнута множина що містить в собі \(X\). Якщо \(X\) замкнута, то \(cl\,X=X\). Для будь-якої множини виконується \(cl(cl\,X)=cl\,X\).

Множина \(X\) є обмеженою, якщо вона міститься в кулі певного скінченного радіуса, тобто якщо існує \(R>0\), таке, що \(X\subseteq B{}_{R}(0)\), де \(B_{R}(\mathbf{a})=\{x\in R^{n}:\:\left\Vert x-\mathbf{a}\right\Vert \leq R\:\}\). Множина \(X\) називається компактною, якщо вона замкнута і обмежена.

Якщо \(X\) компактна множина, або компакт, то модулем \(\left|X\right|\) називається число \[\begin{equation} \left|X\right|=\underset{x\in X}{max}\left\Vert x\right\Vert \end{equation}\] В силу компактності \(\left|X\right|\) множини і неперервності норми максимум у формулі досягається завжди (Теорема Вейєрштраса). Геометричний зміст модуля такий: це радіус найменшої кулі з центром в нулі, яка містить \(X\).

Точка \(x\) називається внутрішньою точкою множини \(X\), якщо для деякого \(\varepsilon>0\) виконується \(B_{\varepsilon}(x)\subset X\). Множина називається відкритою, якщо будь-яка її точка – внутрішня. Сукупність усіх внутрішніх точок називається внутрішністю множини і позначається \(int\,X\). Границею \(\partial X\) множини \(X\) називається множина точок \(\partial X=cl\,X\,\setminus intX\).

Простір \(K(R^{n})\).

Розглянемо простір \(K(R^{n})\), що складається з усіх не порожніх компактних підмножин простору \(R^{n}\). Зокрема, його елементами є всі точки \(R^{n}\), кулі, квадрати та інші. Крім звичайних множинних операцій розглянемо ще дві: операцію суми та множення на число.

Алгебраїчною сумою двох не порожніх множин з простору \(K(R^{n})\) або (що теж саме) сумою двох елементів \(X,\:Y\in K(R^{n})\) називається множина \[ X+Y=\{z=x+y\::\:x\in X,\;y\in Y\,\}\]

Алгебраїчна сума не виводить за межі простору \(K(R^{n})\).

Приклад 2.1. Сума двох куль

Розглянемо чому дорівнює сума двох довільних куль. Виявляється, що \(B_{r_{1}}(a_{1})+B_{r_{2}}(a_{2})=B_{r_{1}+r_{2}}(a_{1}+a_{2})\), тобто при додаванні двох куль їх радіуси додаються, як і вектори, що задають їх центри.

Приклад 2.2. Сума квадрата і кулі.

Нехай задані множини \(X=\{x\in R^{n}:\,\left|x_{1}\right|\le1,\,\left|x_{2}\right|\le1\}\) та \(Y=B_{0.5}(0)\). Їх сума зображена на риисунку (туду).

Операція алгебраїчної суми для двох довільних множин \(X,\:Y\in K(R^{n})\) задовольняє наступним властивостям:

  1. Комутативність: \(X+Y=Y+X\)

  2. Асоціативність: \(X+(Y+Z)=(X+Y)+Z\)

  3. В просторі \(K(R^{n})\) існує нульовий елемент \(\{0\}\) такий що \(\{0\}+X=X\).

В просторі \(K(R^{n})\) немає оберненого елемента для не одно-точкових множин.

Означення 2.1. Множина \(X\subset R^{n}\) називається опуклою, якщо разом з кожними своїми двома точками \(x_{1},\,x_{2}\) вона містить і весь відрізок, що їх з’єднує, тобто всі точки виду

\[\lambda_{1}x_{1}+\lambda_{2}x_{2}\in X\],

де \(\lambda_{1},\lambda_{2}\ge0, \lambda_{1}+\lambda_{2}=1\). Порожня множина вважається опуклою за визначенням.

Приклад 2.3. Опуклі множини

  1. Будь-яка куля \(B_{R}(a)\) з простору \(R^{n}\);

  2. Підпростір \(H^{+}=\left\{ x\in R^{n}|\left(x,a\right)\le\alpha,\,a\in R^{n}\setminus\{0\},\,\alpha\in R\right\}\);

  3. Гіперплощина \(H=\left\{ x\in R^{n}|\left(x,a\right)=\alpha,\,a\in R^{n}\setminus\{0\},\,\alpha\in R\right\}\).

Задача 2.1. Нехай \(X,\,Y\subset R^{n}\) опуклі множини. Чи опуклі наступні множини? Довести.

  1. \(X+Y\);

  2. \(clX\);

  3. \(intX\).

Означення 2.2. Опуклою оболонкою \(coX\) множини \(X\subset R^{n}\) називається найменша опукла множина, що містить \(X\).

Множення множини на число.

Добутком множини \(X\in K(R^{n})\) на число \(\lambda\) називається множина \(Y=\lambda X=\left\{ y=\lambda x:\:x\in X\,\right\}\). Множина \(Y\) є непорожньою, замкнутою і обмеженою множиною, і тому множення на число не виводить з простору \(K(R^{n})\). Далі, якщо \(X\) - опукла, то і \(Y\) - опукла.

Приклад 2.4. Добуток кулі на число.

Покажемо, що \(\lambda B_{r}(0)=B_{\left|\lambda\right|r}(0)\).

Примітка 2.1. З прикладу 2.4 випливає, що будь-яку кулю \(B_{r}(a)\) можна представити у вигляді \(B_{r}(a)=\{a\}+rB_{1}(0)\).

Безпосередньо перевіряється, що для будь яких чисел \(\alpha,\,\beta\in R\) і довільних множин \(X,\,Y\in K(R^{n})\) виконуються наступні властивості:

  1. \(\alpha(\beta X)=(\alpha\beta)X\);

  2. \(1\cdot X=X\);

  3. \(\alpha(X+Y)=\alpha X+\alpha Y\).

Простір \(K(R^{n})\) не є лінійним простором. По-перше, не для кожного елементу існує обернений (існує лише для одно-точкових множин). По-друге не виконується закон дистрибутивності, тобто не завжди виконується рівність \((\alpha+\beta)X=\alpha X+\beta X\).

Приклад 2.5. \(0=(1-1)B_{1}(0)\ne B_{1}(0)-B_{1}(0)=B_{2}(0)\).

Твердження 2.1. Виконується включення в одну сторону \((\alpha+\beta)X\subset\alpha X+\beta X\)

Доведення. Нехай \(y\in(\alpha+\beta)X\), тоді існує \(x\in X\) такий що \(y=(\alpha+\beta)x=\alpha x+\beta x\). Далі, \(\alpha x\in\alpha X\), \(\beta x\in\beta X\) отже \(y\in\alpha X+\beta X\).

Задача 2.2. Показати, що якщо \(\alpha,\beta\ge0\) і множина \(X\) опукла, то рівність \((\alpha+\beta)X=\alpha X+\beta X\) виконується.

Будемо розглядати підпростір \(coK(R^{n})\) простору \(K(R^{n})\), який містить всі всі непорожні опуклі компакти підмножини простору \(R^{n}\).

Образ множини при лінійному відображенні

Нехай \(X\in K(R^{n})\), і в просторі \(R^{n}\) задане лінійне перетворення за допомогою матриці \(A\) розмірності \(n\times n\). Тоді образом множини \(X\) під дією оператора \(A\) називається множина \(Y=AX=\left\{ y\in R^{n}|y=Ax,\,x\in X\right\}\) Образ \(AX\) є непорожньою, замкнутою і обмеженою множиною. Якщо \(X\) - опукла множина, то \(AX\) також опукла.

Приклад 2.6. Розглянемо дію матриці \[A=\left(\begin{array}{cc} \alpha & 0\\ 0 & \beta \end{array}\right)\] на кулю \(B_{R}(0)\)

Для будь-яких матриць \(A,\,B\) і будь-яких множин \(X,\,Y\in K(R^{n})\) виконується:

  1. \(A(BX)=(AB)X\)

  2. \(IX=X\)

  3. \(A(X+Y)=AX+AY\)

  4. \((A+B)X\subset AX+AY\)

Різниця Мінковського

Як зазначалось вище, алгебраїчна різниця двох множин \(X-Y=\{z=x-y\::\:x\in X,\;y\in Y\,\}\) не задовольняє бажаним властивостям. Зокрема, \((X-Y)+Y\neq X\).

Означення 2.3. Різницею Мінковського двох множин \(X,\,Y\in K(R^{n})\) називається множина \[Z=X\stackrel{*}{-}Y=\left\{ z\in R^{n}|z+Y\subset X\right\}\].

З визначення різниці Мінковського випливає, що завжди виконується \((X\stackrel{*}{-}Y)+Y\subset X\).

Означення 2.4. Множина \(X\) повністю вимітає множину \(Y\), якщо \((Y\stackrel{*}{-}X)+X=Y\).

Твердження 2.2. Нехай \(X,\,Y\in K(R^{n})\), тоді \(X\stackrel{*}{-}Y=\underset{y\in Y}{\bigcap}(X-y)\)

Приклад 2.7. Різниця Мінковського двох куль з центром в нулі.

Твердження 2.3. Нехай \(X\in K(R^{n}),\,Y\in K(R^{n})\), тоді \(X\stackrel{*}{-}Y\in K(R^{n})\).

Відстань Хаусдорфа

В просторі \(K(R^{n})\) можна ввести метрику або відстань між двома множинами \(X,\,Y\in K(R^{n})\) за формулою

\[h(X,Y)=min\{r\geq0:\:X\subset Y+B_{r}(0),\:Y\subset X+B_{r}(0)\}\]

Таким чином, відстанню між двома множинами є найменше з додатних чисел, для яких виконуються одночасно два включення: \[X\subset Y+B_{r}(0)\\ \:Y\subset X+B_{r}(0)\]

Ця метрика називається хаусдорфовою. Розглянемо приклад відстані \(h(X,Y)\).

Приклад 2.8. Відстань від точки до кулі \(B_{r}(\bar{a_{1}})\).

Тепер покажемо, що функція дійсно є метрикою. Для цього потрібно показати, що для довільних множин виконуються властивості:

  1. \(h(X,Y)\geq0\);

  2. \(h(X,Y)=0\) тоді і тільки тоді, коли \(X=Y\);

  3. \(h(X,Y)=h(Y,X)\);

  4. \(h(X,Y)\leq h(X,Z)+h(Z,Y)\).

Перші три властивості випливають прямо з означення. Доведемо останню.

Дійсно, зафіксуємо значення відстаней \(h(X,Y),\,h(X,Z),\,h(Z,Y)\):

\[h(X,Y)=min\{r\geq0:\:X\subset Y+B_{r}(0),\:Y\subset X+B_{r}(0)\}\]

\[h(X,Z)=min\{r\geq0:\:X\subset Z+B_{r}(0),\:Z\subset X+B_{r}(0)\}\]

\[h(Z,Y)=min\{r\geq0:\:Z\subset Y+B_{r}(0),\:Y\subset Z+B_{r}(0)\}\]

Позначимо відстані \(h(X,Z),\,h(Z,Y)\) як \(R_{1}\) та \(R_{2}\). Тоді виконуються наступні включення:

\[X\subset Y+B_{R_{1}+R_{2}}(0),\:Y\subset X+B_{R_{1}+R_{2}}(0)\]

Отже \(h(X,Y)\leq R_{1}+R_{2}\), що й потрібно було довести.

Приклад 2.9. Знайти відстань Хаусдорфа між двома довільними кулями \(B_{r}(\bar{a_{1}}),\:B_{R}(\bar{a_{2}})\).

Завдання для практичних занять. Операції з множинами.

  1. Знайти множину \(A(X+Y)\), де

    • 1.1. \[ A=\left(\begin{array}{cc} 0 & 2\\ 2 & 0 \end{array}\right)\], \[X=\left\{ x\in R^{2}|\left|x_{i}\right|\leq1\right\}\] \[Y=B_{0.5}((1,2))\];

    • 1.2. \[A=\left(\begin{array}{cc} 2 & -1\\ 0 & 3 \end{array}\right)\], \[X=\left\{ x\in R^{2}|\underset{i}{\sum}\left|x_{i}\right|\leq1\right\}\] , \[Y=\left\{ x\in R^{2}|\left|x_{1}\right|+2\left|x_{2}\right|\leq1\right\}\] ;

  2. Знайти різницю Мінковського множин \(X,\;Y\). \(X=\left\{ x\in R^{2}|\left\Vert x\right\Vert \leq3\right\}\) , \(Y=B_{0.5}((1,2))\);

  3. Знайти \(X\stackrel{*}{-}Y+Y\) для \(X=\left\{ x\in R^{2}|\left|x_{1}\right|+\left|x_{2}\right|\leq3\right\}\) , \(Y=\left\{ x\in R^{2}|\underset{i}{\sum}\left|x_{i}\right|\leq1\right\}\);

  4. Вкажіть приклад чотирьох опуклих множин на площині таких, що перетин будь-яких трьох з них містить відрізок одиничної довжини але перетин чотирьох не містить ніякого відрізка одиничної довжини.

  5. Нехай для множини \(X\) виконується наступна властивість: для будь яких точок \(x,\!y\in X\) точка \(\frac{1}{2}x+\frac{1}{2}y\in X\). Чи вірно твердження, що \(X\) - опукла множина?

  6. Чи може сума двух неопуклих множин бути опуклою ?

  7. Довести наступні рівності:

    • 7.1 \(X\underset{\text{—}}{*}Y+Y\subset X\subset\left(X+Y\right)\underset{\text{—}}{*}Y\);

    • 7.2 \(X\underset{\text{—}}{*}Y\subset\left(X+Z\right)\underset{\text{—}}{*}\left(Y+Z\right)\);

  8. Якщо множина \(X\) - замкнута чи завжди \(coX\) замкнута?

  9. Знайдіть відстань Хаусдорфа між кулею \(Y=B_{1}((1,2))\) та квадратом \(X=\left\{ x\in R^{2}|\left|x_{i}\right|\leq1\right\}\).

  10. Знайдіть відстань між двома довільними квадратами з довжиною сторони 2.

  11. Покажіть, що множина опукла тттк її перетин з будь-якою лінією - опуклий.

  12. Яка відстань (евклідова) мід гіперплощинами \(\left\{ x\in R^{n}|\;(a,x)=b_{1}\right\} та \left\{ x\in R^{n}|\;(a,x)=b_{2}\right\}\) ?

  13. Розглянемо визначення Вороного для півпростору. Нехай \(a\) та \(b\) дві точки з \(R^{n}\). Покажіть, що множина всіх точок, які ближче (евклідова відстань) до \(a\) ніж до \(b\) утворюють півпростір. Опишіть його у явному вигляді у формі \((c,x)\le d\).

  14. Обчислити опорні функції наступних множин:

  • довільного квадрату

  • еліпсу з центром в нулі

  • довільного ромба

  1. Евклідовою відстанню між множинами називається число \(\rho\left(X,\;Y\right)=\underset{x\in X,\;y\in Y}{min}\left\Vert x-y\right\Vert\). Виразити евклідову відстань між двома опуклими множинами через опорні функції.

  2. Покажіть, що для будь-яких точок \(p,\!q\in R^{n}\) і будь-яких множин \(X,\;Y\in K(R^{n})\) виконуються нерівності:

  • \(\rho(p,\!X)\leq\left\Vert p-q\right\Vert +\rho(q,\!X)\);

  • \(\rho(p,\!Y)\leq\rho(p,\!X)+h(X,\!Y)\);

  1. Діаметром множини називають число \(d\left(X\right)=\underset{x_{1},x_{2}\in X}{max}\left\Vert x_{1}-x_{2}\right\Vert\). Виразіть його через опорну функцію.

  2. Знайдіть опорну функцію об’єднання двох множин.

  3. Знайти \(coX\) для заданої опорної функції:

    • \(c(X,\psi)=max\left\{ 2\psi_{1},\left|\psi_{1}\right|,-\psi_{2}\right\}\) .

    • \(c(X,\psi)=\left|\psi_{1}-\psi_{2}\right|\).

    • \(c(X,\psi)=\left|\psi_{1}\right|+\left|\psi_{2}\right|+\left\Vert \psi\right\Vert\).

  4. \(c(X,\psi)=max\left\{ 2\psi_{1},\left|\psi_{1}\right|,-\psi_{2}\right\}\) , знайти \(coX\).

  5. Чи завжди \(intX = int\;clX\)?

Лекція 2. Опуклі множини та опуклі оболонки множин. Опорна функція.

Означення 2.1. Точка \(x\) називається опуклою комбінацією точок \(x_{1},...,x_{m}\), якщо \(x=\sum_{i=1}^m\alpha_{i}x_{i}\), де всі \(\alpha_{i}\geq0, і =1,...,m\)

Означення 2.2. Множина \(X\) називається опуклою якщо для будь-яких \(x,\:y\in X\), \(\lambda\in[0,1]\) виконується \[\lambda x+(1-\lambda)y\in X.\]

Порожня множина вважається опуклою за визначенням. Геометрично це означає, що опукла множина разом з будь-якими двома точками містить і весь відрізок, що їх сполучає. Простір всіх опуклих компактів будемо позначати \(coK(R^{n})\).

Твердження 2.1. Нехай \(X,\;Y\in coK(R^{n})\), тоді опуклими також будуть множини:

  1. \(X\bigcap Y\);

  2. \(X+Y\);

  3. \(clX\)

  4. \(\alpha X\), \(\alpha\ge0\).

Твердження 2.2. Нехай \(X\in coK(R^{n}),\,Y\in K(R^{n})\), тоді \(X\stackrel{*}{-}Y\) опукла множина.

Означення 2.3. Опуклою оболонкою точок \(x_{1},...,x_{n}\) називається об’єднання всіх їх опуклих комбінацій.

Теорема 2.1. (Каратеодорі) Будь-яку точка \(x\), що належить множині \(coX\), де \(X\in K(R^{n})\), може бути представлена у вигляді не більш як \(n + 1\) точки з множини \(X\).

Доведення. Нехай \(x \in coX\), тоді існує число \(k\) та точки \(x_{i}\in X\), \(i=1,...,k\), такі, що \[x = \sum_{i=1}^{k}{\lambda_{i}x_{i}}\]

де \(\lambda_{i} \ge 0\), \(\sum_{i=1}^{k}{\lambda_{i}}=1\). Припустимо, що \(k > N + 1\). Це означає, що вектори \(x_{2}-x_{1},x_{3}-x_{1},...,x_{k}-x_{1}\) лінійно залежні. Отже, існують дійсні числа \(\mu_{2},\mu_{3}...,\mu_{k}\) не рівні всі нулю, такі, що: \[\sum_{i=2}^{k}{\mu_{i}(x_{i}-x_{1})}\] Визначимо \(\mu_{1} = -\sum_{i=2}^{k}{\mu_{i}}\), тоді \[\sum_{i=1}^{k}{\mu_{i}x_{i}}=0\] \[\sum_{i=1}^{k}{\mu_{i}}=0\] Можемо також вважати, що принаймі одне з чисел \(\mu_{i}\) строго більш за нуль. Отже, для будь-якого числа \(\alpha \in R\) виконується \[x = \sum_{i=1}^{k}{\lambda_{i}x_{i}} - \alpha\sum_{i=1}^{k}{\mu_{i}x_{i}} = \sum_{i=1}^{k}{(\lambda_{i}-\alpha\mu_{i})x_{i}}\] Зокрема, це виконується і для \(\alpha = min \big\{ \frac{\lambda_{i}}{\mu_{i}}: \mu_{i}>0 \big\}\). Таким чином, всі \(\lambda_{i}-\alpha\mu_{i} \ge 0\) і для одного індексу цей вираз дорівнює нулю, отже точка \(x\) може бути розкладена у опуклу комбінацію \(k-1\) точки. Кількість можна зменшувати аж поки \(k > N + 1\). Теорема доведена.

Опорні функції і їх властивості

Визначається опорна функція. Описуються її основні властивості, геометричний зміст. Висвітлюється дуальність відношення функцій і множин.

Визначення опорною функції.

Визначимо для множини \(X \in K(R^{n})\) і вектора \(\psi \in R^{n}\) опорну функцію за формулою: \[c(X,\psi) = \max_{x \in X}{(x,\psi)}\]

Геометричний зміст опорної функції.

опорна множина, опорний вектор, опорна гіперплощина.

Приклад 3.1 Опорна функція від кулі з центром в нулі. \(c(B_{R}(0),\psi) = R\|\psi\|\).

Приклад 3.2 Опорна функція від квадрату з центром в нулі. \(c(Sq_{R}(0),\psi) = \sum |\psi_{i}|\).

Властивості опорних функцій.

  1. Додатня однорідність.

\(c(X,\lambda\psi)=\lambda \;c(X,\psi)\), \(\lambda \ge 0\).

  1. Адитивність.

\(c(X,\psi_{1} + \psi_{2}) \le c(X,\psi_{1}) + c(X,\psi_{2})\)

Наслідок. Функція \(c(X,\cdot)\) - опукла.

  1. \(c(X+Y,\psi)=c(X,\psi)+c(Y,\psi)\)

  2. \(c(AX,\psi)=c(X,A^{*}\psi)\)

  3. \(c(\lambda X,\psi)=c(X,\lambda \psi)\)

  4. \(X \subset Y \implies c(X,\psi) \le c(Y,\psi), \; \forall \psi \in R^{n}\)

  5. \(c(X,\psi) = c(coX,\psi)\)

  6. Відновлення опуклої облонки множини за опорною функцією.

\(coX = \bigcap_{\psi \in B_{1}(0)}{\{x\in R^n: (x,\psi) \le c(X,\psi)\}}\)

Доведення. \[y\in coX \implies (y,\psi) \le c(coX,\psi) = c(X,\psi)\] \[y \notin coX \implies \exists \psi_0 \in B_1(0) : c(coX,\psi_0) < (y,\psi_0) \implies y \notin \bigcap\{...\}\]

  1. \(X\in K(R^n)\) якщо для всіх \(\psi \in B_{1}(0)\) виконується \((x,\psi) \le c(X,\psi)\), то \(x\in coX\).

  2. \(X\in K(R^n)\) якщо для всіх \(\psi \in B_{1}(0)\) виконується \(c(X,\psi) \le c(Y,\psi)\), то \(X \subset coX\).

  3. \(X=Y \implies c(X,\psi) = c(Y,\psi)\), навпаки, якщо \(c(Y,\psi)=c(X,\psi) \implies coX = coY\).

  4. Нехай \(X, Y\in K(R^n)\), якщо \(X\bigcap Y \ne \emptyset\), то для всіх \(\psi \in R^n\) \[c(X,\psi) + c(Y,-\psi) \ge 0 \] Навпаки, якщо для всіх \(\psi \in B_{1}(0)\) виконується \[c(X,\psi) + c(Y,-\psi) \ge 0 \] то \(co X\bigcap coY \ne \emptyset\)

Доведення. \(X\bigcap Y \ne \emptyset \iff {0} \in (X + (-Y))\)

  1. Для довільних \(X,X_{0}\in K(R^n)\), \(\psi,\psi_0 \in R^n\) вірна нерівність \[|c(X,\psi)-c(X_0,\psi_0)|\le\|\psi_0\|h(X,X_0)+|X_0|\|\psi-\psi_0\|+2h(X,X_0)\|\psi-\psi_0\|\] Доведення.

\(c(X,\psi)=c(X,\psi - \psi_0 + \psi_0) \le c(X,\psi-\psi_0)+c(X,\psi_0)\)

\(X\subset B_{|X|}(0) \implies c(X,\psi-\psi_0)\le |X|\|\psi-\psi_0\|\)

\(c(X,\psi_0) \le c(X_0,\psi_0) + c(B_{h(X,X_0)}(0),\psi_0) = c(X_0,\psi_0) + h(X,X_0)\|\psi_0)\|\)

\[c(X,\psi)-c(X_0,\psi_0) \le c(X,\psi_0) + c(X,\psi-\psi_0) - c(X_0,\psi_0) \le |X|\|\psi-\psi_0\| + h(X,X_0)\|\psi_0\|\]

\[|c(X,\psi)-c(X_0,\psi_0)| \le max{(|X|,|X_0|)}\|\psi-\psi_0\|+max{(\|\psi\|,\|\psi_0\|)}h(X,X_0) \] \(\|\psi\|\le \|\psi_0\|+\|\psi-\psi_0\|\) \(|X|\le |X_0| + h(X,X_0)\)

неперервність за сукупністю опорної функції

  1. \(x \in intX \implies (x,\psi)<c(X,\psi), \; \forall\psi\in R^n\). Навпаки, \((x,\psi)<c(X,\psi), \; \forall\psi\in B_1(0) \implies x \in int co X\)

  2. \(h(coX,coY) = max_{\psi \in B_1(0)}{|c(X,\psi) - c(Y,\psi)|}\le h(X,Y)\).

Лекція 3. Багатозначні відображення та інтеграл від багатозначного відображення. Теорема Ляпунова.

Багатозначні відображення. Напівнеперервність зверху і знизу.

Інтеграл від багатозначного відображення.

Теорема Ляпунова (про опуклість інтегралу від б.в.)

Частина II Схема принципу максимума Л.С.Понтрягіна

Лекція 5. Задача оптимального керування.

Постановка лінійної задачі оптимального керування.

Множини досяжності і керованості. Компактність множини досяжності.

Лекція 6. Існування оптимального керування.

Умови керованості у лінійній задачі оптимального керування.

Теорема про існування оптимального керування.

Лекція 7. Формулювання принципу максимуму.

Схема принципу максимуму Понтрягіна.

Приклади його застосування до розв’язання задачі оптимальної швидкодії

Лекція 8. Необхідні умови оптимальності

Необхідні умови оптимальності у лінійній задачі оптимальної швидкодії. Теорема про необхідні умови оптимальності.

Лекція 9. Достатні умови оптимальності

Посилені умови трансверсальності. Теорема про достатні умови оптимальності.

Лекція 10. Синтез оптимального керування.

Задача синтезу оптимального керування для лінійної двовимірної динамічної системи. Схема застосування принципу максимуму Понтрягіна.

Динамічні ігри це математичні моделі взаємодії між різними агентами, що впливають на динамічну систему.

Постановка задачі

Лекція 11. Конфліктно керовані системи. Постановка задачі. Приклади.

Лекція 12. Перший прямий метод Л.С.Понтрягіна.

Лекція 13. Метод екстремального прицілювання М.М.Красовського.

Лекція 14. Метод розв’язуючих функцій.