SET CONVERGENCE IN INFINITE HORIZON OPTIMIZATION Technical Report 87-2 Robert L. Smith Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 Irwin E. Schochetman Department of Mathematical Sciences Oakland University Rochester, Michigan 48063 December 1986

SET CONVERGENCE IN INFINITE HORIZON OPTIMIZATION Irwin E. Schochetman Department of Mathematical Sciences Oakland University Rochester, Michigan 48063 Robert L. Smith Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 December 1986 Abstract We consider the question of convergence of a sequence of closed (non-empty) subsets of a compact metric space in the space of all such subsets equipped with the Hausdorff metric. We obtain equivalent conditions for convergence in terms of (1) equality of liminf and limsup sets and (2) pointwise convergence properties of continuous set selection mappings defined on the metric space of closed subsets. We then apply these results to obtain necessary and sufficient convergence criteria for the finite horizon optimal solution sets encountered in a general infinite horizon optimization problem. Key Words and Phrases Compact metric space, space of closed subsets, Hausdorff metric, limit sets, selection, uniqueness point, nearest-point selection, infinite horizon optimization, finite horizon optimal strategies. 1 Introduction In recent years a number of authors have studied various versions of infinite horizon optimization problems. Of particular interest to us are the papers by Bean and Smith [2], Bes and Sethi [3] and Schochetman and Smith [10]. In each of these cases, as well as others, we have a compact metric space (X, d) of feasible infinite horizon siraiegies and a discounted cumulative net cost function C(x) defined for x in X. The problem is to 1

