Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js
Математический сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Математический сборник, 2022, том 213, номер 5, страницы 30–49
DOI: https://doi.org/10.4213/sm9627
(Mi sm9627)
 

Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

Сильная выпуклость множеств достижимости линейных систем

М. В. Балашов

Институт проблем управления им. В. А. Трапезникова Российской академии наук, г. Москва
Список литературы:
Аннотация: Для линейной управляемой системы xAx+U, x(0)=0, рассматривается множество достижимости на некотором отрезке времени. Исследован ряд ситуаций, когда это множество достижимости является пересечением шаров фиксированного радиуса R (т.е. сильно выпукло с радиусом R), в ряде случаев получена оценка сверху для R. Оказывается, свойство быть сильно выпуклым в определенном смысле достаточно типично для указанного множества достижимости.
Полученный результат имеет ряд приложений: возможность построения внешней многогранной аппроксимации множеств достижимости с меньшей, чем в общем случае, погрешностью в метрике Хаусдорфа, приложения в линейных дифференциальных играх и некоторых оптимизационных задачах.
Библиография: 23 названия.
Ключевые слова: сильная выпуклость, множество достижимости, линейная управляемая система, интеграл Аумана, метрика Хаусдорфа, негладкий анализ.
Финансовая поддержка Номер гранта
Российский научный фонд 22-11-00042
Работа выполнена при финансовой поддержке Российского научного фонда (проект № 22-11-00042).
Поступила в редакцию: 18.06.2021 и 01.11.2021
Англоязычная версия:
Sbornik: Mathematics, 2022, Volume 213, Issue 5, Pages 604–623
DOI: https://doi.org/10.1070/SM9627
Реферативные базы данных:
Тип публикации: Статья
MSC: Primary 49J53, 52A20; Secondary 93C05, 90C26

§ 1. Введение

1.1.

Изучению свойств множеств достижимости систем дифференциальных уравнений в Rn посвящена обширная литература (см. [1]–[4]). Особое место в ней занимают линейные системы. Один из основных вопросов о множестве достижимости – это его структура и в первую очередь ограниченность, замкнутость, выпуклость или какие-то другие геометро-топологические свойства (например, гладкость границы). Для линейной системы xAx+U(t), x(0)=0, U(t) – непрерывный по t компакт, выпуклость множества достижимости вытекает из свойств интеграла Аумана (см. [5]) и содержится в классических монографиях, например в [1; теорема 1, гл. 2, п. 2.2]. По сути указанные результаты о выпуклости интеграла Аумана и т.д. являются прямым следствием теоремы Ляпунова о векторной мере (см. [6]).

Свойства множеств достижимости используются для анализа динамических систем и в некоторых случаях для построения управления. Далеко идущие обобщения множества достижимости, например, альтернированный интеграл Понтрягина (см. [7]) и стабильный мост Красовского (см. [8]), являются важными техническими конструкциями для анализа и решения линейных дифференциальных игр с нулевой суммой. Во многих работах исследуется погрешность многогранной или какой-то иной (например, эллипсоидальной) аппроксимации множества достижимости (см. [9]–[11]), обычно в метрике Хаусдорфа. Поэтому актуальным является усиление свойства выпуклости множества, т.е. замена выпуклости на какой-то тип строгой выпуклости, которая, как известно (см. [12]), гарантирует в свою очередь уменьшение погрешности многогранной аппроксимации множества на сетке единичных векторов.

Одним из важнейших классов строго выпуклых множеств является класс сильно выпуклых множеств. Множество MRn является сильно выпуклым с радиусом R, если оно представимо в виде пересечения замкнутых шаров радиуса R. Сильно выпуклые множества исследованы в работах [13]–[16].

В [17; теорема 4.2] показано, что для нелинейной динамической системы x=f(x), x(0)ΩRn, при определенных условиях (в частности, при условии сильной выпуклости множества начальных состояний Ω) множество достижимости сильно выпукло с некоторым радиусом. Отметим, что идея доказательства состоит в применении опорного принципа для сильно выпуклых множеств, который устанавливается локально по времени для множества достижимости, а не в линеаризации системы.

Автору известно крайне мало глобальных результатов о сильной выпуклости множества достижимости динамической системы или (что по сути – более общий вопрос) о сильной выпуклости интеграла Аумана для многозначного отображения достаточно общей природы.

В работе [18] доказано, что если непрерывное многозначное отображение F(t), t[0,T], имеет сильно выпуклые значения с радиусом R(t), то интеграл Аумана T0F(t)dt является сильно выпуклым множеством с радиусом R=T0R(t)dt.

