I FINITE DIMENSIONAL APPROXIMATION IN INFINITE DIMENSIONAL MATHEMATICAL PROGRAMMING Irwin E. Schochetman Department of Mathematical Sciences Oakland University Rochester, Michigan 48309 Robert L. Smith Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 Technical Report 89-10 April 1989

I FINITE DIMENSIONAL APPROXIMATION IN INFINITE DIMENSIONAL MATHEMATICAL PROGRAMMING Irwin E. Schochetman Department of Mathematical Sciences Oakland University Rochester, Michigan 48309 Robert L. Smith* Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 April 9, 1989 Abstract We consider the problem of approximating an optimal solution to a separable, doubly infinite mathematical program (P) with lower staircase structure by (optimal) solutions to the programs (P(N)) obtained by truncating after the first N variables and N constraints of (P). Viewing the surplus variable associated with the N-th constraint as a state, and assuming that all feasible states are eventually reachable from any feasible state, we show that the efficient set of all solutions optimal to all possible feasible surplus states for (P(N)) converges to the set of optimal solutions to (P). A tie-breaking algorithm which selects a nearest-point efficient solution for (P(N)) is shown (for conbvex programs) to converge to an optimal solution to (P). A stopping rule is provided for discovering a value of N sufficiently large to guarantee any prespecified level of accuracy. The theory is illustrated by an application to production planning. *The work of Robert L. Smith was partially supported by the National Science Foundation under Grant ECS-8700836. 1

I Key Words and Phrases Value convergence, reachability, solution set convergence, tie-breaking, stopping rule, production planning. 1 Introduction Consider the following doubly infinite mathematical programming problem: 00 min E cj(yi,..., j) j=1 subject to (P) EI=1 aij(yl,. yj) > bi, i= 1,2,..., yj E Yj, j 1, 2,..., where Yj C snJj,j = 1,2,... and bi E sm', i = 1,2,.... Apart from the implicit structural assumption that each constraint contains at most finitely many variables, (P) is at this point completely general, including integer programs where each Yj is discrete. Although there is an extensive literature on the solution of semi-infinite mathematical programs (see for example Anderson and Nash [1]), there is relatively little work on the doubly infinite case (Grinold [8, 9, 10], Jones, Zydiak and Hopp [12], and Flam and Wets [7] being notable exceptions). In this paper, we establish conditions on (P) which allow for arbitrarily good approximations to the solutions of (P) by solving finite dimensional approximations to (P) obtained by truncating beyond finitely many variables and constraints. If we interpret the index j in (P) to correspond to the j-th period in a multi-period planning problem, then the above truncation to (P) becomes a finite horizon approximation of an infinite horizon optimization problem. This so-called planning (or solution) horizon approach has an extensive literature (see for example Bean and Smith [3], Bes and Sethi [5], and Schochetman and Smith [18]). Our paper extends this work to a general mathematical programming framework where the requirement of [3,5] that variables be discrete and the assumption of [18] that all finite horizon feasible solutions are extendable to infinite horizon feasible solutions do not hold in general. Moreover, in the presence of a certain property, which we call reachability, we show how to enlarge the set of finite dimensional optimal solutions to guarantee Hausdorff convergence to the set of infinite dimensional optimal solutions as the dimensionality increases. The tie-breaking algorithm of Schochetman and Smith [18] is then employed to select a sequence of finite dimensional optimal solutions that converges to an infinite dimensional optimal solution as the dimensionality of the approximation increases. This differs fundamentally from [7],[8],[9] and [10] where it is shown only that convergent subsequences exist. 2

k Throughout this paper we adopt the following Assumptions A. The feasible activity vectors yj lie in non-empty, compact regions, i.e. each YQ is a non-empty, compact subset of RnT, so that there exists rj > 0 such that Iyjlj < rj, for all yj E Yj and j = 1,2,..., where | j is the Euclidean norm on sRnj. B. The constraint functions are continuous, i.e. for each i = 1, 2,..., aj is a continuous. real-valued function on Y1 x... x Yj, for j = 1,..., i. C. The objective function is continuous and uniformly convergent, i.e. for each j 00 1,2,..., Cj is a continuous, real-valued function on Y~ x... x Yj and EIIcj|llo < o j=1 where Icjlloo = max{cj(yi,...,y)l: yk E Yk, k = 1,... j} In section 2, we establish a Hilbert space context for (P) and show that, as a consequence 00 of Assumption A, the product and metric topologies on IYj are identical. We then show j=1 that under Assumptions A, B and C, (P) has an optimal solution. In section 3, we formally introduce the finite dimensional approximations, (P(N)) to (P) consisting of the first N variables and first N constraints of (P), N = 1,2..., and study their inter-relationships. In section 4, we prove that the sequence of optimal objective function values to the approximating problems (P(N)) converges to the optimal value of (P), as N -x oo (i.e. value convergence). We also show that for convex programs with strictly convex objective functions, the sequence of optimal solutions to the problems (P(N)) also converges to the (unique) optimal solution of (P), as N -* oo (i.e. solution convergence). In section 5, we consider the class of problems where the objective function and constraints are separable and each variable appears in at most finitely many constraints. Treating the surplus vector associated with the N-th constraint of (P(N)) as a state variable, we form for each N, the closure of the set of all optimal solutions to all feasible states. In the presence of our reachability property, we show that this sequence of optimal sets converges to the set of optimal solutions of (P) in the underlying Hausdorff metric. Thus, under reachability we have solution set convergence. Also in this section, we discuss a natural tie-breaking rule for selecting solutions to the (P(N)) in such a way that the resulting solution sequence converges to an optimal solution of (P). We also discuss a forward algorithm which, together with a stopping rule for determining N, yields any desired level of accuracy. Finally, in section 6, we discuss an application in production planning. 3

