Existence and Discovery of Average Optimal Solutions in Deterministic Infinite Horizon Optimization Irwin E. Schochetinan Dept. of Mathematical Sciences Oakhland University Rochester, MI 48309 Robert L. Smith Dept. of Industrill and Operations Engineering University o' Michigan Ann Arbor, MI 48109 Technical Report 97-07 February 1')')7

EXISTENCE AND DISCOVERY OF AVERAGE OPTIMAL SOLUTIONS IN DETERMINISTIC INFINITE HORIZON OPTIMIZATION IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH Department of Mathematical Sciences Oakland University Rochester, Michigan 48309 and Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 February 25, 1997 ABSTRACT. 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 the 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. The concept of a an efficient solution is formalized within this general framework. A feasible solution is efficient if it reaches each of the states through which it passes at minimum cost. Efficient solutions are shown to exist. A principle result of the paper is that, under a state reachability condition, an efficient solution is also average optimal, i.e., average optimal solutions exist which are efficient. 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. We illustrate the theory by an application in equipment replacement under technological change. 1. Introduction Infinite horizon optimization at its most fundamental level is the problem of selecting an infinite sequence of decisions which promises to minimize the associated costs incurred over an unbounded horizon (Bean and Smith [1984], Schochetman and Smith [1989]). One of the key difficulties inherent in this task is the dilemma of evaluating an infinite stream of costs whose cumulative value will typically diverge. Perhaps the most commonly employed criterion is that of discounted costs. This criterion explicitly reflects the time value of money via a discount factor which leads to convergence in cost. Perhaps the second most commonly used criterion is obtained by replacing the original cost stream by its average value per period, the so-called average-cost criterion. Advantages of the latter criterion include: a) the value of a discount factor need not be specified; b) it is a numerically stable substitute for discounted problems with discount factor near 1; c) when costs are not measured in dollars, use of a discount factor becomes artificial and potentially meaningless; and d) cumulative costs need not converge. Despite these advantages, the averagecost criterion introduces a number of mathematical pathologies not shared by the discounted-cost criterion. 1980 Mathematics Subject Classification (1985 Revision). Primary 90C20, Secondary 49A99. Key words and phrases. Average optimality, infinite horizon optimization, efficient solution, state reachability, forward algorithm, equipment replacement. This work was supported in part by the National Science Foundation under Grant DDM-9214894. Typeset by AMS-I1tX 1

2 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH Perhaps the most serious is that, since the average value of an infinite horizon cost stream is insensitive to the costs incurred over any finite horizon, the criterion is extraordinarily underselective. It includes averagecost optimal strategies that are difficult to justify in any other respect (Hopp, Bean, and Smith [1987]). This behavior is correctable in the stationary case by restricting consideration to a set of strategies within which average-cost minimization makes sense. In particular, in stationary problems where neither decision feasibility nor costs are time-dependent, restriction to stationary strategies yields an average-cost optimal strategy that avoids the myopic behavior of the larger class of all average-cost optimal strategies (Ross [1983], Puterman [1994]). In this paper, we extend the latter approach to nonstationary problems where either feasibility or costs (possibly both) are time dependent. However, stationary strategies need no longer be optimal here. Instead, we generalize by restricting consideration to efficient strategies (see Ryan, Bean, and Smith [1992], Schochetman and Smith [1992] for a similar concept in the discounted case). A strategy is efficient if it is average-cost (or equivalently undiscounted total cost) optimal to each of the states through which it passes. We show that an efficient solution always exists and that, under a state-reachability condition, every efficient solution is average-cost optimal. This result is perhaps surprising in that the mixing effects due to ergodicity in the more traditional stochastic setting (Ross [1968], Federgruen and Tijms [1978], Hopp, Bean and Smith [1987], Bean, Lasserre, and Smith [1990], Park, Bean, and Smith [1993]) are absent in our purely deterministic model. As a consequence of the above, we conclude existence of an average-cost optimal solution. Moreover, because of its characterization in terms of its optimal behavior to states, as opposed to from states, we construct a forward algorithm that is guaranteed to successively discover the first, second, and subsequent decisions along an efficient, and hence average-cost optimal, strategy for general nonstationary infinite horizon optimization. The algorithm is similar to the forward algorithms proposed in Schochetman and Smith [1992] in the discounted case. In section 2, we formally introduce the general class of discrete-time infinite horizon problems which we study. We form their finite horizon approximating problems by projection of the feasible region and objective function onto finite dimensional spaces. Efficient solutions are then introduced as feasible infinite horizon solutions which are optimal to each of the states through which they pass. The existence of efficient solutions is demonstrated by a topological compactness argument. In section 3, we introduce a state- reachability property which guarantees that every efficient solution is average-cost optimal, and in particular, that an average-cost optimal solution thus exists. In section 4, we turn to the problem of approximating efficient solutions by their computable finite horizon counterparts. We first show that the sequence of sets of all efficient solutions of the finite horizon approximating problems converges, in the sense of Kuratowski, to the set of efficient solutions of the infinite horizon problem. We next show policy convergence, where the sequence of lexicomin elements of the sets of finite horizon efficient solutions is shown to converge to the lexicomin infinite horizon efficient solution. This is an instance of selection convergence. Average optimal cost convergence is established in section 5. In section 6, a finite forward algorithm, with stopping rule, is given that recursively recovers the first, second, and subsequent decisions in an average-cost optimal efficient solution, whenever the latter is unique. Finally in section 7, we discuss an application of our model to serial equipment replacement under technological change. 2. Problem Formulation We begin with an extremely general deterministic infinite horizon optimization problem, formulated as a dynamic programming problem. The deterministic property removes our model from the stochastic framework required for the majority of average-cost criterion work (Ross [1968], Derman [1966], Federgruen and Tijms [1978]). These stochastic models generally require a single fixed recurrent class of the Markov chain corresponding to every policy, a property that fails in the purely deterministic case. Essentially, the only restriction in this work, apart from being a deterministic model, is the requirement that at most a finite number of decision alternatives is available at each decision epoch. Included are production planning un