Свойства сильной выпуклости множеств управления и терминального множества использовались в работе [11] для доказательства сильной выпуклости альтернированного интеграла Понтрягина и, как следствие, квадратичной скорости сходимости по пространству альтернированных сумм Понтрягина.

В работе [19] было отмечено, что если непрерывное многозначное отображение F(t), t[0,T], имеет компактные (не обязательно выпуклые) значения и множество T0F(t)dt сильно выпукло с радиусом R, то, как следует из линейности интеграла по t, для всякого t[0,T] интеграл Аумана t0F(s)ds также является сильно выпуклым множеством с радиусом R.

В настоящей работе мы хотим описать достаточные условия глобальной по времени сильной выпуклости множества достижимости линейной управляемой системы. В § 4 показано, что в пространстве размерности 2 для управляемой системы с произвольной матрицей A и широким выбором автономного множества управлений U(t)=U множество достижимости сильно выпукло. Основная техническая идея доказательства содержится в лемме 1 о том, что из некоторого локального условия для выпуклого компактного множества следует его сильная выпуклость. Указанная лемма имеет также самостоятельный интерес. В § 5 показано, как полученные результаты могут быть применены в пространстве размерности n3. В конце работы, в § 6, мы обсудим различные приложения полученных результатов.

1.2. Некоторые определения и обозначения

В вещественном евклидовом пространстве Rn размерности n обозначим через (x,y) скалярное произведение векторов x, y, . Положим 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+Q=\{ x+y\mid x\in P,\ y\in Q\}, \end{equation*} \notag
геометрической разностью или разностью Минковского–Понтрягина называется множество
\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
\begin{equation*} \varrho_P(x)=\inf_{p\in P}\| x-p\|. \end{equation*} \notag

Расстоянием по Хаусдорфу между компактными множествами 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 называется функция

\begin{equation*} s(p,Q)=\sup_{x\in Q}(p,x), \qquad p\in\mathbb R^n. \end{equation*} \notag

Для выпуклого замкнутого множества 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} имеем
\begin{equation*} J\int_{0}^{t}F(s)\, ds =\int_{0}^{t}JF(s)\, ds. \end{equation*} \notag

Пример 1. Разберем пример, заимствованный из [20; пример 34.2]. Для матрицы поворота

\begin{equation*} Q(s)=\begin{pmatrix} \cos s & -\sin s \\ \sin s & \cos s\end{pmatrix} \end{equation*} \notag
рассмотрим F(s)=Q(s)P, где P=\operatorname{co}\{ \pm e_1\}. Пусть p=(\cos\theta, \sin\theta) – единичный вектор. Тогда
\begin{equation} s\biggl(p, \int_{0}^{2\pi}F(s)\, ds\biggr) =\int_{0}^{2\pi} |{\cos(s-\theta)}|\, ds=4=s(p, B_4(0)), \end{equation} \tag{2.1}
т.е. \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))

\begin{equation} \exists\, l_0>0\quad\forall\, p,q\in \partial B_1(0) \quad \| p-q\|\leqslant l_0, \quad \| x_p-x_q\|\leqslant R\| p-q\|. \end{equation} \tag{3.1}
Тогда множество 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 имеет место равенство для субдифференциала
\begin{equation*} \partial f(x_0)=\operatorname{cl}\operatorname{co} \Bigl\{\lim_{i\to\infty} f'(x_i)\Bigm| x_i\to x_0,\ f'(x_i) - \text{градиент Фреше и }\exists\,\lim_{i\to\infty} f'(x_i) \Bigr\}, \end{equation*} \notag
откуда получаем 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

\begin{equation*} C\cap B_{1/k}(x_p)\not\subset B_R(x_p-Rp). \end{equation*} \notag
Так как субдифференциал выпуклой индикаторной функции \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, то

\begin{equation*} \| x_p-x_0\|>R\| p-q_0\|\geqslant R\| p-q\|, \end{equation*} \notag
что снова противоречит условию леммы.

Лемма доказана.

Лемма 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], т.е.
\begin{equation*} CU(s)=f(s)U(s)+(C-f(s))U(s), \end{equation*} \notag
имеем
\begin{equation*} \int_{0}^{t}CU(s)\, ds=\int_{0}^{t}f(s)U(s)\, ds+\int_{0}^{t}(C-f(s))U(s)\, ds, \end{equation*} \notag
откуда следует утверждение леммы.

Лемма 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 выполнено равенство

