ADDITIVE DECOMPOSITION OF MATRICES AND OPTIMIZATION PROBLEMS ON INFINITE TIME INTERVALS

We discuss control systems over finite and countable state spaces defined on an infinite time horizon, where, typically, all the associated costs become unbounded as the time grows indefinitely. We consider the limit behavior, as n → ∞, of the expression Pn−1 i=0 v(zi , zi+1) for programs {zi}∞ i=0 in a finite state space X = {xi} N i=1, where v(xi , xj ) is the transition cost from state xi to state xj . To construct optimal programs we will establish and employ an additive decomposition formula which is of the form V = µJ + pηT − ηp T + Θ. In this expression µ is a scalar, J is a matrix that satisfies Jij = 1 for every 1 ≤ i, j ≤ N, p and η are N-dimensional column vectors such that ηi = 1 for all 1 ≤ i ≤ N, and Θ is a matrix satisfying min1≤j≤N Θij = 0 for every 1 ≤ i ≤ N. We will show how to compute µ, p and Θ in time of order O(N5 ). Also, we will discuss infinite horizon optimization problems for certain non-autonomous control systems.