Аннотация:
Для линейной управляемой системы x′∈Ax+U, x(0)=0,
рассматривается множество достижимости на некотором отрезке времени.
Исследован ряд ситуаций, когда это множество достижимости является пересечением шаров фиксированного радиуса R (т.е. сильно выпукло с радиусом R), в ряде случаев получена оценка сверху для R. Оказывается, свойство быть сильно выпуклым в определенном смысле достаточно типично для указанного множества достижимости.
Полученный результат имеет ряд приложений: возможность построения внешней многогранной аппроксимации множеств достижимости с меньшей, чем в общем случае, погрешностью в метрике Хаусдорфа, приложения в линейных дифференциальных играх и некоторых оптимизационных задачах.
Библиография: 23 названия.
Изучению свойств множеств достижимости систем дифференциальных уравнений в Rn посвящена обширная литература (см. [1]–[4]). Особое место в ней занимают линейные системы. Один из основных вопросов о множестве достижимости – это его структура и в первую очередь ограниченность, замкнутость, выпуклость или какие-то другие геометро-топологические свойства (например, гладкость границы). Для линейной системы x′∈Ax+U(t), x(0)=0, U(t) – непрерывный по t компакт, выпуклость множества достижимости вытекает из свойств интеграла Аумана (см. [5]) и содержится в классических монографиях, например в [1; теорема 1, гл. 2, п. 2.2]. По сути указанные результаты о выпуклости интеграла Аумана и т.д. являются прямым следствием теоремы Ляпунова о векторной мере (см. [6]).
Свойства множеств достижимости используются для анализа динамических систем и в некоторых случаях для построения управления. Далеко идущие обобщения множества достижимости, например, альтернированный интеграл Понтрягина (см. [7]) и стабильный мост Красовского (см. [8]), являются важными техническими конструкциями для анализа и решения линейных дифференциальных игр с нулевой суммой. Во многих работах исследуется погрешность многогранной или какой-то иной (например, эллипсоидальной) аппроксимации множества достижимости (см. [9]–[11]), обычно в метрике Хаусдорфа. Поэтому актуальным является усиление свойства выпуклости множества, т.е. замена выпуклости на какой-то тип строгой выпуклости, которая, как известно (см. [12]), гарантирует в свою очередь уменьшение погрешности многогранной аппроксимации множества на сетке единичных векторов.
Одним из важнейших классов строго выпуклых множеств является класс сильно выпуклых множеств. Множество M⊂Rn является сильно выпуклым с радиусом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 показано, как полученные результаты могут быть применены в пространстве размерности n⩾3. В конце работы, в § 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 их суммой Минковского называется множество
Говорят, что множество P является слагаемым множестваR, если найдется такое множество Q, что P+Q=R. Пусть для множества P\subset\mathbb R^n и точки x\in\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 называется (возможно, пустое) множество
Обозначим через \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]) называется
где использованы стандартные обозначения: разбиение \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) – единичный вектор. Тогда
т.е. \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:
Отметим, что условие (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 не найдется, то
Так как субдифференциал выпуклой индикаторной функции \delta (x,C) полунепрерывен сверху, то для \varepsilon=l_0 с учетом одномерности нормального конуса N(C,x_p) имеем
Заметим, что единичный вектор 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 имеем
Если \| 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 выполнено равенство
\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} имеем
Результат леммы вытекает из [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). При этом
Для вектора \| p\|=1 опорным элементом множества Q(s)U_m является точка U_m(Q^\top(s)p) для всех s (кроме конечного числа), когда вектор p ортогонален одному из ребер многогранника U_m(Q^\top(s)p). Отсюда получаем
Положим \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) получаем
для всех единичных векторов p,q, угол между которыми менее \theta_m. В силу леммы 1 и с учетом леммы 2M_m(2\pi) сильно выпукло с R_m=(1+1/m)CL_m. Переходя к пределу по m\to\infty, получаем
Заметим, что для случая, рассмотренного в примере 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, то
В силу теоремы 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.
Будем без ограничения общности считать, что для любой точки (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.
Из определения \alpha_0 получаем {\sigma}/{d}\geqslant \sin \alpha_0 или {d}/{\sigma}\leqslant {1}/{\sin \alpha_0}. По теореме синусов из треугольника Ol_1l_2
последнее суммирование ведется по всем сторонам 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) получаем
и \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]
Найдем зависимость \xi=\xi (s,p). Пусть e – направляющий вектор опорной прямой \mathcal L с нормалью p\in\mathcal K, проходящей через точку U(p). Тогда образом опорной прямой \mathcal L будет прямая, проходящая через точку Q(s)U(p) с направляющим вектором Q(s)e. Легко видеть, что единичный нормальный вектор к этой прямой есть
Поскольку 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]
Поскольку \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)
Угол между \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)\|.
Слагаемое 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.
Аналогично доказательству теоремы 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 сопряжено со значительными техническими трудностями. Например, для системы с матрицей
и U=\operatorname{co}\{\pm e_3\} оценка радиуса сильной выпуклости множества достижимости M(t) весьма трудоемка (в численном эксперименте для t=1 получен радиус R> 100). Поэтому мы рассмотрим случаи системы (2.2), когда задача анализа множества достижимости упрощается.
где 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 имеет вид
Определение. Пусть \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 называется множество
Если множество 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 – компакт. Тогда
Так как 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). Из последнего включения получаем
Важное преимущество сильной выпуклости 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) его внешнюю многогранную аппроксимацию, т.е. множество
Рассмотрим ситуацию в пространстве \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. Пусть
и пусть \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. В описанных выше предположениях
Последнее означает, что найдется точка 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 при условии
В ряде алгоритмов приходится вычислять альтернированный интеграл Понтрягина (см. [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)]), что вычисляется цепочка множеств
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 решить задачу
Тем самым мы ищем (если существует) начальное условие x_0=e^{-At} x и время t такие, что, запуская систему (2.2) с начальным условием x(0)=x_0, мы за время t можем попасть в любую точку M_0, причем это время минимально.
Задача (6.1) близка по смыслу к задаче поиска чебышёвского центра выпуклого компакта M_0\subset\mathbb R^n, т.е. решения задачи
В евклидовом пространстве решение (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?
Функция 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, удовлетворяющее условию
Точно вычислить минимум в определении \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)\|. Заметим, что
Автор благодарен рецензентам за полезные замечания.
Список литературы
1.
Э. Б. Ли, Л. Маркус, Основы теории оптимального управления, Наука, М., 1972, 574 с. ; пер. с англ.: E. B. Lee, L. Markus, Foundations of optimal control theory, John Wiley & Sons, Inc., New York–London–Sydney, 1967, x+576 с.
2.
M. Blanke, M. Kinnaert, J. Lunze, M. Staroswiecki, Diagnosis and fault-tolerant control, Springer, Berlin, 2003, xvii+571 pp.
3.
A. Chutinan, B. H. Krogh, “Computational techniques for hybrid system verification”, IEEE Trans. Automat. Control, 48:1 (2003), 64–75
4.
A. B. Singer, P. I. Barton, “Global optimization with nonlinear ordinary differential equations”, J. Global Optim., 34:2 (2006), 159–190
5.
R. J. Aumann, “Integrals of set-valued functions”, J. Math. Anal. Appl., 12:1 (1965), 1–12
6.
А. А. Ляпунов, “О вполне аддитивных вектор-функциях”, Изв. АН СССР. Сер. матем., 4:6 (1940), 465–478
7.
Л. С. Понтрягин, “Линейные дифференциальные игры преследования”, Матем. сб., 112(154):3(7) (1980), 307–330; англ. пер.: L. S. Pontryagin, “Linear differential games of pursuit”, Sb. Math., 40:3 (1981), 285–303
8.
Н. Н. Красовский, Теория управления движением. Линейные системы, Наука, М., 1968, 475 с.
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
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
11.
Г. Е. Иванов, Е. С. Половинкин, “О сильно выпуклых линейных дифференциальных играх”, Дифференц. уравнения, 31:10 (1995), 1641–1648; англ. пер.: 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; англ. пер.: M. V. Balashov, “On polyhedral approximations in an n-dimensional space”, Comput. Math. Math. Phys., 56:10 (2016), 1679–1685
13.
J.-Ph. Vial, “Strong and weak convexity of sets and functions”, Math. Oper. Res., 8:2 (1983), 231–259
14.
Е. С. Половинкин, “Сильно выпуклый анализ”, Матем. сб., 187:2 (1996), 103–130; англ. пер.: E. S. Polovinkin, “Strongly convex analysis”, Sb. Math., 187:2 (1996), 259–286
15.
Е. С. Половинкин, М. В. Балашов, Элементы выпуклого и сильно выпуклого анализа, 2-е изд., Физматлит, М., 2007, 438 с.
16.
A. Weber, G. Reißig, “Local characterization of strongly convex sets”, J. Math. Anal. Appl., 400:2 (2013), 743–750
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
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
19.
M. V. Balashov, “Lipschitz stability of extremal problems with a strongly convex set”, J. Convex Anal., 27:1 (2020), 103–116
20.
Е. С. Половинкин, Многозначный анализ и дифференциальные включения, Физматлит, М., 2015, 524 с.
21.
Р. Рокафеллар, Выпуклый анализ, Мир, М., 1973, 472 с. ; пер. с англ.: R. T. Rockafellar, Convex analysis, Princeton Math. Ser., 28, Princeton Univ. Press, Princeton, NJ, 1970, xviii+451 с.
22.
M. V. Balashov, “Chebyshev center and inscribed balls: properties and calculations”, Optim. Lett., 2021, 1–14, Publ. online
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
Образец цитирования:
М. В. Балашов, “Сильная выпуклость множеств достижимости линейных систем”, Матем. сб., 213:5 (2022), 30–49; M. V. Balashov, “Strong convexity of reachable sets of linear systems”, Sb. Math., 213:5 (2022), 604–623
\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:
M. V. Balashov, K. Z. Biglov, A. A. Tremba, “On Some Problems with Multivalued Mappings”, ARC, 85:5 (2024), 491
М. В. Балашов, К. З. Биглов, А. А. Тремба, “О некоторых задачах с многозначными отображениями”, Автомат. и телемех., 2024, № 5, 58–85
M. V. Balashov, K. Z. Biglov, A. A. Tremba, “On Some Problems with Multivalued Mappings”, Autom Remote Control, 85:5 (2024), 422
М. В. Балашов, “Достаточные условия линейной сходимости одного алгоритма для нахождения метрической проекции точки на выпуклый компакт”, Матем. заметки, 113:5 (2023), 655–666; 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
М. В. Балашов, Р. А. Камалов, “Оптимизация множества достижимости линейной системы по отношению к другому множеству”, Ж. вычисл. матем. и матем. физ., 63:5 (2023), 739–759; 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