| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях) Сильная выпуклость множеств достижимости линейных систем М. В. Балашов Институт проблем управления им. В. А. Трапезникова Российской академии наук, г. Москва
Англоязычная версия:
Sbornik: Mathematics, 2022, Volume 213, Issue 5, Pages DOI: https://doi.org/10.1070/SM9627 
Реферативные базы данных:
    § 1. Введение1.1.Изучению свойств множеств достижимости систем дифференциальных уравнений в $\mathbb R^n$ посвящена обширная литература (см. [1]–[4]). Особое место в ней занимают линейные системы. Один из основных вопросов о множестве достижимости – это его структура и в первую очередь ограниченность, замкнутость, выпуклость или какие-то другие геометро-топологические свойства (например, гладкость границы). Для линейной системы $x'\in Ax+U(t)$, $x(0)=0$, $U(t)$ – непрерывный по $t$ компакт, выпуклость множества достижимости вытекает из свойств интеграла Аумана (см. [5]) и содержится в классических монографиях, например в [1; теорема 1, гл. 2, п. 2.2]. По сути указанные результаты о выпуклости интеграла Аумана и т.д. являются прямым следствием теоремы Ляпунова о векторной мере (см. [6]). Свойства множеств достижимости используются для анализа динамических систем и в некоторых случаях для построения управления. Далеко идущие обобщения множества достижимости, например, альтернированный интеграл Понтрягина (см. [7]) и стабильный мост Красовского (см. [8]), являются важными техническими конструкциями для анализа и решения линейных дифференциальных игр с нулевой суммой. Во многих работах исследуется погрешность многогранной или какой-то иной (например, эллипсоидальной) аппроксимации множества достижимости (см. [9]–[11]), обычно в метрике Хаусдорфа. Поэтому актуальным является усиление свойства выпуклости множества, т.е. замена выпуклости на какой-то тип строгой выпуклости, которая, как известно (см. [12]), гарантирует в свою очередь уменьшение погрешности многогранной аппроксимации множества на сетке единичных векторов. Одним из важнейших классов строго выпуклых множеств является класс сильно выпуклых множеств. Множество $M\subset\mathbb R^n$ является сильно выпуклым с радиусом $R$, если оно представимо в виде пересечения замкнутых шаров радиуса $R$. Сильно выпуклые множества исследованы в работах [13]–[16]. В [17; теорема 4.2] показано, что для нелинейной динамической системы $x'=f(x)$, $x(0)\in\Omega\subset\mathbb R^n$, при определенных условиях (в частности, при условии сильной выпуклости множества начальных состояний $\Omega$) множество достижимости сильно выпукло с некоторым радиусом. Отметим, что идея доказательства состоит в применении опорного принципа для сильно выпуклых множеств, который устанавливается локально по времени для множества достижимости, а не в линеаризации системы. Автору известно крайне мало глобальных результатов о сильной выпуклости множества достижимости динамической системы или (что по сути – более общий вопрос) о сильной выпуклости интеграла Аумана для многозначного отображения достаточно общей природы. В работе [18] доказано, что если непрерывное многозначное отображение $F(t)$, $t\in [0,T]$, имеет сильно выпуклые значения с радиусом $R(t)$, то интеграл Аумана $\displaystyle\int_{0}^{T}F(t)\, dt$ является сильно выпуклым множеством с радиусом $\displaystyle R=\int_{0}^{T}R(t)\, dt$. Свойства сильной выпуклости множеств управления и терминального множества использовались в работе [11] для доказательства сильной выпуклости альтернированного интеграла Понтрягина и, как следствие, квадратичной скорости сходимости по пространству альтернированных сумм Понтрягина. В работе [19] было отмечено, что если непрерывное многозначное отображение $F(t)$, $t\in [0,T]$, имеет компактные (не обязательно выпуклые) значения и множество $\displaystyle\int_{0}^{T}F(t)\, dt$ сильно выпукло с радиусом $R$, то, как следует из линейности интеграла по $t$, для всякого $t\in [0,T]$ интеграл Аумана $\displaystyle\int_{0}^{t}F(s)\, ds$ также является сильно выпуклым множеством с радиусом $R$. В настоящей работе мы хотим описать достаточные условия глобальной по времени сильной выпуклости множества достижимости линейной управляемой системы. В § 4 показано, что в пространстве размерности $2$ для управляемой системы с произвольной матрицей $A$ и широким выбором автономного множества управлений $U(t)=U$ множество достижимости сильно выпукло. Основная техническая идея доказательства содержится в лемме 1 о том, что из некоторого локального условия для выпуклого компактного множества следует его сильная выпуклость. Указанная лемма имеет также самостоятельный интерес. В § 5 показано, как полученные результаты могут быть применены в пространстве размерности $n\geqslant 3$. В конце работы, в § 6, мы обсудим различные приложения полученных результатов. 1.2. Некоторые определения и обозначенияВ вещественном евклидовом пространстве $\mathbb R^n$ размерности $n$ обозначим через $(x,y)$ скалярное произведение векторов $x$, $y$, $\| x\|=\sqrt{(x,x)}$. Положим $B_R(a)=\{ x\in\mathbb R^n\mid \| x-a\|\leqslant R\}$. Будем обозначать через $e_1,\dots,e_n$ стандартный ортонормированный базис в $\mathbb R^n$. Для подмножеств $P,Q\subset\mathbb R^n$ их суммой Минковского называется множество геометрической разностью или разностью Минковского–Понтрягина называется множество