I 2 Miathemnatical Preliminaries We begin by constructing an infinite dimensional Hilbert space in which we embed (P). Each sRnj is a Hilbert space with usual inner product, norm and metric denoted respec00 tively by (.,.).' L and d, j = 12,. If we let Y = flYj, then by Assumption A and j=1 the Tychonoff Theorem [13, p.143], Y is a non-empty, compact subset of fl2Rn relative to j=1 the product of the metric topologies. Fix 0 < #j < 1, each,such that EZ 1 #?? < oc (for example, Oj = 1/jr3). For each j=1,2,..., denote by Hi the Hilbert space given by 3'nJ as a (real) linear space with inner product, norm and metric given respectively as follows: Ixjyj)j = /3 (Xj,1Xj)j, pj(xj,yj) = 3jd3(xj,yj), XjIj E Hj. Of course, the metrics pj and di are topologically equivalent for all j, so that Y is also a 00 compact subset of H H3. j=1 Let H denote the Hilbert sum [2, p.222] of the Hj, i.e. ZI~3II = /3~xI2oo _H I~, 1 1 2R200 00 0 0 {(xi1eYJHi: xL=..j 333J j=1 j=1 j=1 with inner product given by 00 00 (xy) = Z(x3,yj)j = E03(X21Yjjj~ j=1 j=1 Hence, the corresponding norm and metric are given by 1 1 11XII 11X _112 E 031, I 3 = [f3 ] lixil = and p(~~,y> ~,,~ '= EO8djixj, yj)2 I XlyE H. 3=1.=1 4

I From the choice of 3j, it follows that Y CH. Thus, Y inherits a metric structure from H via p. Lemma 2.1 The p-metric topology and the product metric topology on Y are the same. Proof: See the appendix.. Thus, since Y is compact in the product topology, it is a compact metric space relative to p. Moreover, a sequence {yn} in Y converges to y relative to p if and only if for each j, {y7} converges to yj in Rj relative to the usual Euclidean metric. Define C(Y) to be the space of all compact, non-empty subsets of Y and let D denote the Hausdorff metric on KC(Y) corresponding to p. Recall that for C, K in AC(Y), we have D(C,K) = max(maxp(x,K), max p(y,C)), xEC yEK where p(x, K) = minYEK p(x, y), x E C. In this manner, tC(Y) becomes a compact metric space [11, 15]. This metric will prove useful in sections 4 and 5 where we study solution set convergence. There is an alternate characterization of set convergence which will also prove very useful to us later on. Let KN C Y, for N 1,2,.... Define liminf KN and limsup KN as follows [4, 11, 15,]: 1. y E liminf KN if and only if y E Y and, for each N sufficiently large, there exists yN in KN such that yN -+ y, as N -- oo. 2. y E limsup KN if and only if y E Y and there exists a subsequence {KNk} of {KN} and a corresponding sequence {yk} such that yk E KN, all k, and yk -+ y, as k — + o. If KC Y and K = liminfKN = limsupKN, we write lim KN = K. In general, liminf KN and limsup KN are closed subsets of Y, which may be empty and which satisfy liminf KN C lim sup KN. Now suppose KN is not empty for N large. Since Y is compact, we have that limsupKN $7 0. Also, if K E KC(Y) and KN E AC(Y), all N, then KN -* K in XC(Y) relative to D if and only if K = liminf KN = limsup KN, 5

i.e. limsup KN C K and K C liminf KN [11, 14, 15]. Thus, limKN = K also. For each i = 1, 2,..., recall that bi is an element of the Euclidean space R1Jmi, so that aij: Yi x... x Y -- m, j = 1,2,..., i. Thus, the i-th constraint is a vector inequality involving the first i variables at most. It may be interpreted as a system of m scalar constraints in the components of the yj, j = 1,2,...,i. By Assumption B, each aij is a continuous function, so that the function aij: Y X... x Y j=1 is also continuous, i = 1,2,.... Hence, if we define Fi={YE Y: aj(yl,...,yj) >, i 1,2,... j '=1 then Ft is a closed and hence compact subset of Y. The feasible region X of (P) is then given by 00 X= nFi i=1 Thus, X, being an intersection of compact sets, is itself a compact subset of Y. To avoid the trivial case, we assume that X $ 0, so that each Fi $ 0, as well. A necessary and sufficient condition for this is that the sets {Fi} have the finite intersection property [13, p.136]. Hence, under our assumptions, we have that the feasible region X is in K(Y). Turning to the objective function of (P), for each j = 1,2,..., we have that cj: Y, x... x Yj -~ R. By Assumption C, each cj is continuous. Since Y1 x... x Yj is compact, we have that the sup norm of cj IICjllo = max Icj(yi,...,yj < oo j =1,2,... Y, x... X Yj 00 By Assumption C, we have moreover that ZEIcjll1oo < oo. A sufficient condition for Assumpj=1 tion C to hold is that each cj be of the form ca-kj, where 0 < c < 1 is a discount factor, kj is a continuous function on Y1 x... x Yj and the kj are uniformly bounded. 6

Theorem 2.2 Under Assumptions A, B and C, 00 C(y) = E Cj(yl,...,yj) j=1 defines a continuous function C: Y -+ X which is the uniform limit of the sequence of continuous functions C(.; N) given by N C(y; N) = cj(y,..., y), yE Y. j=1 In particular, given e > 0, there exists N, > 0 such that N > N, implies that 00 I cj(yl,...,yj)] < e, yEY. j=N+1 Proof: The existence of C follows from the completeness of R and the fact that for each y E Y, the sequence of partial sums { cj(Yl,...,yj) is Cauchy in R (Assumption C). Moreover, since this sequence of continuous functions converges uniformly (also by Assumption C), it follows that C is continuous. Finally, the remaining property follows from the uniform convergence. * Since C is continuous on Y and X is a compact, non-empty subset of Y, C attains its minimum on X. Let C* = min C(X) xEX be the optimal objective value of (P) and let X* = {x EX: C() = C*} denote the set of optimal solutions. Then X* is also a compact, non-empty subset of Y. i.e. X' E C(Y), where 0 c X* C X C Y. Our primary objective in this paper is to approximate the optimal objective value C' and an optimal solution x* in X* via corresponding quantities computed from finite dimensional approximations of (P). 7

I 3 The Finite Dimensional Approximations We begin by defining finite dimensional approximations to (P) formed by retaining the first N variables and the first N constraints. For each N = 1,2,..., let (P(N)) be the finite dimensional problem given by N min c,(y1,...,yj) j=l subject to (P(N)) Z-=1 aij(l,..,y) > bi, i = 1,.., N, yj E Y, j=l,...,N. Note that (P(N)) has N constraints in the N vector variables y,..., YN, N = 1, 2,.... Our intent is to ultimately approximate solutions of (P) by solutions of the (P(N)). However, since the latter (being finite dimensional) do not lie within the same space as the former, it will be convenient at times to arbitrarily extend solutions of the (P(N)) so as to make all solutions comparable. More formally, let XN denote the feasible region of (P(N)) and let PN be the canonical projection of Y onto Y1 x... x YN, for N = 1,2,.... Then XN is a N non-empty, compact subset of Y1 x... x YN, since XN = nFi, and i=1 XN D PN(X)7 0, N = 1,2,.... Now for each N, define XN = p(XN), so that XN = XN X YN+1 X YN+2 X... Then XN is the subset of Y consisting of arbitrary extensions of the elements of XN to elements of Y. It is clear that XN is also a non-empty, compact subset of Y, i.e. XN E KC(Y), N=1,2,.... Lemma 3.1 For each N = 1,2,..., we have: (i) XN = y E Y: aij(yl,...,yj) > bi, i = 1,2,...,N. (ii) PN(XN) = XN. (iii) XN+1 C XN. 8

I 00 Since X is the non-empty intersection of the sets XN in IC(Y), i.e. X = ) X~, we N=1 have that XN - X in C(Y), as N - co, relative to the Hausdorff metric D [14, p.339]. However, we cannot conclude that XN -- X, as N -- oo, since points in XN do not lie in Y. On the other hand, it is points in the XN that are computed when we approximate (P) via the (P(N)). Although it is an abuse of notation, it will be convenient to write X(N) in place of XN and XN, where the correct interpretation will be clear from the context. For example, we have that the feasible regions X(N) for the (P(N)) satisfy, X(N) - X in IC(Y) as N - oo, relative to the Hausdorff metric D. Turning to the objective function of (P(N)), let N C(Y1,.., N; N) = cj(yl,...,yj), N=1,2,..., j=1 where the domain of C(.; N) will be either Y1 x... x YN or Y, depending on the context. Then (P(N)) may be abbreviated as min C(y;N), N =1,2,... yEX(N) Also, recall that the C(.; N), when viewed as functions on Y, converge uniformly to C (Theorem 2.2). Since C(-; N) is continuous and X(N) is compact as well as non-empty, it follows that the minimum in (P(N)) is attained. Denote this optimal value by C*(N), N = 1, 2,.... Also let X*(N) be the set of optimal solutions of (P(N)), so that X*(N) is a compact, non-empty subset of X(N), N = 1,2,.... In the next section, we search for conditions which allow for approximating the infinite dimensional optimal objective value C* and an infinite dimensional optimal solution x* by finite dimensional optimal objective values C*(N) and finite dimensional optimal solutions x*(N) for N sufficiently large. 4 Optimal Value and Solution Convergence Before establishing (optimal) value convergence for the finite dimensional programs, we establish value convergence for any convergent subsequence of feasible solutions. 9

Lemma 4.1 Let {Nm} be a subsequence of the positive integers, {ym} a corresponding sequence in Y,and y E Y such that ym -- y. Then C(ym; Nm) -+ C(y), as m CX)o. Proof: For each m, we have: IC(ym;Nm) -C(y) IC(ym; Nm) -C(y'm)I+ C(ym) -C(y)t 00 = IZ c3(y1,...,y7)l +tC(ym)-C(y)I. j=Nm+1 Fix E > 0. Since C is continuous, there exists ml sufficiently large such that m > m1 implies IC(ym) - C(y)l < E/2. Since C is uniformly convergent (Theorem 2.2), there exists No sufficiently large such that N > No implies 00 I Z c3(zI,..., z)I<e/2, zEY. j=N+l Choose m2 sufficiently large so that Nm, ~ No and let mn = max(m, in2). Then m > rno implies C(ym; Nm) - C(y)I < f, which completes the proof. * Theorem 4.2 (Value Convergence) The optimal values of the finite dimensional problems (P(N)) converge to the optimal value of the infinite dimensional problem (P), i.e. C*(N) -* C*, as N -p oo. Proof: If not, there exists e > 0 and a subsequence {C*(N,)} of {C*(N)} such that IC*(Nm)0- C*I~ E, m = 1,2,.... Since each C*(Nm) is attained, there exists x*(Nm) E X*(Nm) such that C*(Nm) = C(x*(Nm);Nm), so that IC(x*(Nm); Nm) - C*I > m = 1,2. 10

I Since Y is compact, passing to a subsequence if necessary, we may assume there exists x E Y such that x*(INm) — + x, as m -- oc. It follows that x E limsupX*(N) which is contained in limsupX(N). But X = limsup X(N), since X(N) - X, as N - o. Hence, x E X, i.e. x is feasible for (P). From Lemma 4.1, it follows that C*(Nm) - C(x), i.e. |C*(NVm) - C*1 - IC(x) - C*l, as m -> oo, so that 0C(x) - C*1 >. Hence, x is not optimal for (P), i.e. x ' X*. Now let x* E X*, so that x* E X(N), all N. In particular, x* E X(Nm), all m. Consequently, C*(Nm) < C(*; Nm), m= 1,2,..., and C(x*;Nm) - C(x*), as m — oo, by Lemma 4.1. Thus, C(z) = lim C*(Nm) < C(x*) = C*, which implies that C(x) = C*, i.e. x is optimal. Contradiction. * Having established value convergence, we next address the question of solution convergence. That is, we seek conditions under which it is possible to choose solutions optimal for (P(N)) which converge to a solution optimal for (P). As we will see shortly, for strictly convex programs (P), this convergence occurs for all solutions optimal for (P(N). However. in general, not all solution selections optimal for the (P(N)) will converge. In fact, we will find it necessary to enlarge the set of possible solution selections from the (P(N)) to include non-optimal feasible solution selections with the property that the limit of any convergent subsequence of these is optimal for (P). More formally, we define a finite dimensional algorithm A* for (P) to be a sequence {A*(N), N = 1,2,...} where each A*(N) is a closed, non-empty subset of X(N) satisfying A*(oo) C X* where A*(oo) is defined to be lim sup A*(N), the set of accumulation points of the A*(N). In this case of course, liminf A*(N), although possibly empty, must also be a subset of X'. For example, if each A*(N) is a closed, non-empty subset of X*(N), then it follows from the definition of lim sup A*(N), Lemma 4.1 and Theorem 4.2 that A* = {A*(N), N = 1,2,...} is a finite dimensional algorithmn for (P). In what follows, we will see that there exist finite dimensional algorithms A* for which A*(N) g X*(N), for all N. We seek a finite dimensional algorithm A* which is itself convergent, i.e. such that A*(N) - A*(oo) in I(Y) relative to the Hausdorff metric D, as N -+ oo. For such A'. we are interested in selecting x*(N) in A*(N), for each N, so that the sequence {x*(N)} converges to a solution in X*. This selection is made as follows. Let p E Y and K E K(Y). Then the distance p(p, K) from p to K is attained, possibly non-uniquely. If sp(K) is such a 11

point for each K in PC(Y), then we call sp a nearest-point selection defined by p. If K is such that p(p, K) is uniquely attained by a point in K, then p is called a uniqueness point for IK. The set of all such uniqueness points will be denoted by U(K). Clearly, K C U(K) C Y in general. Theorem 4.3 Let A* be a finite dimensional algorithm for (P) and A a closed subset of X* containing A*(oo). Then the following are equivalent: (i) A*(N) -- A, relative to the Hausdorff metric D, as N -+ oo. (ii) liminfA*(N) = limsupA*(N) = A. (iii) For all x* E A, there exists x*(N) E A*(N), each N, such that x*(N) - x*, relative to the p metric, as N -* oo. (iv) For each p in U(A) and each nearest-point selection sp defined by p, sp(A*(N)) - x*, as N - oo. In particular, if A = X* is a singleton, where X* = {x*}, then all the above conditions are satisfied; in fact, x*(N) - x*, as N -k oo, where x*(N) is any element of X*(N), N = 1,2,.... Proof: This theorem follows immediately from Schochetman and Smith [19] in conjunction with our previous discussion. * Analogously, we have the following dual version of Theorem 4.3. Theorem 4.4 Suppose A* is a finite dimensional algorithm for (P) with A as above. Then the following are equivalent: (i) liminf A* (N) 0. (ii) There exists an x* E A for which there exists x*(N) E A*(N), each N, such that x*(N) - x*, relative to the p metric, as N -+ oo. (iii) There exists p in U(A) such that sp(A*(N)) - sp(A), as N -- oo, for all nearest-point selections sp defined by p. Theorem 4.4 gives the existence of limit points of A* as a necessary condition for approximating a solution to (P) by suitable choices of solutions to the (P(N)) from the A*(N). In practice, the easier way to demonstrate this condition is to establish the stronger claim that A* converges to some non-empty set A, the latter being condition (i) of Theorem 4.3. 12

A Under this condition, any nearest-point selection (defined by p) of solutions from the A4*(NV) is guaranteed to converge, provided that there is a unique point closest to p from A. Since A C Y, we also have A C H, where H is a Hilbert space. Hence, a sufficient condition for there to be a unique point in A closest to p, for any p E Y, is that A be closed and convex [2, p.15]. In particular, for (P) a convex program, X* is a convex subset of H, where (P) is said to be convex if: (i) Yj is convex, j = 1,2,... (ii) -aij is convex, j = 1,...,i, i = 1,2,... (iii) cj is convex, j = 1,2,... We therefore obtain the following corollary to Theorem 4.3. Corollary 4.5 Let A* be a finite dimensional algorithm for (P) where (P) is a convex program. Then the following are equivalent: (i) A*(N) - X*, as N -+ oo. (ii) For each p E Y and each nearest-point selection sp defined by p, sp(A*(N)) -+ x* as N -- oo, where xp is the unique point in X* closest to p. In the next section, we will construct a finite dimensional algorithm A* which, under a reachability condition, converges to the set of all infinite dimensional optimal solutions X'. Hence, by the previous corollary, nearest-point finite dimensional solutions will converge to an optimal solution of (P). Before leaving this section, we note that if (P) is a convex program with strictly convex objective function C, the optimal solution x* will be uniquely attained. From Theorem 4.:3. we obtain the following. Theorem 4.6 (Solution Convergence) Suppose (P) is a convex program with strictly convex objective function C, i.e. cj is strictly convex on R x... x?njj = 1,2.... Then x*(N) - x*, where x*(N) is any solution to (P(N)), N = 1,2,..., and x* is the unique solution to (P). The previous theorem extends a result established directly by McKenzie in [16]. Note also that in this case, each XN is a singleton (since C(-; N) is strictly convex), while (.' )! is an infinite set in general, consisting of all arbitrary extensions of the unique solution. TTlis is why in the statement of the theorem, we refer to x*(N) as being any solution to (P(.V ). 13

I 5 Solution Convergence Through Tie-Breaking In the previous section, we saw that tie-breaking by means of a nearest-point selection of solutions from a convergent finite dimensional algorithm generates a sequence of solutions which converges to an infinite dimensional optimal solution. Our objective in this section is to construct such a convergent finite dimensional algorithm. We begin by assuming henceforth that (P) is separable lower staircase, i.e. cj(y1,...,y) = cj(yj), = 1,2,... and aj(y,...,yj) = aij(yj), j 1,...i, i = 1,2,... with aij = j=,...,i-2, i =3,4,... Under this assumption, (P) may be written in the form 00 min cj(yj) j=l subject to (P) ai,i-1(yi-1) + a,i(yi) b, i = 1,2,..., yj EYj, j=1,2,..., where ao1 is identically zero. In order to construct a finite dimensional algorithm {A*(N), N = 1,2,...} which converges, for example, to X*, we need by Theorem 4.3 to choose each A*(N) sufficiently large to insure that for each x* E X*, there exists a choice x*(N) in A*(N), all N, such that x*(N) -* x*. On the other hand, we also need to be sure that each A*(N) is sufficiently small so as to insure that each convergent subsequence {x*(Nk), k = 1,2,...} drawn from the A*(N) converges to a point x* in X*. The set X*(N) of all finite dimensional optimal solutions for (P(N)) is too small a choice for A*(N) in general. Instead, viewing N as a discrete time parameter, we enlarge X*(N) to include all solutions optimal to some feasible "state" ending period N. We begin by formalizing the notion of state. Fix N. If (yi,...,yN) is feasible for (P(N)), then the only connection between the constraints of (P(N)) and the remaining constraints of (P) is the value aN+1,N(YN)- We call this value the state s(N) E RmnN+ associated with the solution (y1,..., YN) in X(N). Let s(N) be an arbitrary element of RmN+1 and define X(N,s(N)) = {(y1,...,yN) E X(N): aN+,N(YN) = s(N)}. 14

I Then X(N, s(N)) is the set of (P(N))-feasible solutions (y1,..., YN) having state s(N) at stage N. Since the constraint functions are continuous, it is a closed, although possible empty, subset of X(N). Let S(N) = {s(N) E smN+ X(N,s(N)) 0} = {s(N) E RmN+l: aN+1,N(xN) = s(N), for some x(N) E X(N)} be the set of all states feasible for (P(N)) and let S*(N) = {s(N) E rmN+1: aN+1,N(Xz ) = s(N), for some x* E X*} be the set of all states s(N) optimal for (P). We have S*(N) C S(N), all N. Moreover, one can easily show that, for each N, S*(N) and S(N) are compact, non-empty subsets of RmN+1l For each N and each s(N) in S(N), consider the mathematical program (P(N,s(N))) given by: mn C(y(N); N) subject to (P(N, s(N))) y(N)E X(N,s(N)). Since the minimum C*(N,s(N)) is attained, we may define X*(N,s(N)) = {y(N)E X(N,s(N)): C(y(N);N) = C*(N,s(N))}, which represents the set of all solutions optimal to state s(N) E S(N) for problem (P(N)). Each such X*(N, s(N)) is a compact, non-empty subset of X(N) C Y, i.e. an element of AC(Y). For each N, and S(N) satisfying S*(N) C S(N) C S(N), let X(N,S(N)) = U X*(N,s(N)). s(N)ES(N) For technical reasons, we also define X*(N, S(N)) to be the closure of X(N, S(N)) in Y, so that X*(N, S(N)) E IC(Y), for all N. The set X(N, S(N)), being the set of all solutions optimal to some feasible state in S(N) for (P(N)), is called an efficient set (Ryan, Bean and Smith [17]). In particular, if S(N) = 3(N), then we write X(N) = X(N,X(N)) and X*(N) for X*(N,S(N)). Note that X*(N) c X(N) 15

i is a strict inclusion in general, since X(N) is the union of the X*(N, s(N)) over all feasible states s(N) E S(N), not just those states corresponding to optimal solutions of (P(N)). Remark. One can show that for fixed N, the mapping s(N) -* X(N,s(N)) of S(N) into KC(Y) is upper semi-continuous [4]. If this mapping is also continuous (as for example when YN is discrete), then from the Maximum Theorem [4, p.116], the resulting mapping s(N) -* X*(N,s(N)) of closed S(N) into )C(Y) is upper semi-continuous. In this case, X(N, S(N)) is automatically closed, thus, eliminating the necessity of taking its closure. We turn now to establishing conditions under which the efficient sets X(N, S(N)) converge to the set X* of solutions optimal for (P). From Theorem 4.3, it is necessary and sufficient to establish that (1) X* C liminf X(N,S(N)) and (2) limsup X(N, S(N)) C X*. The next lemma establishes (1). Lemma 5.1 Let S*(N) C S(N) C ~(N), for each N. Then X* C liminf X(N, S(N)). Proof: Let x* E X*, and thus x* E X(N), all N. Fix N and define s(N) = aN+1,N(X*), so that s(N) E S*(N). We next verify that x* E X*(N,s(N)), i.e. x* is optimal for (P(N, s(N))). Suppose not. Then there exists x in X*(N,s(N)) such that x Z x* and C(x; N) < C(x*; N). For such x, we have s(N) = aN+1,N(XN) = aN+1,N(XN). Now define z = (X1,...,XN-1, XN, XN+1, 2N+2,..) Then aN+lv(ZN) + aN+1,N+1(ZN+1) = aN+1,N(XN) + aN+1,N+1 (XN+1) - aN+1,N (XN) + aN+1,N+l (XN.+1) > bN+1. 16

Thus, z is feasible for (P), i.e. z E X. Moreover, co C(z) = C(z; N) +: cj(zj) j=N+1 00 C(x; N) + E C(x) j=N+l oo < C(x*; N) + c,(;) j=N+1 = C(x ), i.e. x* is not optimal. Contradiction. Hence, x* E X*(N, s(N)), so that x* E X(N, S-) C X(N, SN). Since N is arbitrary, we have that 00 x* E n X(NS(N)) CliminfX(N, S(N)). s N=1 In order to establish (2), we require that a state reachability property be satisfied. Definition (Reachability) Suppose S*(N) C S(N) C S(N), for each N. Let k be a positive integer and s(k) a feasible state in S(k). We say that the sequence {S(N), N = 1..... is reachable from state s(k) at k if, given any sequence {t(N), N = 1, 2,...} of feasible states with t(N) E S(N), all N, there exists Nk > k sufficiently large such that for each N > Nk. there exists a sequence of decisions (y,..., y) which (i) is feasible for (P(N)) and achieves state t(N), i.e. (yN,..., ) E X(N,t(N)) and (ii) whose first k decisions are feasible for (P(k)) and achieve state s(k), i.e. (y..., yk) E X(k, s(k)). We say that the sequence {S(N), N = 1,2,...} is reachable from all feasible states if it is reachable from all states s(k) E S(k), for all k, where S(k) = {s(k) E Rmk+ ak+l,k(xk) = s(k), for some x E X} is the set of states at k which are feasible for (P), k = 1,2,.... Note that for each.\. S*(N) C S(N) C S(N), in general. Roughly speaking, a sequence of feasible state sets is reachable if any sequence of states drawn from the sequence of sets can be eventually reached (i.e. attained) from any feasible state of (P) at any stage. This is a key property which decouples current and future decisions, allowing for finite dimensional approximation of an infinite dimensional problem. Thil decoupling effect is formalized in the following theorem. 17

I Theorem 5.2 Let S*(N) C S(N) S(N), all N. If {S(N), N = 1, 2,...} is reachable from all feasible states, then X = lim X(N, t(N)), N —oo for all selections {t(N), N = 1, 2,... } with t(N) E S(N), all N. Proof: Since X(N, t(N)) C X(N), all N, it follows that limsupX(N,t(N)) C limsupX(N) = X, since 00 X= QnX(N) lim X(N). N=1 N-co Now suppose (P) has the reachability property to {S(N), N = 1,2,...} from all feasible states and t(N) E S(N), all N. Let z E X and define s(k) = ak+l,k(zk), k = 1,2j.... Then z E X(k,s(k)) and s(k) E S(k), all k. By reachability for k = 1, (and s(1)), there exists N, > 1 such that for all N > N1, there exists (y,,.., 1,N) which is (P(N))feasible with state t(N) and whose first decision is (P(1))-feasible with state s(1). By reachability for k = 2, there exists N2 > N1 such that for all N > N2, there exists (y2,N 2, 4~N) which is (P(N))-feasible with state t(N) and whose first two decisions are (P(2))-feasible with state s(2). For N, ~ N < N2, define ZN in Y as follows: N z1, j=1,.7 2,N j N, where zj" is chosen arbitrarily in Yj, for j > N. We leave it to the reader to verify that ZN is (P(N))-feasible with state t(N), i.e. ZN E X(N, t(N)), N, < N < N2. Now suppose 1 < N1 < N2 <... < Nk have been found for 1,2,... k respectively by reachability and zNl,..., zNh1 have been constructed so that zN E X(N, t(N)), N, ~ N < Nk- 1Iand zjN = zj, for j = 1,... e, Ne~ N < Ne+l,,e = 1,..., k - i. Recall that Nk has the property that for each N > Nk, there exists (yk,N, Yk/) which is (P(N))-feasible with state t(N) and whose first k decisions are (P(k))-feasible with state s(k). Applying reachability to k + 1, there exists Nk+j > Nk such that for all N > Nk+l, there exists (11+1,N k+l,N) which is (P(N))-feasible with state t(N) and whose first there exist* (Yf, )~.)YN k + 1 decisions are (P(k.f 1))-feasible with state s(k + 1). For Nk ~ N < Nk+1, define zN in Y as follows: = f zj, j = 1,...,Ik, i, ZZk, where z'Y is chosen arbitrarily in Yj, for j > N. Once again, one can show that zN E X(Nt(N)), for Nk ~ N < Nk+1. In this way, we obtain a sequence {zN} in Y such that 18

I zN E X(N, t(N)), all N > N1, and =z, j= l,...,e, Ne <NNe+i, =1,..., k-1, k=1,2,... Therefore, zN - z, as N -+ oo, in the product topology of Y and hence, relative to the metric p as well (Lemma 2.1). Consequently, z E liminf X(N, t(N)). * Theorem 5.2 states that whenever a state sequence is reachable from any feasible state. the feasible decisions which reach those states will eventually cover the entire feasible region X. We return to the task of showing, under reachability, that the efficient sets X(N, S(N)) converge to the set of optimal solutions X*. The next lemma establishes the inclusion in (2) above. Lemma 5.3 Suppose S*(N) C S(N) C S(N), all N. If {S(N), N = 1,2,...} is reachable from all feasible states, then limsup X(N, S(N)) C X*. Proof: Fix x in lim sup X(N, S(N)). Then there exists a sequence 1 <N1 <N2 < N3 <.... and a corresponding sequence {xN} such that xN' E X(Ni, S(Ni)), all i, and xN - x, as i -+ oo. Then, for each i, there exists t(Ni) E S(Ni) such that xNi E X*(Ni, t(Ni)), so that x E limsupiX*(Ni,t(Ni)). For each N different from NA, let t(N) E S(N) be arbitrary, so that we get t(N) E S(N), all N. We next show that limsupX*(N,t(N)) C X. Let I = {1,2,...} U {oo}. Then I is a compact metric space under stereographic projection. Define f: YxI-R by f (y N) C(y; N), yEY, N=1,2,..., (yN) - C(y) C, E Y, N = oo. We claim that f is continuous. In particular, if yf -- y in Y and N, -n oo, as n - oc. then If(y,~) - f(yn',N,) = IC(y)- C(y; N;)l < IC(y) - C(yn)I + IC(yn) - C(yn; Nn) IC(y) - C(yn)I + I E c,(yn)), j=Nn+l 19

which goes to zero as n - oo, since C is continuous and uniformly convergent (Theorem 2.2). Since limX(N,t(N)) = X (Theorem 5.2), it follows that the mapping N -~ X(N,t(N)) is continuous from I into KC(Y). Hence, by the Maximum Theorem [4, p.116], it follows that limsupX*(N,t(N)) C X*. This completes the proof since limsupX*(N, t(NM)) C limsupX*(N,t(N)). ~ i N We are now ready to prove our main result in this section. Theorem 5.4 (Efficient Set Convergence) Suppose (P) is separable lower staircase. Let S*(N) C S(N) C S(N), for all N, and suppose {S(N), N = 1,2,...} is reachable from any feasible state. Then: (i) Setting A*(N) = X*(N, S(N)), all N, we have A*(N) -X* as N -- oo, i.e. A* is a convergent finite dimensional algorithm for (P). (ii) For every p in U(X*), we have that sp(X*(N, S(N))) -- sp(X*), as N -- oo, where sp(X*(N, S(N))) is any point in X*(N, S(N)) nearest to p and sp(X*) is the unique point in X* nearest to p. Remark Part (i) also holds in the weaker sense that limX(N,S(N)) = X* [14, p.337]. However, convergence in IC(Y) relative to the Hausdorff metric D requires closed sets. This is particularly important for the tie-breaking procedure described in part (ii). Proof: By Lemmas 5.1 and 5.3, we have that X* = limX(N,S(N)). Now apply Theorem 4.3 and [14, p.337]to complete the proof. * Theorem 5.4 generalizes (to continuous variable mathematical programs) a result proven for discrete decision sets by Ryan, Bean and Smith [17]. For Yj finite and uniformly bounded. all j, and p sufficiently small (where /j = 3,0 </3 < 1) they showed that the uniqueness set U(K) for any K in I(Y) contains the origin. Moreover, letting p be the origin, they showed that the nearest point selection determined by p corresponds to the lexicographically minimum solution. Since the uniqueness set of X* is all of Y for convex programs, we obtain the following consequence of Theorem 5.4. 20

Corollary 5.5 Suppose the mathematical program (P) in the preceding theorem is convex. Then, for any p in Y, Sp(X*(N, S(V))) - sp(X*), as N - oo. Proof: Apply Corollary 4.5.. The use of efficient set convergence in approximating solutions to (P) via solutions to the (P(N)) is complicated by two issues. The first is the task of computing sp(X*(N, S(N))). which is a solution to a quadratic program. The difficulty lies in determining its feasible region, which is the efficient set X*(N, S(N)). What is required is a parametric right hand side solution of (P(N)). For the discrete case, as in Ryan, Bean and Smith [17], a dynamic programming solution of (P(N)) will automatically generate X*(N, S(N)) = X(N, S(N)) for all S, C S(N) C S(N). Also, for the continuous case with one-dimensional surplus states s(N), as in inventory and production planning, the efficient sets are obtainable through conventional parametric programming. However, as the dimensionality of the surplus states grows, the task of computing X*(N, S(N)) becomes more difficult, since multidimensional variation of the right hand side must be considered. The second issue in implementing efficient set convergence in approximating solutions to (P) via those of (P(N)) involves the choice of N. Under the conditions of Theorem 5.4 or Corollary 5.5, a nearest point to p in X*(N, S(N)) will be arbitrarily close to the infinite dimensional optimal solution in X* nearest to p for sufficiently large N. We next provide a stopping rule for discovering how large N must be to insure a desired level of accuracy. The procedure described below is to solve a sequence of ever higher dimensional approximations to (P) until a stopping criterion is met that insures the desired level of accuracy. Specifically, using the finite dimensional algorithm A*, employment of the stopping rule will approximate the first k decisions of the infinite dimensional optimal solution sp(X*) within an error at most 6 > 0. The first part of the procedure is the stopping rule. We begin by fixing p E U(X*) and a corresponding nearest-point selection sp. Let 5*(N) C S(N) C S(N), all N. Let xp denote the unique element of X* such that p(p,X*) = p(p,xp), i.e. sp(X*) = xp. In what follows, it will be convenient to write xp(N,S(N)) for sp(X*(N,S(N))), all N. Recall that by Theorem 5.4, xp(N,S(N)) -- xp. as N -+ co. Likewise, for s(N) E S(N), it will also be convenient to write xp(N,s(N)) for sp(X*(N,s(N))), N = 1,2,.... Let k be a positive integer and 6 > 0. Assume A* is the algorithm given in Theorem 5.4, i.e. A*(N) = X*(N, S(N)), all N. 21

Stopping Rule Stop at N for algorithm A* if N > k and d(xp (N, s(N))j, x*(N, S(N)) ~ 5, j II1...Ik for all s(N) E S(N). The rule states that the algorithm A* can be terminated when the nearest-point selections to all feasible states in S(N) at N differ from the efficient set selection by at most S in the first k decisions. Forward Algorithm 1.- Choose k and S. Set N = k. 2. Solve (P(N)) using algorithm A* to obtain xp(N, s(N)), for all s(N) E S(N). 3. If the stopping rule is not satisfied, set N = N + 1 and go to 2. 4. Stop. Theorem 5.6 If the Forward Algorithm terminates at N, then x*(N, 5(N)) approximates x* within error at most S in the first k decisions, i.e. dj(x*(N, S(N)-)j,(x*)3) ~ 5, j = 1,.., k. Proof: For each N, let.s*(N) = aN+1,N((X*)N) so that s*(N) E S*(N). By the triangle inequality, we have that + d,(xp(N,s*(N))j, (x*)3), j =1,... Ik. By hypothesis, it follows that di~*(N SN)) Ixp(N, s*(N))j) ~ 8, j =k,. since S*(N) S(N). Thus, the proof will be complete if we show that xp(N, s*(N))3 (x)1, j1,...k. Suppose for the moment that N N E~p((x)-,j)'< Zpj(xp(N,s*(N))j, p3)2. j=1.1=1 22

j Define (x)j, j = l,...V, 3 x p(N,s*(N))j, j= N +.... Then z is (P(N))-feasible with state s*(N), i.e. z E X(N,s*(N)). In fact, by the principle of optimality, z must also be optimal, i.e. z E X*(N, s*(N)). Moreover, by our assumption, N oo p(z p)2 = E pj(zpj)2 + E pj(zj,pj)2 j=1 j=N+1 N oo = Zpj((x *)3 p)2 + E pj(xp(N,s*(N))j,pj)2 j=l j=N+1 o0 < p (xp(N, s*(N))jpj)2 j=l = p(x(N, s*(N)),p)2, which implies that z in X*(N,s*(N)) is closer to p than xp(N,s*(N)). Contradiction. Hence, it must be that N N Epj((x;)jp)2 > E pj(xp(N,s*(N))j,pj)2. j=1 j=l Now define y by x p(N, s*(N))j, j =,..., N YJ (x), j =N+1,.... Since y has state s*(N) at N, it is easy to see that y E X. Moreover, since xp X*(N, s*(N)), we have that N oo C(y) = y Cj(y) + E cj(yj) j=l j=N+l N oo = Ecj(xp(N,s*(N))j) + E cj((x;)j) j=l j=N+1 N co = E C((xp.)) + E Cj((x)3) j=1 j=N+l = C(x), 23

i i.e. y is optimal for (P), so that y E X*. Finally, by above N 00 Xy P, = P Zp(xp(,s(N))j+ Epj) +Y. Z P (x),p) j=1 =N+1~~3N+ N 00 ~ p,((X p) 3,p),) + >ii p3((x*)3,p),) j=1 ~~~=N+1 =p(x*,p)2, which implies that y = xsince x*is the unique point in X* nearest to p. Consequently, and the proof is complete, since N > k by the Stopping Rule. I We turn next to the question of when the stopping criterion will ultimately be met. Theorem 5.7 The Forward Algorithm will finitely terminate for any choice of k and 6 whenever X* (N, s(N)) -+X* in IC (Y), as N — + oc, for all choices s(N) E S(N), N =1, 2,. Proof: If not, then the Stopping Rule is not satisfied eventually for some positive integer k and 6 > 0. Thus, for each N > k there exists s(N) E S(N) and 'N E {1..,k} such that djNv(xp(Njs(N))jN, x*(NS(N))jN) > S. Since { 1,..,k} is a -finite set, there exists jo E { 1, k.,Ik for which 'N = jo infinitely often. Thus, there exists a subsequence {N,} of {N:N > k} such that Nt > k and djo0(xp (Ne Is (Ne))0 olx*(NeS(Ne))j0) > 6, e = 1,21.. By Theorem 5.4, we have that x*(N, S(N)) — + x*, as N -o 0, 50 that x*(Ne, S(N,)) X*as e — + oo. Hence, by Lemma 2.1, x*(NeI S(Ne))jo — + (x*),0, as ~ -oo. By our hypothesis, X*(N, s(N)) -+X' in AC(Y), as N — +00. Thus, X*(Ne,s(Ne)) -Xa. and consequently xp(Ne, s(Ne)) -+x*, [18, Theorem 3.4] so that x p(Ne, s(Ne))3 jo x )jas ~ +0. 24

