sawiki - Вклад участника [ru]

Задача быстродействия "из множества во множество"

2022-11-20T20:16:14Z

Margarita: /* Принцип максимума Понтрягина */

== Постановка задачи ==
'''Задача быстродействия'''$~-$ задача перевода системы из начального фиксированного положения в конечное, также фиксированное, положение за минимальное время.
Пусть система определяется условиями:
\begin{cases}
\dot x(t) = A(t)x(t) + B(t)u(t) + f(t), \\
x(t_0) \in \mathcal{X}^0, x(t_1) \in \mathcal{X}^1, \\
u(t) \in \mathcal{P}(t) \in \text{conv}\mathbb{R}^n, \\
\mathcal{X}^0, \mathcal{X}^1 \in \text{conv}\mathbb{R}^n, \\
t_0 ~- \text{фиксировано}, \\
t_1 - t_0 \rightarrow \underset{u(\cdot)}{\text{inf}},
\end{cases}
где $ A(t), B(t), f(t) ~-$ непрерывны, а $ \mathcal{P} $ непрерывно как многозначное отображение (это требование гарантирует нам, что для любого $ l: \rho(l\vert\mathcal{P}(\tau))$ по $\tau$ непрерывна$^1$).

$^1$В частности, при $m=1$ множество $\mathcal{P}$ выглядит как $\mathcal{P}(\tau) = [a(\tau), b(\tau)]$; неперерывность многозначного отображения означает, что $a(\tau), b(\tau)~-$ непрерывны.

== Множества достижимости и разрешимости ==
'''Множеством достижимости''' в момент времени $t$ будем называть:
\[
\mathcal{X}[t] = \mathcal{X}(t, t_0, \mathcal{X}^0) = \{x| \exists u(\cdot) - \text{измеримая, т.ч.} \forall \tau \leqslant t: u(\tau) \in \mathcal{P}(\tau), \exists x^0 \in \mathcal{X}^0: x(t, t_0, x^0| u(\cdot)) = x\} = \underset{x^0 \in \mathcal{X}^0}{\cup}\mathcal{X}(t, t_0, x^0).
\]

'''Множеством разрешимости''' в момент времени $t$ будем называть:
\[
\mathcal{W}[t] = \mathcal{W}(t, t_1, \mathcal{X}^1) = \{x| \exists u(\cdot) - \text{измеримая, т.ч.} \forall \tau \leqslant t: u(\tau) \in \mathcal{P}(\tau), \exists x^1 \in \mathcal{X}^1: x(t, t_1, x^1| u(\cdot)) = x\} = \underset{x^1 \in \mathcal{X}^1}{\cup}\mathcal{W}(t, t_1, x^1).
\]
[[Файл:Sets1.png|мини|Пример множеств достижимости и разрешимости. Красным отмечена оптимальная траектория.]]

На чертеже приведён пример расположения и изменения множеств достижимости и разрешимости для оптимального времени $t_1^*$. Красным цветом приведён пример оптимальной траектории движения.
=== Свойства множеств достижимости и разрешимости ===
==== Выпуклость и компактность ====
'''Утверждение:''' Множества достижимости и разрешимости$~-$ непустые выпуклые компакты.