\begin{equation*} M(t)(p)-M(t)(q)=\int_{0}^{t} f(s)\bigl( U(s)(p)-U(s)(q)\bigr)\, ds. \end{equation*} \notag

Доказательство вытекает из свойств интеграла.

§ 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) и
\begin{equation*} M_m(t)=\int_{0}^{t}f(s)Q(s)U_m\, ds. \end{equation*} \notag

Зафиксируем 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) сильно выпуклое с
\begin{equation*} R\leqslant \sum_{k=0}^{\infty}R_k \leqslant\frac{1}{\beta} \frac{L_U}{1-e^{2\pi\alpha/\beta}}. \end{equation*} \notag

Следствие доказано.

Теорема 2. Пусть в системе (2.2) n=2, собственные числа матрицы A вещественные и равны: \lambda_{1,2}=\lambda\in\mathbb R. Предположим, что выполняется условие: \exists\, R_0>0 \exists\, \gamma>0 \exists\, \delta>0 такие, что

\begin{equation} \forall\, p\in B_{\delta}(\pm e_2)\cap \partial B_1(0) \qquad U\cap B_{\gamma}(U(\pm e_2))\subset B_{R_0}(U(p)-R_0p). \end{equation} \tag{4.3}
Тогда множество M(t) сильно выпуклое для любого t>0.

Условие (4.3) означает, что локально выполнен опорный принцип для сильно выпуклых множеств с одним R_0 для всех единичных векторов из окрестности \pm e_2.

Доказательство теоремы 2. Фиксируем t>0. Обозначим
\begin{equation*} Q(s)=\begin{pmatrix} 1 & s \\ 0 & 1\end{pmatrix}, \qquad U(s)=Q(s)U. \end{equation*} \notag
Будем без ограничения общности считать, что для любой точки (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)

\begin{equation*} \| U(s)(\xi)-U(s)(\eta)-R_1\xi\|\leqslant R_1 \end{equation*} \notag
получаем \| 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 выполняется условие

\begin{equation} \forall\, p\in B_{\delta}(v)\cap \partial B_1(0) \quad U\cap B_{\gamma}(U(v))\subset B_{R_0}(U(p)-R_0p). \end{equation} \tag{4.9}
Тогда множество 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 имеет вид
\begin{equation*} U=U_1\oplus U_2, \qquad U_i\subset E_i, \quad i=1,2, \end{equation*} \notag
т.е. 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 называется множество

\begin{equation*} \Sigma(M)=P_{E_1}M\oplus P_{E_2}M. \end{equation*} \notag

Для множества 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 – компакт. Тогда

\begin{equation*} M(t)\tfrac{\, *\,}{}\, M_0=M(t)\tfrac{\, *\,}{}\, \Sigma (M_0), \end{equation*} \notag
где \Sigma (M_0) – оболочка прямой суммы множества M_0 относительно подпространств E_1 и E_2.

Доказательство. Обозначим
\begin{equation*} M_i(t)=\int_{0}^{t} e^{A_is}U_i\, ds, \qquad i=1,2. \end{equation*} \notag

Так как 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. В описанных выше предположениях

\begin{equation*} h(M(t),\widehat M(t))\leqslant \varepsilon (\Delta)\sqrt{R_1^2+R_2^2}. \end{equation*} \notag

Доказательство. Пусть x\in \widehat M(t), т.е. x=x_1\oplus x_2, x_i\in \widehat M_i(t), i=1,2. В силу [12; замечание 1]
\begin{equation*} h(M_i(t),\widehat M_i(t))\leqslant R_i\varepsilon(\Delta), \qquad i=1,2. \end{equation*} \notag
Последнее означает, что найдется точка 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 ортогональны и по теореме Пифагора
\begin{equation*} \begin{aligned} \, \varrho^2_{M(t)}(x_1\oplus x_2) &\leqslant \|(x_1\oplus x_2) - (a_1\oplus a_2)\|^2 \\ &=\| x_1-a_1\|^2+\| x_2-a_2\|^2\leqslant\varepsilon^2(\Delta)(R_1^2+R_2^2). \end{aligned} \end{equation*} \notag

Предложение доказано.

Заметим, что несомненным преимуществом рассмотрения множества 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) надо найти решение задачи

\begin{equation*} \min_{\| p\|=1}f(p)=J. \end{equation*} \notag
Функция 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 следует другая оценка:

\begin{equation*} \| Z(t)(p)-Z(t)(q)\|\leqslant R\| p-q\|. \end{equation*} \notag

Лемма 6. Пусть u,v\in\mathbb R^n\setminus\{ 0\}. Тогда

