Second-order convergence of an algorithm calculating the value of linear differential games (Q1363955)

The central concept of differential game theory is of the optimal guaranteed result, i.e., the best result that can be achieved by the first or second player when the actions of his rival are most unfavorable for him. It is well known that for linear differential games the optimal guaranteed result of the first player is equal to that of the second player. This common value is called the game value. The numerical realizations of the linear differential zero-sum game theory have been studied intensively. The realization of this problem, however, is so difficult that for the proposed algorithms the problem of their rate of convergence to the exact game value has not even been posed. The algorithms actually proposed had error orders, no smaller than inversely proportional to the number of time steps of the algorithm. We analyze the possibilities of raising the rate of convergence of the algorithms that implement the existing linear differential zero-sum game theory, taking into account the smoothness and other properties of the cost function and the sets that constrain the players' controls. We propose an algorithm for the calculation of the value of a linear differential game with a convex cost function. Assuming that the set constraining the first player's control is strongly convex, we show that the error of our algorithm is inversely proportional to the squared number of steps.