''Доказательство:'' Заметим, что:
\[
\begin{cases}
\mathcal{X}\left(t, t_0, \mathcal{X}^0\right) = X(t, t_0)\mathcal{X}^0 + \mathcal{X}(t, t_0, 0), \\
\mathcal{W}\left(t, t_1, \mathcal{X}^1\right) = X(t, t_1)\mathcal{X}^1 + \mathcal{W}(t, t_1, 0),
\end{cases}
\]
где $X(t, \tau)~-$ [https://sawiki.cs.msu.ru/index.php/%D0%A4%D1%83%D0%BD%D0%B4%D0%B0%D0%BC%D0%B5%D0%BD%D1%82%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D0%9A%D0%BE%D1%88%D0%B8 фундаментальная матрица Коши].
В самом деле, по [https://sawiki.cs.msu.ru/index.php/%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%9A%D0%BE%D1%88%D0%B8 формуле Коши]:
\[
x(t) = X(t, t_0)x^0 + \int\limits_{t_0}^{t}X(t, \tau)(B(\tau)u(\tau)+f(\tau))d\tau.
\]
Тогда в силу определения множества достижимости через объединение по всем допустимым значениям из исходного множества $\mathcal{X}^0$ и всем допустимым управлениям $u(\cdot)$ получаем формулу выше. Аналогичным образом поступаем с формулой для множества разрешимости.
При решении задачи быстродействия "из точки в точку" доказываются следующие два факта:
\[
\begin{cases}
\mathcal{X}(t, t_0, 0) \in \text{conv}\mathbb{R}^n, \\
\mathcal{W}(t, t_1, 0) \in \text{conv}\mathbb{R}^n.
\end{cases}
\]
По условию задачи: $\mathcal{X}^0, \mathcal{X}^1 \in \text{conv}\mathbb{R}^n$.
Тогда:
\[
X(t, t_0)\mathcal{X}^0 \in \text{conv}\mathbb{R}^n, \\
X(t, t_1)\mathcal{X}^1 \in \text{conv}\mathbb{R}^n.
\]
Суммируя непустые выпуклые компакты, получаем:
\[
\begin{cases}
X(t, t_0)\mathcal{X}^0 + \mathcal{X}(t, t_0, 0) \in \text{conv}\mathbb{R}^n, \\
X(t, t_1)\mathcal{X}^1 + \mathcal{W}(t, t_1, 0) \in \text{conv}\mathbb{R}^n,
\end{cases}
\]
что и требовалось доказать.

==== Критерий оптимальности конечного времени ====
'''Утверждение:''' $t_1^*~-$ оптимальное конечное время тогда и только тогда, когда $t_1^*~-$ минимальный корень уравнения (относительно $t$):
\[
d(\mathcal{X}(t, t_0, \mathcal{X}^0), \mathcal{X}^1) = 0,
\]
на луче $t_1 \geqslant t_0$, где $d(X, Y)~-$ евклидово расстояние между множествами $X$ и $Y$.

''Доказательство'': $\mathcal{X}^1, \mathcal{X}(t, t_0, \mathcal{X}^0) \in \text{conv} \mathbb{R}^n$. Из курса выпуклого анализа (см. книгу А.В. Арутюнова "Лекции по выпуклому и многозначному анализу", Москва, Физматлит, 2014) [https://vk.com/wall-186208863_2873] известно, что:
\[
\forall Z_1, Z_2 \in \text{conv}\mathbb{R}^n: d\left(Z_1, Z_2\right) = 0 \Leftrightarrow \exists z \in Z_1 \cap Z_2.
\]
Отсюда вытекает критерий оптимальности времени $t_1^*$.

== Теорема фон Неймана о минимаксе ==
Если выполнены следующие условия:
\[
\begin{cases}
X, Y - \text{выпуклые компакты}, \\
X \subseteq \mathbb{R}^k, Y \subseteq \mathbb{R}^l, \\
\varphi : X \times Y \rightarrow \mathbb{R} \text{, непрерывна на } X \times Y, \\
\forall y\in Y: \varphi(\cdot, y) -\text{ выпукла по }x, \\
\forall x\in X: \varphi(x, \cdot) -\text{ вогнута по }y,
\end{cases}
\]
то:
\[
\underset{x\in X}{\text{inf}}~\underset{y\in Y}{\text{sup}}~\varphi(x, y) = \underset{y\in Y}{\text{sup}}~\underset{x\in X}{\text{inf}}~\varphi(x, y).
\]
''Доказательство'' теоремы фон Неймана приводится в теоремах 1.3 и 1.1 курса лекций по теории игр и исследованию операций Морозова В.В. [https://teach-in.ru/file/synopsis/pdf/game-theory-M1.pdf].
=== Применение теоремы о минимаксе ===
Воспользуемся теоремой фон Неймана для получения некоторых результатов по нашей задаче.
Пусть $Z^1, Z^2 \in \text{conv}\mathbb{R}^n$. Тогда:
\[
d(Z^1, Z^2) = \text{inf}\left\{||z^1-z^2|| \bigg|~ z^1 \in Z^1, z^2 \in Z^2\right\} = \underset{z^1 \in Z^1}{\text{inf}} d\left(z^1, Z^2\right) = \underset{z^1 \in Z^1}{\text{inf}} \underset{||l|| \leqslant 1}{\text{sup}} \left[<l,z^1> - \rho\left(l \big| Z^2\right)\right].
\]
Применим теорему о минимаксе. Получим:
\[
d(Z^1, Z^2) = \underset{||l|| \leqslant 1}{\text{sup}}\underset{z^1 \in Z^1}{\text{inf}} \left[-<-l,z^1> - \rho\left(l \big| Z^2\right)\right] =\\
=~\underset{||l|| \leqslant 1}{\text{sup}}\left[-\underset{z^1 \in Z^1}{\text{sup}} <-l,z^1> - \rho\left(l \big| Z^2\right)\right] =\\
=~\underset{||l|| \leqslant 1}{\text{sup}}\left[-\rho\left(-l \big| Z^1\right) - \rho\left(l \big| Z^2\right)\right].
\]
Тогда из критерия оптимальности конечного времени: $t_1^* ~-$ минимальный корень уравнений:
\begin{equation}\label{z1}
\underset{||l|| \leqslant 1}{\text{max}}\left[-\rho\left(-l \big| \mathcal{X}^1\right) -
\rho\left(l \big| \mathcal{X}\left(t_1, t_0, \mathcal{X}^0\right)\right)\right] = 0,
\end{equation}
\begin{equation}\label{z2}
\underset{||l|| \leqslant 1}{\text{max}}\left[-\rho\left(-l \big| \mathcal{X}^0\right) -
\rho\left(l \big| \mathcal{W}\left(t_0,t_1,\mathcal{X}^1\right)\right)\right] = 0.
\end{equation}
При этом:
\[
(\ref{z1}) \Leftrightarrow \forall l: ~ \left[-\rho\left(-l \big| \mathcal{X}^1\right) -
\rho\left(l \big| \mathcal{X}\left(t_1, t_0, \mathcal{X}^0\right)\right)\right] \leqslant 0,
\]
\[
(\ref{z2}) \Leftrightarrow \forall l: ~ \left[-\rho\left(-l \big| \mathcal{X}^0\right) -
\rho\left(l \big| \mathcal{W}\left(t_0,t_1,\mathcal{X}^1\right)\right)\right] \leqslant 0,
\]
и для $t_1^* ~ \exists l_1^*, l_2^*: (\ref{z1}), (\ref{z2})$ обращаются в равенство, т.е:
\begin{equation}\label{r1}
-\rho\left(-l_1^* \big| \mathcal{X}^1\right) =
\rho\left(l_1^* \big| \mathcal{X}\left(t_1, t_0, \mathcal{X}^0\right)\right),
\end{equation}
\begin{equation}\label{r2}
-\rho\left(-l_2^* \big| \mathcal{X}^0\right) =
\rho\left(l_2^* \big| \mathcal{W}\left(t_0,t_1,\mathcal{X}^1\right)\right).
\end{equation}
Ниже приведены иллюстрации к уравнениям $(\ref{r1}), (\ref{r2})$.
[[Файл:Img1.png|мини|центр|Иллюстрация для уравнения с опорными функциями.]]
[[Файл:Img2.png|мини|центр|Иллюстрация для уравнения с опорными функциями.]]

== Принцип максимума Понтрягина ==
Пусть задана линейная задача быстродействия:
\[
\begin{cases}
\dot{x} = Ax + Bu, \hspace{5mm} t \in [t_0, +\infty], \\
x(t_0) \in \mathcal{X}_0, x(t_1) \in \mathcal{X}_1, \\
\forall t: u(t) \in \mathcal{P(t)}, \\
(t_1 - t_0) \rightarrow \underset{u}{\text{inf}}.
\end{cases}
\]
Пусть $(x^*(t), u^*(t))~-$ оптимальная пара, $u^*(t)$ переводит фазовую точку из положения $x(t_0) \in \mathcal{X}_0$ в положение $x(t_1) \in \mathcal{X}_1$ за время $t_1$. Тогда существует непрерывная вектор-функция $\psi = \psi(t)$, нигде не обращающаяся в нуль и удовлетворяющая следующим условиям:
\[
\begin{cases}
\dot{\psi(t)} = -A^T\psi(t), & \textbf{ (сопряжённая система)}\\
\langle B^T\psi(t), u^*(t) \rangle \stackrel{\text{п.в.}}{=} \rho(B^T\psi(t) ~|~ \mathcal{P}), & \textbf{ (условие максимума)}\\
\langle \psi(t_0), x(t_0) \rangle = \rho(\psi(t_0) ~|~ \mathcal{X}_0), & \textbf{ (условие трансверсальности в $\mathcal{X}_0$)}\\
\langle -\psi(t_1), x(t_1) \rangle = \rho(-\psi(t_1) ~|~ \mathcal{X}_1), & \textbf{ (условие трансверсальности в $\mathcal{X}_1$)}
\end{cases}
\]
где под $\rho(l|X)$ понимается значение опорной функции множества $X$ в направлении $l$.

''Доказательство'' принципа максимума Понтрягина можно найти в книге: Л.C. Понтрягин, В.Г. Болтянский, Р.В. Гамкрелидзе, Е.Ф. Мищенко. "Математическая теория оптимальных процессов". — М.: Наука, 1976 [http://control.botik.ru/wp-content/files_mf/1447942876im3547.pdf].

== Список литературы ==
* Л.C. Понтрягин, В.Г. Болтянский, Р.В. Гамкрелидзе, Е.Ф. Мищенко. "Математическая теория оптимальных процессов". — М.: Наука, 1976,
* В.В. Морозов. Курс лекций "Теория игр и исследование операций": 2021.
* А.В. Арутюнов. "Лекции по выпуклому и многозначному анализу". Москва, Физматлит, 2014

Теорема Каратеодори

2022-11-01T14:15:18Z

Margarita:

Будем рассматривать $$n$$-мерное пространство $$X$$ — вещественное линейное пространство и $$A \subset X$$. 

'''Выпуклой оболочкой множества $$A$$''' множества называется пересечение всех [[Выпуклое множество и его свойства|выпуклых множеств]], содержащих $$A$$, и обозначается $$\operatorname{conv} A$$. 

Пусть векторы $$x_0 x_1, ..., x_n \in X$$ аффинно независимы. Множество $$S = \operatorname{conv} (x_0, x_1, ..., x_n)$$ называется $$n$$-мерным '''симплексом''' с вершинами $$x_0, x_1,..., x_n$$. В частности, вырожденный симплекс размера $$n$$ — симплекс размера $$n-1$$.

Рассмотрим теорему Каратеодори, которая утверждает, что если точка $$x$$ лежит в выпуклой оболочке подмножества $$A$$ евклидового пространства, то найдётся невырожденный симплекс с вершинами в $$A$$, содержащий $$x$$. 

== Теорема Каратеодори ==
Пусть $$A \subset \mathbb{R}^n$$. Тогда $$\operatorname{conv} A$$ состоит из всевозможных выпуклых комбинаций не более чем $$(n+1)$$ точек множества $$A$$.
[[Файл:My.png|450px|thumb|frame|right|$$Теорема~Каратеодори~в~случае~\mathbb{R}^2$$]]

===== Доказательство =====
Положим
\begin{gather*}
B=\left\{x: x=\sum\limits_{i=1}^{n+1} \alpha_i x_i, \text { где } x_i \in A, ~\alpha_i \geqslant 0~\forall i=\overline{1, n+1}, \sum\limits_{i=1}^{n+1} \alpha_i=1\right\} \text {. }
\end{gather*}
По [[Теорема о наполнении|теореме о наполнении выпуклой оболочки]] $$\operatorname{conv} A: B \subset \operatorname{conv} A$$. Осталось показать, что $$\operatorname{conv} A \subset B$$. 

Пусть $$x \in \operatorname{conv} A$$. Тогда для некоторого натурального $$r$$ справедливо представление:

\begin{gather*}
x=\sum\limits_{i=1}^{r+1} \alpha_i x_i,~~ \text{где } \alpha_i \geqslant 0, ~x_i \in A, ~i=\overline{1, r+1},~ \sum\limits_{i=1}^{r+1} \alpha_i=1.
\end{gather*}

Если $$r \leqslant n$$, то $$x \in B$$. Пусть теперь $$r>n$$. Покажем, что в этом случае $$x$$ можно представить в виде выпуклой комбинации не более чем $$~r~$$ точек множества $$A$$. Если хотя бы одно из чисел $$\alpha_i$$ равно нулю, то это очевидно. Пусть теперь $$\alpha_i>0 ~\forall i$$. Поскольку $$r>n$$, система векторов $$x_i-x_{r+1},~ i=1, \ldots, r$$, линейно зависима. Поэтому найдутся такие числа $$t_1, \ldots, t_r$$, не все равные нулю, что

\begin{gather*}
\sum\limits_{i=1}^r t_i\left(x_i-x_{r+1}\right)=0
\end{gather*}

Положим $$t_{r+1}=-\sum\limits_{i=1}^r t_i$$. Тогда $$\sum\limits_{i=1}^{r+1} x_i t_i=0, \sum\limits_{i=1}^{r+1} t_i=0$$ и, значит, для произвольного числа $$c$$ :

\begin{gather}\label{eq1}
x=\sum\limits_{i=1}^{r+1} \alpha_i x_i+\sum\limits_{i=1}^{r+1} c t_i x_i=\sum\limits_{i=1}^{r+1}\left(\alpha_i+c t_i\right) x_i, \quad \sum\limits_{i=1}^{r+1}\left(\alpha_i+c t_i\right)=1.
\end{gather}

Очевидно, хотя бы одно из чисел $$t_i$$ отрицательно. Кроме того, $$\alpha_i>0$$ для любого $$i$$ и, значит, при $$c=0$$ все числа $$\left(\alpha_i+c t_i\right)$$ положительны. Будем увеличивать параметр $$c$$ от нуля до бесконечности. Тогда, очевидно, существует наименьшее число $$c>0$$ такое, что для всех номеров $$i$$ выполняется $$\left(\alpha_i+c t_i\right) \geqslant 0$$, а для
некоторого $$i_0 \leqslant r+1$$ имеет место $$\left(\alpha_{i_0}+c t_{i_0}\right)=0$$. Поэтому, отбрасывая в представлении (\ref{eq1}) $$i_0$$-е слагаемое $$\left(\alpha_{i_0}+c t_{i_0}\right) x_{i_0}$$, получаем искомое утверждение, т. е. что $$x$$ представимо в виде выпуклой линейной комбинации не более чем $$r$$ точек множества $$A$$. 

Повторяя указанную процедуру конечное число раз, получим, что $$r \leqslant n$$ и, значит, $$x \in B$$. Таким образом, доказано, что $$\operatorname{conv} A \subset B$$.
 

=== Следствия===

Для случая $$n = 1$$ множество $$A\subset \mathbb{R}^1$$ — подмножество прямой, $$\operatorname{conv}(A)$$ — объединение всех отрезков с концами в $$A$$. 

Для случая $$n = 2$$ множество $$A \subset \mathbb{R}^2$$ — подмножество координатной плоскости, $$\operatorname{conv}(A)$$ — объединение всех треугольников с вершинами в $$A$$.

 
 

== Список литературы ==
1) Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2004.

Теорема Каратеодори

2022-10-23T19:17:53Z

Margarita:

Будем рассматривать множество $$X$$ $$-$$ вещественное линейное пространство и $$A \subset X$$. 

[[Файл:Ангелов.jpg|400px|thumb|frame|right|$$Теорема~Каратеодори~в~случае~\mathbb{R}^2$$]]
'''Выпуклой оболочкой множества $$A$$''' множества называется пересечение всех выпуклых множеств, содержащих $$A$$, и обозначается $$\operatorname{conv} A$$. 

'''Симплекс''' $$-$$ геометрическая фигура, являющаяся $$n$$-мерным обобщением треугольника.

Рассмотрим теорему Каратеодори, которая утверждает, что если точка $$x$$ лежит в выпуклой оболочке подмножества $$A$$ евклидового пространства, то найдётся невырожденный симплекс с вершинами в $$A$$, содержащий $$x$$. 

== Теорема Каратеодори ==
Пусть $$A \subset \mathbb{R}^n$$. Тогда $$\operatorname{conv} A$$ состоит из всевозможных выпуклых комбинаций не более чем $$(n+1)$$ точек множества $$A$$.
===== Доказательство =====
Положим
\begin{gather*}
B=\left\{x: x=\sum\limits_{i=1}^{n+1} \alpha_i x_i, \text { где } x_i \in A, ~\alpha_i \geqslant 0~\forall i=\overline{1, n+1}, \sum\limits_{i=1}^{n+1} \alpha_i=1\right\} \text {. }
\end{gather*}
По [[Теорема о наполнении|теореме о наполнении выпуклой оболочки]] $$\operatorname{conv} A: B \subset \operatorname{conv} A$$. Осталось показать, что $$\operatorname{conv} A \subset B$$. 

Пусть $$x \in \operatorname{conv} A$$. Тогда для некоторого натурального $$r$$ справедливо представление:

\begin{gather*}
x=\sum\limits_{i=1}^{r+1} \alpha_i x_i,~~ \text{где } \alpha_i \geqslant 0, ~x_i \in A, ~i=\overline{1, r+1},~ \sum\limits_{i=1}^{r+1} \alpha_i=1.
\end{gather*}

Если $$r \leqslant n$$, то $$x \in B$$. Пусть теперь $$r>n$$. Покажем, что в этом случае $$x$$ можно представить в виде выпуклой комбинации не более чем $$~r~$$ точек множества $$A$$. Если хотя бы одно из чисел $$\alpha_i$$ равно нулю, то это очевидно. Пусть теперь $$\alpha_i>0 ~\forall i$$. Поскольку $$r>n$$, система векторов $$x_i-x_{r+1},~ i=1, \ldots, r$$, линейно зависима. Поэтому найдутся такие числа $$t_1, \ldots, t_r$$, не все равные нулю, что

\begin{gather*}
\sum\limits_{i=1}^r t_i\left(x_i-x_{r+1}\right)=0
\end{gather*}

Положим $$t_{r+1}=-\sum\limits_{i=1}^r t_i$$. Тогда $$\sum\limits_{i=1}^{r+1} x_i t_i=0, \sum\limits_{i=1}^{r+1} t_i=0$$ и, значит, для произвольного числа $$c$$ :

\begin{gather}\label{eq1}
x=\sum\limits_{i=1}^{r+1} \alpha_i x_i+\sum\limits_{i=1}^{r+1} c t_i x_i=\sum\limits_{i=1}^{r+1}\left(\alpha_i+c t_i\right) x_i, \quad \sum\limits_{i=1}^{r+1}\left(\alpha_i+c t_i\right)=1.
\end{gather}

Очевидно, хотя бы одно из чисел $$t_i$$ отрицательно. Кроме того, $$\alpha_i>0$$ для любого $$i$$ и, значит, при $$c=0$$ все числа $$\left(\alpha_i+c t_i\right)$$ положительны. Будем увеличивать параметр $$c$$ от нуля до бесконечности. Тогда, очевидно, существует наименьшее число $$c>0$$ такое, что для всех номеров $$i$$ выполняется $$\left(\alpha_i+c t_i\right) \geqslant 0$$, а для
некоторого $$i_0 \leqslant r+1$$ имеет место $$\left(\alpha_{i_0}+c t_{i_0}\right)=0$$. Поэтому, отбрасывая в представлении (\ref{eq1}) $$i_0$$-е слагаемое $$\left(\alpha_{i_0}+c t_{i_0}\right) x_{i_0}$$, получаем искомое утверждение, т. е. что $$x$$ представимо в виде выпуклой линейной комбинации не более чем $$r$$ точек множества $$A$$. 

Повторяя указанную процедуру конечное число раз, получим, что $$r \leqslant n$$ и, значит, $$x \in B$$. Таким образом, доказано, что $$\operatorname{conv} A \subset B$$.
 

=== Следствия===

Для случая $$n = 1$$ множество $$A\subset \mathbb{R}^1$$ — подмножество прямой, $$\operatorname{conv}(A)$$ — объединение всех отрезков с концами в $$A$$. 

Для случая $$n = 2$$ множество $$A \subset \mathbb{R}^2$$ — подмножество координатной плоскости, $$\operatorname{conv}(A)$$ — объединение всех треугольников с вершинами в $$A$$.

 
 

== Список литературы ==
1) Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2004.

Теорема Каратеодори

2022-10-23T19:10:10Z

Margarita:

Будем рассматривать множество $$X$$ $$-$$ вещественное линейное пространство и $$A \subset X$$. 

[[Файл:Ангелов.jpg|400px|thumb|frame|right|$$Теорема~Каратеодори~в~случае~\mathbb{R}^2$$]]
'''Выпуклой оболочкой множества $$A$$''' множества называется пересечение всех выпуклых множеств, содержащих $$A$$, и обозначается $$\operatorname{conv} A$$. 

'''Симплекс''' $$-$$ геометрическая фигура, являющаяся $$n$$-мерным обобщением треугольника.

Рассмотрим теорему Каратеодори, которая утверждает, что если точка $$x$$ лежит в выпуклой оболочке подмножества $$A$$ евклидового пространства, то найдётся невырожденный симплекс с вершинами в $$A$$, содержащий $$x$$. 

== Теорема Каратеодори ==
Пусть $$A \subset \mathbb{R}^n$$. Тогда $$\operatorname{conv} A$$ состоит из всевозможных выпуклых комбинаций не более чем $$(n+1)$$ точек множества $$A$$.
===== Доказательство =====
Положим
\begin{gather*}
B=\left\{x: x=\sum\limits_{i=1}^{n+1} \alpha_i x_i, \text { где } x_i \in A, ~\alpha_i \geqslant 0~\forall i=\overline{1, n+1}, \sum\limits_{i=1}^{n+1} \alpha_i=1\right\} \text {. }
\end{gather*}
По [[Теорема о наполнении|теореме о наполнении выпуклой оболочки]] $$\operatorname{conv} A: B \subset \operatorname{conv} A$$. Осталось показать, что $$\operatorname{conv} A \subset B$$. 

Пусть $$x \in \operatorname{conv} A$$. Тогда для некоторого натурального $$r$$ справедливо представление:

\begin{gather*}
x=\sum\limits_{i=1}^{r+1} \alpha_i x_i,~~ \text{где } \alpha_i \geqslant 0, ~x_i \in A, ~i=\overline{1, r+1},~ \sum\limits_{i=1}^{r+1} \alpha_i=1.
\end{gather*}

Если $$r \leqslant n$$, то $$x \in B$$. Пусть теперь $$r>n$$. Покажем, что в этом случае $$x$$ можно представить в виде выпуклой комбинации не более чем $$~r~$$ точек множества $$A$$. Если хотя бы одно из чисел $$\alpha_i$$ равно нулю, то это очевидно. Пусть теперь $$\alpha_i>0 ~\forall i$$. Поскольку $$r>n$$, система векторов $$x_i-x_{r+1},~ i=1, \ldots, r$$, линейно зависима. Поэтому найдутся такие числа $$t_1, \ldots, t_r$$, не все равные нулю, что

\begin{gather*}
\sum\limits_{i=1}^r t_i\left(x_i-x_{r+1}\right)=0
\end{gather*}

Положим $$t_{r+1}=-\sum\limits_{i=1}^r t_i$$. Тогда $$\sum\limits_{i=1}^{r+1} x_i t_i=0, \sum\limits_{i=1}^{r+1} t_i=0$$ и, значит, для произвольного числа $$c$$ :

\begin{gather}\label{eq1}
x=\sum\limits_{i=1}^{r+1} \alpha_i x_i+\sum\limits_{i=1}^{r+1} c t_i x_i=\sum\limits_{i=1}^{r+1}\left(\alpha_i+c t_i\right) x_i, \quad \sum\limits_{i=1}^{r+1}\left(\alpha_i+c t_i\right)=1.
\end{gather}

Очевидно, хотя бы одно из чисел $$t_i$$ отрицательно. Кроме того, $$\alpha_i>0$$ для любого $$i$$ и, значит, при $$c=0$$ все числа $$\left(\alpha_i+c t_i\right)$$ положительны. Будем увеличивать параметр $$c$$ от нуля до бесконечности. Тогда, очевидно, существует наименьшее число $$c>0$$ такое, что для всех номеров $$i$$ выполняется $$\left(\alpha_i+c t_i\right) \geqslant 0$$, а для
некоторого $$i_0 \leqslant r+1$$ имеет место $$\left(\alpha_{i_0}+c t_{i_0}\right)=0$$. Поэтому, отбрасывая в представлении (\ref{eq1}) $$i_0$$-е слагаемое $$\left(\alpha_{i_0}+c t_{i_0}\right) x_{i_0}$$, получаем искомое утверждение, т. е. что $$x$$ представимо в виде выпуклой линейной комбинации не более чем $$r$$ точек множества $$A$$. 

Повторяя указанную процедуру конечное число раз, получим, что $$r \leqslant n$$ и, значит, $$x \in B$$. Таким образом, доказано, что $$\operatorname{conv} A \subset B$$.
 

=== Следствия===

Для случая $$n = 1$$ множество $$A\subset \mathbb{R}^1$$ - подмножество прямой, $$\operatorname{conv}(A)$$ — объединение всех отрезков с концами в $$A$$. 

Для случая $$n = 2$$ множество $$A \subset \mathbb{R}^2$$ - подмножество координатной плоскости, $$\operatorname{conv}(A)$$ — объединение всех треугольников с вершинами в $$A$$.

 
 

== Список литературы ==
1) Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2004.

Теорема Каратеодори

2022-10-21T19:01:49Z

Margarita:

== Теорема Каратеодори ==
Пусть $$A \subset \mathbb{R}^n$$. Тогда $$\operatorname{conv} A$$ состоит из всевозможных выпуклых комбинаций не более чем $$(n+1)$$ точек множества $$A$$.
===== Доказательство =====
Положим
\begin{gather*}
B=\left\{x: x=\sum_{i=1}^{n+1} \alpha_i x_i, \text { где } x_i \in A, ~\alpha_i \geqslant 0~\forall i=\overline{1, n+1}, \sum_{i=1}^{n+1} \alpha_i=1\right\} \text {. }
\end{gather*}
По теореме о наполнении выпуклой оболочки $$\operatorname{conv} A: B \subset \operatorname{conv} A$$. Осталось показать, что $$\operatorname{conv} A \subset B$$. 

Пусть $$x \in \operatorname{conv} A$$. Тогда для некоторого натурального $$r$$ справедливо представление:

\begin{gather*}
x=\sum_{i=1}^{r+1} \alpha_i x_i,~~ \text{где } \alpha_i \geqslant 0, ~x_i \in A, ~i=\overline{1, r+1},~ \sum_{i=1}^{r+1} \alpha_i=1.
\end{gather*}

Если $$r \leqslant n$$, то $$x \in B$$. Пусть теперь $$r>n$$. Покажем, что в этом случае $$x$$ можно представить в виде выпуклой комбинации не более чем $$~r~$$ точек множества $$A$$. Если хотя бы одно из чисел $$\alpha_i$$ равно нулю, то это очевидно. Пусть теперь $$\alpha_i>0 ~\forall i$$. Поскольку $$r>n$$, система векторов $$x_i-x_{r+1},~ i=1, \ldots, r$$, линейно зависима. Поэтому найдутся такие числа $$t_1, \ldots, t_r$$, не все равные нулю, что

\begin{gather*}
\sum_{i=1}^r t_i\left(x_i-x_{r+1}\right)=0
\end{gather*}

Положим $$t_{r+1}=-\sum_{i=1}^r t_i$$. Тогда $$\sum_{i=1}^{r+1} x_i t_i=0, \sum_{i=1}^{r+1} t_i=0$$ и, значит, для произвольного числа $$c$$ :

\begin{gather}\label{eq1}
x=\sum_{i=1}^{r+1} \alpha_i x_i+\sum_{i=1}^{r+1} c t_i x_i=\sum_{i=1}^{r+1}\left(\alpha_i+c t_i\right) x_i, \quad \sum_{i=1}^{r+1}\left(\alpha_i+c t_i\right)=1.
\end{gather}

Очевидно, хотя бы одно из чисел $$t_i$$ отрицательно. Кроме того, $$\alpha_i>0$$ для любого $$i$$ и, значит, при $$c=0$$ все числа $$\left(\alpha_i+c t_i\right)$$ положительны. Будем увеличивать параметр $$c$$ от нуля до бесконечности. Тогда, очевидно, существует наименьшее число $$c>0$$ такое, что для всех номеров $$i$$ выполняется $$\left(\alpha_i+c t_i\right) \geqslant 0$$, а для некоторого $$i_0 \leqslant r+1$$ имеет место $$\left(\alpha_{i_0}+c t_{i_0}\right)=0$$. Поэтому, отбрасывая в представлении (\ref{eq1}) $$i_0$$-е слагаемое $$\left(\alpha_{i_0}+c t_{i_0}\right) x_{i_0}$$, получаем искомое утверждение, т. е. что $$x$$ представимо в виде выпуклой линейной комбинации не более чем $$r$$ точек множества $$A$$. 

Повторяя указанную процедуру конечное число раз, получим, что $$r \leqslant n$$и, значит, $$x \in B$$. Таким образом, доказано, что $$\operatorname{conv} A \subset B$$

==== Следствия ====

При $$n = 1$$ Для множества $$A$$ на прямой, $$\operatorname{conv}(A)$$ — объединение всех отрезков с концами в $$A$$. 

При $$n = 2$$ Для множества $$A \subset \mathbb{R}^2$$, не содержащегося в одной прямой, $$\operatorname{conv}(A)$$ — объединение всех треугольников с вершинами в $$A$$.

== Теорема о наполнении выпуклой оболочки ==
Множество $$\operatorname{conv} A$$ состоит из тех и только тех точек, которые являются выпуклыми комбинациями конечного числа точек из $$A$$.

===== Доказательство =====
Обозначим через $$B$$ множество всевозможных выпуклых комбинаций конечного числа точек из $$A$$. Поскольку множество conv $$A$$ выпукло и $$A \subset \operatorname{conv} A$$, то $$B \subset$$ $$\operatorname{conv}$$ $$A$$. Докажем обратное включение. 

Покажем, что множество $$B$$ выпукло. 
Действительно, пусть $$b_1, b_2 \in B$$. Тогда каждая из точек $$b_1$$ и $$b_2$$ представима в виде выпуклой комбинации конечного числа точек из $$A$$, причем, увеличивая, если надо, число этих точек, можно без потери общности считать, что существуют номер $$m$$ и точки $$a_i \in A, i=\overline{1, m}$$, для которых справедливы представления $$b_s=\sum_{i=1}^m \alpha_{s, i} a_i,~ s=1,2$$. Здесь $$\alpha_{s, i}, i=\overline{1, m}, s=1,2$$, - некоторые неотрицательные числа, для которых $$\sum_{i=1}^m \alpha_{s, i}=1,~ s=1,2$$. Осталось доказать, что $$\theta b_1+(1-\theta) b_2 \in B ~~\forall \theta \in[0,1]$$. Действительно,
\begin{gather*}
\theta b_1+(1-\theta) b_2=\sum_{i=1}^m\left(\theta \alpha_{1, i}+(1-\theta) \alpha_{2, i}\right)a_i \in B,
\end{gather*}
поскольку $$\theta \alpha_{1, i}+(1-\theta) \alpha_{2, i} \geqslant 0$$ для всех $$i$$ и

\begin{gather*}
\sum_{i=1}^m\left(\theta \alpha_{1, i}+(1-\theta) \alpha_{2, i}\right)=\theta \sum_{i=1}^m \alpha_{1, i}+(1-\theta) \sum_{i=1}^m \alpha_{2, i}=\theta+(1-\theta)=1.
\end{gather*}

Таким образом, выпуклость множества $$B$$ доказана. В то же время, $$A \subset B$$ и, значит, conv $$A \subset B$$. Итак, равенство conv $$A=B$$ доказано.

== Список литературы ==
1) Чистяков И.A. Лекции по курсу "Оптимальное управление", 2022.

2) Арутюнов А. В. "Лекции по выпуклому и многозначному анализу", М.: ФИЗМАТЛИТ, 2004.