\begin{equation*} \biggl\| \frac{u}{\| u\|}-\frac{v}{\| v\|}\biggr\|\leqslant \frac{1}{\sqrt{\| u\|\,\| v\|}}\| u-v\|. \end{equation*} \notag

Для доказательства нужно умножить обе части неравенства на \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
и не представляет серьезных технических проблем.

Благодарности

Автор благодарен рецензентам за полезные замечания.

Список литературы

1. Э. Б. Ли, Л. Маркус, Основы теории оптимального управления, Наука, М., 1972, 574 с.  mathscinet  zmath; пер. с англ.: E. B. Lee, L. Markus, Foundations of optimal control theory, John Wiley & Sons, Inc., New York–London–Sydney, 1967, x+576 с.  mathscinet  zmath
2. M. Blanke, M. Kinnaert, J. Lunze, M. Staroswiecki, Diagnosis and fault-tolerant control, Springer, Berlin, 2003, xvii+571 pp.  mathscinet  zmath
3. A. Chutinan, B. H. Krogh, “Computational techniques for hybrid system verification”, IEEE Trans. Automat. Control, 48:1 (2003), 64–75  crossref  mathscinet  zmath
4. A. B. Singer, P. I. Barton, “Global optimization with nonlinear ordinary differential equations”, J. Global Optim., 34:2 (2006), 159–190  crossref  mathscinet  zmath
5. R. J. Aumann, “Integrals of set-valued functions”, J. Math. Anal. Appl., 12:1 (1965), 1–12  crossref  mathscinet  zmath
6. А. А. Ляпунов, “О вполне аддитивных вектор-функциях”, Изв. АН СССР. Сер. матем., 4:6 (1940), 465–478  mathnet  mathscinet  zmath
7. Л. С. Понтрягин, “Линейные дифференциальные игры преследования”, Матем. сб., 112(154):3(7) (1980), 307–330  mathnet  mathscinet  zmath; англ. пер.: L. S. Pontryagin, “Linear differential games of pursuit”, Sb. Math., 40:3 (1981), 285–303  crossref
8. Н. Н. Красовский, Теория управления движением. Линейные системы, Наука, М., 1968, 475 с.  mathscinet  zmath
9. A. B. Kurzhanski, P. Varaiya, “On verification of controlled hybrid dynamics through ellipsoidal techniques”, Proceedings of the 44th IEEE conference on decision and control (Seville, 2005), IEEE, 2005, 4682–4687  crossref
10. Inseok Hwang, D. M. Stipanović, C. J. Tomlin, “Polytopic approximations of reachable sets applied to linear dynamic games and a class of nonlinear systems”, Advances in control, communication networks, and transportation systems, Systems Control Found. Appl., Birkhäuser Boston, Boston, MA, 2005, 3–19  crossref  mathscinet  zmath
11. Г. Е. Иванов, Е. С. Половинкин, “О сильно выпуклых линейных дифференциальных играх”, Дифференц. уравнения, 31:10 (1995), 1641–1648  mathnet  mathscinet  zmath; англ. пер.: G. E. Ivanov, E. S. Polovinkin, “On strongly convex differential games”, Differ. Equ., 31:10 (1995), 1603–1612
12. М. В. Балашов, “О многогранных аппроксимациях в n-мерном пространстве”, Ж. вычисл. матем. и матем. физ., 56:10 (2016), 1695–1701  mathnet  crossref  zmath; англ. пер.: M. V. Balashov, “On polyhedral approximations in an n-dimensional space”, Comput. Math. Math. Phys., 56:10 (2016), 1679–1685  crossref  mathscinet
13. J.-Ph. Vial, “Strong and weak convexity of sets and functions”, Math. Oper. Res., 8:2 (1983), 231–259  crossref  mathscinet  zmath
14. Е. С. Половинкин, “Сильно выпуклый анализ”, Матем. сб., 187:2 (1996), 103–130  mathnet  crossref  mathscinet  zmath; англ. пер.: E. S. Polovinkin, “Strongly convex analysis”, Sb. Math., 187:2 (1996), 259–286  crossref
15. Е. С. Половинкин, М. В. Балашов, Элементы выпуклого и сильно выпуклого анализа, 2-е изд., Физматлит, М., 2007, 438 с.  zmath
16. A. Weber, G. Reißig, “Local characterization of strongly convex sets”, J. Math. Anal. Appl., 400:2 (2013), 743–750  crossref  mathscinet  zmath
17. A. Weber, G. Reissig, “Classical and strong convexity of sublevel sets and application to attainable sets of nonlinear systems”, SIAM J. Control Optim., 52:5 (2014), 2857–2876  crossref  mathscinet  zmath
18. H. Frankowska, C. Olech, “R-convexity of the integral of set-valued functions”, Contributions to analysis and geometry (Baltimore, MD, 1980), Johns Hopkins Univ. Press, Baltimore, MD, 1981, 117–129  mathscinet  zmath
19. M. V. Balashov, “Lipschitz stability of extremal problems with a strongly convex set”, J. Convex Anal., 27:1 (2020), 103–116  mathscinet  zmath
20. Е. С. Половинкин, Многозначный анализ и дифференциальные включения, Физматлит, М., 2015, 524 с.
21. Р. Рокафеллар, Выпуклый анализ, Мир, М., 1973, 472 с.  zmath; пер. с англ.: R. T. Rockafellar, Convex analysis, Princeton Math. Ser., 28, Princeton Univ. Press, Princeton, NJ, 1970, xviii+451 с.  mathscinet  zmath
22. M. V. Balashov, “Chebyshev center and inscribed balls: properties and calculations”, Optim. Lett., 2021, 1–14, Publ. online  crossref
23. V. V. Goncharov, G. E. Ivanov, “Strong and weak convexity of closed sets in a Hilbert space”, Operations research, engineering, and cyber security, Springer Optim. Appl., 113, Springer, Cham, 2017, 259–297  crossref  mathscinet  zmath

