Выпуклый анализ

2022-09-16T05:53:18Z

Tochilin: Новая страница: «== Разделы курса == # Выпуклая функция и ее свойства # [[Выпуклое множество и его свойства]...»

== Разделы курса ==
# [[Выпуклая функция и ее свойства]]
# [[Выпуклое множество и его свойства]]
# [[Опорная функция множества]]
# [[Теорема Каратеодори]]
# [[Поляра множества и ее свойства]]
# [[Теория двойственности Фенхеля-Моро]]
# [[Субдифференциалы выпуклых функций]]

Заглавная страница

2022-09-16T05:47:50Z

Tochilin: /* Курсы */

Добро пожаловать на страницу с учебными материалами кафедры системного анализа ВМК МГУ. Главная идея этого сайта — собрать в одном месте конспект кафедральных курсов, которые читаются студентам. Целью является создание таких статей, которые бы объясняли всю суть понятным языком, но при этом не в ущерб математической строгости.
== Курсы ==
# [[Выпуклый анализ]]
# [[Преобразования Лапласа-Фурье]]
# [[Оптимальное управление]]

Задача быстродействия

2021-11-04T15:19:53Z

Tochilin:

Задача быстродействия

2021-11-04T15:19:23Z

Tochilin:

Будет готово 28.12.2020 к 14:00

== Постановка задачи ==
''Задача быстродействия'' - задача перевода системы из начального фиксированного положения в конечное, также фиксированное, положение за минимальное время.

Пусть наша система описывается следующими условиями:
\[
\begin{cases}
\dot{x}(t) = A(t)x(t) + B(t)u(t) + f(t), \\
x(t_0) = x^0, \\
x(t_1) = x^1, \\
u(\tau) \in \mathcal{P}(\tau) \in \text{conv}\mathbb{R}^m, \\
t_1 - t_0 \rightarrow \inf,
\end{cases}
\]

