SOLUTION APPROXIMATION IN INFINITE HORIZON LINEAR QUADRATIC CONTROL IRWIN E. SCHOCHETMAN Department of Mathematical Sciences Oakland University Rochester, MI 48309 ROBERT L. SMITH Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 91-25 September 1991 C/?aQh n -e? 7''' G rodoU

SOLUTION APPROXIMATION IN INFINITE HORIZON LINEAR QUADRATIC CONTROL Irwin E. Schochetman* Department of Mathematical Sciences Oakland University Rochester, Michigan 48309 Robert L. Smitht Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 September 9, 1991 Abstract We consider the problem of choosing a discounted-cost minimizing infinite-stage control sequence under nonstationary positive semidefinite quadratic costs and linear constraints. Specific cases include the nonstationary LQ tracker and regulator problems. We show that the optimal costs for finite-stage approximating problems converge to the optimal infinite-stage cost as the number of stages grows to infinity. Under a state reachability condition, we show that the set unions of all controls optimal to all feasible states for the finite-stage approximating problems converge to the set of infinite-stage optimal controls. A tie-breaking rule is provided that selects finite-stage optimal controls so as to force convergence to an infinite horizon optimal control. Key Words and Phrases Linear dynamic quadratic criteria control, infinite horizon, nonstationary, positive semidefinite costs, bounded variable. *The work of Irwin E. Schochetman was partially supported by an Oakland University Research Fellowship. tThe work of Robert L. Smith was partially supported by the National Science Foundation under Grant ECS-8700836. 1

1 Introduction Consider the following infinite stage linear quadratic control problem. 00 min [ - rk)Q k(Z - rkk) + uRkuk] k=O subject to (C) Xk+1 = Akxk + Bkuk + dk, Zk = CkXk, k = 0, 1,2,..., and Uk E UkCIRm, Xk E XkCIR, Zk E RP, k = 0,1,2,..., where Xo in JR1 is given. We make the following assumptions on the problem data: A. The data are deterministic. B. Each matrix Qk and Rk is symmetric and positive semi-definite. C. Each Xk is a closed convex subset of IR'. D. Each Uk is a compact convex subset of IR"m. E. The resulting feasible region is non-empty. F. The objective function converges absolutely and uniformly over the feasible region. As usual, Xk is the state, Uk is the control and Zk is the output. The quantity dk is a (known) disturbance. If we set dk to zero, all kc, then we get the nonstationary LQ tracker problem [12] as a special case. Alternatively, if we also set Ck to the identity matrix and rk to zero, all k, then we get the nonstationary LQ regulator problem [12]. The general infinite horizon LQ problem (C) is challenging in several respects. First, the presence of nonstationary data, as well as constraints on the admissible controls, presents a problem that is acknowledged to be difficult to solve [1,9]. It is nonetheless almost certain that in practice there will be bounds on feasible controls and states. Also, generalizing previous work [2,9], we do not require the control space in each period to be finite. Second, Assumption B allows the quadratic control costs to be positive semi-definite, so that in 2

general there will be multiple infinite horizon optima. This complicates the task of approximating an infinite horizon optimal solution though finite horizon truncations as in [2,9,10], since, in general, finite horizon optimal controls will not converge. In the presence of a state reachability property similar to that of [10], we show how to select finite horizon optimal controls so as to force convergence to an infinite horizon optimal control strategy. In related work, in a more abstract framework than ours, [5] establishes existence of an optimal infinite horizon solution and [7] proves convergence of optimal values for a "moving horizon" sequence of approximating solutions (see also [6] for related stability results). In section 2, we introduce the finite horizon (or finite stage) approximations (C(N)) to (C) consisting of the first N controls and N constraints of (C). We then establish that the optimal values of (C(N)) converge to the optimal value of (C) (i.e. optimal value convergence). We also show that for positive definite control costs, the optimal controls for (C(N)) converge to the optimal control strategy of (C), (i.e. solution convergence). In section 3, in the presence of a state reachability property, we show that the best approximations in the set of optimal controls for (C(N)) converge to the best approximation in the set of infinite horizon optimal controls. This allows for an arbitrarily close approximation to an infinite horizon optimal solution by solving a sufficiently long finite horizon version of (C). Finally, in section 4, we illustrate the preceding development with an application to multiproduct production planning. 2 Value and Solution Convergence Our first objective is to characterize the set of states Vk at stage k that are reachable by admissible controls from the initial state x0. That is, let V1 = {Aoxo + Bou + do: u e Uo} and Vk+l = {Ak + Bk+dk E Vk E Uk}, k = 1,2,.... Then it is easy to see that each reachable set Vk is a compact, convex, non-empty subset of 1R1. Next define the set Sk of all feasibly reachable states at stage k from the initial state x0. Let T = {Aoo o+Bou+do:u E Uo}, S1 = T1 nX1, and Tk+1 = {AkX+BkU+dk:xESk,uE Uk} Sk+l = Tk+lnXk+l, k = 0, 1,2,.... 3

Clearly, each Tk and Sk is a compact, convex subset of IRJ. Since there exists a feasible solution to (C) by Assumption E, both Tk and Sk are non-empty, kI = 1,2,.... If X = R, all j, then of course Sk = Tk = Vk, all k. For an explicit construction of the feasibly reachable states when controls and states are linearly constrained, see [11]. Lemma 2.1 For each k = 0, 1,2,..., the following are equivalent: (i) x E Sk+1. (ii) x E Xk+l and there exist uj E Uj, 0 < j < k and Xj E Sj, 1 < j < k, such that xj+l = Ajxj + Bjuj + dj, for j = 0,1,..., k, where Xk+l = x. Proof: Omitted. * Finally, define the set of reachable outputs Zk by Zk {Ckx:xeVk}, k=1,2,.... Then each Zk is a compact, convex, non-empty subset of IRP. For convenience, we let yk = (ukl, Xk,Zk),Yk = Uk-l x Vk x Zk,k = 1,2,... and Y = IHI=IYk. Then each Yk is compact, convex and non-empty. As in [14], we embed Y in a Hilbert space formed by the weighted Hilbert sum of its component spaces. Letting q = m + n + p, we have that Yk C IR, k = 1, 2,.... Since the Yk are compact, for each k, there exists rk > 0 such that 11 Yk 11< rk, where || * || is the usual 00 norm on IRq. Fix 0 < fk < 1, such that Z/3irk < oo; for example, set 3k = 1/krk. Let k=l,0 H ={(Yk):Yk E R k=l 1,2,...,andEk2 || k || 2< 00}. k= 1 Then H becomes a Hilbert space contained in 1 IIklRq with inner product < x, y > given by 00 < x,y>= 32(k,yk), k= 1 where (,.) is the usual inner product on IRq. From our choice of the /k, it follows that Y C H, so that Y inherits the Hilbert metric p of H, where p(x, y) = (< x - y, - y >)1/2, x, y E H. It was noted in [14, Lemma 2.1] that the p-metric topology on Y is the same as the product topology, so that Y is a compact metric space relative to p by the Tychonoff theorem. Moreover, a sequence {yn} in Y converges to y relative to p if and only if for each k, {yk} converges to yk in IR relative to the usual Euclidean metric. 4

Define KC(Y) to be the space of all compact, non-empty subsets of Y and let D denote the Hausdorff metric on K(Y) derived from p [4]. In this way, IC(Y) becomes a compact metric space, so that convergence in )C(Y) is relative to D. There is an alternate characterization of convergence in KC(Y) which will prove useful in stating our main results. Let KN C Y, for N = 1,2,.... Define liminf KN and limsup KN as follows [4,8]: 1. y E liminf KN if and only if y E Y and, for each N sufficiently large, there exists yN E KN such that yN -Y y, as N -+ oo. 2. y e lim sup 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 KNk, all k, and yk - y, as k -- oo. If K C Y and K = liminfKN = limsup KN, we write lim KN = K and say that {KN} Kuratowski- converges to K. In general, lim inf KN and lim sup KN are closed, possibly empty, subsets of Y, which satisfy liminf KN C limsup KN. Suppose now KN is not empty for N large. Since Y is compact, we have that lim sup KN 7$ X. Also, if K E KC(Y) and KN E C(Y), all N, then KN -* K in /C(Y) relative to D if and only if lim KN = K. The feasible region F for (C) is clearly a closed, convex subset of Y. Thus, F is also compact and nonempty by Assumption E, so that F E 1C(Y). From this it follows that the set Sk of feasibly reachable states at stage k is non-empty, for each k. If x = (Xk) E F, then by Lemma 2.1, Xk E Sk, all k. If we also write y = (Yk) and abbreviate the objective function for (C) by 00 C( = Z[(k - rk) Qk(Zk - rk) + uRkUk], k=O then (C) becomes min C(y). yEF In order to establish continuity for the objective function, we let ci(yi) = ci(uo, xi, i) = (Z - ro)tQo(zo - ro) + 4Rouo + (Z1 - rl)tQ1(Z1 - rl) and Ck(yk) = Ck(Uk-1, Xk, Zk) = (Zk- rk)tQk(Zk - rk) + U-_lRk-lUk-1, k = 2,..., 00 so that each Ck is a continuous, convex function on IRm x IRn x IRP. Then C(y) = ECk(Yk), k=l y E Y. Since the Uk and Zk are compact, we may define /k = max || Ik, II0, = 1,2,..., ukCEUk''

and (k= max | zk-rk 11, k= 1,2,... zkEZk 00 00 Throughout this paper, we assume -'2 11 Rk 112< oo and Ck II Qk 112< o0, where k=i k=1 11 A 112= sup. 11 Aw 11 /11 w 1| denotes the matrix norm of matrix A relative to the ~2-norm on IRm and 1R' respectively. If 11 Ck loo= supykEY Ck(yk) denotes the supremum norm of Ck as a function on Yk, then 00 00 00 Z II Ck 11~<j E II Rk 112 + E (k II Qk 112< 00, k= 1 k=O k=1 i.e. the series is absolutely convergent. Consequently, the correspondence y -- C(y) defines a continuous, real-valued function C on Y which is the uniform limit of the sequence N {I Ck}= 1 of continuous partial sums. kc=I Since C is continuous on Y and F is a compact, non-empty subset of Y, the objective function C attains its minimum C* on F. If we let F*= {y E F: C(y) C}, then F* is a compact, non-empty subset of Y, i.e. F* E C(Y). Thus, under our assumptions, (C) is a convex programming problem with continuous objective function C, compact, convex, non-empty feasible region F, optimal objective value C* and compact, non-empty optimal solution set F*. Note that since C is not required to be strictly convex, F* will not be a singleton in general, so that there may be multiple optimal solutions y*. Our primary objective in this paper is to approximate the optimal value C* and an optimal solution y* of (C) by corresponding quantities obtained from finite-stage subproblems of (C). To this end, let N be a positive integer and define the problem (C(N)) as follows: N-1 min [Zk - rk) Qk(k - rk) + URkUk)] + (ZN - rN)QN(ZN - rN) k=O subject to (C(N)) Xk+l = AkXk+BkUk+dk, k=0,1,...,N-1, Zk = CkXk, k=1,...,N, Uk EUk, k E Xk, Zk E Zk, k= 1,2,..., where ox (hence Zo) is given. In order that feasible solutions for (C(N)) be comparable to those of (C), we have defined (C(N)) to be an infinite stage problem with constraints and objective function depending 6

only on the first N stages. The feasible solutions are just arbitrary extensions of the feasible solutions to the N-stage truncation of (C). For each N = 1, 2,..., the feasible region F(N) for (C(N)) is contained in Y. Moreover, F(N + 1) C F(N) and F C F(N), so that F(N) is non-empty, N = 1,2,.... Also, each F(N) is compact and convex and F = lim F(N). If N-.oo x E F(N), then automatically xk E Sk, k = 1,..., N. For convenience, denote the objective function for (C(N)) by C(;N). Then (C(N)) becomes min C(y; N). yEF(N) By our assumptions, the continuous functions C(.; N) converge uniformly to C on the compact space Y. Moreover, each C(; N) is convex, so that (C(N)) is again a convex programming problem. We set C*(N) = min C(y; N) yEF(N) and F*(N) ={y F(N): C(y;N) = C*(N)}, N = 1,2,..., so that C*(N) is the optimal objective function value and F*(N) is the set of optimal solutions for (C(N)). Clearly, each F*(N) is a compact, non-empty subset of F(N). Theorem 2.2 (i) (Optimal Value Convergence). The optimal values of the finite-stage problems (C(N)) converge to the optimal value of the infinite-stage problem (C), i.e. C*(N) - C*, as N - oo. (ii) (Optimal Solution Convergence) If Qk and Rk are positive definite, for some k 1,2,..., then C is strictly convex. In this event, (C) has a unique optimal solution y*, i.e. F* = {y*}. If y*(N) is any optimal solution to (C(N)), then the sequence {y*(N)} converges to y* in the product topology of Y. In particular, optimal controls {1* (N)}1k= of the finite-stage problems (C(N)) converge to the optimal control {u}}lo= of the infinite-stage problem (C), i.e. uk(N) - uk, as N -- oo, for k = 1,2,.... Proof: (i) and (ii) follow immediately from Theorems 4.1 and 4.5 of [14] respectively.. Remark: More generally, the last part of this theorem is valid whenever F* is a singleton [14]. In view of this result, it remains to study the question of optimal solution convergence when F* is not a singleton, i.e. when there exist multiple optimal solutions to (C). The 7

difficulty is that in this case of multiple infinite-stage optima, optimal controls to the finitestage subproblems may not converge. In order to allow for convergence, we need to enlarge the set of finite-stage controls from which we select. In particular, we enlarge F*(N) to include optimal controls to all states. In this regard, note that if y is feasible for (C(N)), then the only connection between the constraints of (C(N)) and the remaining constraints of (C) is the value ANXN, which is the dynamic programming state associated with y at stage N. This is the motivation for what follows. If s is any element of IRE, define F(N, s) to be the set of (C(N))-feasible solutions having dynamic programming state s at stage N, i.e. F(N,s) = {y E F(N): ANN = s, N = 1,2,.... Thus, F(N, s) is a (possibly empty) compact subset of F(N). Define S(N) = ANSN - {s E R: ANX =, some x E SN}, N =1,2.... Then S(N) is the set of all (C(N))-feasible dynamic programming states at stage N. Lemma 2.3 For each N = 1,2,..., S(N) = {(s R:F(N, s) ) } = {s E IR: ANXN = s, for some y E F(N)}. Proof: Follows from Lemma 2.1.. For each N = 1,2,... and s E S(N), consider the mathematical program (C(N), s) given by min C(y; N). (C(N), s) yeF(N,s) Since the minimum value C*(N, s) is attained, we may define F*(N, s) = {y e F(N, s): C(y; N) = C(N, s)}, which represents the set of all solutions optimal to dynamic programming state s E S(N) for problem (C(N)). Each such F*(N, s) is a compact, non-empty subset of F(N), i.e. an element of KC(Y). In order to construct a sequence of (C(N))-feasible solution sets which converges to F* in K(Y), define (N)= UES(N)F*(N, s), N = 1,2,.... For technical reasons, we also define * (N) to be the closure of F (N) in Y, so that F*(N) E IC(Y), all,N. 8

3 Controllability, Reachability and Solution Convergence via Best Approximation We turn next to the task of establishing conditions under which the sets F*(N) converge to F* in K(Y). When this happens, the sequence of best-approximations from the Y*F(N) (relative to any point in Y) is guaranteed to converge to the best-approximation in F* [14]. (A best-approximation from a set K E KC(Y) with respect to a point p E Y is a point in K closest in the Hilbert metric to p.) As we saw in [14], a sufficient condition for this convergence was a state reachability property. As we shall see, this property in turn can be derived from a suitable controllability property for the constraint system. In order to define controllability for this problem, we must first express xk+1 in terms of Xj,,..., Uk, for O < j < k. As is customary, for O < j < k + 1, define the matrix -F(kj) { Ak..Aj, j < k, iI j, j=k+1. Also, for 0 < j < k define the matrices <,(k \j) = [Bk, AkBk-l, AkAk-lBk-2,..., Ak *. Aj+lBj], j < k,.(k,j) =( Bk, j = k, and ^(k J j [I, Ak, AkAk-1,..., Ak... Aj+], j < k, ~(kj) =, j = k. Lemma 3.1 We have the following properties for r, 4, and ~: (i) r(k,j)=Akr(k- 1,j), 0 < j < k. (ii) I(k,j) = [Bk, Ak * ((k - l,j)], 0 < j < k, where Ak * I)(k - l,j) is the partitioned matrix 4I(k - l,j) with each matrix in the partition premultiplied by Ak. (iii) IV(k,j) = [I, Ak *'(k - 1,j)], 0 < j < k, where Ak * (k - 1,j) is defined as in (ii). Proof: These follow immediately from the definitions.. Lemma 3.2 For each 0 < j < k, suppose x+l = Aexe + Beut + de, e = j,..., k, where Xe ERn, for all e. Then xk+l = r(kj)xj + 4(k,j)[uk,... ujlt + tI(k,j)[dk,., dj]t. 9

Proof: By induction on j and k with k > j. * We are now ready to define controllability. Let 0 < j < k. The constraint system for (C) is (j, k) - controllable if, for each xj E Si and xk+l E Sk+l, there exists ui E Ui, j < i < k, such that: (i) Xk+l r(Fk,j)xj + Q(k,j)[uk,..., uj]t + (k,j)[dk,..., dj]t and (ii) r(i,j)xj + 4)(i,j)[ui,...,,Uj]t + 1(i,j)[di,..., dj]t E Si+1, j < i < k - 1. Remarks: Part (i) says that, for any pair of feasible states xj and Xk+l at stages j and k + 1 respectively, there exists a sequence uj;,..., k of controls which transforms xj into Xk+l. Alternately, the Uj x... x Uk - span of the columns of 4(k,j) contains the subset of IR" given by Sk+1 - r(k, j)Sj - (k, j)[dk,..., dj]t. Part (ii) says that the states si obtained in the intermediate stages satisfy si E Si, j < i < k, i.e., they are feasible. In the special case where each Xi is 1R, this is automatically the case. Then, the constraint system of (C) is (j, k) - controllable if (i) holds. We say that the constraint system for (C) is controllable if, for each j = 0,1, 2,..., there exists kj > j such that the constraint system for (C) is (j, k) - controllable for each k > kj. Hence, the constraint system is controllable if from any feasible state, we can eventually reach all subsequent feasible states. A simple sufficient condition for controllability is given in the following Lemma. Lemma 3.3 Fix 0 < j < k and assume Xi = IR, all i. Then the constraint system for problem (C) is (j, k)-controllable if the Uk-span of the columns of Bk contains Sk+i - r(k,j)Sj - 1(k, j)[dk,..., dj]t. Consequently, the constraint system for (C) is controllable if, for each j = 0, 1,2,..., there exists kj > j such that the preceding condition holds for (j, k), for each k > kj. Proof: Omitted.. The key assumption of [14] which guaranteed that lim.F*(N) = F* was the notion of reachability in the dynamic programming sense. Our next objective is to define reachability in a control-theoretic sense (which will imply the dynamic programming reachability property of [14]) and compare it with the property of controllability. Let k be a nonnegative integer and Sk E Sk. Then the sequence of all feasible control states {SN} is reachable from the state Sk at stage k if, given any sequence of feasible states {tN} with tN E SN, N = 1,2,..., there exists Nk > k sufficiently large such that for each N > Nk, there exists yN E F(N) satisfying xN = tN and x = Sk. (Note that F(N) C F(k), for all N.) The feasible sequence {SN} is reachable from all finite-stage feasible control states if it is reachable from all Sk E Sk, all k = 0, 1, 2,.... 10

Remark: It is not difficult to verify that this notion of reachability implies that of [14]. Also, reachability implies that F(N, sN) -F, as N — oo, for all feasible state sequences {SN}. Theorem 3.4 If the constraint system of problem (C) is controllable, then {SN} is reachable from all finite-stage feasible control states. Proof: Let k be non-negative integer and Sk E SK. By Lemma 2.1, there exist ui E Ui, 0 < i < k - 1, xi E Si, 1 < i < k - 1, such that xi+l = Aixi + Biui + di, i = 0,1,..., k - 2, and Sk = Ak-lXk-1 + Bk-lUk-1 + dk-1. Let {tN} be such that tN E SN, N = 1,2,.... By controllability, there exists Nk > k such that the constraint system for (C) is (k, N) - controllable, for each N > Nk. Fix N > Nk. Then there exists iN E Ui, ck < i < N -, such that SN = tN and si E Si,k+ 1< i N - 1, where i+1 r(i, k)sk + (i, k)[ui,..., N]t + (i, k)[d,, dk]t, k < i < N - 1. Define Ui:, O < i < k- 1, U= N u, k i <N-1, arb. in Ui, i > N, xi, 1 < i < k - 1, XN = Si, k < i < N arb. in Vi, i> N+ 1, zN = CixZN, i 1,2,... and Yi = (uNi x, z), Zi 1,2.... Then yi E Y, i = 1,2,.... Hence, yN = (yN) E Y. For O < i < kc - 1, we have = AiXN + BuiN + di 11

For i = k, we have xN = sk = Ak-lXk-l + Bk-lUk- + dk-1 =Ak-l k-1 + Bk-1lUk + dk-1 For k + 1 < i < N, we have x = i = r(i - 1, k)sk + (4(i - 1, k)[u_,..., ] + (i -1, )[di+l,. dk]t = Ailr(i -2, k)sk + [Bi-, Ai-l * 4(i- 2, k)][uN1,.., t + [I, Ail *(i - 2, k)[di_,..., dk]t Ailr(i - 2, k)sk + Bi-1Ul + Ail * b(i - 2, k)[u,..., uk + di-l + Ai_- * (i - 2, k)[di_2,..., dk]t Ai_i[r(i - 2, k)sk + 4(i - 2, k)[uN_2, *,u ] + (i-2, - k)[4_2,..., dk] + Bi-luN_ 1 + di-l Ailxi_l + Bi-1uN1 + di-1, where, in particular, xN = SN = tN. Thus, yN E F(N), xk = Sk and xN = tN. Consequently, {SN} is reachable from all finite-stage feasible states. r We are now ready to state our main result. Theorem 3.5 Suppose the constraint system of (C) is controllable. Then: (i) lim.F*(N) = F* in IC(Y), i.e., lim F*(N) = F*, in the sense of Kuratowski. N —oo N-+oo (ii) For each point p in Y, the sequence {yP(N)} converges to yp, where yp(N) is any bestapproximation in T*(N) to p and yp is the unique best-approximation in F* to p. In particular, if y;(N) = ((Up)k-l(N), (x)k(N), (Zp)k(N))= and yp = ((U;)k-1, (x)k, (Zp)k))~=1, then (up)k-_(N) -- (up)k-1, as N - oo, for k = 1, 2,... Proof: By our hypothesis and Theorem 3.4, it follows that {SN} is reachable from all finite horizon feasible states. It is then easy to see that this implies the reachability condition of Theorem 5.4 of [14] (for the sets S(N) = ANSN). Hence, the conclusions of this theorem and its Corollary 5.5 follow. r Theorem 3.5 says that we can arbitrarily well approximate an infinite-stage optimal control by solving a finite stage subproblem of sufficiently long horizon. From the standpoint of implementation, if we approximate the continuous control spaces Uk by uniformly bounded discrete qontrol sets, then two simplifications follow [13]. First, F*(N) = F*(N), thus avoiding the necessity to form the closure of (N). Therefore, a standard forward dynamic 12

programming algorithm will, as N increases, automatically generate the set F* (N) of optimal controls to all feasible states. Second, for (3k) sufficiently small, the best-approximation yp(N) (with p the origin) is the lexicomin, i.e. the lexicographically smallest element of the finite set.F*(N). By Theorem 3.5, the lexicomin first-stage control from F*(N) will eventually lock-in and agree with the infinite horizon first-stage optimal control for that and all subsequent horizons. In this manner, the forward dynamic programming algorithm will recursively recover the lexicomin infinite horizon optimal control. A stopping rule is provided in [14] that determines how large the horizon N must be to guarantee agreement with the infinite horizon first-stage optimal control. 4 Multiproduct Production Planning In this section, we illustrate the previous development with an application to production planning. Consider the problem of scheduling production of several products to meet a non-stationary, deterministic demand over an infinite horizon. The objective is to optimally balance the economies of scale of production against the cost of carrying inventory. If we assume convex quadratic costs for production and inventory holding, then the problem may be formulated by the following mathematical program (P) [3], where vector inequalities are interpreted componentwise: 00 min E tk [Xt+Qk+lXk+l + uURkUk] k=O subject to (P) Xk+l = Xk + Uk -dk, -b < xk a, 0 < Uk<q, k=0,1,2,..., where (for convenience) the initial inventory Xo = 0, Xk E IRn is the multiproduct inventory ending period k, Uk E IRn is multiproduct production in period k, and dk E IR' is multiproduct demand for production in period k. The quantity a is the discount factor reflecting the time-value of money, where 0 < a < 1. We require that q > 0, a > 0, b > 0 and 0 < dk < q, k = 0,1,2,.... If a component of b is positive, then backlogging is allowed for the corresponding product. We impose the following assumptions on (P). 13

Assumptions I. For each k, Qk and Rk are positive semi-definite. Moreover, 00 E ak(ll+lQk+1112 + lIRk2) <00. kc=O II. liminf dk < q and lim sup dk > 0. Assumption I is similar to the cost assumptions of (C). A sufficient condition for the series to converge is that the sequences { |Qk| 12} and { Rk I 12} be uniformly bounded. Then the series is essentially the geometric series with 0 < a < 1. Assumption II is a regularity condition required to guarantee controllability for (P). Clearly, (P) is a special case of (C) with rk = 0, Ak = Bk = Ck = I,Uk = [0,q], Xk [-b, a] and Zk = Xk, k = 0,1,2,.... It is easily seen that the feasible region F for (P) is non-empty; for example, let Uk = dk, so that Xk = Zk = 0, k = 0, 12,.... Thus, (P) satisfies all the hypotheses of section 2. Consequently, C* denotes the optimal objective value of (P) and F* the nonempty set of optimal solutions. For each N = 1,2,..., the finite-stage approximation (P(N)) to (P) is given by N min E ca [XtkQk+lXk+ + utRkk] kc=O subject to (P(N)) Xk+ = Xk + Uk- dk, k =0,1,...,N- 1, -b < k a, = 1,2... 0 < Uk < q, k = 0 1,2,.... Since the inventory levels X1,..., XN are defined by the production schedule U,...,UN via k k Xk = - dj, k = 1,....,N, j=o j=1 we will say that (,..., UN,...) is feasible for (P(N)) if 0 < Uk < q, all k, and k k k -b+Ed E, < a+Edj, k =1,...,N. j=1 j=o j=l As in section 2, we let F(N) denote the non-empty feasible region of (P(N)), F*(N) the non-empty set of optimal solutions to (P(N)) and C*(N) the optimal objective value for 14

(P(N)). As in section 3, let SN denote the set of feasible control states at stage N, F* (N) the set of (P(N)) - feasible solutions which are optimal to some state s E SN and F*(N) the closure of fF*(N) in IC(Y). Note that SN is identical to both (1) the set of feasible inventories ending period N and (2) the set of feasible dynamic programming states S(N) at stage N since AN = I. We next turn to the problem of establishing controllability for the constraint system of (P). For the given data, it is clear that r(k,j) = I, k > j - 1, and k-j+l ~D(k, j)= I.'7- I = (kc, j), for 0 < j < k. Thus, for 0 < j < k and xj E IRW, the equation in Lemma 3.2 becomes k k Xk+1 =Xj + E ui - di, i=j i=j as expected. Hence, for 0 < j < k, the constraint system of (P) is (j, k) - controllable if, for each sj E Sj and Sk+ 1ei Sk+, there exist 0 < ui < q, i = j,..., k, such that k k (i) Sk+1 =Sj +E ui - Edi and i=j i=j i i (ii) si+l E Si+i, where si+ = sj + - de, i = j,..., k - 1. e=j e=j As a consequence of Assumption II for (P), we have: Lemma 4.1 For each product i = 1,...,n: (i) there exists 0 < ai < qi and a subsequence {d m}~J of {dj}? such that dm < ai < q(, all m, and (ii) there exists 0 < 6i < q' and a subsequence {d,},'~ of {d,}0il such that 0 < 63 < d_, all e. Proof: This is Lemma 6.1 of [14] for each of the n products. m Remark: Part (i) says we may stockpile inventory for product i by at least (qi - ai) units in periods jm. Part (ii) says that inventory for product i will be depleted by at least 6i units in periods je. We are now ready to verify the main result of this section. 15

Theorem 4.2 Under Assumption II, the constraint system of (P) is controllable. Proof: See Appendix. * Thus, we conclude: Theorem 4.3 If (P) has the property that lim infjd < qi and lim supjdA > 0, i = 1,.., n, then the constraint system of (P) is controllable. Consequently, the convergence results for (C) in Theorem 3.5 are valid for (P). Remark: If there is only one product, then the objective function is simply 00 Z a [Qk+ilk+l + Rkuk] k=O where Qk+\ and Rk are non-negative real numbers. If they are both positive for some k, then the objective function is strictly convex, thus making the need for selection unnecessary by Theorem 2.3. However, for n > 2, the matrices Qk+l and Rk can be positive semi-definite without being trivial, i.e., without being zero, thus requiring best-approximation selections to obtain convergence. 16

Appendix Theorem 4.2 Under Assumption II, the constraint system of (P) is controllable. Proof: Fix i = 1,...,n. For product i, we may have to reach at worst from (1) -bi to ai or (2) from ai to -bi. Suppose (1) is the case. By Lemma 4.1, for each j = 0, 1,2,..., there exists a unique integer Ki1 > j such that K,1-1 -bi + E (qi _- d) < ai e=j while K3^ -bi + E(q'- d) > a. e=j Now suppose (2) is the case. By Lemma 4.1, for each j = 0, 1,2,..., there exists a unique integer K?2 > j such that K'2 - 1 a - E d > -b e=j while Ki2 ai - dE < -b,. e=j Set K max(K1, K,2)and Kj= max{K} +1, j= 1,2,.... Let j=0,1,2,... and choose k > Kj, so that k > j in particular. We will show that the constraint system of (P) is (j, k) - controllable. Let sj e Sj and Sk+l E Sk+l By Lemma 2.1, there exist 0 < ue < q, O < e < j - 1, and xe E St, 1 < e < j - 1, such that Xe+l = Xe + ue, ~=0,...,j-1, with xj = sj. Now fix i = 1,..., n. Then there exist three cases: i i i' i i j = sk, < sk+l or sj > sk+. If sj s+i, define Z = 4, j e< k. 17

Then 0 < ue < qi, all ~, and k k Sj + E u-Ede sj = Sk+ e=j e=j e e Also, -bi < si < ai, where 4+l = S + E U - dh, j ~ < k - 1. h=j h=j If si < s1+1, then arguing as above, there exists a unique integer k}l < K. j < K k such that k"l-1 s5 + E (qi_ d) < S-+l, e=j while kfcl s~ + (qt - de) > i+l e=j In this case, define u = si -i -E (qi4)+4 k S+l%. - d d, kjl<e < k. Then 0 < ue < qi, all e, and k k k k S++E u-E = S3 + E i l +. E - e=j I=j \ e=j e=k / e = sic+1' Also, -bi < si < ai, where s+ is as above, j < e < k - 1. Finally, if s} > s4+l, then arguing as above, there exists a unique integer k}2 < KC2 Kj < k such that k.2 - 1 ^i i E5 - e > k+ e=j while ki2 iik Sj- aE < Ski+' e=j 18

In this case, define 0, j< < k2-1 2 k3.2 U 4st+i-sj+,det, kj2, e=j d4 k2 <e < k. Then 0 < ue < qi, all e, and k k k sj+Eu-E4- =d + U^ + (: d -Ed e=j 3=j e=.2+l e= - Sic+t k+ 1' Once again, -i + <, j E [, ] and k- 1. For each i= 1, 2,..., n, we have defined ue, j < e < k, such that u} E [0, qi] and Sek k e sj + E u- - E d = ek+l. e=j e=j To complete the proof, we need to show that S1+1 E Se+l, j < e < k - 1, where I t Se+i = Sj + E Ut - E dt. t=j t=j But this follows from sj e Sj, ut E [0,q], for j < t < k, -b < se+l < a, for j < ~ < k - 1, and the definitions of the Sc+l, for j < e < k - 1. 19

References 1. Bertsekas, D.P. [1976], Dynamic Programming and Stochastic Control, Academic Press, New York, 1976. 2. Bes, C. and J.B. Lasserre [1986], "An on-line procedure in discounted infinite-horizon stochastic optimal control," Journal of Optimization Theory and Applications 50, pp 61-67. 3. Denardo, E. [1982], Dynamic Programming: Models and Applications, Prentice-Hall, Inc., Englewood Cliffs, New Jersey. 4. Hausdorff, F. [1962], Set Theory, 2nd Ed., Chelsea, N.Y. 5. Keerthi, S.S. and E.G. Gilbert [1985], "An existence theorem for discrete-time infinitehorizon optimal control problems," IEEE Transactions on Automatic Control 30, pp 907-909. 6. Keerthi, S.S. and E.G. Gilbert [1986], "Optimal infinite-horizon control and the stabilization of linear discrete-time systems: state-control constraints and nonquadratic cost functions," IEEE Transactions on Automatic Control 31, pp 264-266. 7. Keerthi, S.S. and E.G. Gilbert [1988], "Optimal infinite-horizon feedback laws for a general class of constrained discrete-time systems: stability and moving-horizon approximations," Journal of Optimization Theory and Applications 57, pp 265293. 8. Kuratowski, C. [1966], Topologie I, Academic Press, New York. 9. Lasserre, J.B. [1984], "Infinite horizon nonstationary stochastic optimal control problem: a planning horizon result," IEEE Transactions on Automatic Control 29, pp 836-837. 10. Lasserre, J.B. and C. Bes [1986], "Detecting planning horizons in deterministic infinite horizon optimal control," IEEE Transactions on Automatic Control 31, pp 70-72. 11. Lasserre, J.B. [1987], "A complete characterization of reachable sets for constrained linear time-varying systems," IEEE Transactions on Automatic Control 32, pp 836-838. 12. Lewis, F.L. [1986], Optimal Control, Wiley, New York. 20

13. Ryan, S., J. Bean and R.L. Smith [1991], "A tie-breaking algorithm for discrete infinite horizon optimization", Operations Research, forthcoming. 14. Schochetman, I.E. and R.L. Smith [1991], "Finite dimensional approximation in infinite dimensional mathematical programming," Mathematical Programming, forthcoming. 21