EXISTENCE AND DISCOVERY OF AVERAGE-COST OPTIMAL SOLUTIONS 3 der nonstationary demand, parallel and serial equipment replacement under technological change, capacity planning under nonlinear demand, and optimal search in a time-varying environment. For convenience, we embed the problem within a discrete-time framework, where each decision is made at the beginning of each of a series of equal time periods, indexed by j = 1, 2,.... The set of all possible decisions available in period j (irrespective of the period's beginning state) is denoted by Yj, and is assumed to be finite. For convenience we let Yj = {0, 1,2,..., mj} with the usual discrete topology, with mj 1, j = 1,2,... (we may interpret decision 0 as signaling no action for that period). We model the problem as a dynamic system governed by the state equation j = fj(sj-l,yj), Vj = 1,2,..., where: so is the given initial state of the system (beginning period 1), sj is the state of the system at the end of period j, i.e., beginning period j + 1, yj is the control or decision selected in period j with knowledge of the beginning state sjl, Sj is the given (finite) set of feasible states ending period j, so that sj E Sj, Vj = 1,2,..., The set Yj(sj-1) is the given (finite) non-empty subset of decisions available in period j when the system is in state sj-_ E Sj-1, so that yj E Yj(sj-1) C Yj, and fj is the given state transition function in period j, where fj: Fj - Sj, for Fj = {(sj-l,yj) E Sj-1 x Yj: yj E Yj(sj-1)}, Vj = 1,2,... We set So = {so}, and require that Sj = {fj(sj-l,yj): sj-_ E Sj_-, yj E Yj(sj-1)}, Vj = 1,2,..., so that, in particular, S1= {fl(so, Y1): Y1 e Y(so)}. Thus, each Sj is exactly the set of feasible, i.e., attainable, states in period j. Note that our state space formulation is essentially without loss of generality since we can if necessary identify distinct states to every feasible sequence of preceding decisions. We will at times adopt the equivalent view that models the decision problem via a directed acyclic network where the nodes correspond to the states sj, j = 1,2,... and a directed arc joining state sj to state sj+1 corresponds to an action in Yj+p(sj) that transforms state sj into state sj+l via the state transition function f. Every directed path from node so to node sj then corresponds to a feasible sequence of decisions that results in state sj at the end of period j. The product set Y = fI=1Yj which contains all feasible decision sequences or strategies is then a compact topological space relative to the product topology, i.e., the topology of componentwise convergence. (Note that in general not all strategies in Y will be feasible.) Because of the finiteness of the Yj, componentwise convergence yields eventual agreement in each component of the limiting strategy. Lemma 2.1. Let y E Y, {y"} C Y, such that y" y, as n - oo. Let 1 < K < oo. Then there exists nK sufficiently large such that y' = yj in Yj, Vj = 1,..., K, for all n n nK. Proof. Omitted. O In section 4, we will find it necessary to assume that the sequence {mj} is bounded by some 1 < m < oo, i.e., mj, m, all j. In this event, the product topology on Y is metrizable with metric d given by 00 d(x,y)= f3txj -yjl, Vx,y E Y, j=1

4 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH where we choose p so that 0 < 3 < l/(m + 1). We will let IC(Y) denote the set of all closed (hence, compact), non-empty subsets of Y. Equipped with the Hausdorff metric D (Berge [1963]) derived from the above metric d, C(Y) is also a compact metric space (Hausdorff [1962]). It is well-known that the resulting convergence in K:(Y) is set convergence in the sense of Kuratowski (Kuratowski [1966], Hausdorff [1962]). Recall that a sequence of sets T, in an abstract metric space (Z, p) is said to Kuratowski converge to T, written limTn = T, if T = limsupTn = liminf T, where: (i) lim inf Tn= the set of points x in Z for which there exists xn E T, for n sufficiently large, such that p(xn, x) -- 0, as n -. oo. (ii) limsupTn = the set of points x in Z for which there exists a subsequence {Tn,} of {Tn}, and a corresponding sequence {xj}, such that xj E Tnj, Vj, and p(xj, x) -- 0, as j -+ oo. Now let x E Y. Define x to be feasible if xj E Yj(sj-1), where sj = fj(sj_-, xj), for all j = 1,2,.... We define the feasible region X to be the subset of Y consisting of all those x which are feasible. Lemma 2.2. The subset X of all feasible solutions is non-empty and closed in Y, i.e., X E CK(Y). Proof. The non-emptiness of X follows immediately from our assumption that Yj(sj-i) 0, for all sj_- E Sj_1, and for all j = 1, 2,.... To show X is closed in the metric space Y, let {xn} be a sequence in X and y an element of Y for which x - y in Y, i.e., x -- yj, as n -- o, Vj = 1, 2,.... We show that y E X, i.e., yj E Yj(sj-1), where sj = fj(sj1, yj), Vj = 1,2,.... By Lemma 2.1, we have that for each j, eventually x1 = yj. Let 1 < K < oo. Then there exists m sufficiently large such that xX = yj, Vj = 1,2,..., K. Since xm E X by hypothesis, we have that x E Yj (s_ 1), where s = fj (sm 1, x), for all j = 1, 2,.... Then: Y1 = x E Y1(so), fi(so,y) = fi (so, x) = s1 so that sl = s; Y2 = x2 E Y2(s) = Y2(sl), f2(l, Y2) = f2(Sl, x ) = s2, so that s2 = s2; so that SK-1 = sm_1; and YK = -x E YK(SK-_) = YK(SK-1), fK(sK-1,YK) = fK(sK-1,K) = SK, so that SK = sm. Since K is arbitrary, it follows that x E X. D Clearly, the infeasability of an infinite strategy is determinable from observing a finite sequence of its initial decisions. Practically speaking, this hardly a restriction since the feasibility of a potential decision in period j is allowed to depend upon the entire sequence of decisions previously made. Suppose y E Y and N is a positive integer. Suppose y is such that yj E Yj(sjl), where sj = f;(sj-1, /j), for j = 1,2,..., N, i.e., y is feasible through period N. In this event, for each such j ( N, we define sj(y) to be the state sj = fj(sj-,yj), which is an element of Sj. If we do this for each j = 1,2,...,N, then notationally we have that sj(y) = fj(sj-l(y),yj). (Note that the state sj(y) is well-defined.) We will refer to each such sj(y) as the state through which y passes at the end of period j. If both z,y E Y satisfy the

EXISTENCE AND DISCOVERY OF AVERAGE-COST OPTIMAL SOLUTIONS 5 previous property with respect to N, and yj = zj, Vj = 1, 2,..., N, then sj(y) = sj(z) for all j = 1, 2,..., N. Moreover, if x E X, then the previous property is satisfied for x and all positive integers N, so that sj(x) is defined for each period j = 1,2.... in this case. Finally, if x E X, then (sj 1(x), xj) E Fj, Vj = 1,2,.... Turning to the objective function, we also allow the cost of a decision made in period j to depend upon the sequence of previous decisions, or more accurately, upon the state resulting from these decisions. Specifically, we let cj(sj_-, yj) be the real-valued cost of decision yj in period j, if we are in state sj-1 beginning period j. We thus obtain cost functions cj: Fj - IX, which we assume are uniformly bounded, i.e., there exists 0 < B < oo such that cj(sjl,yj)| I B, Vsjl E Sj1, Vyj E Yj(s-1), VJj = 1,2,... We will adopt the average-cost optimality criterion in this paper. Specifically, for each strategy x E X, we define the associated average-cost A(x) by A(x) = lim sup - Ecj(sj-i(x),Xj), j=1 so that -B ~ A(x) < B, Vix E X. One of the pathological aspects of the average cost criterion is it's failure to be continuous, as the following example illustrates. Example 2.3. For each j =, 2,..., let Yj =Sj = Yj(sj-1) = {0,1}, for s-1 = 0 and 1, so = 0, fj(sj_l,yj) = sj+y ( mod 2), and cj (sj _,yj) yj, V(sj1, yj) E F,. Then it is easily seen that the feasible region X = Y. Moreover, let x" =(1, 1,..., 1,0,0,...), Vn= 1,2,..., and x~~ = (1,1,1,...). Then xz -x, x in X, as n -A oo, A(x~~) = 1, but A(xn) = 0, Vn. Hence, A(x') +7 A(x~), as n - oo. Since X is compact, it is of interest (Aliprantis and Border [1994, p.44]) to know whether A is possibly lower semi-continuous in general. However, in this example we have that O = liminf A(x") < A(x~~) = 1, n so that this is not the case either. Of course, if c} is replaced by -cj, for all j, then we see that A is also not upper semi-continuous in general. Our average-cost optimization problem (P) can now be formulated as: min A(x) (P) zEX We will denote the set of optimal solutions to (P) by X*. Of course, X C X* C X, in general. Incidentally, another pathological aspect of the average-cost criterion is that X* need be not closed in Y, since the optimality of a strategy x is unaffected by costs incurred over early periods.

6 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH We remark that the discounted-cost criterion is formally included in the average- cost case. Let x E X. Consider the objective function of the discounted-cost criterion 00 D(x) = Cj(sj_- (x), xj)a, j=l where 0 < a < 1. Set 3 j-1 cj(sj I(x), x) = j E C(Sii_(x),xi)a1 - C E C(Si(x),xi), Vj =2,3,... 1=1 1=1 where c' (so, x) = cl (so, x1 ). Then N N 3 1 i=i kE cj(sj_ (x),xj) = N (s_1 (x), x),', j=l l=l so that 1 N 00 A(x) = limsup c, (sji( - ), ) ) = cL(sLi-(x),xl)a1 = D(x). 3N=1 1=1 In this way, we may transform any discounted-cost problem into an equivalent average-cost problem. Our primary objective in this paper is to approximate optimal solutions of (P) by solutions of finite horizon truncations of (P). To this end, for each N = 1, 2,..., let KN be the (finite) projection of the feasible region X onto Y1 x.. x YN, i.e., KN is equal to the set of (xl,...,xN) E Y1 x.. x YN which satisfy: xj E Yj(sj-1), where sj = fj(sj-,zj), Vj = 1,2,...,N. The set KN denotes a set of N-horizon feasible strategies in the (finite) set Y1 x... x YN of all N-horizon strategies. Note that every element of KN can be feasibly completed to an element of X. Moreover, the first N decisions of every element of X lie within KN. In fact, a subset in RIN has these two properties if and only if it is the projection of X onto IRN. It is for this reason that we believe KN is the natural choice for the feasible region of the N-th approximating subproblem. Now, for technical reasons, we embed KN into Y by letting XN denote the set of all arbitrary extensions of the elements of KN, i.e., XN = KN x YN+1 X YN+2 x..., so that XN e SC(Y), all N. We shall effectively identify XN and KN. Note that if x E XN, then (sN(X), XN) E FN. Moreover, it is clear that hK+l C KN X YN+1, so that XN+I C XN, N = 1,2,..., i.e., the sets XN are nested downward. Moreover, their Kuratowski limit exists and is the infinite horizon feasible region X, as the following lemma demonstrates. Lemma 2.4. We have X = 1 XN. Thus, lim XN = X. N —oo

EXISTENCE AND DISCOVERY OF AVERAGE-COST OPTIMAL SOLUTIONS 7 Proof. Clearly, X C XN, all N, so that X C nl'1XN. Conversely, let x E n 1=XN and suppose x i X. Then 6 = d(x, X) > 0, where as usual, 6= inf d(x,y). yEX Let No be sufficiently large such that N0vo+1 2-i < 6 and y E X. If xi = Yi, 1 i < No, then d(x,y)< E 2<6, 'i=No+l which is a contradiction. Thus, for each y E X, there exists 1 < iy 6 No for which xiy 7 Yiy. This implies that x ~ XN0, which is a contradiction. For the second part, see Aubin [1990]. l We define the N-horizon average-cost optimization problem (PN) as follows: min AN(X), (PN) XEXN where N AN4(x) = N cj (sj_(x),xj), Vx e XN, j=1 is the average cost of strategy x over horizon N, VN = 1, 2,.... It will be convenient to write CN(X) = NAN(x), i.e., N CN(X) = cj(sj- (x),xj), Vx XN. j=1 Clearly, each AN: XN -+ IR is a continuous function, since AN depends only on KN, which is finite and discrete. Similarly for CN. Note that if M > N, then CM(X)- CN(X) < (M - N)B. Problem (PaN) is really an N-horizon problem since only the first N entries of x matter, i.e., if x E XN is (Pv)-optimal, then so is (xl,..., N, YN+v, YN, +2,...), where yj E Yj can be chosen arbitrarily Vj > N+ 1. We have defined (PN) in this way so that solutions to (PN) are in Y, for all N, i.e., they are comparable to each other and to the solutions of (P) as well. Hence, (PN) is effectively a finite problem which is finitely solvable (in the worst case) by enumeration of the elements of KN. The optimal solution set X* to (PNv) is then a non-empty, closed subset of Y, since KN is finite and non-empty. Thus, X* E K(Y), for all N. Although the X'N are nested downward, the X* need not be. We will denote the optimal objective value to (PN) by AN, VN = 1,2,.... Now, for each N = 1,2,... and s E SN, define XN(s) = {X E XN: SN(X) = S}, so that {XN(s): s E SN} is a partition of XN. If x E XN, then sN(x) is the unique element of SN for which x E XN(sN(x)), VN = 1,2,.. The following lemma observes that the state at time N of a strategy depends only upon the first N decisions associated with that strategy.

8 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH Lemma 2.5. Let N = 1, 2,..., and s E SN. If x E XN(s), then (X1,...,XN, YN+1,YN+2,... ) E XN(S), where yj E Yj is arbitrary for all j = N + 1,.... Proof. This follows from the definition of XN(s). O The key property that formally endows states with the intuitive notion that they should incorporate all of the information about past decisions relevant to making future decisions is formalized by the following lemma. Roughly speaking, it says that if two finite horizon feasible strategies with different horizons have the same state at the earlier horizon, followed by identical decisions to the later horizon, then a) the earlier strategy is feasible to the later horizon, with the same ending state as the later strategy, and b) the costs-per-period are the same from the earlier horizon to the later horizon. Lemma 2.6. If O < N < M < oo, x E XM, y e XN, SN(X) = SN(y) and (XN+,..., XM) = (YN+1,..., YM), then a) y E XM, SM(y) = SM(X) and b) Cj(sj_ (x), Xj) = cj(sj-i(y),yj), Vj = N + 1,..., M. Proof. Left to the reader. We will repeatedly apply the previous lemma in different contexts. Thus, it will be convenient to refer to Lemma 2.6 as being applied to the context (N, M, y, x). In particular, note that Lemma 2.5 is a consequence of the Lemma 2.6 applied to (0, M, y, x), with Xo = Y and so(x) = so(y) = so 3. Efficient Solutions The state-space formulation above associated a unique state at each time period with every infinite horizon feasible solution. Solutions that have the property of optimally reaching each of the states through which they pass are called efficient solutions (Schochetman and Smith [1992], Ryan, Bean, and Smith [1992]). Such a solution offers little opportunity for retrospective regret in that at every state along its path, there was no better way to reach that state. This efficiency of movement through the state space suggests efficient solutions as candidates for average-cost optimality. This last observation will be explored in the next section, where efficient solutions will indeed be shown to be average-cost optimal under a state reachability property. In this section, we formalize the notion of an efficient solution and prove the existence of such solutions. For each 1 ~ N < oo and s E SN, consider the problem (PN(s)) defined as follows: min AN(X) (PN(s)) XEXN(s) Optimal solutions to (PN(s)) consist of those N-horizon feasible strategies of least cost which have state s ending period N. As was the case for (PN), such optimal solutions exist and form a closed set in Y. Denote them by XN(s), so that XN(s) e K(Y), for all N and all s E SN. Remark 3.1. Let N = 1, 2,.... If x is an N-horizon optimal solution, then it is optimal to its own state N (x) ending period N, i.e., if x E X,, then x E X (SN(x)). This follows because x E XN(SN(x)) C XN. Hence, if x is least-cost over XN, the same must be true over the smaller set XN(sN(x)). For each N = 1, 2,..., define Xk to be the set of all N-horizon feasible strategies which are optimal to some feasible state s E SN, i.e.,

