Все выпуски

В статье рассматриваются приближенные решения неантагонистических дифференциальных игр. Приближенное равновесие по Нэшу может быть построено по заданному решению вспомогательной стохастической игры с непрерывным временем. Мы рассматриваем случай, когда динамика вспомогательной игры задается марковской цепью с непрерывным временем. Для этой игры функция цены определяется решением системы обыкновенных дифференциальных включений. Таким образом, мы получаем конструкцию приближенного равновесия по Нэшу с выигрышами игроков, близкими к решениям системы обыкновенных дифференциальных включений. Также предложен способ построения марковской игры с непрерывным временем, аппроксимирующей исходную игру.

The paper is concerned with approximate solutions of nonzero-sum differential games. An approximate Nash equilibrium can be designed by a given solution of an auxiliary continuous-time dynamic game. We consider the case when dynamics is determined by a Markov chain. For this game the value function is determined by an ordinary differential inclusion. Thus, we obtain a construction of approximate equilibria with the players' outcome close to the solution of the differential inclusion. Additionally, we propose a way of designing a continuous-time Markov game approximating the original dynamics.

В работе рассматривается пространство Стоуна булевой алгебры подмножеств одного счетного частично упорядоченного множества. Главной особенностью этого множества является наличие бесконечного числа непосредственных последователей у каждого его элемента. Отсюда следует, что каждый фиксированный ультрафильтр данного пространства Стоуна является неизолированной точкой, а подмножество свободных ультрафильтров всюду плотно. В работе дана классификация точек пространства, доказано, что есть свободные ультрафильтры, которые не являются пределами последовательностей фиксированных ультрафильтров, а также свободные ультрафильтры, определяемые цепями частично упорядоченного множества. Рассмотрены кардинальные инварианты подпространства свободных ультрафильтров. Доказано, что это подпространство имеет счетное число Суслина, но не сепарабельно.

The paper concerns the Stone space of the Boolean algebra of subsets of one countable partially ordered set. The main feature of this set is the existence of countably many successors of each of its elements. From this property it follows that every fixed ultrafilter of this Stone space is a nonisolated point; the subset of free ultrafilters is dense everywhere. The classification of space points is given; the fact that there are free ultrafilters, which are not limits of sequences of fixed ultrafilters, as well as free ultrafilters determined by chains of partially ordered set, is proved. The cardinal invariants of the subspace of free ultrafilters are considered. It is shown that this subspace has the countable Suslin number, but is not separable.

Рассматривается задача оптимального управления системой бесконечного числа однотипных агентов. Пространство допустимых для агентов состояний является конечным. В рассматриваемой постановке имеется общий для всех агентов оптимизируемый функционал и общий центр управления, выбирающий стратегию для агентов. Предполагается, что выбираемая стратегия является позиционной. В настоящей работе рассматривается случай, когда динамика состояний агентов задается некоторой марковской цепью с непрерывным временем. Предполагается, что матрица Колмогорова этой цепи в каждом состоянии зависит от текущего состояния, выбранного управления и распределения всех агентов. Для такой задачи в работе показано, что решение в классе позиционных стратегий может быть построено на основе решения детерминированной задачи оптимального управления в конечномерном фазовом пространстве.

We consider an optimal control problem for an infinite amount of agents of the same type. We assume that agents have a finite state space. The given formulation of the problem involves an objective functional that is common for all agents and a common control center that chooses a strategy for agents. A chosen strategy is supposed to be positional. In this paper we consider a case when the dynamics of agents is given by a Markov chain with continuous time. It is assumed that the Kolmogorov matrix of this chain in each state depends on the current state, the chosen control and the distribution of all agents. For the original problem, it is shown that concerning positional strategies the solution can be obtained through the solution of the deterministic control problem in a finite-dimensional phase space.

Рассматривается одна булева алгебра и ее пространство Стоуна как бикомпактное расширение счетного дискретного пространства. Доказаны некоторые свойства этого расширения.

We consider one Boolean algebra and its Stone space as a compactification of a countable discrete space. Some properties of the compactification are proved.

В данной работе рассматривается булева алгебра того же типа, что и алгебра, построенная Беллом, и пространство Стоуна этой булевой алгебры. Данное пространство является компактификацией счетного дискретного пространства N. Доказано существование изолированных точек в наросте данной компактификации, которые являются пределами некоторых сходящихся последовательностей. Также доказано, что любое открыто-замкнутое подмножество нашего пространства, которое гомеоморфно βω, является замыканием объединения конечного числа антицепей из N. В конце приведены два примера: замкнутое подмножество нароста без изолированных точек, которое не гомеоморфно βω\ω; подмножество нароста, которое гомеоморфно βω\ω, но не является замкнутым.