find inf C(x). xEX Under varying hypotheses, the infimum is attained, thereby giving rise to a non-empty, closed (hence compact) subset X* of X consisting of optimal strategies. The finite horizon approach to approximating the elements of X* consists of truncating the cost function C(x), for each, at finite horizon times T > 0, thus giving rise to the problem of finding inf C(x,T), xEX for each T > 0, where C(x,T) is the T-horizon truncated cost C(x) for x in X. These infima are also attained, yielding non-empty, closed subsets of X denoted by X*(T),T > 0. Consequently, we are led to the problem of defining and determining convergence of the X*(T) to X*. More generally, this suggests the problem of studying convergence of closed sets. Problems of this type, in different contexts, have been studied in the past by several authors. Of particular interest to us are the papers by Michael [9], Fell [6] and Effros [5]. Our motivation is to extend the results of these authors so as to give relevant answers to our infinite horizon closed set convergence problem. In section 2 we discuss the Hausdorff metric D (corresponding to d) on the space C(X) of closed, nonempty subsets of X and compare the underlying metric topology on this space with two other possible topologies-the finite topology of Michael [9] and the H-topology of Fell [6]. Given a sequence {Fi} in C(X), Effros [5] defines two limit sets, liminf Fi and limsup Fi, for this sequence. In section 3, we characterize each of these sets in a form amenable to our problem of interest and establish various additional properties. In section 4, we show that a sequence in C(X) converges with respect to D if and only if its limsup and lim inf are equal, in which case the limit of the sequence is this common set. For purposes of approximating an infinite horizon optimum, it is more important to be able to obtain a corresponding sequence of points {xi} from the sequence {Fi} of sets which converges to a point x in the limit set of the sequence. This suggests the study of selections defined on C(X) and their continuity properties. Particular selections, which we call nearest-point selections corresponding to "uniqueness-points," play a special role. This is the subject matter of section 5. Finally, in section 6, we apply the main results of the previous sections to the closed sets X*(T),T > 0, of our infinite horizon optimization problem, obtaining several equivalent conditions for the X*(T) to converge in the Hausdorff metric. 2 Topologies for Closed Subsets Let (X, d) denote an arbitrary compact metric space and C(X) the set of all non-empty, closed (hence compact) subsets of X. For each x in X, the mapping y -X d(x, y) is continuous on X. Thus, for each K in C(X), the minimum of d(x, y), for y in K, is attained and we may define d(x, K) = min d(x, y), x E X, K E C(X). yEK Moreover, for each such K, the mapping x -- d(x, K) is also continuous on X [4, Theorem 4.2]. Hence, for each C in C(X), the maximum of d(x, K), for x in C, is also attained and we may therefore define h(C,K) = maxd(x, K), C,K E C(X). xEC Although h is not a metric on C(X) (it's not symmetric), we can obtain a metric D on C(X) if we define D(C, K) = max(h(C, IK), h(K, C)), C, K E C(X). 2

This is the well-known Hausdorff metric on C(X) [4,7,8,9]; it satisfies D({x}, {y}) = d(x, y), x, y E X. Moreover, (C(X), D) is a compact metric space [9, Theorem 4.2]. In additon to this topology on C(X), there is the finite topology of E. Michael [9] and the H-topology of J. M. G. Fell [6]. However, as observed in [6,9], the finite topology, the H-topology and the Hausdorff metric topology are all the same on C(X), since X is compact and Hausdorff. Thus, for the remainder of this paper, it will be convenient to discuss convergence in C(X) in terms of the Hausdorff metric D only. 3 Limit Set Results Since C(X) is a metric space, it is first countable (in fact second countable), so that it suffices to consider convergence for sequences in C(X). Although we will ultimately be interested in convergence for a family of closed sets indexed by the positive reals, this poses no difficulty, since all our results are valid for such families as well. Thus, there is no harm in considering convergence for the more appropriate and convenient case of sequences in C(X). Let {Fi} be a sequence in C(X). As in [5], define liminf Fi (resp. limsup Fi) to be the set of all x in X such that every neighborhood of x is eventually (resp. frequently) intersected by the Fi. In general, lim inf Fi C lim sup Fi; also liminfFi and limsup Fi are closed in X. In fact, limsup Fi is an element of C(X), since it must be non-empty (the Fi are non-empty and X is compact). However, liminfFi can be empty; for example, if X = {0, 1, F2i = {0},F2i+l = {1}, then liminfFi = 0. Lemma 3.1 Let x be an element of X. Then x belongs to limsup Fi if and only if there exists a subsequence {Fi}, of {Fi} and a corresponding subsequence {xik} such that xik E Fik, all k, and xik -+ x, as k -+ co. Proof: Let x be an element of limsup Fi. For each k = 1, 2,..., let B(x, 1/k) denote the open ball of radius 1/k centered at x. By definition of limsup Fi, there exists il > 1 such that Fi, nB(x, 1/1) 0. Suppose we have chosen indices il < i2 <... < ik-1 such that ij >j, j= 1,...,k-1, and Fij n B(x, l/j) 0, j = 1,...,k- 1. Then, for j = k, there exists an index ik such that ik > k, ik-1 < ik and Fik nB(x, 1/k): 0. In this way, we obtain a subsequence {Fi } of {Fi} having the property that Fi, n B(x, 1/k) 0 0, k = 1,2.... For each k, let xik be an element of Fik nB(x, 1/k). It is easy to see that xik - x, as k -- oo. Conversely, suppose {Fik } and {fXi } are as in the statement of the lemma. Let N be any neighborhood of x. Then there exists kN sufficiently large such that xik E N, for k > kN, i.e. Fik nN 0, k > kN. 3

Since {Fi,} is a subsequence of {JF}, it follows that N is frequently intersected by the Fi, i.e. x belongs to lim sup Fi. ~ A similar result holds for lim inf Fi. Lemma 3.2 Let x be an element of X. Then x belongs to liminf Fi if and only if for each i, there exists xi in Fi such that xi -- x, as i -- oo. Proof: Suppose x is an element of liminf Fi. Let B(x, 1/k) be as above, for k = 1, 2,.... As in the previous proof, we may obtain a sequence of indices ii < i2 < --- < ik < *. such that ik > k and Fi B(x, 1/k) # 0, i > ik, k = 1, 2,.... (Recall that B(x, 1/k) is eventually intersected by the Fi.) For each k = 1,2,..., choose xi in Fi n B(x, 1/k), for ik < i < ik+1. For i < ii, choose xi in Fi arbitrarily. Then {i,} is a sequence such that xi E Fi, all i, and xi -> x, as i -- oo. The reverse implication is obvious. * The next lemma follows immediately from the previous two lemmas and the fact that liminf Fi C lim sup Fi. Lemma 3.3 The following are equivalent for the sequence {F}i (i) lim inf Fi = lim sup Fi. (ii) For every x in limsup Fi, there exists xi in Fi, i = 1, 2,..., such that xi -+ x, as i -D oo. More generally, we have Theorem 3.4 Let {Fi} be a sequence in C(X) and F an element of C(X). Then the following are equivalent. (i) F = lim inf Fi = limsup Fi. (ii) F D lim sup Fi and for every x in F, there exists xi in Fi, i = 1, 2,..., such that xi -- x, as i -- oo. Corollary 3.5 Iflimsup{Fi} is a singleton {x}, then liminfFi = {x} also. In this case, Xi —x, as i oo, for all choices of xi in Fi, i = 1, 2,.... Proof: Let xi E Fi, all i. If xi 7f x, then there exists a subsequence {xil, of {xi} and e > 0 such that d(xi,,x) >, n = 1,2,.... Passing to a subsequence if necessary, we may assume there exists y in X such that xin —y, as n —oo. Therefore, {xi,^ is a sequence in the {Fi,} which is a subsequence of {Fi}, so that y e limsup Fi, which is equal to {x} by hypothesis, i.e. y = x. Hence, xi, —x, as n —+oo and {xin} is bounded away from x. Contradiction. Thus, xi —x, for all choices of {xi} in {Fi}, so that lim inf Fi = {x} also. i Before concluding this section, we establish the following useful result. Lemma 3.6 Let {Fi} be a sequence in C(X). If {Fij} is a subsequence of {Fi}, then lim inf Fi C lim inf Fi C limsup Fij C limsup Fi. i. j Proof: This follows from Lemmas 3.1 and 3.2. I 4

4 Hausdorff Metric Convergence Recall that (C(X), D) is a compact metric space, where D is the Hausdorff metric. In this section we will show, amongst other things, that the conditions of Theorem 3.4 are equivalent to convergence in the Hausdorff metric. Lemma 4.1 Let {F}i be a sequence in C(X)and F an element of C(X). (i) If F D limsup Fi, then Fi -- F if and only if h(F, Fi) -0. (ii) If F C liminf Fi, then Fi -+ F if and only if h(Fi,F) -+O. Proof: From the definition of D, it follows that h(Fi, F) -- 0 and h(F, Fi) — + 0, if Fi -- F, as i -- oo. Thus, in each case, it suffices to verify the reverse implication. (i) Suppose F D limsup Fi. By definition of h, we have h(Fi, F) = max d(x, F), xEFi where the function x -, d(x, F) is continuous and each Fi is compact. Thus, for each i, there exists x, in Fi such that h(Fi,F)= d(xi, F), i = 1,2,.... Suppose d(xi, F) 74 0. Then there exists e > 0 and a subsequence {Fj,} of {F,} such that d(xi, F) >, j 2,.... Since X is compact, passing to a subsequence if necessary, we may assume that there exists x in X such that xij - x, as j - oo. Since x belongs to limsup Fi by Lemma 3.1, we have that a is in F by hypothesis. Hence, d(xi, F) min d(xi,y) yEF < d(xij,,), j= 1,2,..., which implies that d(xij,F) is eventually less than e. Since this is a contradiction, it follows that h(Fi, F) -> 0 automatically in this case. Consequently, h(F, Fi) - 0 implies D(Fi, F) -- 0, as i -+ oo. (ii). Now suppose F C liminfFi. This time we have h(F, Fi) = max d(y, Fi), yEF so that, for each i, there exists yi in F such that h(F,Fi)= d(yi,Fi), i= 1,2,.... If d(yi, Fi) 74 O, then there exists a subsequence {Fij} of {Fi} and e > 0 such that d(yijFi)>e, j =,2,.... Since F is compact, passing to a subsequence if necessary, we may assume there exists y in F such that Yij -y, as j-+oo. But by hypothesis, we have that y is in liminfFi necessarily. Therefore, by Lemma 3.2, there exists xi in Fi, for each i, such that xi-+y, i.e. xij,-y, as j-+oo. Consequently, d(yij, Fij) min d(yij,z) zEFij < d(yij, xij) < d(yij, y) + d(y, xij), 5

which implies that d(yij, Fij) —O, as j —oo. Since this is a contradiction, it follows that h(F, Fi)-+O automatically in this case. Hence, it follows that D(Fi, F)- O if h(Fi,F)-O0. * Theorem 4.2 Let {Fi} and F be as above. The following are equivalent: (i) F = lim inf Fi = limsup F,. (ii) Fi-IF in C(X), as i —oo. Proof: Suppose (i) is true. Then by the proof of the previous lemma, we have that h(Fi,F) —O and h(F,Fi)-*O, i.e. D(Fi,F)-~O, as i-+oo. Conversely, suppose (ii) is true. We will show that F C liminfFi and F D limsup Fi. Suppose x is in F. Then, for each i, there exists xi in Fi such that d(x,xi) = d(, Fi) < maxd(y,Fi) yEF = h(F, F), i=1,2.... Necessarily, d(x, xi)-^O, as i —oo so that x is in liminf Fi by Lemma 3.2. Thus, F C liminfFi. Now suppose x is in limsup Fi but not in F. For each y in F, there exists 6(y) > 0 such that B(x, 6(y)) n B(y, 6(y)) = 0, where B(z, 6) is the open ball of radius 6 centered at z. The collection {B(y, 6(y)): y E F} is an open cover of compact F. Therefore, there exist yl,..., y, in F such that n F C U B(y, (yj)). j=1 For convenience, let 6j = 6(yj),j = 1,..., n and define 6= min{li,.. n} B(x, b) n (U1 B(yj, j )) = 0. Since x is in limsup Fi, by Lemma 3.1, there exists a subsequence {Fi, } of {F,} and a corresponding sequence {xik} such that xi, E Fi, all k, and xi.k- x, as k-)oo. Hence, there exists k6 sufficiently large such that ik E B(x,6), i.e. d(xik, x) < 6, k > k6. 6

Moreover, h(Fik,F) = maxd(y,F) YE Fik > d(xi,,F), k= 1,2.... For each k, let Zik be an element of F such that d(xik,zik) = d(ik, F), k = 1,2.... Necessarily, each zik belongs to some ball B(yjik, jk). Thus, d(x, yj) < d(x, Xi,) + d(xi, z.i) + d(zi, Yj.) < 6 + d(zik,zik,) + jk, i.e. d(xi,,z, ) > d(x,yjk )- - bj, k = 1,2,.... But, for each j = 1,..., n, we have B(x, S)nB(yj,6i) =0, so that d(x, j) > 26j. In particular, this is true for j = jk. Consequently, d(xik,Zik) > 6jk-6, > 6, since jk > 26, k = 1,2.... Hence, d(xik,F) > 6, so that h(Fik,F) >, k= 1,2,.... This implies that h(Fi, F) 74 0, i.e. D(Fi, F) 74 0. This is a contradiction, so that limsup Fi C F. U Remark The reader should note that Theorem 4.2 may be constructed from [5,6,9] by piecing together the appropriate results. We are giving an alternate proof which is direct and self-contained. Corollary 4.3 Suppose Fi is a singleton {xi}, for i sufficiently large. If x is an element of X, then xi- x if and only if limsup Fi = liminf Fi = {x}. Proof: This follows from the fact that D({xi}, {x) = d(xi,x), i = 1,2,.... Corollary 4.4 Let {Fi} be an arbitrary sequence in C(X). Any accumulation point F of {Fi} (i.e. any limit F of a subsequence of {Fi}) satisfies lim inf Fi C F C lim sup Fi. Proof: If {Fik} is a subsequence of {F,} such that Fik-+F, then, by the theorem, F = liminf Fi, = limsup Fi. Now apply Lemma 3.6. * 7

5 Selections and Point Convergence In this section, we consider the convergence of Fi to F versus the convergence of some xi in Fi to some x in F. Roughly speaking, we will see that convergence of the Fi to F is equivalent to convergence of the xi to x for smooth choices of the xi and x. In this regard, we define a selection on C(X) to be a mapping S: C(X)-+X such that S(F)E F, F EC(X). Note that selections need not be continuous as is the case in [9]. Our objective will be to equate convergence of Fi to F with convergence of S(Fi) to S(F). before we can do this, we need two more concepts. Let p be an arbitrary point in X. For each F in C(X), there exits at least one x in F such that d(p, ) = d(p, F). If, for each F in C(X), we define Sp(F) to be any such x in F, then we will call Sp a nearest-point selection defined by p. Of course, there exists more than one such selection in general for a given p in X. Now fix F in C(X). If p is such that there exists a unique x in F as above, then we will say that p is a uniqueness point for F (relative to d). In this case, d(p, x) < d(p,y), for all y in F different from x. Let F1 denote the uniqueness set for F, i.e. the set of all uniqueness points for F. If p E F1 and Sp is a nearest-point selection defined by p, then Sp(F) is uniquely determined in F. In general, F C F CX and 0 0 F1 0 X. Note also that F1 being equal to X is a generalization of F being a singleton. Lemma 5.1 Let F be an element of C(X) and p a point in F1. If Sp is a nearest-point selection defined by p, then Sp is continuous at F. Proof: Suppose Fi-OF and Sp(Fi) 7f Sp(F). Then there exists a subsequence {Fik} of{Fi} and e > 0 such that d(Sp(Fik),Sp(F)) >, k = 1, 2,.... But {Sp(Fi, )} is a sequence in compact X. Thus, passing to a subsequence if necessary, we may assume there exists z in X such that Sp(Fi,)-*z, as k -- oo. Since Sp is a selection, it follows that z is in lim sup Fi, which is in turn contained in F by hypothesis (Theorem 4.2). We then have that e < d(Sp(Fi,),Sp(F)) < d(Sp(F,,), z)+ d(z,S(F)), where d(Sp(Fik),)-O0, as k - oo. Therefore, d(z,Sp(F)) >, also, i.e. z and Sp(F) are distinct elements of F. Consequently, d(p, Sp(F)) < d(p,z), since p E F1. Define r = 2[d(p, z)- d(p, Sp(F))]. 2 8

Then d(p, z)- d(p, Sp(F)) > rI, so that d(p, Sp(F)) < d(p, z)- q. Since the function y-+d(p, y) is continuous on X, there exists an open ball B(Sp(F),,) of radius 0 < 6, < r centered at Sp(F) such that d(p, y) < d(p, z)- r, y E B(Sp(F), 5,). We claim that D(Fi,, F) > 6,, if k is such that Fik nB(Sp(F), 6,)= 0. To see this, observe that d(Sp(F),w) > 6, w E Fik, i.e. d(Sp(F), Fik) 65,, so that h(F, Fik) 6,. Consequently, D(Fik,F) > b6,, for such k. By our hypothesis, Fik —F, so that there exists k, sufficiently large such that D(Fik, F) < 6, k > k. By the previous claim, we must have that Fik n B(Sp(F), 6,7) 0, k > k,. For each k > k,,, let xik be an element of Fik n B(Sp(F), 6,), so that d(Sp(F), ik) < 6. For such k, we have: d(p, Sp(Fi,)) < d(p, zi) < d(p, Sx(F))+ d(S(F), Xik < d(p, Sp(F)) + 6, < d(p, Sp(F)) + r. But d(p, Sp(F)) + - = d(p, z) - 7, so that d(p, Sp(Fik)) < d(p,z)- 77, k > k,. Also, d(p, Sp(Fik)) —d(p, z), as k - oo, 9

since Sp(Fi,)- z, ask - 00. Consequently, d(p, z) < d(p, )- 77, which is a contradiction since q > O. Hence, Sp(Fi)-SSp(F) and Sp is continuous at F. U Theorem 5.2 Let {Fi} be a sequence in C(X)and F an element of C(X). Then the following are equivalent. (i) Fi —F, as i —oo. (ii) F D limsup Fi and Sp(Fi) —Sp(F), as i —oo, for all nearest-point selections Sp on C(X) defined by p in F1. Proof: Suppose (i) is true. Then, for each p in F1, Sp is continuous at F by Lemma 5.1, so that Sp(Fi) — Sp(F), as i —oo. The rest of (ii) follows from Theorem 4.2. Now suppose (ii) is true and it is not the case that Fi —F. Since F D limsup Fi, by Lemma 4.1, it must be true that h(F, Fi) 74 0. Thus, there exits e > 0 and a subsequence {Fik} of {Fi} such that h(F,Fik)>, k=1,2,.... Let xik be an element of F for which h(F,Fi) = d(zik,Fi) >, = 1,2,.... Passing to a subsequence if necessary, we may assume that there exists x in F such that zi,-+z, as k-+oo. Consequently, x E F1. If S. denotes any nearest-point selection defined by x, then, by our hypothesis, we have that S,(Fi) —S,(F). Since {SX(Fi,)} is a subsequence of {S(Fi)}, it follows that Sx(FJik) —S(F), as k —oo, where SX(Fik) E Fik, all k, and x = S-(F) E F. Therefore, d(ik, Fik) = min d(ik, y) yEFik < d(xik,S (Fik)) < d(x,, x) + d(x, S,(Fi,)), where d(xik, x)-0, as k - 0oo, and d(x, S(Fi)) = d(Sr(F), S(Fi))-0, as k oo. Consequently, d(xik, Fik)-O, as k -- oo, which is a contradiction. Hence, Fi-+F, as i -. oo. [ 10

Corollary 5.3 The following are equivalent: (i) Fi —F, as i -- oo. (ii) F D limsup Fi and S(Fi)-4S(F), for all selections S on C(X) which are continuous at F. Corollary 5.4 If F1 = X, then the following are equivalent: (i) Fi-F, as i -- oo. (ii) Sp(Fi)- Sp(F), as i -+ oo, for all nearest-point selections Sp on C(X) defined by p in X. (iii) S(Fi)-+S(F), as i -- oo, for all selections S on C(X) which are continuous at F. Example 5.5 Let (X,d) be an arbitrary compact metric space having at least two distinct elements. Suppose xi —x and yi-+y in X, as i -+ oo, where x $ y. Define Fi = zi,yi}, i= 1,2,..., and F= x, y}. Then it is easy to see that F C liminf Fi and F D limsup Fi, so that they are equal. Hence, Fi —F in C(X), as i -- oo. Moreover, Fl = {z E X: d(x, z) d(y,z)}. The following example of an infinite, non-linear mathematical program is much more interesting. Example 5.6 Let X denote the product of countably many copies of the unit interval [-1, 1]. The compact product topology is metrizable by the metric given by d(X, Iy) i~= 1xi - yi 1/2, y E X', where x = (xi),y = (yi). Let 0 < a < 1 and consider the following infinite horizon mathematical program: (MP) max i 1ai 2 subject to xil < 1, i= 1,2,.... Let X* denote the set of optimal solutions to (MP). It is easy to see that X* ={x E X: xi=, all i}, so that X* is uncountable. One interpretation of this is that for every discount factor a, there exist uncountably many infinite horizon optima for this problem. Now let N be a positive integer and consider the following N-horizon modification of (MP): N (MP)N max ai x i=1 subject to xil<1, i=1,2,.... 11

If X* denotes the set of optimal solutions to (MP)N, then it is obvious that X* = {x E X: xi = ~1,1 < i < N), N = 1,2,.... XN={XEX: x*=: 1<i<N}, N=1,2,.... Thus, X' D X2 D X3D... D XN D.D X*. We leave it to the reader to verify that X* = lim inf X = l sup XN, so that X -+X* in C(X), as N —oo. In fact, one may verify that D(X,X*) 21-N, N = 1, 2,.... The uniqueness set of X* is given by (X*)l = {x E X:i: O, all i}. Let p be an element of (X*)1. Then a nearest-point selection Sp defined by p satisfies: (Y~*\, {i 1, if pi > 0, Sp(* )i -1, ifpi < 0, and 1, if 1 < i <N and p >0, Sp(X )i= -1,- if1< i <N and pi <0, i, if i>N. Note that Sp(XN) is the unique element of XV having the property that d(p, XN) = d(p, Sp(X)), N = 1,2,.... Of course, SP(XA')-+Sp(X*), as N-.oo, as required by Theorem 5.2. 6 Application to Infinite Horizon Optimization We are now ready to apply the main results of the previous sections to our general infinite horizon optimization problem studied in [10]. We refer the reader to this reference for the details of what follows. As observed in section 1, we have a compact metric space (X, d) of feasible infinite horizon strategies (or solutions), a closed, non-empty subset X* of X consisting of the optimal infinite horizon solutions and, for each T > 0, a closed, non-empty subset X*(T) of X consisting of the T-horizon optimal solutions. In [10], we observed that only the elements of limsup X'*(T) could be approximated by elements of the X*(T), T > 0. Accordingly, we defined X*(oo) to be limsupX*(T). More generally, we defined a finite-horizon solution algorithm to be a mapping T —A(T) on the positive real numbers for which A(T) is a non-empty, closed subset of X*(T),T > 0. For each such A, we analogously defined A(oo) to be limsup A(T), so that A(oo) is a closed, non-empty subset of X*(oo). In particular, if A(T)= X*(T), T > O, 12

so that A(oo) = X*(oo), then we called A the maximal algorithm and X*(oo) the set of all algorithmically optimal infinite horizon solutions. If A(T) is a singleton {x*(T)} in X*(T), all T > 0, then we called A a simple algorithm. As before, let (C(X), D) denote the compact metric space of closed, non-empty subsets of X with D the Hausdorff metric corresponding to d. Then, for each algorithm A, A(oo) is an element of C(X)and {A(T): T > 0} is a generalized sequence in C(X). As in section 5, we are interested in selections S defined on C(X); in particular, we wish to concentrate on nearest-point selections Sp defined by points p in X. If A is an arbitrary algorithm, it will be convenient in this setting to denote Sp(A(T)) by xA(T), T > 0, and Sp(A(oo)) by xA. If A is the maximal algorithm, we will write x*(T) and xp instead. Thus, given an algorithm A and point p in X, each nearest-point selection Sp defined by p determines a simple algorithm given by {IX(T):T >0}. In this sense, Sp provides us with a tie-breaking rule by selecting, for each T > 0, a T-horizon optimal solution from the set A(T) of discovered such solutions using nearness to p as the selection criterion, and then choosing arbitrarily from amongst those nearest to p. We are interested in determining when a simple algorithm of the above form converges to xr. As observed in section 3, all the results of the previous sections (as well as their proofs) are valid for generalized sequences indexed by the positive reals. In this section, we apply these results to {A(T): T > 0} and A(oo). Since A(oo) = limsupA(T), the following theorem is immediate from Theorems 3.4, 4.2, and 5.2. Theorem 6.1 Let A be an arbitrary algorithm for the general infinite horizon optimization problem studied in [10]. Then the following are equivalent: (i) A(oo) = liminfA(T). (ii) For every x* in A(oo), there exists X*(T) in A(T), allT > 0, such that x*(T)-+x* in (X, d), as T-+oo. (iii) A(T) —A(oo) in (C(X), D), as T —oo. (iv) XA(T)-xA in (X, d), as T —oo, for all simple algorithms of the form { (T): T > 0}, where p is in the uniqueness set of A(oo). In particular, this theorem is valid for the maximal algorithm. Corollary 6.2 The following are equivalent: (i) X*(oo) = liminfX*(T). (ii) For every x in X*(oo), there exists x*(T) in X*(T), all T > 0, such that x*(T))*x* in (X,d), as T-*oo. (iii) X*(T)-+X*(oo) in (C(X), D), as T —,oo. (iv) xp(T) — x in (X,d), as T-+oo, for all simple algorithms of the form {xP(T) T > 0}, where p is in the uniqueness set of X*(oo). Corollary 6.3 If A(oo) is a singleton {x*}, then the conditions of Theorem 6.1 hold. Moreover, given any {x*(T): T > 0} in {A(T): T > 0}, we have that x*(T) —x*, as T —oo. Proof: Apply Corollary 3.5. ~ 13

