1. Исходная постановка. Дискретизация

Рассмотрим линейную управляемую систему

$$\dot x(t)=A(t)x(t)+B(t)u(t)+C(t)v(t)+f(t);$$ (1.1)

здесь $t$ - время, меняющееся на ограниченном отрезке $[t_0,\vartheta]$, $x(t)$ - $n$-мерный вектор-столбец, характеризующий состояние в момент $t$, $u(t)$ и $v(t)$ - управляющие воздействия первого и второго игроков в момент $t$ размерности $n_1$ и $n_2$ соответственно. Значения $u(t)$ и $v(t)$ принадлежат выпуклым компактам $P\subset {R}^{n_1}$ и $Q\subset {R}^{n_2}$ соответственно. Матрицы-функции $t\longmapsto A(t)$, $t\longmapsto B(t)$, $t\longmapsto C(t)$ размерностей $n\times n$, $n_1\times n$, $n_2\times n$ и вектор-функция $t\longmapsto f(t)$ размерности $n$ определены и непрерывны на $[t_0,\vartheta]$. Зафиксированы начальное состояние $x^0\in {R}^n$ и выпуклый компакт $M\subset {R}^n$. Пространство ${R}^n$ ($n$-мерных векторов-столбцов) снабжено евклидовой нормой. Рассматривается позиционная дифференциальная игра с начальной позицией $(t_0,x^0)$, фиксированным моментом окончания $\vartheta$ и платой $x\longmapsto \sigma(x)=\mathop{\rm dist}\nolimits (x,M)$; последний символ означает расстояние от точки $x$ до множества $M$ в ${R}^n$. Формализация игры следует работе [1]. Далее, пусть $\gamma^0$ - цена игры. Стратегию первого игрока, решающую из позиции $(t_0,x^0)$ задачу наведения системы (1.1) на $\gamma$-окрестность $M^{\gamma}$ ($\gamma>0$) в момент $\vartheta$ (см. [1, 4]), будем кратко называть $\gamma$-наводящей.

Введем дискретные аналоги квазистратегий первого игрока (см. [4]). Пусть $\Delta=(\tau_i)_{i=0}^m$ - разбиение отрезка $[t_0,\vartheta]$ ( $t_0=\tau_0<\tau_1<\cdots<\tau_m=\vartheta$) и $\alpha$ - (малый) положительный параметр. Далее $\delta(\Delta)=\max\{ \tau_{i+1}-\tau_i: i=0,\dots,m-1\}$. Фиксируем конечное семейство точек из $P$ таких, что их выпуклая оболочка $P_{\alpha}$ отклоняется от $P$ не более, чем на $\alpha$ в метрике Хаусдорфа. Также фиксируем конечное семейство точек из $Q$ таких, что их выпуклая оболочка отклоняется от $Q$ не более, чем на $\alpha$ в метрике Хаусдорфа; множество всех точек указанного семейства обозначим $Q_{\alpha}$. Всякую функцию $u(\cdot): [t_0,\vartheta]\longmapsto P_{\alpha}$, постоянную на каждом полуинтервале $[\tau_i,\tau_{i+1})$ ( $i=0,\ldots, m-1$), будем называть $(\Delta,\alpha)$-управлением первого игрока и отождествлять с вектором $u=(u_1,\ldots,u_m)$, где $u_i=u(\tau_{i-1})$ ($i=1,\ldots,m$). Таким образом, множество всех $(\Delta,\alpha)$-управлений первого игрока есть $(P_{\alpha})^m$; далее будем его также обозначать как $P(\Delta,\alpha)$. Всякую функцию $v(\cdot): [t_0,\vartheta]\longmapsto Q_{\alpha}$, постоянную на каждом полуинтервале $[\tau_i,\tau_{i+1})$ ( $i=0,\ldots, m-1$), будем называть $(\Delta,\alpha)$-управлением второго игрока и отождествлять с вектором $v=(v_1,\ldots,v_m)$, где $v_i=v(\tau_{i-1})$ ($i=1,\ldots,m)$; таким образом, множество всех $(\Delta,\alpha)$-управлений второго игрока есть $(Q_{\alpha})^m$; далее будем для него также использовать обозначение $Q(\Delta,\alpha)$.

З а м е ч а н и е 1. Множество $Q(\Delta,\alpha)$ конечно.

