Article ID: | iaor2004728 |
Country: | United States |
Volume: | 23 |
Issue: | 2 |
Start Page Number: | 416 |
End Page Number: | 432 |
Publication Date: | May 1998 |
Journal: | Mathematics of Operations Research |
Authors: | Smith R.L., Schochetman I.E. |
Keywords: | 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 decision of an efficient, and hence average optimal, infinite horizon solution.