We consider the Boolean algebra of the same type as algebra constructed by Bell, and the Stone space of this Boolean algebra. This space is a compactification of a countable discrete space N. We prove that there are isolated points in a remainder of this compactification, which are limits of some convergent sequences. We prove that a clopen subset of our space, which is homeomorphic to βω, is a closure of the union of finitely many antichains from N. We construct two examples: a clopen subset of the remainder without isolated points, which is not homeomorphic to βω\ω; a subset of the remainder which is homeomorphic to βω\ω, but is not a clopen.

Настоящая работа посвящена исследованию асимптотических свойств числа серий в последовательности дискретных случайных величин, управляемых цепью Маркова с конечным числом состояний. Состояние цепи на каждом шаге определяет закон распределения знаков в управляемой последовательности на этом шаге. Такая случайная последовательность представляет собой модель скрытой марковской цепи. При помощи метода Чена-Стена получена оценка расстояния по вариации между распределением числа серий длины не меньше заданной в случайной последовательности, управляемой цепью Маркова, и сопровождающим распределением Пуассона. Для ее вывода сначала рассматривалась последовательность из независимых неоднородных полиномиальных случайных величин, а затем использован прием, позволяющий получить оценку расстояния по вариации между смешанным пуассоновским распределением и пуассоновским распределением с параметром, равным среднему числу серий длины не меньше заданной. Эта оценка строится на основе дисперсии параметра смешанного пуассоновского распределения и выведенной ранее оценки для расстояния по вариации для полиномиальной схемы. Отдельно рассмотрен случай стационарной цепи Маркова. При помощи полученных оценок доказаны пуассоновская и нормальная предельные теоремы для числа серий длины не меньше заданной, а также найдено предельное распределение для наибольшей длины серии в управляемой случайной последовательности.

The present paper is devoted to studying the asymptotic properties of a number of runs in the sequence of discrete random variables controlled by Markov chain with a finite number of states. A chain state at each step determines the law of characters distribution in the controlled sequence at this step. This random sequence represents a model of hidden Markov chain. Using Chen-Stein method we estimate the total variation distance between the distribution of the number of runs with length not less than predetermined length in the random sequence controlled by Markov chain and the accompanying Poisson distribution. For this purpose we first consider the sequence of independent inhomogeneous polynomial random variables, and then we use an approach which allows to get the estimate for total variation distance between mixed Poisson distribution and Poisson distribution with the parameter which equals to an average number of runs with length not less than predetermined. The estimate is based on both the variance of the mixed Poisson distribution parameter and the estimate obtained earlier for the total variation distance for the polynomial scheme. Separately we consider the case of a stationary Markov chain. Using derived estimates we investigate Poisson and normal limit theorems for the number of runs with length not less than predetermined, as well as the limit distribution for the maximal run length in a controlled sequence.

В статье рассматривается общий случай маршрутной задачи дискретной оптимизации, осложненной условиями предшествования; изучается влияние условий предшествования на вычислительную сложность решений таких задач методом динамического программирования. Особенность применяемого метода динамического программирования заключается в его «экономичности»: подзадачи, не соблюдающие условия предшествования и, следовательно, не участвующие в оптимальном решении, не рассматриваются, что позволяет сберечь и вычислительную мощность, и память.

Этот метод c 2004 года используется А.Г. Ченцовым и его соавторами, но степень экономии ресурсов исследовалось мало. Мы предлагаем подход к решению этой проблемы, основанный на комбинаторном анализе числа подзадач, существенных в смысле условий предшествования. Применяя известные комбинаторные правила сложения и произведения, мы получили результат для важных частных случаев условий предшествования: а) «независимые» наборы условий предшествования; б) «цепь» условий предшествования - когда условия задают линейный порядок; в) случай, когда в графе предшествования нет неориентированных циклов, и исходящая степень любой вершины не превышает единицы. Последний случай представляет собой условия предшествования, встречающихся в практической задаче маршрутизации движений инструмента в машинах листовой резки и соответствует требованию вырезать внутренний контур прежде внешнего.