Движение, порождаемое $(\Delta,\alpha)$-управлением $u$ первого игрока и $(\Delta,\linebreak\alpha)$-управлением $v$ второго игрока, определим как решение $x(\cdot)$ дифференциального уравнения (1.1) c $u(t)=u_i$, $v(t)=v_i$ для $t\in [\tau_{i-1},\tau_i)$ ($i=1,\ldots,m$) и с начальным условием $x(t_0)=x^0$; конечную точку $x(\vartheta)$ этого решения обозначим через $x(u,v)$. Заметим, что

$$x(u,v)=\xi^0+\sum_{i=1}^m \left( \Phi_i^{\Delta}u_i+ \Psi_i^{\Delta}v_i\right),$$ (1.2)

где

$$\xi^0=X(\vartheta,t_0)x^0+\int\limits_{t_0}^{\vartheta} X(\vartheta,\tau)f(\tau)\,d\tau,$$

$(t,\tau)\longmapsto X(t,\tau)$ - фундаментальная матрица однородного уравнения

$$\dot x(t)=A(t)x(t),$$

$$\Phi_i^{\Delta}=\int\limits_{\tau_i}^{\tau_{i+1}} X(\varthet... ...\limits_{\tau_i}^{\tau_{i+1}} X(\vartheta,\tau)C(\tau)\,d\tau.$$

Отображение $s$ множества $Q(\Delta,\alpha)$ всех $(\Delta,\alpha)$-управлений второго
игрока в множество $P(\Delta,\alpha)$ всех $(\Delta,\alpha)$-управлений первого игрока будем называть $(\Delta,\alpha)$-квазистратегией первого игрока, если оно удовлетворяет следующему условию неупреждаемости: для любых $j\in \{ 1,\ldots,m\}$, $v^1$, $v^2\in Q(\Delta,\alpha)$ таких, что $v_i^1=v_i^2$ при всех $i\le j$, выполняется $s(v^1)_i= s(v^2)_i$ при всех $i\le j$. Будем говорить, что $(\Delta,\alpha)$-квазистратегия $s$ первого игрока $\gamma$-наводящая, если $x(s(v),v)\in M^{\gamma}$ для любого $v\in Q(\Delta, \alpha)$.

Лемма 1   Для любого $\varepsilon>0$ существуют $\delta_0>0$ и $\alpha_0>0$ такие, что при $\delta(\Delta)\le\delta_0$, $\alpha\le\alpha_0$ и всяком $\gamma\ge 0$ верны следующие утверждения:

(i) если существует $\gamma$-наводящая позиционная стратегия первого
игрока, то существует $(\gamma+\varepsilon)$-наводящая $(\Delta,\alpha)$-квазистратегия первого игрока,

(ii) если существует $\gamma$-наводящая $(\Delta,\alpha)$-квазистратегия первого игрока, то существует $(\gamma+\varepsilon)$-наводящая позиционная стратегия первого игрока.

З а м е ч а н и е 2. Числа $\delta_0$ и $\alpha_0$ могут быть выражены явно через модули непрерывности матриц-функций $t\longmapsto B(t)$, $t\longmapsto C(t)$, $t\longmapsto X(\vartheta,t)$, константы, равномерно ограничивающие нормы их значений, и константы, равномерно ограничивающие нормы элементов из множеств $P$ и $Q$.

Доказательство леммы 1 опускаем.

Пусть $\gamma^0(\Delta,\alpha)$ - точная нижняя грань всех $\gamma\ge 0$, для которых существует $\gamma$-наводящая $(\Delta,\alpha)$-квазистратегия первого игрока. Из леммы 1 легко получается

Следствие 1   Для любого $\varepsilon>0$ существуют $\delta_0>0$ и $\alpha_0>0$ такие, что при $\delta(\Delta)\le\delta_0$, $\alpha\le\alpha_0$ выполняется $\vert\gamma^0(\Delta,\alpha)-\gamma^0\vert\le \varepsilon$.

З а м е ч а н и е 3. Согласно замечанию $2$, числа $\delta_0$ и $\alpha_0$ могут быть выписаны явно.

Итак, при достаточно малых $\delta(\Delta)$ и $\alpha$ задача об аппроксимации цены $\gamma^0$ сводится к задаче о нахождении величины $\gamma^0(\Delta,\alpha)$. Последняя задача, в свою очередь, может быть представлена как задача конечномерного выпуклого программирования. Опишем это представление. Пусть $S(\Delta,\alpha)$ - линейное пространство всех функций $s: v\longmapsto s(v)= (s(v)_1,\ldots,s(v)_m): Q(\Delta,\alpha)\longmapsto ({R}^{n_1})^m$ (напомним, что $n_1$ - размерность управляющего воздействия первого игрока). Вследствие конечности множества $Q(\Delta,\alpha)$ пространство $S(\Delta,\alpha)$ конечномерно. Превратим $S(\Delta,\alpha)$ в евклидово пространство, вводя для каждых $s^1$, $s^2\in S(\Delta,\alpha)$ их скалярное произведение по формуле

$$\left< s^1,s^2 \right>_{S(\Delta,\alpha)}= \sum_{v\in Q(\Delta,\alpha)} \sum_{i=1}^m \left< s^1(v)_i, s^2(v)_i \right>;$$

здесь и далее $\left< \cdot,\cdot \right>$ - скалярное произведение в ${R}^k$. Ясно, что каждая $(\Delta,\alpha)$-квазистратегия $s$ первого игрока, есть элемент из $S(\Delta,\alpha)$, удовлетворяющий, во-первых, ограничению

$$s(v)\in P(\Delta,\alpha)\quad (v\in Q(\Delta,\alpha)),$$ (1.3)

и, во-вторых, условию $s(v)_i-s(w)_i=0 \quad (i=1,\ldots,j)$ при $v_i=w_i$ ($i=1,\ldots,j$). Последнее условие (неупреждаемости) запишем в операторной форме:

$$F_{\Delta,\alpha} s=0.$$ (1.4)

Оператор $F_{\Delta,\alpha}$ действует из $S(\Delta,\alpha)$ в линейное конечномерное пространство $R(\Delta,\alpha)$ всех функций $r: (v,w)\longmapsto r(v,w)=(r(v,w)_1,\ldots, r(v,w)_m): \left( Q(\Delta,\alpha) \right)^2\longmapsto \left( {R}^{n_1} \right)^m$. Значение $F_{\Delta,\alpha}s$ оператора $F_{\Delta,\alpha}$ на элементе $s\in S(\Delta,\alpha)$ определяется по формуле

$$\left( F_{\Delta,\alpha}s \right)(v,w)_i=\left\{ \begin{arra... ..._i,\\ [2ex] 0, & \mbox{в противном случае}. \end{array}\right.$$ (1.5)

Заметим, что оператор $F_{\Delta,\alpha}$ линеен. Итак, справедлива

Лемма 2   Элемент $s\in S(\Delta,\alpha)$ есть $(\Delta,\alpha)$-квазистратегия первого игрока тогда и только тогда, когда $s$ удовлетворяет ограничениям
(1.3) и (1.4).

Пространство $R(\Delta,\alpha)$ будем далее считать евклидовым; скалярное произведение элементов $r^1$, $r^2\in R(\Delta,\alpha)$ зададим по формуле

$$\left< r^1,r^2 \right>_{R(\Delta,\alpha)}= \sum_{(v,w)\in \l... ...\right)^2} \sum_{i=1}^m \left< r^1(v,w)_i, r^2(v,w)_i \right>.$$ (1.6)

Из леммы 2 вытекает

Следствие 2   Число $\gamma^0(\Delta,\alpha)$ есть оптимальное значение в задаче на поиск минимума

$$\max_{v\in Q(\Delta,\alpha)} \mathop{\rm dist}\nolimits (x(s(v),v),M)\to\min$$ (1.7)

при ограничениях (1.3), (1.4).

Задача (1.7), (1.3), (1.4) есть, очевидно, задача конечномерного выпуклого программирования. Для решения этой задачи, в принципе, применимы стандартные итерационные методы оптимизации. Однако, негладкость минимизируемой функции, возникающая за счет входящей в нее операции максимизации (см. (1.7)), и большая, вообще говоря, размерность задачи создают серьезные трудности на пути конструктивной реализации стандартных методов. Наша цель - указать конструктивный, по возможности готовый для программирования, специализированный алгоритм, позволяющий проверить неравенство $\gamma\ge\gamma^0(\Delta, \alpha)$ при заданном $\gamma>0$.

От задачи (1.7), (1.3), (1.4) перейдем к задаче на минимум

$$\sum_{v\in Q(\Delta,\alpha)} \mathop{\rm dist}\nolimits (x(s(v),v),M^{\gamma})\to\min$$ (1.8)

при ограничениях (1.3), (1.4); здесь $\gamma$ - неотрицательный параметр. Из леммы 2 легко получаем

Следствие 3   Число $\gamma^0(\Delta,\alpha)$ есть точная нижняя грань всех $\gamma\ge 0$, для которых оптимальное значение в задаче (1.8), (1.3), (1.4) равно нулю.

Имея в виду этот факт, сосредоточимся на методе решения задачи (1.8), (1.3), (1.4).