i Hence, by the triangle inequality, dj (xp(Ne, s(Ne)) j, x(Ne, S(Ne))j0) -) 0, as e - o, which is a contradiction. * If the convergence condition of Theorem 5.7 holds, then the Stopping Rule will be satisfied eventually. What remains is to give a sufficient condition for this convergence to take place. Theorem 5.8 Let s(N) E S(N), all N. If(P) has a unique solution, then X*(N, s(N)) - X* in AC(Y), as N -+ oo and hence the Forward Algorithm will finitely terminate for any choice of k and 6. Proof: By the proof of Lemma 5.3, we have that limsupX*(N,s(N)) C X*. On the other hand, X* C liminfX*(N,s(N)) by Corollary 2.2 of Schochetman and Smith [18]. * 6 An Application to Production Planning The theoretical development of (P) in the previous sections proceeded from three major assumptions: separability, lower staircase structure and reachability. Sequential decision making over an unbounded horizon constitutes an important class of problems which typically meet these assumptions. In particular, the lower staircase structure can be obtained by introducing inventory-like surplus variables which summarize the effect of past decisions on current and future decisions. Examples include production and inventory planning and control, capacity expansion and equipment replacement. We will illustrate the previous development by an application to production planning. Consider the problem of scheduling production to meet non-stationary, deterministic demand over an infinite horizon. The objective is to optimally balance the scale of production against the cost of carrying inventory. The problem may be formulated by the following mathematical program [6, p.87]: 00 min E (kj(Pj) + hj(Ij))c-1 j=l subject to (Q) Ii-1 + Pi -I = Di, i = 1,2,... 0 < Pj < P, j 1,2,... -B < I < I, j = 1,2,..., where Ij is the net inventory ending period j with lo = 0, Pj is the production in period j, Dj is the demand for production in period j, kj is the production cost and hj is the 25