В связи с более сложной структурой случая в) по сравнению с остальными для него вместо аналитической формулы представлен алгоритм; алгоритм реализован на языке C++, зависимость его вычислительной сложности от числа связанных условиями предшествования объектов имеет не более чем квадратичный порядок. В дальнейшем мы предполагаем расширить область применения нашего подхода до более общих вариантов условий предшествования. Отметим также, что наш подход не зависит от критерия оптимальности, соответственно, может применяться для анализа сложности решения методом динамического программирования в произвольных маршрутных задачах с условиями предшествования.

We consider the general case of Precedence Constrained TSP (or a less general case of Sequential Ordering Problem) solved with a special kind of dynamic programming method that uses precedence constraints to significantly reduce the number of subproblems that must be solved to find the optimal solution of the original problem. Our aim is to quantify this reduction, which is necessary to clarify the influence of precedence constraints on computational complexity of dynamic programming solutions of such problems. This variety of the method of dynamic programming has been developed by A.G. Chentsov and his co-authors since 2004 but there was only one attempt at examining the influence of precedence constraints on complexity, which only described the influence of a single precedence constraint in the form of an “address pair” (sender, receiver).

Our approach to studying the complexity of this method is essentially the combinatorial analysis of the number of subproblems that are feasible in the sense of abiding by precedence constraints. Using the well-known combinatorial principles, the rule of product and the rule of sum, we established the estimates of complexity reduction for the following cases: a) “independent” sets of precedence constraints; b) “chains” of precedence constraints, when the precedence constraints define a linear ordering on the objects bound by them; c) precedence constraints expressed by an acyclic directed graph with outdegree (the number of receivers per sender) at most one. The latter case of precedence constraints is the one encountered in real-life problems of optimizing the route of the cutter in various machines used to cut sheet material. Since this is the most complex case of the three analyzed, instead of an analytic formula, we had to develop an algorithm (which we implemented in C++) to quantify the reduction; the computational complexity of the algorithm is less than quadratic with respect to the number of objects constrained by the precedence constraints. We intend to develop our approach to treat other cases of precedence constraints, eventually reaching the general case. We would also like to note that our method is optimization criterion-agnostic and thus applicable to many kinds of TSP, as long as they are precedence constrained and solvable by dynamic programming; in fact, our approach may be used to analyze the complexity of the dynamic programming method solution of any discrete optimization problem that deals with ordering subject to precedence constraints.

В работе дан обзор проблем, приводящих к необходимости анализа моделей линейных и нелинейных динамических систем в форме стохастических дифференциальных уравнений со случайными запаздываниями различного типа, а также представлены некоторые известные методы решения этих задач. Далее в статье предлагаются новые подходы к приближенному анализу линейных и нелинейных стохастических динамических систем, изменения запаздываний которых описываются дискретной марковской цепью с непрерывным временем. Используемые подходы базируются на сочетании классического метода шагов, расширения пространства состояния стохастической системы и метода статистического моделирования (Монте-Карло). В рассматриваемом случае такой подход позволил упростить задачу и привести исходные уравнения к системам стохастических дифференциальных уравнений без запаздывания. Более того, для линейных систем получена замкнутая последовательность систем обыкновенных дифференциальных уравнений увеличивающейся размерности относительно функций условных математических ожиданий и ковариаций вектора состояния. Изложенная схема демонстрируется на примере стохастической системы второго порядка, изменения запаздывания которой описываются марковской цепью с пятью состояниями. Все расчеты и построение графиков проводились в среде математического пакета Mathematica с помощью программы, написанной на входном языке этого пакета.

The paper provides an overview of the problems that lead to a necessity for analyzing models of linear and nonlinear dynamic systems in the form of stochastic differential equations with random delays of various types as well as some well-known methods for solving these problems. In addition, the author proposes some new approaches to the approximate analysis of linear and nonlinear stochastic dynamic systems. Changes of delays in these systems are governed by discrete Markov chains with continuous time. The proposed techniques for the analysis of systems are based on a combination of the classical steps method, an extension of the state space of a stochastic system under examination, and the method of statistical modeling (Monte Carlo). In this case the techniques allow to simplify the task and to transfer the source equations to systems of stochastic differential equations without delay. Moreover, for the case of linear systems the author has obtained a closed sequence of systems with increasing dimensions of ordinary differential equations satisfied by the functions of conditional expectations and covariances for the state vector. The above scheme is demonstrated by the example of a second-order stochastic system. Changes of the delay in this system are controlled by the Markov chain with five states. All calculations and graphics were performed in the environment of the mathematical package Mathematica by means of a program written in the source language of the package.