Remark The previous corollary is true, in particular, for A equal to the maximal algorithm, i.e. A(T) = X*(T),T > 0, and A(oo) = X*(oo). This observation is the Planning Horizon Theorem (Theorem 6) of Bean and Smith in [2]. See also the end of section 5 of [10]. In [10], we defined an algorithm to be convergent if A(oo) is a singleton. However, in view of the previous theorem, it makes more sense to say that A is convergent if the equivalent conditions of Theorem 6.1 are satisfied. Therefore, given a convergent algorithm A, the problem of finding a nearest-point simple algorithm {xp (T): T > 0} which converges to an optimal infinite horizon solution can be replaced by the problem of finding a point p in the uniqueness set (A(oo))l of the limit set A(oo) of A. In general, this may be difficult to do. Of course, it is not if this uniqueness set is all of X, in which case any point p in X will do. Our next example gives sufficient conditions for this to happen. Example 6.3 Suppose X is contained in a Hilbert space. If A is an algorithm having the property that A(oo) is convex, then for each p in X, there exists a unique point yp in A(oo) which is nearest to p [l,p.15], i.e. the uniqueness set of A(oo) is all of X. The point yp is called the best approximation to p in A(oo). A sufficient condition for A(oo) to be convex is that A(T) be convex for all T > 0 and A(T) —+A(oo). Such a case is important since it provides for a tie-breaking finite horizon algorithm x*(T) that arbitrarily well approximates an infinite horizon optimum xp without the restrictive assumptions of [2,3,10] that X*(oo) be a singleton. Acknowledgement: The work of Robert L. Smith was supported in part by the National Science Foundation under Grant No. ECS-8409682. 14