EXISTENCE AND DISCOVERY OF AVERAGE-COST OPTIMAL SOLUTIONS 9 X, = U X ( s ). sESN Since this is a finite (disjoint) union of closed, non-empty subsets of Y, it follows that Xk E KC(Y), for all N. Remark 3.2. For each N = 1,2,..., we have that Xk D XN because if x E X*, then x e XN(s), for the state s = SN(X) in SN. The following lemma is a version of the Principle of Optimality: any optimal solution (to its state) at time N must have been optimal to the state it passed through at each time M < N. Lemma 3.3. Let N = 1, 2,... and x E XN. If x is optimal to horizon N (necessarily with ending state SN(x)), then x is optimal to every earlier horizon M (with ending state sM(x)), i.e., if x E X (SN (x)), then x e X*(sM(x)), for all 1 ~ M < N. Proof. Let 1 < M < N. By hypothesis, x E XN C XM, so that x E XM(SM(x)), in particular. If x is not optimal for (PM(SM(x))), then there exists y E XM(SM(x)) such that AM(y) < AM(x), i.e., M M CM(y) = Cj(sja1(y), yj) < Z cj(sj_-(x), xj) = CM(X). j=1 j=1 Define = (Y1,-,YM, XM+1, XM+2.-.), so that z E XM(sM(x)) (Lemma 2.5), where sM(z) = SM(x). By Lemma 2.6, we have that z E XN(SN(X)) and CN(Z) = CM(Z) + CN(z) - CM(Z) = CM(Y) + CN() - CM(x) < CM(X) + CN(X) - CM(X) = CN(), i.e., AN(Z) < AN(X), which is a contradiction, since x is optimal for (PN(sN(x))). [ The following theorem is also a version of the Principle of Optimality: any optimal solution (to its state) at time N + 1 must have been optimal to the state it passed through at time N. Equivalently, the efficient solutions are nested downward. (Recall that the optimal solutions X* need not be nested downward.) Theorem 3.4. For each N = 1, 2,..., we have X^,+1 C XN. Proof. Let x e XN+1. Then x e X(s N+1(x)), where sN+l(x) E SN+1. By Lemma 3.3, we have that x E Xr(sN(x)), where SN(x) E SN, so that x E Xr'. D We can now formally define an efficient solution to be any solution in Y which is a member of XN, for each N = 1, 2,.... That is, the set X* of (infinite horizon) efficient solutions is given by X = noN= X. Efficient solutions may thus be characterized as feasible solutions that are optimal to each of the states through which they pass, i.e. x* E XN(SjN(X*)) for each N = 1, 2,.... Note that X* is a closed subset of Y, while X* is not closed in general.

10 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH Lemma 3.5. The set X* is non-empty, i.e., X* E K(Y). Proof. Let x* E Xk, all N. Then {xN} is a sequence in the compact metric space Y. Thus, there exists y in Y and a subsequence {X*} of {Xv} such that x* -* y in Y, as k -- oo. Fix N. By Lemma 3.3, there exists kN sufficiently large such that x*N E Xk, for all k > kN. Since X' is closed, it follows that y E Xk. But N is arbitrary. Hence, y E X*. O By the previous lemma, efficient solutions always exist in our setting. We demonstrate in the next section that, under an additional hypothesis, they are necessarily average-cost optimal. 4. State-Reachability and Average-Cost Optimality In this section, we show that, under a state-reachability property, efficient solutions are average-cost optimal. We then conclude the existence of an average-cost optimal solution under state-reachability, as a consequence of the existence of efficient solutions. Recall that for each N = 1,2,..., we have X C XN, so that {sN(x): x E X} C SN Conversely, since every finite horizon feasible strategy is extendable to a feasible infinite horizon strategy, we have that {SN(x): x E X} SN, so that SN ={sN(x): xeX}, VN=1,2,..., i.e.. every N-horizon feasible state is realizable as the N-horizon state of some infinite horizon feasible solution. Thus, there is no distinction between finite and infinite horizon feasible states. We now present a notion of bounded state-reachability which requires roughly that it be possible to feasibly reach any state within a bounded number of periods from any other feasible state. Definition 4.1 (Bounded Reachability Property). There exists a positive integer R such that for each 1 K K < oo, each s E SK and each finite sequence of states (tK,..., tK+R) in SK X - * * X SK+R, there exists K ( L ( K + R and y E XL for which sK(y) = s and SL(y) = t(L). We will refer to this as the Bounded Reachability Property for (K, s; (tK,..., tK+R)). If there exists R > 0 for which this property holds for all K, s; (tK,...,tK+R), then problem (P) is said to satisfy Bounded Reachability. We now can prove the main result of this paper. Theorem 4.2. Suppose (P) satisfies Bounded Reachability. Then every efficient solution is average-cost optimal, i.e., X' C X*. Proof. Let v E X*. Since X* = liminfN XN, there exists a sequence {sN} and a corresponding sequence {Xs:(SN)} such that SN E SN, x*(SN) E X{(sN), all N, and x*(sN) -- v in Y, as N -+ oo. Since XK*(SN) C XN, all N, it follows that v e liminfNh XN = X, i.e., v is feasible for (P). We next show that v is optimal for (P), i.e., A(v) < A(x), Vx E X, so that v E X*. Let x be an arbitrary element of X. Fix 1 ( K < oo. Let nk be as in Lemma 2.1, B as in section 2 and R as in the Bounded Reachability Property. Fix T sufficiently large so that T ) nk and T > K + R. Without loss of generality, we may assume that nk K h+ R. Set N = T and y = x*(T, sT) for convenience, so that

EXISTENCE AND DISCOVERY OF AVERAGE-COST OPTIMAL SOLUTIONS 11 ST(Y) = ST and y is optimal for (PT(ST)). Since x*(N, SN) -+ v, as N -~ oo, and T 0 nk, it follows from Lemma 2.1 that yj = vj, j = 1,..., K. Furthermore, since so is the initial state for all strategies, we have that SK(V) = SK(Y) and cj(sj-_(v),vj) = cj(sji(y),yj), Vj = 1,..,, by Lemma 2.6 applied to (0, K, y, v) (or (0, K, v, y)). Applying the Bounded Reachability Property to (K, SK(X); (SK(y),... SK+R(Y)), there exists K < L 6 K + R and z E XL such that SK(Z) = SK(x) and SL(Z) = SL(Y). Observe that z E XL(SL(z)) = XL(SL(Y)) and y E XT C XL. *** Insert Figure 1 here *** Now let W= (X1,...,XK, ZK+1,..., ZL, YL+1, YL+2,-..). Then w E XK(SK(X)) (Lemma 2.5), so that SK(W) = SK(X) = SK(Z), w e XL(SL(Z)) = XL(SL(Y)), Sj_-(w) = Sj-l(Z), SL(w) = sL(Z) = SL(y), and cj (sj-(W), Wj) = cj (S.,-1(),Zj), Vj = K + 1,...,L, by Lemma 2.6 for (K,L,w,z). Similarly, by Lemma 2.6 for (L,T,w,y), we have that w E XT(ST) = XT(ST(Y)), ST(w)= = S = T(), Sj_ 1 (W) = Sj- i(y), and cj(sj-_(w),wj) = C j(sl(y),yj), Vj = L +,...,T. Since y is optimal for (PT(ST)), it follows that CT(w) > CT(y). But CT(w) = CK(W) + [CL(W) - CK(w)] + [CT(w) - CL(W)] = Ch'(Z) + [CL(Z) - CK(Z)] + [CT(Y) - CL(Y)], and CT(Y) = CK'() + [CL(y) - CK(Y)] + [CT(Y) - CL(Y)] = CK(V) + [CL(y) - CK(Y)] + [CT(W) - CL(W)], so that CK(V) < CK(x) + [CL() - CK(Z)] + [CK(Y) - CL(Y)], which implies that CK(v) < CK(X) + 2(L - K)B < CK(x)+ 2RB.

12 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH Hence, 2RB AK(V) AK(x) + -, K where K is arbitrary. Consequently, A(v) = lim sup AK(v) K 2RB ( lim supAK(x) + lim sup K K K = A(x), which implies that v E X*. Thus, X* C X*. Corollary 4.3. Suppose (P) satisfies Bounded Reachability. Then there exists an average optimal solution for (P), i.e., X* # 0. Proof. Follows from Lemma 3.5 and Theorem 4.2. D 5. Optimal Solution Convergence We showed in the previous section that efficient solutions, in the presence of Bounded Reachability, are average-cost optimal, i.e., 0 $ X* C X*. However, in general, the inclusion is strict, X* C X*, i.e., there are average-cost optimal solutions which may fail to be efficient. This is clear since average-cost optimality is a long-run property while efficiency is a short-run property. It is in this sense that efficient solutions strengthen the under-selective criterion of average-cost optimality (Hopp, Bean, and Smith [1987]). Moreover, efficient solutions inherit the long-run properties of average-cost optimality through their behavior in the short-run, i.e., optimality to every state through which they pass. It is this latter characterizing property that we exploit in this section to approximate an efficient, and hence average-cost optimal, solution by solving for short-run optimal solutions to (P). The following result says that the N-horizon efficient solutions Xk arbitrarily well approximate the infinite horizon efficient solutions X*, for sufficiently long horizon N. Lemma 5.1. (Average-Cost Optimal Solution Set Convergence) The sequence {Xk} of N-horizon efficient solution sets converges in KC(Y) to the set X* of all infinite horizon efficient solutions. Proof. This follows from the definition of X* and Theorem 3.4. D The previous lemma assures us that for every efficient solution x* E X*, there is a sequence of N-horizon efficient solutions x* E X' which converges to x*. We turn next to the problem of finding such a selection {X* } from the {Xk}. Following Ryan, Bean, and Smith [1992], we recall the notion of lexicomin of a subset of '. Define the lexico order -< on Y as follows. For x, y E Y, x -< y if there exists a positive integer k for which xj = yj, for j = 1,..., k - 1, and Xk < yk. We will write x -< y if x = y or x -< y. Clearly, ~ is a partial order on Y. Since it also satisfies the Law of Trichotomy, i.e., for each x, y E Y, either x < y, x = y or y -< x, the relation -< is a linear order on Y. It will be convenient to denote the element (0,0,...) in the compact metric space Y by 0. The following lemma shows that for our choice of /, i.e., 0 < 3 < 1/(m + 1), the distances to elements of Y from 0 determine the lexico order -<. Lemma 5.2. Let x,y E Y. Then x -< y if and only if d(8,x) < d(8,y). Hence, x = y if and only if d(O,x) = d(, y).

EXISTENCE AND DISCOVERY OF AVERAGE-COST OPTIMAL SOLUTIONS 13 Proof. Suppose x -< y. Let k be such that xj = yj, for j = 1,...,k - 1, and Xk < yk. Then, 00 d(, y) - d(O, x) = Y [lyjl - jxj I = j(yj — 1X) j=l oo 3=1 = k(k - xk) + Z /j(yj -Xj), j=k+l where yk - Xk > 1 and 00 oo SE j(yj - Xj) -m E pi j=k+l j=k+l oo = -mk+l E j j=0 pk+l =-1 Consequently, d(S, y)- d(, x) k_ mfc+ /3k(1 -m3p) 1-/3 >0, since 3 < 1/(m + 1). Conversely, suppose d(6, x) < d(9, y). By the Law of Trichotomy, we have that x < y, x = y or y < x. But it can't be that y = x or y -< x, since it would then follow as above that d(0, y) d(O, x). Hence, x < y. Now let V be an arbitrary non-empty subset of Y and A E Y. We define A to be a lenicomin of V if A E V and A -< x, for all x E V such that x ( X. Note that lexicomins are unique, when they exist. (Suppose A and u are distinct lexicomins of V. Then A -< M and p -< A necessarily, and without loss of generality, it follows that there exists a positive integer k such that Ak, /lk and Ak < Ak. Contradiction.) We will denote the lexicomin of V by A(V), whenever it exists. Example 5.3. To see that lexicomins do not exist in general, in Example 2.3, let n y = (00,..0, 1,...0...), Vn=1,2,... and V = {y, Y... ). Suppose A is the lexicomin of V, where Aj O0, Vj = 1,2,.... Clearly, A = 0 necessarily, which is a contradiction, since 0 V. The following lemma emphasizes that a lexicomin is a nearest point selection.

14 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH Lemma 5.4. Let V be a subset of Y and x E V. Then x is the lexicomin of V if and only if x is the point in V nearest to 0. Proof. Follows immediately from Lemma 5.2. 0 The following lemma assures us that such a nearest-point selection from a set exists whenever the set is closed. Lemma 5.5. Let V be a closed non-empty subset ofY. Then there exists a (unique) lexicomin of V. In particular, 0 is the lexicomin of Y. Proof. The function x -- d(0, x) is continuous on the compact set V. Hence, it attains its minimum at some point of V, which is necessarily the lexicomin of V by the previous lemma. E The converse of this lemma is not true in general. Example 5.6. Let x' be as in Example 2.3, Vn = 1,2,..., and define V = {, x1, x2,... }. Then V is not closed in Y and 0 is clearly the lexicomin of V. The following proposition assures us that the lexicomin selection from a sequence of Kuratowski-converging sets is convergent. Proposition 5.7. Let {F,} be a sequence in WC(Y) which converges to F in IC(Y). Then the sequence {A(Fn)} converges to A(F) in Y. Proof. In the terminology of Schochetman and Smith [1989], 0 is a uniqueness point for F and {A(F,)} is a nearest-point selection from the F, defined by 0. The result then follows from Theorem 3.4 of Schochetman and Smith [1989]. 0 We are now in position to obtain our average-cost optimal solution convergence result in terms of solution strategies instead of solution strategy sets. Theorem 5.8. (Average-Cost Optimal Policy Convergence) The sequence {X(Xk} of lexicomin N-horizon efficient solutions converges in Y to the lexicomin infinite horizon efficient solution A(X*), i.e., lim A(Xk) = A(X*). N —+O Proof. Recall that Xk -> X* in AC(Y), as N -+ oo. Since X* and the Xk are closed and non-empty, each contains a lexicomin denoted by A(X*) and A(Xk), respectively, VN = 1, 2,.... By Proposition 4.7, we have that lim A(X,) = A(X*) N-_oo in Y, where A(X*) e X*, i.e., it is an optimal solution for (P). Thus, we have average-cost optimal solution convergence in the familiar point sense. O 6. Value Convergence In the previous section, we demonstrated policy convergence of solutions of the approximating problems (PN) to an infinite horizon average-cost optimal solution of (P). However, since the average-cost operators AN fail to converge uniformly to A (indeed, A is not a continuous function in general), we cannot conclude value convergence in the average-cost case. In particular, as the next example illustrates, the optimal average cost A+* of problem (PN) need not converge to the optimal average cost A* of (P); in fact, it need not converge at all.

EXISTENCE AND DISCOVERY OF AVERAGE-COST OPTIMAL SOLUTIONS 15 Example 6.1. Let the non-cost data be as in Example 2.3. However, this time define each cj differently. Observe that the set of half-open, half-closed intervals {[3k, 3k+1): k = 0, 1, 2,...} yields a partition of the half-line [1, oo). Thus, for each integer 1 < j < oo, there exists a unique non-negative integer kj satisfying 3kj < j < 3kc+l. For each j = 1, 2,..., define cj to be the constant function equal to aj on Sj_1 x Yj, where 0f, if kj is even, aj 1, if kj is odd. Observe that in this case, Xv = XN, where y E XN if and only if there exists a positive integer 1 < jy N satisfying j = 1, 1...,, yj= O j = jy,...,N, arb., j = N+ 1,.... Moreover, N A = aj, VN= 1,2,..., j=l 3,9 1 To show that the sequence {AN} does not converge, we show that the disjoint subsequences {A*2k}~ and {A,2fc+ }~ are bounded away from each other. We have: A3k = 3[(32 - 3) +... + (32k-1 - 32k-2)] 32k-1 < 32k 1 = - Vk =0,1,2,..., 3, while A3*+ = 321 [(32 -3) +... + (32k-1 - 32k-2)] + 32k1 (32k+1 _ 32k) 32k+1 1 (32k+ 32k) 32k+-( - 32k 32k+l 2 =2 Vk = 0,1,2,.... 3, Thus, the sequence {Aj} does not converge at all. Despite the previous counter-example, there is a weaker sense in which the optimal average-cost values {ANv} of the subproblems (PN) approximate the optimal average-cost value A* of the problem (P). Theorem 6.2. Suppose (P) satisfies Bounded Reachability. Then A* = lim sup AN. N

16 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH Proof. Let x* E X* (Lemma 3.5) and x4 E XN, so that A* = A(x*) (Theorem 4.2) and A* = AN(X*), VN = 1,2,.... Since x* E X and X C XN, it follows that x* E XN, so that AN(X) AN(X*), VN=1,2,.... Hence, since both sequences are bounded, by the results of Goldberg [1964], we have that lim sup AN(x4) * lim sup AN(x*), N N i.e., lim sup A*v A*. N Conversely, let R be as in the Bounded Reachability Property. Fix N > 2R, so that M = N - R > R, and set v = x*4 for convenience. Applying the Bounded Reachability Property to the data (M, SM(V); (SM(X),..., S(X*))), we conclude that there exists M < L < N and w E XL such that SM(w) = SM(V) and sL(w) = sL(x*). Define Z = (V1,...,VM,WM+1,... - WL, XL+_, XL+_2,..-). *** Insert Figure 2 here *** Clearly, z E XL by Lemma 2.6. Also by Lemma 2.6 for (L,N,z,x*), we have that z E XN, SN(z) = SN(X*), SO that z E XN(SN(X*)), and cj(sjl(z), j) = cj(sj-l(X*),Xj), Vj = 1,2,...,N. Also recall that since x* E X*, we have that x* E Xv(SN(X*)). Since x* is an optimal solution to (PN(SN(X*))) and z E XN(sN(X*)), it follows that CN(X') < CN(z) = CM(Z) + [CN () - CM(z)] < CM(Z) + (N - M)B = CM(Z) + RB ~ CM(V) + RB = CN(V) + [CM(v) - CN(v)] + RB < CN(v) + ICN(v) - CM(V)I + RB CN(V) + (N- M)B + RB =CN(V) + 2RB, so that 2RB AN)(x*) AN(v)+ — N for N > 2R. Hence, by the results of Goldberg [1964], we have

EXISTENCE AND DISCOVERY OF AVERAGE-COST OPTIMAL SOLUTIONS 17 A* = lim sup [AN(X*)] O lim sup AN(V)+ 2R N N RB < lim sup [AN(v)] + 2 limr N N ---oo N = lim sup AN(V), N i.e., A* < lim sup Av, N which completes the proof. O Remark 6.3. Theorem 6.2 says that A(x) = limsupN AN(xN), for x = x* E X* and XN = XN X~, VN = 1,2,.... For a general sequence {xN} such that xN E XN, all N, even if xN -- x in Y, as N -) oo, it is not necessarily the case that A(x) = limsupN AN(xN). Thus, the convergence claimed in Theorem 6.2 is restricted to optimal average-cost values, unlike in the discounted case. 7. A Next-Decision Forward Algorithm We know from average-cost optimal policy convergence (Theorem 5.8) that the first decision of the lexicomin efficient solution to problem (PN), for large N, is the same as the first decision of the lexicomin infinite horizon average-cost optimal solution. (Note the trivial nature of this claim when made with respect to an arbitrary average-cost optimal solution, since finite leading decisions are irrelevant to the property of being average cost optimal!) A finite algorithm for discovery of this first decision is then lacking only a procedure for numerically discovering how large N must be for the claimed invariance to occur. We incorporate the determination of such a horizon, called a solution horizon (Bes and Sethi [1988]), within the forward algorithm below. We find the efficient solution set and the associated lexicomin solution for increasingly longer horizons N, until a stopping rule is met. At this point, a solution horizon has been discovered; hence, the first decision of the lexicomin infinite horizon average-cost optimal efficient solution has also been discovered. (The algorithm is similar in spirit to that proposed in Lasserre [1986] in the discounted case except that we use a lexicomin selection thus avoiding the assumption there that the optimal first decision is unique.) Forward Algorithm (1) Set horizon N = 1. (2) Find the set X;,(SN) of all solutions optimal to state SN at horizon N, for each state SN in the set SN of all N-horizon feasible states. (3) Determine the lexicomin efficient solutions AX(sN) to state SN at horizon N, for all feasible states SN E SN. Set the lexicomin efficient solution AN for horizon N equal to the lexicomin of {A\(SN): sN E SN}. (4) (Stopping Rule) If (SN)1 = (AN(sN))l, for all SN E SN, stop. The first decision of the lexicomin infinite horizon average optimal solution is A; = (A*(N))1. Otherwise, increment the horizon N to N + 1 and go to step 2. It is clear from the Principle of Optimality that if the Stopping Rule is met, then the first decision of the lexicomin infinite horizon efficient solution has been found. The next theorem provides a sufficient condition that guarantees the Stopping Rule will eventually be met.

18 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH Theorem 7.1. Suppose that for every choice ( s, s2,...) in N=i SN, we have that lim X (SN) = X* N-+oo in KC(Y). Then the Stopping Rule holds at some 1. N < oo. Proof. For each N = 1,2,..., and each SN E SN, let AN (sN) = lexicomin of X* (SN), Av = lexicomin of Xv and A* = lexicomin of X*. Note that A* must be in X*(rN), for some unique rN E SN, by definition of Xk. Necessarily, A* is the lexicomin of X (rN), ie, A = A*(rN), VN = 1,2,... Now suppose that the hypothesis is satisfied, but not the Stopping Rule. Then, for each N = 1,2,..., there exists tN E SN such that rN # tN and (AX(tN))l # (=A(rN))l = (AX)1. If not, then the Stopping Rule would be satisfied at any N where this was not the case. But we have seen that AN - A* in Y, so that (A*N)1 = A, for large N (Lemma 2.1). Consequently, (AN(tN))1 # A*, for large N. But, by hypothesis, lim X* (tN) = X, so that lim A*(tN) = A*, V — oo which implies (Lemma 2.1) that A* (tN)i = A\, for large N. This is a contradiction. O The hypothesis of Theorem 7.1 is unfortunately difficult to establish directly in specific cases. We can however provide a sufficient condition for this hypothesis which, although quite strong, is not vacuous (see section 8 for an instance where it is met). Theorem 7.2. If X* is a singleton {x* }, then the hypothesis of Theorem 7.1 is satisfied. Proof. Let SN E SN, for each N = 1,2,.... It suffices to show that limsup X,(sN) C {x*} N and x E liminf Xv (sN). N If x E limsupN XN(sN), then x E limsupN X^, by definition of Xk. But limsupN XN = X*, so that x = X* by hypothesis. Conversely, since limNO,, Xk = X*, x' is the limit of any selection from the Xk. In particular, x* is the limit of any selection from the X*(sN), i.e., x' E liminfN X*(SN). ~ From a practical point of view, it is important to note that even in the absence of conditions that guarantee that the Stopping Rule will eventually be met, if for whatever reason the Stopping Rule is eventually met in an application of the forward algorithm, then we are assured that the first decision of an efficient infinite horizon average-cost optimal solution has been found.

EXISTENCE AND DISCOVERY OF AVERAGE-COST OPTIMAL SOLUTIONS 19 8. Application to Equipment Replacement Virtually every discrete infinite horizon decision making problem is included within the framework of the general problem (P) posed in section 2. We illustrate this claim here with the problem of acquiring and retiring equipment over an infinite horizon in the presence of technological change (Denardo [1982], Bean, Lohmann, and Smith [1985], [1994]). We also establish that the key property of Bounded Reachability is satisfied for this case. Suppose that we have a single piece of equipment in place at the beginning of period 1. At the beginning of each succeeding period j, we have the option of. keeping the equipment in place or replacing it by one of mj new alternative equipment types, Vj = 1,2,.... We denote this set of possible decisions available at the beginning of period j by Yj = {0,1,2,...m,}m, Vj = 1,2,..., where 0 denotes the decision to retain the current piece of equipment, and 1 < k s mj denotes the decision to replace the current piece of equipment by one of technology type k when mj ) 1 (if mj = 0, we are not allowed to replace the equipment in period j). Note that a piece of equipment of type i in period j may not be the same type as a piece of equipment of type i in period k # j. For convenience, we assume that there exists an upper bound on the number of different technologies, i.e., m _ supj mj < oo, so that to avoid the trivial case m > 1. It will also be convenient to let Yo = {1} and mo = 1, corresponding to the equipment type in place at the beginning of period 1. Associated with each equipment type k in period j is its physical life lj(k), which represents its maximum useful economic life, so that for each j = 0, 1, 2,..., we have a function Ij: {1,...,mj}- N. In particular, lo(l) is the maximum life of the initial piece of equipment. We assume that sup max lj(k) < oo, lj<oo 1<k<mj i.e., any type of equipment in any period has a maximum useful life. For each j = 1, 2,..., define the function r: Y - {0,1,...,j} by rj ( max{i j: yi > 0}, if there exists 1 < i < j for which yi > 0, 0, if = 0, Vi = 1,...,j, for each y E Y, so that rj(y) depends only on yl,..., yj. Thus, following strategy y, when rj(y) is positive, it represents the period (at or before period j) in which we last replaced equipment. If it is zero, the equipment in place in period j is the original equipment we started with at the beginning of the problem. In particular, if y E XN, then rN(y) is the period at or before N of last replacement following strategy y. Similarly for y Y. We next introduce the state spaces. At time 0, the age of the original piece of equipment is (for convenience and without loss of generality) defined to be 1. Thus, the residual life of the original piece of equipment at time 0 is lo(l) - 1. In period N, the state (k, h) will correspond to being at the beginning of period N with a piece of equipment of type k that was acquired h periods ago, so that so = (1, 1). Thus, for each N = 1,2,..., define SN={(k,h) EN x: l< h e N-h+l(k), l<kc mNh-h+1}.

20 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH For convenience, let So = {so} = {(1, 1)}. Note that tN-h+l (k) denotes the physical life of a type k piece of equipment acquired in period N - h + 1. If y E XN, then SN(Y) = (YN(y), N - rN(y)+ 1), VN = 1,2,.... Necessarily, if N = 1, 2,... and s = (k, h) E SN, then XN(S) = { E XN: sN(y) = (k, h)}, i.e., XN(k,h) = {y E XN: rN(y) = N- h+ 1, YN-h+1 = k}. Fix j > 1 and sj-1 E S-jl. Then sj_i = (k, h), where 1 < h j, 1 < k < mj-h and h < fj-h(k). Then define Yj(sj-) = Yj (k, h) as follows: Y, (k, h) {Yj, if h < lj-l(k), Yj(kh) = {YjY\{0}, if h > _l(k). Yi(fO})j, 1- < Lemma 8.1. Let j > 1, 77 E Yj and (k, h) E N x N. Then ((k, h),7r) E Fj if and only if 1 S h < j, 1 k < mjh, h < lj-h(k), and 0 r1 <mj, if h < lj-_(k), l r 7 Smj, if h > Ij-_(k). Proof. Omitted. Now fix j > 1. Define fj: Fj -- Sj as follows:,.,,,, f (k,h t+l), if r/=0, fj((kh), l) (kh+), f 7 0, (77,1), if r7 0, for each ((k, h), r) E Fj. Lemma 8.2. For each j = 1, 2,..., we have that Sj = {fj(sj,,yj): sj1_ E Sj_1, yj E Yj(sj-l)}. Proof. Omitted. The cost of acquiring and operating a new piece of equipment in period j involves a) retiring the current piece of equipment, b) receiving a salvage value, c) acquiring the replacement equipment at a cost-topurchase, and d) operating that equipment over the periods it is kept. In particular, for j = 1,2,..., let Ij = {0, 1,..., j} for convenience, and assume we are given the following data: pj(k) = the purchase price at the beginning of period j of one unit of a piece of equipment of type k, for k = 1,2,...,mj, so that p3: Y\{O} - R

EXISTENCE AND DISCOVERY OF AVERAGE-COST OPTIMAL SOLUTIONS 21 where we assume that p =supmax{pj (k): k = 1, 2,..., mj < oo; the j-th period cost of operating a piece of equipment of type k which was acquired h periods ago, (kh) for k = 1,..., mj-h and h = 0,... j - 1, jj(k, h) = the j-th period cost of operating the original piece of equipment, for k = 1 and h = j, so that Wj: Yj x Ij - X, where we assume that w supmax{wj(k,h): h =,...,j; k = 1,..., mj < oo, and the salvage value at the beginning of period j of a piece of equipment of type k which was acquired h periods ago,, h) for h = 0,..,j-1 and k = 1,...,mj_h, ~j(k, h)= the salvage value at the beginning of period j of the original piece of equipment, for k= 1 and h=j, so that j: Yj x Ij - R, where we assume that v supmax{vj(k, h): h = 0,...,j; k=,...,mj} < oo. 3 We turn now to defining the cost functions cj. Fix j = 1, 2,.... For fixed y E Xj, with sjl(y) = (k,h), let c (s (-y),y )= f pj(yj) + wj(yj, O) - vj(sj_(y)), if yj > 0, = j(Sj- 1 (y) + (0, 1)), if yj = 0, i.e., c ((k, h) y) Pj (yj) + wj (yj, 0) - vj (k, h), if yj > 0, It then follow), tif yf =0. It then follows that for B > p + wu + v, we have that ci (sj - 1 (), yj) < B, Vj=1 1. y E Xj

22 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH The set Y of all infinite replacement schedules (feasible or not) is the product of the Yj, i.e., Y = IJ.l Yj As in ~2, this is a compact metric space. We turn now to describing the feasible replacement schedules X, i.e., those replacement schedules in Y which can be implemented. Fix a replacement schedule y E Y and, for convenience, let rj = rj(y), Vj = 1,2,.... Then y is feasible if, in every period j, the age j - rj of the current piece of equipment does not exceed the maximum life rj (yrj) of that piece of equipment, i.e., y E X if and only if the feasibility condition j - rj < tr (yr ) is satisfied for all j 1,2,.... Thus, we have: Lemma 8.3. The feasible region X consists precisely of those y E Y for which j - r(y) < fr,(y)(Yr,(y)), Vj = 1, 2,.. In particular, X # 0. Proof. Note that X # 0 since (1, 1,...) E X. O To complete the application of our model to equipment replacement, we must establish the following property. Theorem 8.4. The Bounded Reachability Property holds for the Equipment Replacement under Technological Change Problem. Proof. Let R be a positive integer such that R i sup max ej(k) lj<oo 1ik<mj which we have assumed to be finite. Let 1 S K < oo, s = (k, h) E SK, so that 1 < h s K + 1 necessarily, and let tK+j = (UK+j, vK+j) E SK+j, Vj = 0,..., R, so that vj < R, K j K + R. Let L= K + R. To choose y XL, observe that 1 VK+R R, so that K + R - K+R + I ) K +1, where the quantity on the left is the time at which the piece of type UK+R equipment (in place in period K + R) was installed. Let z E XK be such that sK (z) = s = (k, h), and define y E Y as follows: Zj, j=17..., K, 1, j = K + 1,...,K + R-K+R, Yj UK+R, j = K + R-VK+R +, O, j = K + R-VKR+ 2,...,K +R, arb., j= K+R+l,...,oo. Then y E XL because we have chosen a piece of equipment of the type available and its physical life has not been exceeded. Moreover, it is clear that sK(y) = s = (k, h),

EXISTENCE AND DISCOVERY OF AVERAGE-COST OPTIMAL SOLUTIONS 23 and SL(y) = tL = (UK+R, VK+R). This completes the proof. O Consequently, all of the previous results hold for this model. In particular, the Forward Algorithm of section 7 may be employed, whenever the Stopping Rule is eventually met, to find the next replacement decision in a rolling horizon procedure, to recover an optimal replacement schedule over the infinite horizon. Similar stopping rules have been empirically observed to be usually met in practice, at least in the discounted-cost case (Bean, Lohmann, and Smith [1985]). A sufficient theoretical condition for it to be met in the average-cost case is (by Theorem 7.2) that X* = {x*}. For example, in the classic problem of replacing equipment under stationary technology, since the problem is mathematically equivalent to a knapsack problem, a singleton efficient solution obtains whenever the turnpike policy equipment type that minimizes the infinite horizon average-cost under a stationary replacement strategy is unique (Gillmore and Gomory [1966]). We note that it is not difficult to extend this observation to the nonstationary case of technological change. Acknowledgment: We are grateful to an anonymous referee for several suggestions that significantly improved the clarity of the exposition. REFERENCES 1. Aliprantis, C. and K. C. Border, Infinite Dimensional Analysis: A Hitchhiker's Guide, Springer-Verlag, NY, 1994. 2. Aubin, J.-P., Set-Valued Analysis, Birkhauser, Boston, 1990. 3. Bean, J. C., Lasserre, J. B., and R. L. Smith, Denumerable State Nonhomogeneous Markov Decision Processes, Journal of Mathematical Analysis and Applications 153 (1990), 64-77. 4. Bean, J. C., Lohmann, J. R., and R. L. Smith, Equipment Replacement Under Technological Change, Naval Research Logistics 41 (1994), 117-128. 5. _, A Dynamic Infinite Horizon Model, The Engineering Economist 30 (1985), 99-120. 6. Bean, J. C. and R. L. Smith, Conditions for the Existence of Planning Horizons, Mathematics of Operations Research 9 (1984), 391-401 August, 1984.. 7. Berge, C., Topological Spaces, Oliver and Boyd, London, 1963. 8. Bes, C. and S. Sethi, Concepts of Forecast and Decision Horizons: Applications to Dynamic Stochastic Optimization Problems, Mathematics of Operations Research 13 (1988), 295-310. 9. Denardo, E. V., Dynamic Programming: Models and Applications, Prentice-Hall, Englewood Cliffs, 1982. 10. Derman, C.,, Denumerable state Markovian decision processes - average cost case, Annals of Mathematical Statistics 37 (1966), 1545-1554. 11. Federgruen, A. and H. C. Tijms, The Optimality equation in average cost denumerable state semi-Markov decision problems, recurrency conditions and algorithms, Journal of Applied Probability 15 (1978), 356-373. 12. Gillmore, P. C. and R. E Gomory, The Theory and Computation of Knapsack Functions, Operations Research 14 (1966), 1045-1074. 13. Goldberg, R. R., Methods of Real Analysis, Blaisdell Pub. Co.. Waltham, 1964. 14. Hausdorff, F., Set Theory, 2nd ed., Chelsea. New York. 1962. 15. Hopp, W. J, Bean, J. C. and R. L Smith, A New Optimality Criterion for Non-homogeneous Markov Decision Processes, Operations Research 35 (1987), 875-883. 16. Kuratowski, K., Topologie I, II, Academic Press. New York, 1966. 17. Lasserre, J., Detecting Planning Horizons in Deterministic Infinite Horizon Optimal Control, IEEE Transactions on Automatic Control 31 (1986), 70-72. 18. Park, Y., Bean, J. C. and R. L Smith, Optimal Average Value Convergence in Nonhomogeneous Markov Decision Processes, Journal of Mathematical Analysis and Applications 179 (1993), 525-536. 19. Puterman, M. L., Markov decision processes: discrete stochastic dynamic programming, John Wiley & Sons, New York, 1994. 20. Ross, S.,, Non-discounted Denumerable Markov Decision Models, Annals of Mathematical Statistics 39 (1968), 412-423. 21.., Introduction to Dynamic Programming, Academic Press, NY, 1983.

24 IRWIN E. SCHOCHETMAN AND ROBERT L. SMITH 22. Ryan, S. M., Bean, J. C., and R. L Smith, A Tie-breaking Algorithm for Discrete Infinite Horizon Optimization, Operations Research 40 (1992), S117-S126. 23. Schochetman, I. E. and R. L Smith, Infinite Horizon Optimization, Mathematics of Operations Research 14 (1989), 559-574. 24., Finite Dimensional Approximation in Infinite Dimensional Mathematical Programming, Mathematical Programming 54 (1992), 307-333.

o) 0 -I, (D c C (D I m (D (D o 0 CDlt CD o 0 o 0) 0 I CC X-. ---------- N en v U);r - -IC) l7I en r- -----------?C -i x N

C, 0 -I. C(D ID 0 _0 mo 3 Q) (D a) C) 0 CQ 0 CD 0 (D e) Cl) 15 (0 cn -- z 11 I eC) x 3, C) IX* II 0) III C) N () I-.1 --- —------- Z C) 0-1% V) z x * C) z -L N X