где $ x_0, x_1, t_0 $ - фиксированы, $ A(t), B(t), f(t) $ - непрерывны, а $ \mathcal{P} $ непрерывно как многозначное отображение (это требование гарантирует нам, что для любого $ l: \rho(l\vert\mathcal{P}(\tau)$ по $\tau$ непрерывна$^1$).

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

Отметим, что отказ от требования $u(\tau) \in \mathcal{P}(\tau) \in \text{conv}\mathbb{R}^m$ невозможен; в этом случае $ \overline{\mathcal{X}_\mathcal{P}[t_1]} = \mathcal{X}_\overline{\mathcal{P}}[t_1] $. Разумность такого отказа показывает следующий пример:

==== Пример 1 ====
Пусть система описывается уравнениями
\[
\begin{cases}
\dot{x} = u, \\
x(0) = 0, \\
u(\tau) \in [-1, 1].
\end{cases}
\]

Тогда множеством достижимости $\mathcal{X}_1$ буде бесконечный треугольник в I и IV квадрантах, лежащий внутри прямых $x=t$ и $x=-t$. При этом, геометрически ясно, что замена множества допустимых управлений с отрезка $[-1, 1]$ на двухточечное множество $\{-1, 1\}$не изменит множества достижимости: любую точку, лежащую внутри $\mathcal{X}_1$, можно соединить с началом координат ломанной, содержащей звенья, параллельные прямым $x=t$ и $x=-1$.

Именно этот прием используется при управлении парусными судами при отсутствии попутного ветра(при этом говорят, что судно идет галсом).

Введем множество достижимости
\[
\mathcal{X}[t_1] = \mathcal{X}(t_1, t_0, x^0) = \{ x = x(t_1, t_0, x^0 \vert u(\cdot)), u(\tau) \in \mathcal{P} \}.
\]

Введем также трубку достижимости $\mathcal{X}[\cdot]$. Следует понимать, что множество достижимости - это множество, а трубка достижимости - это функция, отображающая время на соответствующее множество достижимости. Ее графиком будем называть множество $ \mathcal{X}[\cdot] = \{(t,x): x\in\mathcal{X}[t]\} $.

Ключевую роль играет следующее утверждение

==== Утверждение 1 ====
Если $t_1^*-t_0$ - время оптимального взаимодействия, $ x^*, u^* $ - соответственно траектория и управления, отвечающие этому времени, то $ (t_1^*, x^*(t_1^*)) \in \partial\mathcal{X}[\cdot] $.

Следующий пример показывает, что в криволинейных координатах это утверждение, вообще говоря, неверно.

==== Пример 2 ====
Пусть система описывается уравнениями
\[
\begin{cases}
\dot{\rho} = u_1, \vert u_1 \vert \le 1, \\
\dot{\varphi} = u_2, \vert u_2 \vert \le 1, \\
\rho(0) = \rho^0 > 0, \\
\varphi(0) = \varphi^0.
\end{cases}
\]

Если бы это были декартовы координаты на плоскости, то трубкой достижимости была бы "распухающий квадрат" $ \mathcal{X}[t_1] = \{ \vert x-x^0 \vert \le t_1, \vert y - y^0 \vert \le t_2 \} $. В нашем же случае это будет "распухающий кольцевой сектор", и множество достижимости не будет выпуклым. Это приведет к тому, что если финальная точка будет отвечать углу в $\pi$, то $ (t_1^*, x^*(t_1^*)) \notin \partial\mathcal{X}[\cdot] $.

Введем функцию $\varepsilon[t_1] = d(x^1, \mathcal{X}[t_1])$.

==== Утверждение 2 ====
$ t_1^* - t_0 $ - время оптимального взаимодействия $ \iff t_1^*$ - наименьший корень уравнения $ \varepsilon[t_1] = 0, t_1 \ge t_0 $.

При этом стоит иметь в виду, что если некое множество $Z$ - компакт, то $x \in Z \iff d(x, Z) = 0$.

== Свойства множества достижимости ==
Далее доказательства опускаются, но их знать обязательно нужно.
==== Утверждение 3 ====
$ \mathcal{X}[t_1] \in \text{conv}\mathbb{R}^n $.

==== Лемма 1 (ОЧЕНЬ важная) ====
$ \sup_{u(\cdot)} \left[ \int\limits_{t_0}^{t_1} <s(\tau), u(\tau)> d\tau \right] = \int\limits_{t_0}^{t_1} \sup_{u \in \mathcal{P}} <s(\tau), u> d\tau $.

== Условие максимума ==
Перейдем непосредственно к решению задачи быстродействия. Выпишем в терминах опорных функций условие $ x^1 \in \mathcal{X}[t_1]: $
\[
<l, x^1> \le \rho(l \vert \mathcal{X}[t_1])
\]
для любого $l$, или, в терминах расстояний до множества, $ d(x^1, \mathcal{X}[t_1] = \varepsilon[t_1] = 0 $. Фиксируем произвольное число $\hat{\varepsilon}$. Тогда верна следующая цепочка равносильных переходов:
\[
d(x^1, \mathcal{X}[t_1]) \le \hat{\varepsilon} \iff x^1 \in \mathcal{X}[t_1] + \hat{\varepsilon}B_1(0) \iff <l, x^1> \le \rho(l \vert \mathcal{X}[t_1]) + \hat{\varepsilon}\vert\vert l \vert\vert.
\]

В силу положительной однородности левой и правой части по $l$, последнее соотношение можно нормировать и записать в виде
\[
\sup_{\vert\vert l \vert\vert = 1}(<l, x^1> - \rho(l \vert \mathcal{X}[t_1])) \le \hat{\varepsilon},
\]

откуда следует, что $\varepsilon[t_1] = \sup_{\vert\vert l \vert\vert}(<l, x^1> - \rho(l \vert \mathcal{X}[t_1])) $. Таким образом, отсюда время быстродействия $t_1^*$ находится как наименьший корень уравнения $ \varepsilon[t_1^*] = 0 $.

Возьмем вектор $ l^0 \in \text{Argmax}_{\vert\vert l \vert\vert = 1}(<l, x^1> - \rho(l \vert \mathcal{X}[t_1])) $. Тогда $ <l^0, x^1> = \rho(l^0 \vert \mathcal{X}[t_1^*]) $, что означает, что $x^1$ лежит на пересечении опорной гиперплоскости и самого множества. Отсюда $ u^*(\tau) = u^{l_0}(\tau) $. Таким образом, мы можем записать необходимое условие максимума:

Если $u^*$ есть управление, доставляющее оптимальное управление, то
\[
<B^T(\tau)\psi(\tau)u^*(\tau)> = \max_{u \in \mathcal{P}(\tau)}<B^T(\tau)\psi(\tau), u>.
\]

Естественно встает вопрос: является ли это это условие достаточным? Оказывается нет - следующий пример показывается, что условию максимума может удовлетворять вообще любое допустимое управление!

==== Пример 3 ====
Рассмотрим следующую задачу быстродействию:
\[
\begin{cases}
\dot{x}_1 = u - 1, \\
\dot{x}_2 = u + 1, \\
x^0 = [0, 0]^T, \\
x^1 = [-1, 1]^T, \\
\vert u(t) \vert \le 1.
\end{cases}
\]

В этой задаче, $ \mathcal{P}(t) \equiv \mathcal{P} = [-1, 1] $. Найдем опорную функцию для этой задачи:
\[
\rho(l \vert \mathcal{X}[t_1]) = \int\limits_0^{t_1}<l, [-1, 1]^T> + \int\limits_0^{t_1}\rho([1, 1]^Tl \vert \mathcal{P}(\tau))d\tau = t_1(l_2 - l_1) + t_1\vert l_1 + l_2\vert.
\]

Легко видеть, что это сумма опорных функций одноточечного множества и отрезка. С геометрической точки зрения, множество достижимости есть отрезок, соединяющий на плоскости точки $ [-1, -1]^T $ и $[1, 1]^T$, который "ползает" по плоскости. Очевидно, что для быстрейшего достижения очки $[-1, 1]^T$ надо "ползти" вверх по прямой $y=-x$. Тогда в момент $t^*=1$ мы достигнем финальной точки.

Однако для нахождения оптимального управления нам (формально) надо было бы найти вектор-максимизатор $l_0$. На эту роль подходят вектора $ \frac{1}{\sqrt{2}}[-1, 1]^T $ и $ \frac{1}{\sqrt{2}}[1, -1]^T $.

Выпишем условие максимума:
\[
<B^Tl^0, u^*> = \max_{u \in \mathcal{P}}<B^Tl^0, u>,
\]

которое в нашем случае вид $0 = 0$.

Хотя приведенный пример показывает редкую для линейных систем ситуацию, стоит поставить вопрос о условиях, позволяющих использовать условие максимума как необходимое и достаточное условие.

==== Условие нормальности (общности положения) ====
Рассмотрим частный случай нашей задачи: Пусть $A, B$ - const, а $\mathcal{P}$ - выпуклый многогранник с непустой внутренностью, построенный на точках $u_1, u_2, \dots, u_M$, причем $u_j \in \partial\mathcal{P}, j = \overline{1, M}$. Пусть $ w = w^{k,l} = u^k-u^l $, где $k, l$ соединены ребром. Потребуем, чтобы выполнялось условие нормальности (или условие общности положения):
\[
\text{Векторы } Bw, ABw, \dots, A^{n-1}Bw \text{ линейно независимы}.
\]
Отметим, что если $\mathcal{P}$ имеет вид "параллелепипеда", $ \mathcal{P} = \{ u \in \mathbb{R}^m \vert a_i \le u_i \le b_i, i = \overline{1, m} \} $, а матрица $B$ состоит из столбцов $b^1, b^2, \dots, b^m$, то условие нормальности требует линейной независимости векторов $ b^i, Ab^i, \dots, A^{n-1}b^i $ для всех $i$, что представляет собой в точности условие полной управляемости.

Роль этого условия раскрывает следующая теорема.

==== Теорема 1 ====
Если выполняется условие нормальности, то условию максимума удовлетворяет единственное управление.

==== Замечание 1 ====
На самом деле, условие нормальности гарантирует строгую выпуклость множества достижимости.

==== Пример 4 ====
Рассмотрим задачу
\[
\begin{cases}
\dot{x}_1 = u_1, \vert u_1 \vert \le 1, \\
\dot{x}_2 = u_2, \vert u_2 \vert \le 1. \\
\end{cases}
\]

Эта система вполне управляема, но не сильно вполне управляема. Множество достижимости в данном случае - квадрат (т.е. не строго выпуклое). Случай, в котором условие максимума выделяет единственное управление, бывает тогда, когда финальная точка оказывается на углу квадрата.

=== Условие управляемости при выпуклости множества $\mathcal{P}$ ===
==== Теорема 2 ====
Пусть $\mathcal{P}$ строго выпукло и имеет непустую внутренностьб, и выполнено условие полной управляемости,
\[
\text{rg}[B\vert AB\vert \dots\vert A^{n-1}B] = n.
\]
Тогда условие максимума определяет оптимальное управление единственным образом.