References 1. Aubin, J.P. [1979], Applied Functional Analysis, J. Wiley, New York. 2. Bean, J.C. and R.L. Smith [1984], "Conditions for the Existence of Planning Horizons," Math. of Oper. Res. 9, 391-401. 3. Bes, C. and S. Sethi [1986], "Concepts of Forecast and Decision Horizons: Applications to Dynamic Stochastic Optimization Problems" to appear in Math. of Oper. Res.. 4. Dugundji, J. [1966], Topology, Allyn and Bacon, Boston. 5. Effros, E.G. [1965], "Convergence of Closed Subsets in a Topological Space," Proc. Amer. Math. Soc. 16, 929-931. 6. Fell, J.M.G. [1962] "A Hausdorff Topology for the Closed Subsets of a Locally Compact Non-Hausdorff Space," Proc. Amer. Math. Soc. 13, 472-476. 7. Kuratowski, C. [1966] Topologie I, Academic Press, New York. 8. Kuratowski, C. [1968] Topologie II, Academic Press, New York. 9. Michael, E. [1951] "Topologies on Spaces of Subsets," Trans. Amer. Math. Soc. 71, 152-182. 10. Schochetman, I.E. and R.L. Smith [1986], "Infinite Horizon Optimization", Technical Report, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109. 15