Existence and Discovery of Average Optimal Solutions in Deterministic Infinite Horizon Optimization

We consider the problem of making a sequence of decisions, each chosen from a finite action set over an infinite horizon, so as to minimize its associated average cost. Both the feasibility and cost of a decision are allowed to depend upon all of the decisions made prior to that decision; moreover, time-varying costs and constraints are allowed. A feasible solution is said to be efficient if it reaches each of the states through which it passes at minimum cost. We show that efficient solutions exist and that, under a state reachability condition, efficient solutions are also average optimal. Exploiting the characterization of efficiency via a solution's short-run as opposed to long-run behavior, a forward algorithm is constructed which recursively discovers the first, second, and subsequent decisions of an efficient, and hence average optimal, infinite horizon solution.