inventory holding/backorder cost for period j, j = 1, 2,.... The factor a is the discount factor reflecting the time value of money, where 0 < a < 1. We require that P > 0, I > 0, B > 0 and P > Dj > 0, all j. If B > 0, then backlogging is allowed. We impose the following assumptions on (Q). Assumptions I. For each j, the production cost kj and inventory holding cost hj are continuous, convex and uniformly bounded by an exponential function with rate at most 1/a, i.e. there exists G > 0 and 0 < 7 < 1/a such that max( sup kj(Pj), sup hj(Ij)) < G y, j = 1,2,.. O<Pj<P -B<I <I II. liminf Dj < P and limsup Dj > 0. Assumption I provides for existence of an optimal solution and for flexibility in choosing p in Y for nearest-point selection. Assumption II is a regularity condition required to guarantee reachability for (Q). Our first task is to show that (Q) may be reformulated as a special case of (P). For each j, define YJ [ p] and Yj = [-B,I] x [0,P]. Then yj E?2, all j, and the Yj are the same compact, convex subset of 32. The production planning problem (Q) may now be expressed in the form (P) as follows: 00 min E Cj(yj) j=l subject to (Q) ai,i-1(yi_1) + aii(yi) > bi, i 1,2,.. yj E Yj, j=l,2,... where cj(yj) [kj(Pj) + hj(Ij)]-1, j = 1,2,..., aii(Yi) 1 1 [ i=,2... a,.iY-) I ii i = =2,3,...., 26