Образец цитирования: М. В. Балашов, “Сильная выпуклость множеств достижимости линейных систем”, Матем. сб., 213:5 (2022), 30–49; M. V. Balashov, “Strong convexity of reachable sets of linear systems”, Sb. Math., 213:5 (2022), 604–623
Цитирование в формате AMSBIB
\RBibitem{Bal22}
\by М.~В.~Балашов
\paper Сильная выпуклость множеств достижимости линейных систем
\jour Матем. сб.
\yr 2022
\vol 213
\issue 5
\pages 30--49
\mathnet{http://mi.mathnet.ru/sm9627}
\crossref{https://doi.org/10.4213/sm9627}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4461445}
\zmath{https://zbmath.org/?q=an:1520.93034}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2022SbMat.213..604B}
\transl
\by M.~V.~Balashov
\paper Strong convexity of reachable sets of linear systems
\jour Sb. Math.
\yr 2022
\vol 213
\issue 5
\pages 604--623
\crossref{https://doi.org/10.1070/SM9627}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000992262800002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85162688542}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/sm9627
  • https://doi.org/10.4213/sm9627
  • https://www.mathnet.ru/rus/sm/v213/i5/p30
  • Эта публикация цитируется в следующих 5 статьяx:
    1. M. V. Balashov, K. Z. Biglov, A. A. Tremba, “On Some Problems with Multivalued Mappings”, ARC, 85:5 (2024), 491  crossref
    2. М. В. Балашов, К. З. Биглов, А. А. Тремба, “О некоторых задачах с многозначными отображениями”, Автомат. и телемех., 2024, № 5, 58–85  mathnet  crossref
    3. M. V. Balashov, K. Z. Biglov, A. A. Tremba, “On Some Problems with Multivalued Mappings”, Autom Remote Control, 85:5 (2024), 422  crossref
    4. М. В. Балашов, “Достаточные условия линейной сходимости одного алгоритма для нахождения метрической проекции точки на выпуклый компакт”, Матем. заметки, 113:5 (2023), 655–666  mathnet  crossref  mathscinet; M. V. Balashov, “Sufficient Conditions for the Linear Convergence of an Algorithm for Finding the Metric Projection of a Point onto a Convex Compact Set”, Math. Notes, 113:5 (2023), 632–641  crossref
    5. М. В. Балашов, Р. А. Камалов, “Оптимизация множества достижимости линейной системы по отношению к другому множеству”, Ж. вычисл. матем. и матем. физ., 63:5 (2023), 739–759  mathnet  crossref  zmath; M. V. Balashov, R. A. Kamalov, “Optimization of the reachable set of a linear system with respect to another set”, Comput. Math. Math. Phys., 63:5 (2023), 751–770  mathnet  crossref  mathscinet  zmath
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математический сборник Sbornik: Mathematics
    Статистика просмотров:
    Страница аннотации:607
    PDF русской версии:82
    PDF английской версии:76
    HTML русской версии:217
    HTML английской версии:179
    Список литературы:56
    Первая страница:15
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025