Пусть $H$ — банахово пространство, $T>0$, $\sigma\in[1;\infty]$ и задана шкала банаховых пространств $W[0;\tau]$, $\tau\in(0;T)$, индуцированная сужениями из пространства $W=W[0;T]$; $\mathcal{F}\colon L_\sigma(0,T;H)\to W$ — вольтерров оператор; $f[u]\colon W\to L_\sigma(0,T;H)$ — управляемый вольтерров оператор, зависящий от управления $u\in U$. Рассматривается уравнение вида $$ x=\mathcal{F}\bigl( f[u](x)\bigr),\quad x\in W. $$ Для этого уравнения устанавливаются признаки тотально (по множеству допустимых управлений) глобальной разрешимости при условии глобальной разрешимости некоторого функционально-интегрального неравенства в пространстве $\mathbb{R}$. Во многих частных случаях указанное неравенство может быть конкретизировано как задача Коши для обыкновенного дифференциального уравнения. Фактически, развивается аналогичный результат, доказанный автором ранее, на этот раз при других, более удобных для практического использования условиях (хотя и в более частной постановке). Отдельно рассматриваются случаи: 1) компактного вложения пространств и непрерывности операторов $\mathcal{F}$, $f[u]$ (такой подход автором ранее не использовался); 2) выполнения локально-интегрального аналога условия Липшица относительно указанных операторов. Во втором случае доказывается также единственность решения. В первом случае применяется теорема Шаудера, во втором — технология продолжения решения по времени, то есть продолжения вдоль вольтерровой цепочки. В качестве примера рассматривается нелинейное волновое уравнение в пространстве $\mathbb{R}^n$.

Let $H$ be a Banach space, $T>0$, $\sigma\in[1;\infty]$ and let $W[0;\tau]$, $\tau\in(0;T)$, be the scale of Banach spaces which is induced by restrictions from a space $W=W[0;T]$; $\mathcal{F}\colon L_\sigma(0,T;H)\to W$ be a Volterra operator (an operator with Volterra property); $f[u] \colon W\to L_\sigma(0,T;H)$ be a controlled Volterra operator depending on a control $u\in U$. We consider the equation as follows $$x=\mathcal{F}\bigl( f[u](x)\bigr),\quad x\in W.$$ For this equation we establish signs of totally (with respect to a set of admissible controls) global solvability subject to global solvability of some functional integral inequality in the space $\mathbb{R}$. In many particular cases the above inequality may be realized as the Cauchy problem associated with an ordinary differential equation. In fact, the analogous result which was obtained by the author formerly is developed, this time under other hypotheses, more convenient for practical usage (although in more particular statement). Separately, we consider the cases of compact embedding of spaces and continuity of the operators $\mathcal{F}$, $f[u]$ (such an approach has not been used by the author formerly), from one hand, and of local integral analogue of the Lipschitz condition with respect to that operators, from another hand. In the second case we prove also the uniqueness of solution. In the first case we use Schauder theorem and in the second case we apply the technique of solution continuation along with the time axis (id est continuation along with a Volterra chain). Finally, as an example, we consider a nonlinear wave equation in the space $\mathbb{R}^n$.

В настоящее время продолжают активно изучаться неэрмитовы топологические системы. В данной статье в строгом подходе изучена одна из ключевых неэрмитовых систем — модель Хатано–Нельсона $H$. Найдена функция Грина для этого гамильтониана. С помощью функции Грина аналитически получены собственные значения и собственные функции $H$ для конечных и полубесконечных цепей, а также для бесконечной цепи с локальным потенциалом. Обсуждается неэрмитов скин-эффект для упомянутых выше моделей. Также описана граница между локализованными и резонансными состояниями (при нулевой энергии — это граница между неэрмитовыми топологическими фазами).

At present, non-Hermitian topological systems continue to be actively studed. In a rigorous approach, we study one of the key non-Hermitian systems — the Hatano–Nelson model $H$. We find the Green function for this Hamiltonian. Using the Green function, we analytically obtain the eigenvalues and eigenfunctions of $H$ for finite and semi-infinite chains, as well as for an infinite chain with a local potential. We discuss the non-Hermitian skin effect for the models mentioned above. We also describe the boundary between localized and resonant eigenfunctions (for the zero spectral parameter, this is the boundary between non-Hermitian topological phases).