alo is identically zero and bi = i = 1,2,.... Di j By construction, the program (Q) is convex and separable lower staircase. Moreover, since Y. 0 1 h j-=,2,..., [L Dj yields a feasible solution for (Q), we have that the feasible region X: 0. For each N = 1,2,..., the finite dimensional approximation (Q(N)) to (Q) becomes a finite horizon approximation given by N min E c((yj) j=l subject to (Q(N)) ai,i-1(Yi-1) + aii(Yi) > bi, i = 1,2,...,N, yj E Yj, j=1,2,...,N. Since the inventory levels I1,...,IN are defined by the production schedule PI,..., PN via ~3 3 j - EP - E D, j=1,2,...,N, i=i i=l we will say that (P1,..., PN) is feasible for (Q(N)) if 0 < Pj < P and.1 3 3 -B + Di < P I, < I + EDi, j=l,...,N. i=l i=1 i=1 Suppose (P1,..., PN) is (Q(N))-feasible. The corresponding state s(N) is then given by s(N) = aN+1,N(YN) [-1 O] [ PN -IN i.e. s(N) can be identified with the feasible inventory IN at the end of period N. Moreover. if we let X(N) denote the non-empty set of (Q(N))-feasible production schedules, i.e. X(N) = (P,...,PN) E [O,P]N:-B < -E o <, I < n < N. j=l j=l 27

then X(N) is clearly a convex polytope. Also, since the mapping N N (PI,...,PN) -A ZPj - Dj = IN j=1 j=1 is continuous and affine on X(N), its (non-empty) image is a compact, convex subset of [-B,I]. Thus, the set S(N) of all (Q(N))-feasible states may be identified with a closed subinterval of [-B, I], i.e. (N) = {[ -B < X < I for some B and I satisfying -B < -B < I < I. For the case of no backlogging, i.e. B = 0, and where either kj or hj is strictly increasing on its respective domain, 1 < j < N, it is clear that if (P,,..., Pk) is optimal for (Q(N)), then the inventory IN ending period N must be zero. It then follows that X*(N) C X*(N, 0), where 0 = [0, 0]t. Since the opposite inclusion is also true, we have that X*(N) = X*(N, 0). Therefore, when it is feasible to obtain a strictly positive ending inventory for period N (e.g. when B = 0, P = 2, = 1, Dj = 1, all j), we must have X*(N) C X(N), i.e. strict inclusion. Thus, in general, X(N) is strictly larger than X*(N), all N. We turn next to the problem of establishing reachability for (Q). Lemma 6.1 Under Assumption II: (i) There exists 0 < p < P and a subsequence {Dj: m = 1,2,...} of {Dj: j = 1,2,...} such that Djm < p < P, for all m. (ii) There exists 0 < 6 < P and a subsequence {D: n = 1,2,...} of {Di: i = 1, 2,...} such that 0 < 6 < Din, all n. Remark Assumption II is necessary as well as sufficient for (i) and (ii) to hold. Proof: Omitted. * By Lemma 6.1, since 0 <3<'j < P, all j, it follows that inventory can be stockpiled by the amount P - Dj > 0 during periods of maximum production. In particular, this amount will be at least a = P - p > 0 during the periods jm, m = 1,2,.... Analogously, inventory can be depleted by the amount Di during periods of no production, where this amount will be at least 6 during the periods in, n = 1,2,.... This is enough to guarantee reachability as the next lemma asserts. 28

Lemma 6.2 Suppose S*(N) C S(N) C S(N), all N. Then, under Assumption II, {S(N), N = 1,2,...} is reachable from all feasible states. Proof: See the Appendix. r Under Assumptions I and II, we then have (from Theorem 5.4) that efficient set convergence takes place for (Q) and, moreover, (from Corollary 5.5) that any nearest-point selection of points from the efficient sets will converge to an optimal solution of (Q). More specifically, let P*(N) = (P*(N),..., P(N)) be the production schedule for (Q(N)) corresponding to a nearest selection to the origin 0 in Y for the efficient set X*(N) = X *(N,I(N)), consisting of the closure of all optimal production schedules to all possible feasible inventories ending period N. Let p = (P1, P, P...) be the production schedule corresponding to the unique optimal solution to (Q) nearest 0. Theorem 6.3 Suppose (Q) satisfies Assumptions I and II. Then P*(N) - P*, as N -- o0, i.e. P;(N) -+ P;, as N -- oo, for allj = 1,2,3,.... Since the states, i.e. inventories, are one-dimensional, it is not difficult to calculate the efficient sets and hence, the nearest-point selections P*(N),N = 1,2,.... The previous theorem assures us that these approximations to the infinite horizon optimal production schedule will converge to P* as the horizon N lengthens. The Forward Algorithm of section 5 may, moreover, be used to attempt discovery of a horizon N sufficiently far off to generate the desired accuracy in our estimate of the optimal first production decision P1. It is interesting to note that in the discrete case of no backlogging corresponding to B = 0, the monotonicity of the optimal production schedule P*(N) in the horizon N [6. p.105] yields for all selections Pj(N) -+ P*, as N - oo, for all j, and hence, P*(N) - P*. as N -+ oo. One can show from this same monotonicity property that the efficient set point closest to the origin is the closest amongst those with zero ending inventory, i.e. the closest from the finite horizon optima X*(N). Therefore, the selection procedure reduces. in the no backordering case, to the classical result that P*(N) P*, as N -) oo. However. in the presence of backordering, the monotonicity property no longer holds [6, p.105]) and nearest-point selections are thus employed to ensure convergence. Acknowledgement We are indebted to Peter Benson for the statement and proof of Lemma 2.1. 29

I APPENDIX In this appendix, we give the proofs of Lemma 2.1 and Theorem 6.2. Lemma 2.1 The p-metric and product metric topologies on Y are the same. Proof: From the formulas in section 2, it is not difficult to see that convergence in Y relative to p implies pointwise convergence in the Yj relative to the d, j = 1,2,.... Thus, the product topology is contained in the metric topology. Conversely, suppose U is a p-metric open subset of Y. Fix x in U and let e > 0 be such that B,(x) C U, where B(x) = {y EY: p(x,y) < e}. For each j, consider the mapping yj - dj (xj, yj) of JRnj into R. Since this mapping is continuous and Yj is compact, there exists xX in Yj such that dj(x, xj) = max, dj(y, xj)2,... yj EYj Let x* = (x*), so that x* E Y; consequently, xz E H. Then 00 p(x,x)2 = E 32 dj(xj, x*)2 < 0o, j=l so that there exists N sufficiently large for which 00 E /Pdj( (jxj)2 < 62/2. j=N+l Define 6 = e/I/2N < e and W = B}(xi) x... x B (XN) x YN+1 x YN+2 x, where Bj(xj) is the open ball in Yj of dj-radius 6 centered at xj. Then Wx is a subset of Y which is open in the product topology, since it is a product of open sets, finitely many of which are proper. Also, x E Wx, so that UC U W. xEU Conversely, let x E U and y E We. Then, by definition of W,, we have that N = p(X, y)2 23dj(x, yj)2 + jdj(xyj)2 j=l j=N+l 30

N oo < E; 62 + E 3:dj(Xj,yj)2 j=l j=N+1 N oo < E 6 + E 2dj(xX)2 j=l j=N+1 N < E e2/2N + 62/2 j=l = 2 Therefore, y E B,(x) C U, i.e. W, C U, x E U, so that U W, C U and hence U W., = U/. xEU xEU Consequently, since U is the union of product open sets, it is itself an open subset of Y in the product topology. Hence, the metric topology is contained in the product topology and the proof is complete. * Lemma 6.2 Suppose S*(N) C S(N) C S(N), all N. Then, under Assumption II, {S(N), N = 1, 2,...} is reachable from all feasible states. Proof: We will show more generally that {(N): N= 1,2,...} is reachable from any state s(k) in S(k) at any period k = 1,2,.... Accordingly, suppose we are given period k with feasible ending inventory J and a sequence of feasible ending inventories IK1,K2,...,KA,.... Then there exists (Q(k))feasible (yl,..., Yk) with Ik = J. Suppose for the moment that J = -B and we wish to reach inventory level I at some time in the future. By Lemma 6.1(i), there exists unique Nk such that k+NI -B + E (P-Dj)< I j=k+l while k+Nh+l -B + Z (P-Dj)>I. j=k+l Analogously, suppose that J = I and we wish to reach inventory -B. By Lemma 6.1 (ii), there exists Nk' such that k+Ni' I - E Dj > -B j=k+l 31

I while k+N"'+1 ' - S Dj < -B. j=k+l Now set Nk = max(k + Nk + 1, k + Nk" + 1) and let N > Nk. We will show that we can feasibly reach from inventory level J at the end of period k to inventory level KN at the end of period N. Recall that we have Q (k)-feasible productions P1,..., Pk with inventories satisfying Ik = J. Fix N > Nk. There are three cases to consider: J = KN,J < KN and J > KN. If J = KN, define P3 = D.,j = k + 1,..., N. Then (P17...,PN) is (P(N))-feasible with ending inventory N N IN = - Dj j=1 j=1 k k = P3-E Dj j=1 j=1 J KN. If J < KN, then as above, there exists unique n' such that k + n' < k + N', i.e. k + n'+ 1 < N, and k+n' J~+: (P - Dj). KN =kl+l while k+n'+l J+ 5 (P-Dj)>KN. j=k+l Define P) j =ki ll i... kE + n', Dk+ni+l + KN _ j _ 1:k+n' (P - Dj), j =kI n / + i Dj, j = j (n')2,j...kn N. Then (P1,..., PN) is (P(N))-feasible with ending inventory N N IN = Pi E Dj.=1 j=1 k+n'+l k+n'+l - PJ%- Dj.i=1 1j=1 32

I k+n'+l = J+ E (Pj-Dj) j=k+l k+n' = J+ E (P-Dj) j=1 = KN. + Pk+n'+l - Dk+n'+l Finally, if J > KN, then there exists unique n" such that k + n" < k + N', i.e. k +n" + 1 < N, and k+n" J- 1E Dj > KN j=k+l while k+n"+l J- Dj <KN. j=k+l In this case, define Pi=, j = k+1,...k+n", Dk+n,+l - J + E=k+l Dj + KN, Dj, j=k+n"+2,...,N. j = k + n" + 1, Then (P1,...,PN) is (P(N))-feasible with ending inventory N IN = E P j=1 N -ED J=l k+n"+l = E pjj=1 k+n" =J- E Dj k+n"+l E D j=l + Pk+n"+l - Dk+n"+l = KN, as required. * 33

i REFERENCES 1. E. J. Anderson and P. Nash, Linear Programming in Infinite Dimensional Spaces (Wiley, New York, 1987). 2. J.-P. Aubin, Applied Functional Analysis (Wiley, New York, 1979). 3. J. C. Bean and R. L. Smith, "Conditions for the Existence of Planning Horizons," Mathematics of Operations Research, 9 (1984) 391-401. 4. C. Berge, Topological Spaces (Oliver and Boyd, London, 1963). 5. C. Bes and S.P. Sethi, "Concepts of forecast and decision horizons: applications to dynamic stochastic optimization problems", Mathematics of Operations Research, 13 (1988) 295-310. 6. E. V. Denardo, Dynamic Programming: Models and Applications (Prentice-Hall, Englewood Cliffs, 1982). 7. S. D. Flam and R. J.-B. Wets, "Existence results and finite horizon approximates for infinite horizon optimization problems", Econometrica 55 (1987) 1187-1209. 8. R. Grinold, "Infinite horizon programs", Management Science 18 (1971) 157-170. 9. R. Grinold, "Finite horizon approximations of infinite horizon linear programs", Mlathematical Programming 12 (1977) 1-17. 10. R. Grinold, "Convex infinite horizon programs", Mathematical Programming 25 (1983) 64-82. 11. F. Hausdorff, Set Theory (2nd. ed.) (Chelsea, New York, 1962). 12. P. C. Jones, J. L. Zydiak and W. J. Hopp, "Stationary dual prices and depreciation". Mathematical Programming 41 (1988) 357-366. 13. J. L. Kelley, General Topology (Van Nostrand, New York, 1955). 14. K. Kuratowski, Topologie I (Academic Press, New York, 1966). 15. K. Kuratowski, Topologie II (Academic Press, New York, 1968). 16. L. W. McKenzie, "Turnpike theory", Econometrica 44 (1976) 841-865. 17. S. Ryan, J. C. Bean and R. L. Smith, "A tie-breaking algorithm for infinite horizon optimization", Working Paper, The University of Michigan, 1989. 34

i 18. I. E. Schochetman and R. L. Smith,"Infinite horizon optimization", Mathematics of Operations Research 14 (1989) 1-16. 19. I. E. Schochetman and R. L. Smith, "Convergence of selections with applications in optimization", Working Paper, The University of Michigan, 1988, submitted to Journal of Mathematical Analysis and Applications. 35