$$
\begin{equation*}
P\tfrac{\, *\,}{}\, Q=\{ x\mid x+Q\subset P\}=\bigcap_{x\in Q}(P-x).
\end{equation*}
\notag
$$
Говорят, что множество $P$ является слагаемым множества $R$, если найдется такое множество $Q$, что $P+Q=R$. Пусть для множества $P\subset\mathbb R^n$ и точки $x\in\mathbb R^n$ Расстоянием по Хаусдорфу между компактными множествами $P$ и $Q$ называется число
$$
\begin{equation*}
\begin{aligned} \, h(P,Q) &=\inf\bigl\{ \varepsilon>0\mid P\subset Q+B_{\varepsilon}(0),\, Q\subset P+B_{\varepsilon}(0)\bigr\} \\ &=\max\Bigl\{ \max_{x\in P}\varrho_Q(x),\, \max_{x\in Q}\varrho_P(x)\Bigr\}. \end{aligned}
\end{equation*}
\notag
$$
Опорной функцией множества $Q\subset\mathbb R^n$ называется функция Для выпуклого замкнутого множества $U\subset\mathbb R^n$ определим нормальный конус в точке $x\in U$, т.е. $N(U,x)=\{ p\in\mathbb R^n\mid (p,x)=s(p,U)\}$. Для выпуклого компактного множества $U\subset\mathbb R^n$ и вектора $p\ne 0$ множество $U(p)=\{ x\in U\mid (p,x)=s(p,U)\}$ – опорное множество (элемент) множества $U$ в направлении $p$. Напомним, что $U(p)$ есть субдифференциал $s(\cdot,U)$ в точке $p$. Мы будем использовать символы многозначных отображений $F(t)$, $t\in [0,T]$. Обычно для каждого $t$ множество $F(t)$ будет компактным (выпуклым), непрерывным по $t$ в метрике Хаусдорфа. Договоримся обозначать опорное множество для $F(t)$ и вектора $p\ne 0$ через $F(t)(p)$. Субдифференциалом выпуклой функции $f\colon \mathbb R^n\supset D\to\mathbb R$ в точке $x_0\in\mathbb R^n$ называется (возможно, пустое) множество
$$
\begin{equation*}
\partial f(x_0)=\{ p\in\mathbb R^n\mid f(x)\geqslant f(x_0)+(p,x-x_0)\ \forall\, x\in D\}.
\end{equation*}
\notag
$$
Обозначим через $\operatorname{co} P$ и $\operatorname{cone}P$ соответственно выпуклую и коническую оболочки множества $P\subset\mathbb R^n$. Пусть $\operatorname{cl}P$ – замыкание множества $P$, а $\operatorname{int}P$ – внутренность. Множество $M\ne\varnothing$ называется сильно выпуклым с радиусом $R$, если $M=\bigcap_{x\in X}B_R(x)$. Для выпуклого компактного множества $M$ эквивалентны (см. [15; теоремы 4.2.7 и 4.3.3]) следующие условия: 1) множество $M$ сильно выпукло с радиусом $R$; 2) (опорный принцип) для любого $\| p\|=1$ выполнено $M\subset B_R(M(p)-Rp)$; 3) $\| M(p)-M(q)\|\leqslant R\| p-q\|$ для всех $\| p\|=\| q\|=1$. § 2. Интеграл от многозначного отображения и множество достижимости линейной системыНапомним, что для многозначного отображения $F(t)$, $t\in [0,T]$, с непрерывными в метрике Хаусдорфа компактными значениями из $\mathbb R^n$ интеграл Аумана (см. [5]) есть
$$
\begin{equation*}
\int_{0}^{t}F(s)\, ds=\biggl\{ \int_{0}^{t} f(s)\, ds\Bigm| f\in F \text{ - измеримая по Лебегу ветвь}\biggr\}.
\end{equation*}
\notag
$$
Интегралом Римана (см. [20; гл. 4, § 30]) называется
$$
\begin{equation*}
\int_{0}^{t}F(s)\, ds=\lim_{|\tau |\to 0}\sum_{i=0}^{I-1}F(\xi_i)(x_{i+1}-x_i),
\end{equation*}
\notag
$$
где использованы стандартные обозначения: разбиение $\tau=\{ x_i\}_{i=0}^I$, мелкость разбиения $|\tau |=\max_{i}(x_{i+1}-x_i)$, выборка $\xi_i\in [x_i,x_{i+1}]$. Для непрерывного многозначного отображения с компактными значениями указанные интегралы совпадают и равны интегралу от $\operatorname{cl}\operatorname{co} F(t)$ (см. [20], где теорема 30.6 и определение 31.7 гарантируют равенство интегралов Римана и Лебега, теорема 35.1 дает эквивалентность интегралов Аумана и Лебега). Из определений следуют линейность интеграла по отрезку интегрирования, равенство $s\biggl(p, \displaystyle\int_{0}^{t}F(s)\, ds\biggr)=\int_{0}^{t}s(p,F(s))\, ds$ для любого $p\in\mathbb R^n$, а также то, что опорное множество $\displaystyle\int_{0}^{t}F(s)\, ds$ в направлении $p\ne 0$ есть $\displaystyle\int_{0}^{t}F(s)(p)\, ds$. Иными словами,
$$
\begin{equation*}
\biggl( \int_{0}^{t}F(s)\, ds\biggr)(p)=\int_{0}^{t}F(s)(p)\, ds.
\end{equation*}
\notag
$$
Для всякой матрицы $J\in\mathbb R^{n\times n}$ имеем Пример 1. Разберем пример, заимствованный из [20; пример 34.2]. Для матрицы поворота рассмотрим $F(s)=Q(s)P$, где $P=\operatorname{co}\{ \pm e_1\}$. Пусть $p=(\cos\theta, \sin\theta)$ – единичный вектор. Тогда т.е. $\displaystyle\int_{0}^{2\pi}F(s)\, ds=B_4(0)$. Рассмотрим систему $x'\in Ax+U(t)$. Здесь $x\in\mathbb R^n$, $A\in\mathbb R^{n\times n}$, $U(t)\subset\mathbb R^n$ – выпуклый компакт, непрерывный по $t$ в метрике Хаусдорфа. Рассмотрим множество достижимости $M(t)$ указанной системы с начальным условием $x(0)=0$. Делая замену $x=e^{At}z$, получаем
$$
\begin{equation*}
M_z(t)=\int_{0}^{t}e^{-A s}U(s)\, ds, \qquad M(t)=M_x(t)=\int_{0}^{t}e^{A(t-s)}U(s)\, ds.
\end{equation*}
\notag
$$
Выпуклость $M(t)$ вытекает из выпуклости интеграла Аумана. В настоящей работе нас будет интересовать случай постоянного $U(t)=U$:
$$
\begin{equation}
x'\in Ax+U, \quad x(0)=0, \qquad U \text{ - выпуклый компакт}.
\end{equation}
\tag{2.2}
$$
В этом случае $\displaystyle M(t)=\int_{0}^{t}e^{A(t-s)}U\, ds=\int_{0}^{t}e^{As}U\, ds$.
§ 3. Некоторые свойства интегралов и сильно выпуклых множествЛемма 1. Пусть выпуклое множество $C\subset \mathbb R^n$ удовлетворяет условию ($x_p=\arg\max_{x\in C}(p,x)$) Тогда множество $C$ сильно выпуклое с радиусом $R$. Отметим, что условие (3.1) означает, что $\arg\max_{x\in C}(p,x)$ для любого единичного вектора $p$ является одноточечным множеством. Доказательство леммы 1. Для $\| p\|=1$ положим $H_p(C)=\{ x\in\mathbb R^n\mid (p,x)\leqslant s(p,C)\}$. Заметим, что $\operatorname{int} C\ne\varnothing$, и пусть $\Gamma\subset \partial C$ – точки гладкости $\partial C$. Как известно из выпуклого анализа (см. [21; теорема 25.6]), для выпуклой функции $f\colon B_{\delta}(x_0)\to\mathbb R$ имеет место равенство для субдифференциала откуда получаем $C=\bigcap_{x\in \Gamma,\, p\in N(C,x),\, \|p\|=1}H_p(C)$ (для доказательства трактуем локально $\partial C$ как график выпуклой функции). Допустим, найдутся такие точка $x\in \Gamma$ и единичный вектор $p(x)\in N(C,x)$, что $C\not\subset B_R(x-Rp(x))$. Если такой точки $x$ во множестве гладкости границы $\Gamma$ не найдется, то
$$
\begin{equation*}
C\subset\bigcap_{x\in \Gamma,\ p(x)\in N(C,x),\, \|p(x)\|=1} B_R(x-Rp(x))\subset\bigcap_{x\in \Gamma,\, p\in N(C,x),\, \|p\|=1}H_p(C)=C
\end{equation*}
\notag
$$
и множество $C$ является сильно выпуклым с радиусом $R$. Обозначим, как обычно, $p(x)$ и $x\in\Gamma$ через $p$ и $x_p$ соответственно. Поскольку локальная сильная выпуклость эквивалентна глобальной (см. [17; теорема 1.1]), то для всякого $k\in\mathbb N$ Так как субдифференциал выпуклой индикаторной функции $\delta (x,C)$ полунепрерывен сверху, то для $\varepsilon=l_0$ с учетом одномерности нормального конуса $N(C,x_p)$ имеем
$$
\begin{equation}
\exists\,\delta>0 \quad \forall\, x\in \partial C \quad \| x-x_p\|<\delta \quad \forall\, \| q\|=1, \quad q\in N(C,x), \qquad q\in p+B_{l_0}(0).
\end{equation}
\tag{3.2}
$$
Заметим, что единичный вектор $p$ в конусе $N(C,x_p)$ единственный в силу включения $x_p\in\Gamma$. Отсюда получаем, что для всех достаточно больших $k\in\mathbb N$ для всякого $x\in B_{1/k}(x_p)\cap \partial C$ всякий единичный вектор $q\in N(C,x)$ удовлетворяет условию $\| q-p\|\leqslant l_0$. Пусть $k\in\mathbb N$, $1/k<\delta$ ($\delta$ – число из (3.2)) и $C_0=B_{1/k}(x_p)\cap \partial C$. Положим $z=x_p-Rp$. Пусть точка $x_0\in C_0$ выбрана из условия $\| x_0-z\|=\max_{x\in C_0}\| x-z\|$. Очевидно, $\| x_0-z\|=R_1>R$. Положим $q_0=(x_0-z)/\| x_0-z\|$. Заметим, что по построению вектора $q_0$ выполнено равенство $x_0=\arg\max_{x\in C_0}(q_0,x)$ и для $x_0=z+R_1q_0$, $x_p=z+Rp$ имеем
$$
\begin{equation*}
\begin{aligned} \, \| x_0-x_p\|^2 &=\| q_0(R_1-R)+R(q_0-p)\|^2 \\ &=(R_1-R)^2+R^2\| q_0-p\|^2+2R(R_1-R)(q_0,q_0-p) \\ &\geqslant (R_1-R)^2+R^2\| q_0-p\|^2. \end{aligned}
\end{equation*}
\notag
$$
Если $\| p-q_0\|\leqslant l_0$, то при $q_0\in N(C,x_0)$ получаем противоречие с (3.1). Если $q_0\notin N(C,x_0)$, то из определения $C_0$ имеем $x_{q_0}\notin C_0$, откуда $\|x_p-x_{q_0}\|>\|x_p-x_0\|$ и снова приходим к противоречию с (3.1). Пусть ${\| p-q_0\|> l_0}$. Поскольку для всякого единичного вектора $q\in N(C,x_0)$ выполнено $\| q-p\|\leqslant l_0$, то что снова противоречит условию леммы.Лемма доказана. Лемма 2. Пусть $f\colon [0,t]\to\mathbb R$ – непрерывная функция с положительными значениями, $U(s)\subset\mathbb R^n$, $s\in [0,t]$, – многозначное отображение с выпуклыми компактными значениями. Пусть $C>0$ и $f(s)\leqslant C$ для всех $s\in [0,t]$. Тогда $\displaystyle \int_{0}^{t}f(s)U(s)\, ds$ является слагаемым множества $\displaystyle \int_{0}^{t}CU(s)\, ds$. Доказательство. В силу выпуклости $U(s)$ для всех $s\in [0,t]$, т.е. имеем откуда следует утверждение леммы. Лемма 3. Пусть $f\colon [0,t]\to\mathbb R$ – непрерывная функция с положительными значениями, $U(s)\subset\mathbb R^n$, $s\in [0,t]$, – многозначное отображение с выпуклыми компактными значениями. Пусть $\displaystyle M(t)=\int_{0}^{t}f(s)U(s)\, ds$. Тогда для любых единичных векторов $p,q$ выполнено равенство Доказательство вытекает из свойств интеграла. § 4. Сильная выпуклость множества достижимости в плоском случаеЛемма 4. Пусть система (2.2) имеет матрицу $A_1=J^{-1}AJ$ в жордановой форме, $U_1=J^{-1}U$, $J\in \mathbb R^{n\times n}$ – матрица перехода. Если множество $\displaystyle M_1(t)=\int_{0}^t e^{A_1s}U_1\, ds$ сильно выпуклое с радиусом $r$, то $\displaystyle M(t)=\int_{0}^{t}e^{As}U\, ds$ сильно выпукло с радиусом $R=r\alpha^2/\beta$, где $\alpha=\| J\|=\max_{\| h\|=1}\| Jh\|$, $\beta=\min_{\| h\|=1}\| Jh\|$. Доказательство. Из равенства $e^{As}=Je^{A_1s}J^{-1}$ имеем
$$
\begin{equation*}
M(t)=\int_{0}^{t}Je^{A_1s}J^{-1}U\, ds=\int_{0}^{t}Je^{A_1s}U_1\, ds=JM_1(t).
\end{equation*}
\notag
$$
Результат леммы вытекает из [15; теорема 4.3.3]. Лемма доказана. Лемма 4 показывает, что достаточно проанализировать ситуацию для системы (2.2) с матрицей $A$ в жордановой форме. Теорема 1. Пусть $f\colon [0,2\pi]\to \mathbb R_+$ – непрерывная функция, $C>0$ и $f(s)\leqslant C$ для всех $s\in [0,2\pi]$. Пусть $Q(s)$ – матрица поворота (см. пример 1) и $U\subset\mathbb R^2$ – выпуклый компакт. Пусть $\displaystyle M(t)=\int_{0}^t f(s)Q(s)U\, ds$. Тогда множество $M(2\pi)$ сильно выпукло с константой $R=CL_U$, где $L_U$ – периметр $\partial U$. Для телесного множества $U$ периметр $L_U$ есть длина спрямляемой кривой $\partial U$. Для отрезка $L_U$ есть его удвоенная длина. Доказательство теоремы 1. Пусть $\{U_m\}_{m=1}^{\infty}$ – последовательность выпуклых многоугольников, аппроксимирующих $U$ в метрике Хаусдорфа ($h(U_m,U)\to0$) и Зафиксируем $U_m$, $M_m(t)$ для $m\in\mathbb N$. Пусть $L_m$ – длина $\partial U_m$. Пусть $\theta_m$ – минимальный угол (раствор) конусов $N(U_m,x)$ по всем крайним точкам $x$ множества $U_m$. Рассмотрим единичные векторы $p,q$ такие, что $\| p- q\|\leqslant 2\sin(\theta_m/2)$. Уменьшим, если необходимо, $\theta_m>0$ так, чтобы выполнялось неравенство $\theta_m\leqslant 2( 1+1/m)\sin(\theta_m/2)$. При этом
$$
\begin{equation}
\theta\leqslant 2\biggl( 1+\frac1m\biggr)\sin\frac{\theta}{2} \quad \forall\, \theta\in (0,\theta_m).
\end{equation}
\tag{4.1}
$$
Для вектора $\| p\|=1$ опорным элементом множества $Q(s)U_m$ является точка $U_m(Q^\top(s)p)$ для всех $s$ (кроме конечного числа), когда вектор $p$ ортогонален одному из ребер многогранника $U_m(Q^\top(s)p)$. Отсюда получаем
$$
\begin{equation*}
\max_{a\in U_m}(p, Q(s)a)=\max_{a\in U_m}(Q^\top(s)p, a)=\bigl(Q^\top(s)p, U_m(Q^\top(s)p)\bigr).
\end{equation*}
\notag
$$
Имеем
$$
\begin{equation}
\begin{aligned} \, \notag \bigl\| M_m(2\pi)(p)-M_m(2\pi)(q)\bigr\| &=\biggl\| \int_{0}^{2\pi} f(s)Q(s)\bigl( U_m(Q^\top(s)p)-U_m(Q^\top(s)q)\bigr)\, ds\biggr\| \\ &\leqslant C \int_{0}^{2\pi} \bigl\| U_m(Q^\top(s)p)-U_m(Q^\top(s)q)\bigr\|\, ds. \end{aligned}
\end{equation}
\tag{4.2}
$$
Положим $\mathbb K=\operatorname{cone}\{ p,q\}$, и пусть $\theta$ – угол между векторами $p,q$. Пусть $\{a_k\}_{k=1}^{K+1}$ – вершины $U_m$, занумерованные против часовой стрелки, $a_{K+1}=a_1$. Подынтегральное выражение в правой части формулы (4.2) не равно нулю тогда и только тогда, когда $Q(s)\mathbb K\not\subset \bigcup_{k=1}^K N(U_m,a_k)$, откуда с учетом (4.2) получаем
$$
\begin{equation*}
\int_{0}^{2\pi} \bigl\| U_m(Q^\top(s)p)-U_m(Q^\top(s)q)\bigr\|\, ds \leqslant\sum_{k=1}^{K}\theta\| a_k-a_{k+1}\|=\theta L_m.
\end{equation*}
\notag
$$
В силу формулы (4.1)
$$
\begin{equation*}
\theta L_m\leqslant 2\biggl( 1+\frac1m\biggr)L_m\sin\frac{\theta}{2} =\biggl( 1+\frac1m\biggr)L_m\| p-q\|.
\end{equation*}
\notag
$$
Итак,
$$
\begin{equation*}
\| M_m(2\pi)(p)-M_m(2\pi)(q)\|\leqslant \biggl( 1+\frac1m\biggr)CL_m\| p-q\|
\end{equation*}
\notag
$$
для всех единичных векторов $p,q$, угол между которыми менее $\theta_m$. В силу леммы 1 и с учетом леммы 2 $M_m(2\pi)$ сильно выпукло с $R_m=(1+1/m)CL_m$. Переходя к пределу по $m\to\infty$, получаем
$$
\begin{equation*}
M_m(2\pi)\to M(2\pi), \qquad \biggl( 1+\frac1m\biggr)CL_m\to CL_U,
\end{equation*}
\notag
$$
т.е. $M(2\pi)$ сильно выпукло с $R=CL_U$. Теорема 1 доказана. Заметим, что для случая, рассмотренного в примере 1, теорема 1 дает точную оценку. Следствие. Пусть в системе (2.2) $n=2$, собственные числа матрицы $A$ равны $\lambda_{1,2}=\alpha\pm i\beta$, $\beta>0$. Тогда для любого выпуклого компакта $U$ множество $M(2\pi/\beta)$ сильно выпукло с радиусом $R=\frac{1}{\beta}CL_U$, где $L_U$ – периметр границы $U$ и $C=\max\{ 1, e^{2\pi{\alpha}/{\beta}}\}$. Если $\alpha<0$, то $M(+\infty)$ сильно выпуклое с радиусом $R=L_U/(\beta (1-e^{{2\pi\alpha}/{\beta}}))$. Доказательство. По теореме 1 множество $M(2\pi{\alpha}/{\beta})$ сильно выпукло c $R=({1}/{\beta})CL_U$. Если $\alpha<0$, то
$$
\begin{equation*}
\begin{aligned} \, M(+\infty) &=\int_{0}^{+\infty} e^{\alpha s}Q(\beta s)U\, ds =\sum_{k=0}^{\infty}\int_{2\pi{k}/{\beta}}^{2\pi(k+1)/\beta} e^{\alpha s}Q(\beta s)U\, ds \\ &=\sum_{k=0}^{\infty}\frac{1}{\beta}\int_{2\pi k}^{2\pi (k+1)} e^{s\alpha/\beta}Q(s)U\, ds. \end{aligned}
\end{equation*}
\notag
$$
В силу теоремы 1 получаем, что $k$-е слагаемое в последней сумме сильно выпуклое с ${R_k\leqslant e^{2\pi k\alpha/\beta}(L_U/\beta)}$. Отсюда следует, что $M(+\infty)$ сильно выпуклое с Следствие доказано. Теорема 2. Пусть в системе (2.2) $n=2$, собственные числа матрицы $A$ вещественные и равны: $\lambda_{1,2}=\lambda\in\mathbb R$. Предположим, что выполняется условие: $\exists\, R_0>0$ $\exists\, \gamma>0$ $\exists\, \delta>0$ такие, что Тогда множество $M(t)$ сильно выпуклое для любого $t>0$. Условие (4.3) означает, что локально выполнен опорный принцип для сильно выпуклых множеств с одним $R_0$ для всех единичных векторов из окрестности $\pm e_2$. Доказательство теоремы 2. Фиксируем $t>0$. Обозначим Будем без ограничения общности считать, что для любой точки $(a,b)\in U$ для ординаты $b$ выполнено $b\geqslant 0$. Этого легко достичь, сдвинув $U$. 1. Множество $U$ – многоугольник. В силу (4.3) множества $U(\pm e_2)$ одноточечны. В силу одноточечности $U(\pm e_2)$ и того, что $U$ – многоугольник, найдется число $\alpha_0>0$ такое, что угол между осью абсцисс $Ox$ и любой стороной $\partial U(s)$ не менее $\alpha_0$ при всех $s\in [0,t]$. Рассмотрим произвольную сторону $l=[(a_1,b_1),(a_2,b_2)]$ многоугольника $U$, причем $b_1<b_2$. Пусть $p,q\in\partial B_1(0)$ и угол между $p, q$ равен $\theta$. Выберем число $\theta>0$ меньше, чем раствор любого нормального конуса в вершинах множеств $U(s)$ по всем $s\in [0,t]$. Тогда опорные элементы $U(s)(p)$ и $U(s)(q)$ достигаются в вершинах $Q(\tau )l$ при условии, что $\tau\in [s,s+\Delta s]$, где $Q(s)l\perp q$, $Q(s+\Delta s)l\perp p$. Это значит, что угол между векторами $l_1=(a_2-a_1+s(b_2-b_1), b_2-b_1)$ и $l_2=(a_2-a_1+(s+\Delta s)(b_2-b_1), b_2-b_1)$ равен углу между $p$ и $q$, т.е. $\theta$. Пусть
$$
\begin{equation*}
d=\| l_1\|, \qquad \angle (l_1l_2O)=\alpha\in (\alpha_0,\pi-\alpha_0), \qquad \sigma=b_2-b_1>0, \qquad \angle (l_1Ol_2)=\theta.
\end{equation*}
\notag
$$
При этом $\| l_1-l_2\|=\sigma\Delta s$. Из определения $\alpha_0$ получаем ${\sigma}/{d}\geqslant \sin \alpha_0$ или ${d}/{\sigma}\leqslant {1}/{\sin \alpha_0}$. По теореме синусов из треугольника $Ol_1l_2$
$$
\begin{equation}
\frac{\sin\theta}{\sigma\Delta s}=\frac{\sin\alpha}{d}\geqslant \frac{\sin\alpha_0}{d}, \qquad \Delta s\leqslant \frac{d}{\sigma}\,\frac{\sin\theta}{\sin\alpha_0}\leqslant \frac{\sin\theta}{\sin^2\alpha_0}.
\end{equation}
\tag{4.4}
$$
Положим $C=\max\{ 1, e^{\lambda t}\}$ и $M=\max_{s\in [0,t]}\| Q(s)\|$. Тогда
$$
\begin{equation}
\| M(t)(p)-M(t)(q)\|\leqslant \int_{0}^{t}e^{\lambda t}\| U(s)(p)-U(s)(q)\|\, ds\leqslant \sum_i Cd_i\Delta s_i;
\end{equation}
\tag{4.5}
$$
последнее суммирование ведется по всем сторонам $l_i$ многоугольника $U$, $d_i=\max_{s\in [s_i,s_i+\Delta s_i]}\| Q(s)l_i\|$, $\| l_i\|$ – длина $l_i$ (при $s\in [s_i,s_i+\Delta s_i]$ опорные элементы $U(s)(p)$ и $U(s)(q)$ достигаются в вершинах $Q(s)l_i$). С учетом (4.4) из (4.5) получаем
$$
\begin{equation*}
\sum_i Cd_i\Delta s_i \leqslant \frac{CM}{\sin^2\alpha_0}\sin\theta\sum_i \| l_i\|=\frac{CM}{\sin^2\alpha_0}L_U\sin\theta.
\end{equation*}
\notag
$$
Итак,
$$
\begin{equation*}
\| M(t)(p)-M(t)(q)\|\leqslant \frac{CM}{\sin^2\alpha_0}L_U\cdot 2\sin\frac{\theta}{2}=\frac{CM}{\sin^2\alpha_0}L_U\cdot\| p-q\|.
\end{equation*}
\notag
$$
По лемме 1 множество $M(t)$ сильно выпуклое с $R=({CM}/{(\sin^2\alpha_0)})L_U$. 2. Множество $U$ произвольное. Пусть число $\delta>0$ взято из условия (4.3). Положим
$$
\begin{equation*}
\mathcal K_1=\bigl\{ p\in B_{\delta}(-e_2)\mid \|p\|=1\bigr\}, \qquad \mathcal K_2=\bigl\{ p\in B_{\delta}(e_2)\mid \|p\|=1\bigr\}
\end{equation*}
\notag
$$
и $\mathcal K=\mathcal K_1\cup \mathcal K_2$. Так как образы $Q(s)B_{R_0}(U(p)-R_0p)$ есть эллипсы, которые сильно выпуклы (см. [15; теорема 4.3.3]), то найдется $R_1>0$ такое, что для любого $p\in\mathcal K$ и $s\in [0,t]$
$$
\begin{equation*}
\begin{gathered} \, Q(s)B_{R_0}\bigl(U(p)-R_0p\bigr)\subset B_{R_1}\bigl(Q(s)U(p)-R_1\xi\bigr), \\ \xi\in N\bigl(Q(s)U, Q(s)U(p)\bigr), \qquad \|\xi\|=1. \end{gathered}
\end{equation*}
\notag
$$
Найдем зависимость $\xi=\xi (s,p)$. Пусть $e$ – направляющий вектор опорной прямой $\mathcal L$ с нормалью $p\in\mathcal K$, проходящей через точку $U(p)$. Тогда образом опорной прямой $\mathcal L$ будет прямая, проходящая через точку $Q(s)U(p)$ с направляющим вектором $Q(s)e$. Легко видеть, что единичный нормальный вектор к этой прямой есть
$$
\begin{equation}
\xi=\xi (s,p)=\frac{(Q^\top(s))^{-1}p}{\| (Q^\top(s))^{-1}p\|}.
\end{equation}
\tag{4.6}
$$
Поскольку $Q(s)U(\pm e_2)=U(s)(\pm e_2)$ для всех $s\in [0,t]$ и преобразование $Q(s)$ невырожденное и непрерывное при $s\in [0,t]$, то с учетом (4.6) получаем для всех $p\in \mathcal K$ и $s\in [0,t]$
$$
\begin{equation}
U(s)\cap \bigl( Q(s)B_{\gamma}(U(\pm e_2))\bigr)\subset B_{R_1}(0)+U(s)(\xi(s,p))-R_1\xi(s,p).
\end{equation}
\tag{4.7}
$$
Положим для всех $s\in [0,t]$ и $i=1,2$
$$
\begin{equation*}
\mathcal M_i(s)=\operatorname{cone}\{ \xi (s,p)\mid p\in \mathcal K_i\}, \qquad \mathcal M_i=\bigcap_{s\in [0,t]}\mathcal M_i(s), \quad \mathcal M=\mathcal M_1 \cup \mathcal M_2.
\end{equation*}
\notag
$$
Поскольку $\pm e_2$ – внутренний вектор $\mathcal M_{1,2}(s)$ при всех $s$, то из соображений непрерывности $\xi (s,p)$ и компактности по $s$ имеем $-e_2\in \operatorname{int} \mathcal M_1$, $e_2\in \operatorname{int} \mathcal M_2$. Следовательно, существует $\mu>0$ такое, что для любого единичного вектора $q\notin \mathcal M_1\cup \mathcal M_2$ и единичного вектора $e$, $(q,e)=0$, синус угла между $e$ и осью $Ox$ не менее $\mu$. Иными словами, угол между всякой прямой с нормалью $q$ и осью абсцисс не менее $\alpha_0$. Фиксируем $s\in [0,t]$ и единичные векторы $\xi, \eta$ из $\mathcal M_i$ для $i=1$ или $i=2$. Из включения (4.7) получаем $\| U(s)(\xi)-U(s)(\eta)\|^2\leqslant 2R_1(\xi, U(s)(\xi)-U(s)(\eta))$. Меняя местами $\xi$ и $\eta$, получаем
$$
\begin{equation*}
\| U(s)(\xi)-U(s)(\eta)\|^2\leqslant 2R_1\bigl(\eta, U(s)(\eta)-U(s)(\xi)\bigr).
\end{equation*}
\notag
$$
Складывая два последних неравенства, находим
$$
\begin{equation}
\| U(s)(\xi)-U(s)(\eta)\|\leqslant R_1\| \xi-\eta\|.
\end{equation}
\tag{4.8}
$$
Определим аппроксимацию $\widetilde U$ множества $U$:
$$
\begin{equation*}
\partial\widetilde U=\Gamma_1\cup \Gamma_2\cup\Gamma,
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
\Gamma_1=\bigl\{ U(p)\mid p\in \mathcal M_1, \|p\|=1\bigr\}, \qquad \Gamma_2=\bigl\{ U(p)\mid p\in \mathcal M_2, \|p\|=1\bigr\}
\end{equation*}
\notag
$$
и $\Gamma$ – ломаная (имеющая, вообще говоря, две компоненты связности), аппроксимирующая $\partial U\setminus (\Gamma_1\cup \Gamma_2)$. Рассмотрим произвольное ребро $l=[(a_1,b_1),(a_2,b_2)]\subset \Gamma\subset \partial \widetilde U$, $b_1<b_2$. Положим
$$
\begin{equation*}
\ell_s=Q(s)l=[(a_1+sb_1,b_1),(a_2+sb_2,b_2)], \qquad \sigma=b_2-b_1>0.
\end{equation*}
\notag
$$
Угол между $\ell_s$ и осью $Ox$ не менее $\alpha_0=\arcsin \mu>0$, поэтому, как и в п. 1, ${\sigma}/{\ell_s}\geqslant\sin\alpha_0$. Пусть также $d=\| \ell_s\|$. Выберем $\theta$ так, что $\theta$ меньше раствора нормального конуса в любой вершине $Q(s)\Gamma$ при всех $s\in [0,t]$. Если в общих точках (точках стыка) $Q(s)\Gamma$ и $Q(s)\Gamma_i$ нормальный конус к $U(s)$ имеет пустую внутренность, то его не учитываем для определения $\theta$. Зафиксируем такие единичные векторы $p,q$, что угол между ними не более $\theta$, $C=\max\{ 1, e^{\lambda t}\}$, $M=\max_{s\in [0,t]}\| Q(s)\|$. Поясним следующую формулу:
$$
\begin{equation*}
\begin{aligned} \, &\| \widetilde M(t)(p)-\widetilde M(t)(q)\|\leqslant \int_{0}^{t}e^{\lambda t} \| \widetilde U(s)(p)-\widetilde U(s)(q)\|\, ds \\ &\qquad\leqslant 2\biggl( CtR_1\| p-q\|+\sum_i \frac{Cd_i^2}{\sigma_i\sin\alpha_0}\sin\theta\biggr)\leqslant 2\biggl( CtR_1+\sum_i \frac{CM}{\sin^2\alpha_0}\| l_i\|\biggr)\| p-q\| \\ &\qquad=2\biggl( CtR_1+\frac{CM}{\sin^2\alpha_0}L_{\widetilde U}\biggr)\| p-q\|. \end{aligned}
\end{equation*}
\notag
$$
Слагаемое $CtR_1\| p-q\|$ отвечает за случай $p,q\in\mathcal M_i$, $i=1$ или $i=2$. Сумма $\sum_i ({Cd_i^2}/({\sigma_i\sin\alpha_0}))\sin\theta$ в обозначениях п. 1 отвечает за ситуацию, когда $\widetilde U(s)(p)$ и $\widetilde U(s)(q)$ содержатся на ломаной $Q(s)\Gamma$. Коэффициент 2 появляется при оценке интеграла, когда $p\in \mathcal M_i$, $i=1$ или $i=2$, а $\widetilde U(s)(q)\in Q(s)\Gamma$. Итак,
$$
\begin{equation*}
R_{\widetilde M(t)}=2\biggl( CtR_1+\frac{CM}{\sin^2\alpha_0}L_{\widetilde U}\biggr).
\end{equation*}
\notag
$$
Переходя к пределу $\widetilde U\to U$, получаем
$$
\begin{equation*}
R_{M(t)}=2\biggl( CtR_1+ \frac{CM}{\sin^2\alpha_0}L_{U}\biggr)=2\biggl( CtR_1+\frac{CM}{\mu^2}L_{U}\biggr).
\end{equation*}
\notag
$$
Теорема 2 доказана. Аналогично доказательству теоремы 2 можно доказать следующую теорему. Теорема 3. Пусть в системе (2.2) $n=2$, собственные числа матрицы $A$ вещественны и различны. Предположим, что $\exists\, R_0>0$ $\exists\, \gamma>0$ $\exists\, \delta>0$ такие, что для любого из векторов $v=\pm e_1$ или $v=\pm e_2$ выполняется условие Тогда множество $M(t)$ сильно выпуклое для любого $t>0$. § 5. Множества достижимости в размерности больше 2. Оболочка прямой суммыДоказательство результатов о сильной выпуклости множества достижимости системы (2.2) для случая $n\geqslant 3$ сопряжено со значительными техническими трудностями. Например, для системы с матрицей
$$
\begin{equation*}
A=\begin{pmatrix} -1 & 1 & 0 \\ 0 & -1 & 1 \\ 0 & 0 & -1\end{pmatrix}
\end{equation*}
\notag
$$
и $U=\operatorname{co}\{\pm e_3\}$ оценка радиуса сильной выпуклости множества достижимости $M(t)$ весьма трудоемка (в численном эксперименте для $t=1$ получен радиус $R> 100$). Поэтому мы рассмотрим случаи системы (2.2), когда задача анализа множества достижимости упрощается. Рассмотрим матрицу
$$
\begin{equation}
A=\begin{pmatrix} A_1 & 0 \\ 0 & A_2 \end{pmatrix}\in\mathbb R^{n\times n},
\end{equation}
\tag{5.1}
$$
где $A_1\in\mathbb R^{m\times m}$, $A_2\in \mathbb R^{(n-m)\times (n-m)}$. Обозначим $E_1=\mathbb R^m$, $E_2=\mathbb R^{n-m}$, $\mathbb R^n=E_1\,{\oplus}\, E_2$. Заметим, что $E_1$ и $E_2$ – ортогональные подпространства. Пусть в системе (2.2) множество $U$ имеет вид т.е. $U$ является прямой суммой подмножеств из $E_i$. Тогда
$$
\begin{equation}
\begin{gathered} \, \notag e^{As}=\begin{pmatrix} e^{A_1s} & 0 \\ 0 & e^{A_2s} \end{pmatrix}, \\ \begin{split} M(t) &=\int_{0}^{t}e^{As}U\, ds=\int_{0}^{t} \begin{pmatrix} e^{A_1s} & 0 \\ 0 & e^{A_2s} \end{pmatrix} (U_1\oplus U_2)\, ds=\int_{0}^{t} (e^{A_1s}U_1)\oplus (e^{A_2s}U_2)\, ds \\ &=\biggl(\int_{0}^{t} e^{A_1s}U_1\, ds\biggr) \oplus \biggl(\int_{0}^{t} e^{A_2s}U_2\, ds\biggr). \end{split} \end{gathered}
\end{equation}
\tag{5.2}
$$
Определение. Пусть $\mathbb R^n=E_1\oplus E_2$ ($E_1=\mathbb R^m$, $E_2=\mathbb R^{n-m}$), $M\subset \mathbb R^n$. Обозначим через $P_{E_i}$ ортогональный проектор на $E_i$. Тогда оболочкой прямой суммы множества $M$ относительно подпространств $E_1$ и $E_2$ называется множество Для множества $M=B_1(0)\subset \mathbb R^4$ и подпространств $E_1=Ox_1x_2x_3$, $E_2=Ox_4$
$$
\begin{equation*}
\Sigma (B_1(0))=\{ x\in\mathbb R^4\mid x_1^2+x_2^2+x_3^2\leqslant 1,\, x_4\in [-1,1]\}.
\end{equation*}
\notag
$$
Для того же множества $M$ и подпространств $E_1=Ox_1x_2$, $E_2=Ox_3x_4$
$$
\begin{equation*}
\Sigma (B_1(0))=\{ x\in\mathbb R^4\mid x_1^2+x_2^2\leqslant 1,\, x_3^2+x_4^2\leqslant 1\}.
\end{equation*}
\notag
$$
Если множество $U$ в системе (2.2) является оболочкой прямой суммы, а матрица $A$ имеет вид (5.1), то $M(t)$ состоит из прямой суммы слагаемых меньшей размерности, сильная выпуклость которых может быть доказана в случае $m=1$, $m=2$, а также в некоторых других случаях индуктивно. Ряд теоретико-множественных операций с множеством достижимости вида (5.2) не меняется от того, участвует в них некоторое множество или его оболочка прямой суммы. Ниже рассмотрим один пример. Лемма 5. Пусть множество достижимости для системы (2.2) с матрицей $A$ (5.1) имеет вид (5.2), $U=U_1\oplus U_2$, $U_i\subset E_i$, $i=1,2$. Пусть $M_0\subset\mathbb R^n$ – компакт. Тогда где $\Sigma (M_0)$ – оболочка прямой суммы множества $M_0$ относительно подпространств $E_1$ и $E_2$. Доказательство. Обозначим
Так как $M_0\,{\subset}\,\Sigma (M_0)$, то $M(t)\frac{\, *\,}{}\, M_0 \supset M(t)\frac{\, *\,}{}\, \Sigma (M_0)$. Поэтому если $M(t)\frac{\, *\,}{}\, M_0$ пусто, то пусто и множество $M(t)\frac{\, *\,}{}\, \Sigma (M_0)$. Пусть $x\,{\in}\, M(t)\frac{\, *\,}{}\, M_0$, т.е. $x\,{+}\,M_0\,{\subset}\, M(t)$. Из последнего включения получаем
$$
\begin{equation*}
P_{E_i}x+P_{E_i}M_0\subset P_{E_i}M(t)=M_i(t), \qquad i=1,2.
\end{equation*}
\notag
$$
Складывая включения, находим
$$
\begin{equation*}
\begin{gathered} \, P_{E_1}x\oplus P_{E_2}x+P_{E_1}M_0\oplus P_{E_2}M_0\subset M_1(t)\oplus M_2(t)=M(t), \\ x+P_{E_1}M_0\oplus P_{E_2}M_0=x+\Sigma (M_0)\subset M(t), \qquad x\in M(t)\tfrac{\, *\,}{}\, \Sigma (M_0). \end{gathered}
\end{equation*}
\notag
$$
Лемма доказана. § 6. ПриложенияВажное преимущество сильной выпуклости $M(t)$ для приложений – возможность многогранной аппроксимации $M(t)$ с квадратичной по мелкости сетки точностью (этому посвящен п. 6.1; пп. 6.2, 6.3 идейно также опираются на это свойство). В примере 2 будет показано, как свойство сильной выпуклости множества достижимости работает при решении некоторых задач без аппроксимации множеств многогранниками. На основе свойства сильной выпуклости множества достижимости и некоторых других свойств доказывается линейная скорость сходимости метода проекции градиента для решения задачи минимизации опорной функции некоторого множества на единичной сфере. Это позволяет выяснить пустоту/непустоту пересечения $M(t)\cap M$, где $M$ – некоторый выпуклый компакт. 6.1. Второй порядок погрешности многогранной аппроксимацииИзвестно (см. [12], [15]), что погрешность многогранной аппроксимации сильно выпуклого с радиусом $R$ множества имеет второй порядок по мелкости сетки единичных векторов. Пусть $\mathbb G$ – сетка единичных векторов мелкости $\Delta\in (0,1/2)$ (см. [15; определение 2.6.1], [12; определение 1]). Рассмотрим для множества достижимости $M(t)$ его внешнюю многогранную аппроксимацию, т.е. множество
$$
\begin{equation*}
\widehat M(t)=\bigl\{ x\in\mathbb R^n\mid (p,x)\leqslant s(p,M(t))\ \forall\, p\in\mathbb G\bigr\}.
\end{equation*}
\notag
$$
Тогда для случая сильной выпуклости $M(t)$ в $\mathbb R^n$ с радиусом $R$ имеет место оценка (см. [12], [15])
$$
\begin{equation*}
h(M(t), \widehat M(t))\leqslant R\frac{\Delta^2}{1-\Delta^2/2}.
\end{equation*}
\notag
$$
Рассмотрим ситуацию в пространстве $\mathbb R^n$, $n\geqslant 3$. Пусть множество $M(t)$ является прямой суммой $M_1(t)\oplus M_2(t)$, как в формуле (5.2). Если $M_i(t)$ сильно выпуклое с радиусом $R_i>0$, $i=1,2$, то легко предъявить многогранную аппроксимацию $M(t)$ второго порядка по параметру мелкости $\Delta$. Отметим, что прямая сумма сильно выпуклых множеств не является сильно выпуклым множеством. Для построения аппроксимации рассмотрим сетки $\mathbb G_i\subset E_i$ единичных векторов мелкости $\Delta$ в пространствах $E_i$, $i=1,2$, $E_1\oplus E_2=\mathbb R^n$. Пусть
$$
\begin{equation*}
\widehat M_i(t)=\{ x\in E_i\mid (p,x)\leqslant s(p,M_i(t))\ \forall\, p\in\mathbb G_i\},
\end{equation*}
\notag
$$
и пусть $\widehat M(t)=\widehat M_1(t)\oplus \widehat M_2(t)$. Предложение. Пусть $\varepsilon=\varepsilon (\Delta)=\frac{\Delta^2}{1-\Delta^2/2}$ и множества $M_i(t)$ сильно выпуклы с $R_i>0$, $i=1,2$. В описанных выше предположениях Доказательство. Пусть $x\in \widehat M(t)$, т.е. $x=x_1\oplus x_2$, $x_i\in \widehat M_i(t)$, $i=1,2$. В силу [12; замечание 1] Последнее означает, что найдется точка $a_i\in M_i(t)$ такая, что $\| x_i-a_i\|\leqslant R_i\varepsilon$. Поскольку $x_i-a_i\in E_i$, $i=1,2$, то векторы $x_1-a_1$ и $x_2-a_2$ ортогональны и по теореме Пифагора Предложение доказано. Заметим, что несомненным преимуществом рассмотрения множества $M(t)$ в виде прямой суммы подмножеств является тот факт, что суммарное количество векторов сеток $\mathbb G_1\subset E_1=\mathbb R^m$ и $\mathbb G_2\subset E_2=\mathbb R^{n-m}$ мелкости $\Delta$ существенно меньше, чем число векторов сетки той же мелкости $\Delta$ в $\mathbb R^n$. 6.2. Приложение к линейным дифференциальным играмРассмотрим линейную дифференциальную игру в следующей постановке: найти начальное условие $x(0)$, откуда можно перевести за время $T$ фазовый вектор $x$ на терминальное множество $M$, т.е. $x(T)\in M\subset\mathbb R^n$ при условии
$$
\begin{equation*}
x'=Ax+u+v, \qquad t\in [0,T], \quad u\in U, \quad v\in V, \quad A\in \mathbb R^{n\times n},
\end{equation*}
\notag
$$
$M$, $U$, $V$ – выпуклые компакты. В ряде алгоритмов приходится вычислять альтернированный интеграл Понтрягина (см. [7]) и его приближение альтернированными суммами. Заменой $z(t)=e^{A(T-t)}x(t)$ приводим задачу к виду
$$
\begin{equation*}
z'=e^{A(T-t)}u+e^{A(T-t)}v, \qquad u\in U, \quad v\in V, \quad z(T)\in M.
\end{equation*}
\notag
$$
Напомним (см. [11; формула (12)]), что вычисляется цепочка множеств
$$
\begin{equation*}
M_0=M, \qquad M_{k+1}=(M_k\tfrac{\, *\,}{}\, \mathcal V_k)+(-\mathcal U_k), \quad k=1,\dots,K
\end{equation*}
\notag
$$
(игра преследования), где
$$
\begin{equation*}
\mathcal U_k=\int_{t_k}^{t_{k+1}} e^{A(T-t)}U\, dt, \qquad \mathcal V_k=\int_{t_k}^{t_{k+1}} e^{A(T-t)}V\, dt,
\end{equation*}
\notag
$$
$0=t_0<t_1<\dots<t_K=T$ – разбиение отрезка $[0,T]$. (За деталями алгоритма и определением стратегий игроков – функций $u$ и $v$ – мы отсылаем читателя к работам [7], [11], [8].) В результате строится множество начальных состояний $M_K$, из которого возможно гарантированное попадание в терминальное множество $M$ первым игроком (с управлением $u$) при произвольных действиях второго игрока (с управлением $v$). В работе [11] доказана квадратичная сходимость по пространству (по мелкости сетки, на которой аппроксимируются множества) альтернированных сумм Понтрягина. При этом существенной является сильная выпуклость множеств $M$ и $U$, так как она гарантирует сильную выпуклость всех множеств $M_k$ и тем самым квадратичную аппроксимацию. В ряде задач возможен отказ от сильной выпуклости $U$ и требование сильной выпуклости интегралов, задающих $\mathcal U_k$. Например, в силу следствия (см. § 4) эта сильная выпуклость имеет место в $\mathbb R^2$ для любого компакта $U$ при условии, что корни характеристического полинома матрицы $A$ комплексно сопряженные и $\operatorname{Im}\sigma (A)\ne 0$. 6.3. Некоторые оптимизационные задачиРассмотрим следующую задачу: для системы (2.2) и выпуклого компакта $M_0\subset \mathbb R^n$ решить задачу
$$
\begin{equation}
t\to\min_{t\geqslant 0}, \qquad\exists\, x\in\mathbb R^n \quad x+M(t)\supset M_0.
\end{equation}
\tag{6.1}
$$
Тем самым мы ищем (если существует) начальное условие $x_0=e^{-At} x$ и время $t$ такие, что, запуская систему (2.2) с начальным условием $x(0)=x_0$, мы за время $t$ можем попасть в любую точку $M_0$, причем это время минимально. Задача (6.1) близка по смыслу к задаче поиска чебышёвского центра выпуклого компакта $M_0\subset\mathbb R^n$, т.е. решения задачи
$$
\begin{equation*}
R\to\min, \qquad \exists\, x\in\mathbb R^n \quad x+B_R(0)\supset M_0.
\end{equation*}
\notag
$$
В евклидовом пространстве решение $(x,R)\in\mathbb R^n\times \mathbb R$ существует и единственно. В общем случае задача поиска чебышёвского центра является NP-сложной задачей. Известные алгоритмы для поиска чебышёвского центра и его обобщений не дают разумных оценок между точным и приближенным решениями по точке для выпуклых компактов $M_0$ произвольного вида. В работе автора [22] был предложен алгоритм поиска чебышёвского центра в пространстве небольшой размерности и получена оценка погрешности алгоритма. При этом для полученных результатов существенна как сильная выпуклость шара $B_R(0)$, так и сильная выпуклость множества, входящего в задачу. Аналогичные методы можно применять и к задачам типа (6.1) при условии сильной выпуклости множества $M(t)$. Приведем пример, когда сильная выпуклость множества достижимости гарантирует решение некоторой оптимизационной задачи. Пример 2. Пусть в $\mathbb R^n$ в системе (2.2) множества $M(t)$ сильно выпуклы с радиусом $r>0$ при $t\in [0,T]$, $M\subset\mathbb R^n$ – сильно выпуклый компакт с радиусом $r_M$, $0\notin M$. Пусть существует такое число $R_0>0$, что $M=X+B_{2R_0}(0)$, где $X$ – выпуклый компакт, для которого известны $s(p,X)$ и $X(p)$ для всех $\| p\|=1$. Пусть также $0\in U$. Последнее означает, что множества достижимости монотонно растут по включению: при $0\leqslant t_1<t_2$ имеем $M(t_1)\subset M(t_2)$. Допустим, что $M(T)\cap M\ne \varnothing$. Для момента времени $t\in (0,T)$ требуется выяснить, верно ли $M(t)\cap M\ne\varnothing$? Положим
$$
\begin{equation*}
R=r+r_M, \qquad M_0=M\tfrac{\, *\,}{}\, B_{R_0}(0)=X+B_{R_0}(0),\qquad Z(t)=M(t)+(-M_0).
\end{equation*}
\notag
$$
Задачу можно переформулировать так: для момента времени $t\in (0,T)$ найти расстояние от $0$ до $Z(t)$ и сравнить с $R_0$. На языке опорных функций для функции $f(p)=s(p,Z(t))=s(p,M(t))+s(p,-M_0)$ надо найти решение задачи Функция $f$ зависит также от $t$, но эту зависимость мы будем опускать. Решение задачи, при условии $0\notin Z(t)$, очевидно, достигается на векторе $p_0=-P_{Z(t)}0/\| P_{Z(t)}0\|$. В силу определения функции $f$, если $J<-R_0$, то пересечение $M(t)\cap M$ пусто. Если $J\geqslant -R_0$, то $M(t)\cap M\ne\varnothing$.Таким образом, возникает задача минимизации опорной функции $f(p)$ на единичной сфере. Покажем, что эта задача может быть решена градиентным методом при $J< 0$ при подходящем выборе начальной точки итераций. Заметим, что множество $Z(t)$ сильно выпуклое с радиусом $R$ для всех $t\in [0,T]$ и для функции $f$ имеем для любого ненулевого вектора $p$ равенство $f'(p)=Z(t)(p)$. Из определения $Z(t)$ вытекает, что $Z(t)\frac{\, *\,}{}\, B_{R_0}(0)+B_{R_0}(0)=Z(t)$, и поэтому для любых единичных векторов $p$, $q$ выполнена оценка $\| Z(t)(p)-Z(t)(q)\|\geqslant R_0\| p-q\|$ (см. [23; определение 3.2, теорема 3.6]). Из сильной выпуклости $Z(t)$ с радиусом $R$ следует другая оценка: Для доказательства нужно умножить обе части неравенства на $\sqrt{\| u\|\,\| v\|}$ и возвести в квадрат. Обозначим $S=\{ p\in\mathbb R^n\mid \| p\|=1\}$. Пусть $p_0\in S$ – решение задачи, т.е. $f(p_0)=J < 0$. Имеем $|J|=|f(p_0)|>0$. Также заметим, что из необходимого условия экстремума получаем $|J|=|(p_0,f'(p_0))|=\| f'(p_0)\|$. Выберем единичный вектор $p_1$: $\|p_1-p_0\|\leqslant{R_0^2}/{R^2}$. Фиксируем положительное число $\lambda$, удовлетворяющее условию
$$
\begin{equation*}
\lambda\leqslant \min\biggl\{ \frac{R_0^2/R}{R^2+L|J|},\frac1L\biggr\}, \quad\text{где }\ L\geqslant h(\{0\},Z(T))+1.
\end{equation*}
\notag
$$
Точно вычислить минимум в определении $\lambda$ мы не можем (о числе $J$ мы знаем лишь, что $J< 0$), но легко получить оценку на $\lambda$ через оценку $|J|$ сверху. Самая грубая оценка – это $|J|\leqslant L$. Рассмотрим итерационный процесс $p_{k+1}=P_S(p_k-\lambda f'(p_k))$. Пусть вектор $p_k\,{\in}\, S$ построен и $\| p_k\,{-}\,p_0\|\,{\leqslant}\, R_0^2/R^2$. Положим $L_k=\| f'(p_k)\|=\| Z(t)(p_k)\|$. Заметим, что
$$
\begin{equation*}
L_k\leqslant h(\{0\},Z(T))\leqslant L-1, \qquad 1-\lambda L_k>1-\lambda L \geqslant 0.
\end{equation*}
\notag
$$
С учетом леммы 6 и соотношений
$$
\begin{equation*}
\| p_0-\lambda f'(p_0)\|=\|p_0\|+\lambda \| f'(p_0)\|=1+\lambda |J|, \qquad \| p_k-\lambda f'(p_k)\|\geqslant 1-\lambda L_k
\end{equation*}
\notag
$$
получаем следующую оценку:
$$
\begin{equation*}
\begin{aligned} \, &\| p_{k+1}-p_0\|^2=\| P_S(p_k-\lambda f'(p_k))-P_S(p_0-\lambda f'(p_0))\|^2 \\ &\quad \stackrel{\text{лемма 6}}{\leqslant} \frac{1}{(1-\lambda L_k)(1+\lambda |J|)} \| p_k-\lambda f'(p_k)-(p_0-\lambda f'(p_0))\|^2 \\ &\qquad=\frac{\| p_k-p_0\|^2-2\lambda (p_k-p_0,f'(p_k)-f'(p_0))+\lambda^2\| f'(p_k)-f'(p_0)\|^2}{(1-\lambda L_k)(1+\lambda |J|)}. \end{aligned}
\end{equation*}
\notag
$$
Из неравенств
$$
\begin{equation*}
(p_k-p_0,f'(p_k)-f'(p_0))\geqslant \frac1R \| f'(p_k)-f'(p_0)\|^2
\end{equation*}
\notag
$$
(см. [15; доказательство теоремы 4.3.2]),
$$
\begin{equation*}
\begin{gathered} \, \| f'(p_k)-f'(p_0)\|=\| Z(t)(p_k)-Z(t)(p_0)\|\geqslant R_0\| p_k-p_0\|, \\ \| f'(p_k)-f'(p_0)\|\leqslant R\| p_k-p_0\| \end{gathered}
\end{equation*}
\notag
$$
имеем
$$
\begin{equation*}
\| p_{k+1}-p_0\|^2\leqslant \| p_k-p_0\|^2\frac{1-2\lambda R_0^2/R+\lambda^2R^2}{(1-\lambda L_k)(1+\lambda |J|)}.
\end{equation*}
\notag
$$
При выбранном $\lambda$
$$
\begin{equation*}
q(\lambda)=\frac{1-2\lambda R_0^2/R+\lambda^2R^2}{(1-\lambda L_k)(1+\lambda |J|)}\in (0,\gamma) \quad\text{для некоторого }\ \gamma<1.
\end{equation*}
\notag
$$
Покажем это. В силу оценки
$$
\begin{equation*}
\begin{aligned} \, L_k-|J| &=\|f'(p_k)\|-\| f'(p_0)\|\leqslant \| f'(p_k) - f'(p_0)\|=\|Z(t)(p_k)-Z(t)(p_0) \| \\ &\leqslant R\|p_k-p_0\|\leqslant\frac{R_0^2}{R} \end{aligned}
\end{equation*}
\notag
$$
получаем
$$
\begin{equation*}
\begin{aligned} \, &1-\frac{2\lambda R_0^2}{R}+\lambda^2R^2 - (1-\lambda L_k)(1+\lambda |J|) \\ &\qquad=-\frac{2\lambda R_0}{R}+\lambda^2R^2+\lambda (L_k-|J|)+\lambda^2 L_k |J| \leqslant \lambda \biggl(-\frac{R_0^2}{R}+\lambda R^2+\lambda L_k |J| \biggr) \\ &\qquad \leqslant \lambda \biggl(-\frac{R_0^2}{R}+\frac{R_0^2}{R}\,\frac{R^2+|J| (L-1)}{R^2+|J|L} \biggr)=-\frac{R_0^2}{R}\,\frac{\lambda |J|}{R^2+|J|L}<0; \end{aligned}
\end{equation*}
\notag
$$
напомним, что $\sup_k L_k\leqslant L-1$. Мы имеем сходимость алгоритма с линейной скоростью:
$$
\begin{equation*}
\| p_{k+1}-p_0\|\leqslant q(\lambda )\| p_{k}-p_0\| \quad\text{для всех }\ k\geqslant 1.
\end{equation*}
\notag
$$
Если мы ищем минимальное $t>0$, при котором $M(t)\cap M\ne\varnothing$, то должны “ловить” значение $J=-R_0$. Заметим в заключение, что вычисление градиента $f'(p_k)$ в момент времени $t$ сводится к вычислению интеграла
$$
\begin{equation*}
\begin{gathered} \, f'(p_k)=Z(t)(p_k)=M(t)(p_k)+(-M_0)(p_k)=\int_{0}^{t}(e^{As}U)(p_k)\, ds+(-M_0)(p_k), \\ (-M_0)(p_k)=(-X)(p_k)-R_0p_k, \end{gathered}
\end{equation*}
\notag
$$
и не представляет серьезных технических проблем. БлагодарностиАвтор благодарен рецензентам за полезные замечания. 
Цитирование в формате AMSBIB
\RBibitem{Bal22} |
|
||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|