Duality in Infinite Dimensional Linear Programming H. Edwin Romeijn Department of Operations Research & Tinbergen Institute Erasmus University Rotterdam P.O. Box 1738 3000 DR Rotterdam, The Netherlands Robert L. Smith and James C. Bean Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 89-20 June 1989 Revised November 1989 Revised May 1990 Forthcoming in Mathematical Programming

DUALITY IN INFINITE DIMENSIONAL LINEAR PROGRAMMING * H. Edwin Romeijn Department of Operations Research & Tinbergen Institute Erasmus University Rotterdam P.O. Box 1738 3000 DR Rotterdam, The Netherlands Robert L. Smith Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 James C. Bean Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 June 1989 Revised November 1989 Revised May 1990 Abstract We consider the class of multistage linear programs with infinitely many variables and constraints having the property that every constraint contains at most finitely many variables while every variable appears in at most finitely many constraints. Examples include production planning and equipment replacement over an infinite horizon. We form the natural dual linear programming problem and prove strong duality under a transversality condition that dual prices are asymptotically zero. That is, *This material is based on work supported by the National Science Foundation under Grant No. ECS8700836. 1

we show, under this transversality condition, that optimal solutions are attained in both primal and dual problems and their optimal values are equal. The transversality condition, and hence strong duality, is established for an infinite horizon production planning problem. Key Words and Phrases Infinite dimensional linear program, duality, infinite horizon optimization. Abbreviated title Infinite dimensional duality. 1 Introduction Consider the following doubly infinite linear programming problem: 00 min ctx i=1 subject to (P) Allxl > bl Ai,i1xi_- + Aiixi > bi (i = 2,3,...) O < i < u, (i=1,2,...) and its natural dual 00 max ('yil - u'yi2) i=1 subject to (D) A 1 + A+l,ii+, -Yi2 < ci (i = 1,2,...) yij > 0 (i= 1,2,...;j=1,2) where ci,ui,xi,yi2 E R'n and b,yil E Rm' are all column vectors, and Aij is a (mi x nj)matrix. The problem (P) represents the class of all (bounded) linear programs having the property that every constraint contains at most finitely many variables and (in a dual fashion) every variable appears in at most finitely many constraints (Schochetman and Smith (1989b)). Applications include infinite horizon production planning under nonstationary demand, equipment replacement under technological change, and capacity expansion. In 2

this paper, we establish a theory of duality for (P) and (D) by providing conditions under which both weak and strong duality hold. Historically, abstract duality theory allowing for consideration of the infinite dimensional case began with the fundamental paper of Duffin (1956). Charnes, Cooper, and Kortanek (1963) subsequently stated and proved a strong duality theorem for semi-infinite linear programming using an extension of Farkas' lemma as proven by Haar. However, as later pointed out by Duffin and Karlovitz (1965), they failed in that paper to explicitly include an interior point condition without which a duality gap may exist. The failure of strong and even weak duality to hold in the infinite dimensional case in the absence of interior point conditions (Luenberger (1969, p. 217)) or, more generally, closedness (Anderson and Nash (1987, p. 52), Ponstein (1980)), has kept much of the literature at an abstract level. The difficulty has been in establishing these conditions in concrete cases. Much of the success thus far has in fact been limited to the semi-infinite case, introduced in Charnes, Cooper, and Kortanek (1963), and subsequently developed in Ben-Israel, Charnes, and Kortanek (1969), Karney (1981), Borwein (1981,1983), and Duffin, Jeroslow, and Karlovitz (1983). The so-called separably infinite programs introduced in Charnes, Gribek, and Kortanek (1980) allow an infinite number of variables and constraints, although no infinite subset of constraints is allowed to contain more than finitely many distinct variables. Programs that are truly doubly infinite are excluded and in particular, (P) is not included in this class. Work on the doubly infinite case includes Evers (1973,1983), Hopkins (1971), Grinold (1971,1977), and Jones, Zydiak, and Hopp (1988). Grinold (1971) provides sufficient conditions for the existence of optimal primal and dual solutions for a special class of doubly infinite problems and establishes a weak duality theorem for a stationary infinite stage LP in Grinold (1977). This latter work was extended to convex programs in Grinold (1983). Jones, Zydiak and Hopp (1988) applies the general theory developed in Grinold and Hopkins (1972) to a cost stationary infinite horizon equipment replacement problem with time varying demand to establish the existence of optimal stationary dual solutions. Our approach, as in Grinold (1971,1977,1983) is to establish properties for (P) and (D) indirectly through the inheritance of such properties from finite dimensional approximations of (P) and (D). These are formed by truncating beyond finitely many variables and constraints. This approach avoids the necessity of establishing closedness or interior point properties for (P) or (D) directly. Viewing the index i in (P) as corresponding to the ith period in a multiperiod planning problem, the above truncation to (P) becomes a finite horizon approximation to an infinite horizon problem. This so-called planning (or solution horizon) approach to the analysis of (P) has an extensive literature (for more recent work, see, e.g., Bean and Smith (1984), Bes and Sethi (1988), and Schochetman and Smith (1989a)). Throughout the paper, we adopt the following 3

Assumptions A. The set, X, of feasible solutions to (P) is nonempty, i.e., X # 0. B. The objective function C(x) = Zi1 cxi in (P) is uniformly convergent over x, i.e., E,1 c1c1ilIoo< oo where Ilcilloo = max{lc'ixl:0 < x < ui}. A sufficient condition for Assumption B to hold is that each ci be of the form acki where O < a < 1, and the ki and ui are uniformly bounded (a corresponds here to a discount factor). In section 2, we establish topological spaces within which to embed (P) and (D) and thereby establish that (P) has an optimal solution. We also formally define the finite dimensional truncations (P(N)) and (D(N)) consisting of the first N variables and N constraints of (P) and (D) respectively. In section 3, weak duality is established for the pair (P) and (D) under the condition that the off diagonal submatrices Ai+1,i are eventually nonnegative for all i. Moreover, whenever weak duality holds, we show that no duality gap exists, i.e., the infimal value of the primal program (P) equals the supremal value of the dual program (D). In section 4, strong duality is established under a transversality condition requiring that the optimal dual multiplier associated with the ith constraint converges to zero as i goes to infinity. Roughly speaking, we require that the optimal prices of future resources become arbitrarily small. Under this condition, an optimal dual solution is shown to exist at which primal and dual objective values are equal and complementary slackness holds. Finally, in section 5, as an illustration of the general theory, we establish strong duality under mild regularity conditions for a general nonstationary infinite horizon production planning problem. 2 Mathematical Preliminaries We begin by forming the product spaces fI?,L Rn' and H[T=i Rm'i+" within which we embed (P) and (D). Each is equipped with the corresponding product topologies inherited from the underlying Euclidean spaces so that for example a sequence {x7} C 1lHi Rni converges precisely when its components xt converge in the Euclidean metric for all i. That is, x'n -x as n — > oo if and only if x' -- xi as n -- oo for all i = 1,2,.... Similarly for {yn} C nl, Rm +n'. Note that the nonnegative orthant has an empty interior in both spaces, so that interior point conditions do not hold here. Since the feasible region for (P), X, is closed and contained within the compact set no 1[0,,u], it is also compact and, by Assumption A, nonempty. By Assumption B, the 4

objective function C(x) = St c/Xi is a continuous function over X (Schochetman and Smith (1989a)). It follows that an optimal solution x* to (P) exists. Since the objective function in (D) may fail to converge for some feasible y ~E f1H Rmi+ni, we shall for now replace the objective function in (D) by N B(y) = lim sup j (b'y - u'Yi2). N —oo i=1 We shall see later that the two objective functions are in agreement over a subset of the feasible solutions Y to (D) known to contain any optimum. We shall establish duality results for (P) and (D) by demonstrating their inheritance from finite dimensional approximations (P(N)) and (D(N)). These are formed by dropping all variables and constraints beyond the first N of (P) and (D), respectively. More formally, we define (P(N)) by N min y cXi i=1 subject to (P(N)) A11x1 > b1 Aii-li-_ + Aiixi > bi (i = 2, 3,..., N) O0<xi < Ui (i= 1,2,...N) and (D(N)) by N max E (byi -Uyi2) miax / ( b;iyil - uiYi2) i=1 subject to (D(N)) AiYil + A+ i+ll -Yi2 ci (i 1,2,...,N -1) ANNYN1 -YN2 CN Yij > 0 (i=1,2,...,N;j=l,2). Note that (D(N)) is the ordinary linear programming dual of (P(N)) so that classical weak and strong duality holds for each pair (P(N)), (D(N)) for all N. That is, by weak duality, we have that B(y; N) < C(x; N) for all x E X(N),y E Y(N) and for all N, where B(y; N) and C(x; N) and Y(N) and X(N) are the objective functions and feasible regions of (D(N)) and (P(N)) respectively. Here X(N) is regarded as a subset of Il'i R'i with the first N elements arbitrarily extended to elements of f~i= Rn'. It will also, at times, be convenient to think of X(N) as a subset of nL Rn'. We shall use the same notation for 5

both where the interpretation should be clear from the context. Similarly, for Y(N). Strong duality provides that B*(N) = C*(N) for all N where B*(N) and C*(N) are the optimal values to linear programs (D(N)) and (P(N)) respectively. Note that (P(N)) has an optimal solution for all N since its feasible region is nonempty and compact (since X C X(N) for all N) and its objective function is continuous. In the next section, we construct a counterexample to weak duality for the pair (P) and (D) and provide a sufficient condition for weak duality to hold. We end this section with a summary of notation. X: feasible region of (P) Y feasible region of (D) X(N):feasible region of (P(N)) Y(N) feasible region of (D(N)) C(x) = Ei-l Cxi C(x;N) N= E c B(y) = limsupNvoo B(y; N) B(y; N) (i- N2) C* optimal value of (P) C*(N):optimal value of (P(N)) X* = { E XIC(x) = C*} X*(N) = {E X(N)IC(x; N)= C*(N)} B*: optimal value of (D) B*(N):optimal value of (D(N)) Y* {y E YIB(y) = B*} Y*(N) = {ye (N)IB(y; N)= B*(N)) 3 Weak Duality Because the feasible region to (D) is unbounded, weak duality for the pair (P) and (D) may fail to hold. Consider for example the following instance of (P): minE subject to ( subject to (P) 6

X1 > 1 Y1 + zx > 1 -2yi_l+ xi > -2Xi;,1 +yi + zi > 0 0 < xi < 2i-1 O<yi < 2i-1 0 < zi < 1 so that (D) is given by (i= (i= (i= (i = (i= 2,3,...) 2,3,...) 1,2,...) 1,2,...) 1,2,...) N sup lim sup ul + vi - N —*oo i=2 (2ipi + 2iqi + ri)) subject to (D) ui - 2vi+l - pi vi - 2ui+l - qi Vi - ri ui, viPi, qi,ri < 0 < 0 < (1)i-l > 0 (i- =1,2,...) (i= 1,2,...) (i= 1,2,...) (i= 1,2,...). It is a simple matter to verify that (P) satisfies Assumptions A and B. However, the following solution is optimal for (P) with value 0 i = 2i-1 i = 2i-1 z = 0 (i = 1, 2,...) (i = 1, 2,...) (i= 1,2,...), while the following solution is optimal for (D) with value 2 ui 1 ()i-1 i = (1 )i-1 Pi qi= ri = 0 (i = 1,2,...) (i = 1,2,...) (i= 1,2,...). Hence weak duality fails for this instance of (P). It is interesting that weak duality holds and is easily shown when (D) is defined as the algebraic dual of (P) (Anderson and Nash (1987, p. 18)). However a concrete representation of algebraic duals is usually unattainable in the infinite dimensional case. Evidently, (D) as given here is not such a representation. In fact, its objective function is not a linear functional. The pathology exhibited above can be eliminated by requiring that all feasible solutions of (D) be feasible for (D(N)), i.e., Y C Y(N) for large N. The following theorem provides a sufficient condition for this to occur. 7

Theorem 3.1 Suppose that Ai+l,i is eventually nonnegative, i.e. there exists a positive integer N' such that Ai+l,i > 0 for all i > N'. Then B(y) < C(x) for all x E X,y E Y. Proof: If y E Y, then we have for all N > N': CN > ANNYN1 + AN+1,NYN+1,1 - YN2 > ANNYN1 - YN2 since YN+1,1 > 0 and AN+1,N contains only nonnegative elements. Hence y is also feasible for (D(N)), i.e., y E Y(N), for all N > N'. By Weak Duality for finite dimensional LP-problems we have: B(y; N) < min C(x; N) = C*(N) xEX(N) for all y E Y, N > N'. Our assumptions on the function C(.) imply that value convergence holds for (P), i.e., limN-.O C*(N) exists and is equal to C* (Schochetman and Smith (1989b)). Therefore we have: B(y) = limsupB(y; N) < lim C*(N) = C* < C(x) N —oo N-*oo for all x E X,y E Y.. Fortunately, the nonnegativity condition on the off diagonal elements Ai+1,i is not restrictive in most multistage planning problems where Ai+l,i corresponds to inventory carryover from the previous period. Theorem 3.1 tells us that every feasible value of the primal (P) will be an upper bound to every feasible value of the dual (D). The next result shows that the supremum of the later equals the infimum (i.e., minimum) of the former. We summarize this claim by saying that no duality gap exists. Theorem 3.2 (No Duality Gap) Suppose weak duality holds, i.e. B(y) < C(x) for all x E X,y E Y. Then B* = sup B(y) = min C(x) = C*. yEY xEX Moreover, value convergence holds for (D), i.e. B* = limN- o B*(N). 8

Proof: Consider y*(N) E Y*(N) ( y*(N) is an optimal solution of (D(N))). Then define zN as: z< = yj(N) (i 1,... N; j =1,2) il= 0 (i= N + 1...) iN =max(0,-ci) (i +.. where f = max(d, e) (d, e, f E R') is defined as follows: fi = max(di, ei) (i = 1, 2,...,n) and where 0 = (0,..,0)'. Obviously, zN satisfies the first N - 1 constraints of (D). Furthermore A N A N 2=A ANNZN1 + AN+1,NZN+1,1 — N2 = A NNY(N) Y2 CN and Aizi + A+i, l - = - max(0, -ci) = min(O, ci) < ci for i = N + 1,.... Thus, zN E Y. Note also that zN E Y*(N). Now we have B* = supB(y) yEY B(zN) tIN M = lim sup E (bizl - uZ M —oo _ N M M = lim sup - u max(,c) N zi - uiii2z ( b zil- u ii2 -M —OOt i=N+l M \ ( y*(N) - i*(N)) + lim;sup N- ( ui -, i=1 IM-*oo i=N+l B(y*(N) N)-i minf ( j:c,< Umax(O,-c) oo M —+O \i=N+l j:cij<0 C*(N)- E E (-uicij) i=N+1 j:cij<O 9

for all N. In the last step we have used the absence of a duality gap for finite dimensional LP, and the fact that -uijcij > 0 for all (i,j) such that cij < 0. Since i=1 j:cij<0 < max E E uijCij, E (-uijcij) i=1 j:cij>O i=l j:cij<0 00 / _< /max ucijj, E (-uijcij) i=l j:cij>O j:cij<O / 00 = IIllcioo < 0 i=1 we can conclude that 00 lim E E (-uicij) = O. N —-+ oo. i=N+1 j:cij <0 Furthermore, limN-.oo C*(N) exists and is equal to C*. So now we have B* > C* By weak duality we have B* = supyEy B(y) < infEx C(x) = C*, so we can conclude that B* = C*. Also, lim B*(N) = lim C*(N) = C* = B*. * N —oo N-0oo0 4 Strong Duality In this section, we establish conditions under which an optimal solution, y*, exists to the dual program (D). Under weak duality and Theorem 3.2, it will follow that optimal primal and dual values are attained and equal, i.e. strong duality. The method will be to construct a candidate solution for y* from the set Y*(oo) of accumulation points of finite dimensional dual optima Y*(N). We begin by establishing that every pair of accumulation points x* and y* of corresponding finite dimensional optimal solutions are primal and dual feasible and moreover necessarily satisfy complementary slackness. 10

Lemma 4.1 Suppose x*(N) E X*(N), y*(N) E Y*(N) are optimal solutions for (P(N)) and (D(N)), respectively, N = 1,2,3,.... Furthermore, assume that for some subsequence {Nk} of the positive integers that is independent of i, we have lim x;(Nk) = x? k —boo lim y (Nk) y= k —*oo (i- =1,2,...) (i= 1,2,...), i.e., x* E X*(oo) and y* E Y*(oo), the sets of accumulation points of X*(N) and Y*(N) respectively. Then x* E X and y* E Y, i.e. X*(oo) C X and Y*(oo) C Y. Furthermore, x* and y* satisfy complementary slackness, i.e., (Aiixi_1 + Aix - bi) = 0 (ui - xi) Y2 = 0 and (ci - AY - Ai + y)' 4 = Oci-Ati 1,+l iyi+l,l + Yi2 xX — for i = 1, 2,.... Proof The fact that x* E X and y* E Y follows immediately from the fact that every constraint is a linear function of finitely many variables. By complementary slackness for finite dimensional linear programming we have, for all k: (Ai,i-l_,_(Nk) + Aii (Nk) - bi) y(Nk) = 0 ~ii (i = 1,2,..., Nk) (1) (ui - x(N))(Nk) = 0 - * i2 k (i = 1,2,...,Nk) (2) and (c - Aiy(Nk) - A+,yt+ (Nk) + y2(N )) X(Nk) = 0 (i = (cN - A * (Nk)+ yN2(Nlk)) +x(Nk) = 0 Taking the limit for k -* oo in, for example, equation (2) yields for all i: 1,2,..., Nk-1) (3) (4) 11

lim (ui - x(Nk))'y 2(Nk) = 0 k — oo or (i - lim xi(N ( lim Y(Nk) = o k- oo \kb-+oo thus (ui - x )',= 0. Analogously we get for all i: (Aii__ + Aiix i - b) 0 and (ci - Aiiy +1 Y1 + Y 2) x 0. I'' ii i l if,i i+i,1 %Yi2 xi The next theorem provides a transversality condition that under weak duality guarantees optimality for any pair of primal and dual feasible solutions that satisfy complementary slackness. Theorem 4.2 Suppose x E X, y E Y satisfy complementary slackness. Furthermore, suppose that liminf y'1 Ai+l,ii = 0. t —-oo Then 00 N C(x) = c'i = limsup (bail - ui2) = B(y) i=l Ni —o i~=l If, moreover, weak duality holds, then x is an optimal solution for (P), and y is optimal for (D). Furthermore, if lim A+l,Ai+l,ixi- = 0 then 00 B(y) = E (bi2 - uiY2). i=l Proof By complementary slackness we have, for all i, 12

i - At.yi - Ai+1,1ii+1,1 + Yi2) i = 0 or equivalently Cixi = IAiij +. xA +l,iY i+ll - Xii2 Summation over all i on both sides yields: 00 00 C(X) = c'i _ = >: (iA'ii + xA/+,i+. - xY i i=1 i=l Also by complementary slackness: Xi4 Al + - = i-lAi,i-lYil + XiAiil = iYil and xiYi2 -U iYi2 so B(y) N lim sup y (b,1l - uyi2) N-+oo i=N = lim sup: (~-xi- i,iYl + xiAi - xYi2) lim sup x'i' ~ ~' N-+oo i =limsup (f (Zi Ai Y ii+ + i - Xi+2 - NiAN+I,NYN+1, 1 N-oo NtiN i 00 = (AiiYil - + -xA+l,iYi+l,l - i2 - liminf N N+1,NYN+1,1 i=1 00 =AE (i yi + xA+,ii+, - zi=2) C(X). i=1 Since weak duality holds, we have the optimality of x and y. Furthermore, if lim IAi+lii = 0 t-+00 we can conclude B(y) = limsup (bi- 2) = lim-inf (bi - u = (b i-ui 2) N4o i1N-oo i=1 iY- uiyi2) N —-oo.= i~~~~~~~~~l~~~~ i 1 l 13

Note that the objective function values given for the dual formulation of Sections 1 and 2 are in agreement for y under the conditions of Theorem 4.2. The following theorem is the main result of the paper. Theorem 4.3 Suppose the following conditions on (P) hold: (i) The constraint data Ai+,i, ui, mi and ni for (P) are uniformly bounded over i, i.e., (ui)j < U < oo, (Ai+l,i)kl < a < oo, mi < m < oo and ni < T < oo for all i,j, k, 1. (ii) Weak duality holds for (P) and (D) (iii) Transversality holds for (D), i.e., lim Y* = 0 i-.oo for some y* E Y*(oo). Then y* E Y* and strong duality holds, i.e., there exist optimal solutions x* E X* and y* E Y* such that C(x*) = B(y*). Proof Since y* E Y*(oo), there exists a subsequence {Nk} such that lim y (Nk) = y k-oo for all i, where y (NIk) E Y*(Nk) for all k. Choose x*(Nk) E X*(Nk) n X for all k. Then, passing to a subsequence of {Nk} if necessary, we have lim xt(Nk) = x k —-oo for all i for some x* E X by the compactness of f =[O0,ui] in the product topology. By Lemma 4.1, x* and y* satisfy complementary slackness. By assumption, lim e'y* = 0. i —+oo il So we have Yi+1,1'Ai+* Ytt+l,l Ai+l,iXi mi+l n, E=:(Y (+l,l)k(xt)I(Ai+l,i)kl k=l 1=1 mi+l ni - E (8lE(Y*+1,)ka k=l 1=1 mi+1 = n Eu a ((Y+1,)k k=l < nua( te'*1,1) 14

which gives limninf Y+ll'Ai+l,ixt < n7ua lim e'y, = 0. i —,oo- i — oo So, Theorem 4.2 says that x* is optimal for (P) and y* is optimal for (D), and the corresponding objective function values are equal. I Remarks: 1) Condition (ii) by Theorem 3.1 may be replaced by the requirement in (i) that o < (Ai+1,i)kl <'a < oo for all i, k, 1. 2) From the proof of Theorem 4.3, we may relax the requirement that mi < m < oo in (i) by replacing condition (iii) with the requirement that lim e'y1 = 0. The important condition in Theorem 4.3 for strong duality to hold is the transversality condition that requires (in the language of Schochetman and Smith (1989a)) algorithmically optimal prices of resources available in the ith period go to zero as i goes to infinity. To this point, it is not clear whether any nontrivial instance of (P) satisfies this condition. In the next section, we prove that a classic production planning problem satisfies the transversality condition and hence is an important problem for which duality holds. 5 An Application to Production Planning over an Infinite Horizon Consider the problem of scheduling production to meet nonstationary demand over an infinite horizon. The problem may be formulated by the following linear program (Denardo (1982, p. 87)): 00 min (kiPi + hiIi)aii=l subject to (Q) Ii_1+Pi-I > di (i=1,2,...) O<Pi < Pi (i=1,2,...) o<Ii < 7, (z=1,2,...) where Ij is the net inventory ending period j with Io =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 inventory holding cost for period j, j = 1, 2,.... The factor a is the discount factor reflecting the time value of money, where 0 < a < 1. The dual (D) becomes 15

N sup limsup Z(diw, -Piu - ivi) N-+oo i= subject to (D) Wi - Ui < ki (i-1,2,...) -Wi + wi+1 -i < hi-1 (i 1,2,...) w, u,, vi > 0 (i 1,2,...). Note that without loss of optimality, we have that demand is met exactly, i.e., Ii1 + Pi- I = di for all i, in program (Q). As in Schochetman and Smith (1989b), we make the following Assumptions: (i) infi(Pi - di) > 0. (ii) Pi < P < oo for all i Ii < I < oo for all i. (iii) ki, hi > 0 and max(ki, hi) < Gyi for all i for some 0 < G < oo, 0 < 7 < 1/a. Note that (Q) is of the form (P) under the identification xi = (Pi IJ)', c- = (k hi)a"-l, Aii-I = (1 0), A; = (1 - 1), bi = di, and pi = (i Ti)'. It is easily verified that Assumptions A and B of Section 1 are satisfied. Moreover, since the off diagonal submatrices Ai_,i = (1 0) > 0 for all i, we have by Theorem 3.1 that under Assumptions (i), (ii), and (iii), weak duality holds for (Q) and therefore there is no duality gap by Theorem 3.2. Verification of the transversality conditions for strong duality will be considerably more difficult. We begin by establishing that we may restrict consideration without loss of optimality to a bounded subset of the feasible solutions to (D) and (D(N)). Set yi = (wi,ui, vi) E R3 and y = (w,u, v). Lemma 5.1 For the Production Planning Problem (Q), there exists i < oo for all i, such that sup B(w, u, v) = sup B(w, u, v). yEY yEY where Y= {y E Y: yi < Yi for all i}. Moreover, for all N: sup B(w, u, v; N) = sup B(w, u, v; N) yE((N) yEY(N) 16

where Y(N) = {y E Y(N): y < i for all i}. Proof See Appendix. * Lemma 5.2 For the Production Planning Problem (Q), suppose y(N) E Y(N) for all N. Suppose further that lim wi (Nk) = wi k —coo exists for all i for some subsequence {Nk} of the positive integers. If lim sup wi > 0 i —-oo then lim inf B(y(N); N) = -oo. N —oo Proof See Appendix. * We are now ready to prove the main result of this section. Theorem 5.3 Suppose the Production Planning Problem (Q) satisfies Assumptions (i), (ii), and (iii). Then weak and strong duality hold for (Q) and (D), i.e. B(y) C(x) for all x E X and y E Y and there exist x* E X* and y* E Y* such that B(y*) = C(x*). Proof Consider any sequence {y*(N)}, y*(N) E Y*(N) for all N. Without loss of generality we can assume y*(N) E Y for all N. Since Y lies in the product of compact sets, it is compact in the product topology. Hence there exists a subsequence of {y*(N)} converging to some y* E Y. Since no duality gap exists for (Q), we have that limN- B(y*(N); N) = B* > -oo. Thus, by Lemma 5.2, lim w* = 0. i —-oo 17

and = 2). We conclude that strong duality holds for the production planning problem. i Hence weak and strong duality hold for the Production Planning Problem under very mild regularity conditions. One might expect the same result under comparable conditions for a wide variety of investment planning problems including equipment replacement and capacity expansion. 6 Conclusions We have established weak and strong duality for a large class of doubly infinite linear programs under the key transversality condition that dual prices asymptotically converge to zero. Moreover this transversality condition was shown to be met by a nonstationary infinite horizon production planning problem. Using weak duality, one can bound the optimal primal value thus providing a measure of error to approximate solutions to (P). Moreover, under strong duality, it becomes possible in principle to analytically establish optimality of a candidate primal solution by demonstrating equality in value with a known optimal dual solution. 18

References E.J. Anderson and P. Nash, "Linear Programming in Infinite-dimensional Spaces" (Wiley, New York, NY, 1987). J.C. Bean and R.L. Smith, "Conditions for the Existence of Planning Horizons," Mathematics of Operations Research 9 (1984) 391-401. A. Ben-Israel, A. Charnes, and K. Kortanek, "Duality and Asymptotic Solvability over Cones," Bulletin of the American Mathematical Society 75 (1969) 318-324. C. Bes and S. Sethi, "Concepts of Forecast and Decision Horizons: Applications to Dynamic Stochastic Optimization Problems," Mathematics of Operations Research 13 (1988) 295310. J.M. Borwein, "Direct theorems in Semi-infinite Convex Programming," Mathematical Programming 21 (1981) 301-318. J.M. Borwein, "Semi-infinite Programming Duality: How Special Is It?," in: A.V. Fiacco and K.O. Kortanek (eds), Semi-Infinite Programming and Applications (Springer-Verlag, Berlin, 1983). A. Charnes, W.W. Cooper, and K.O. Kortanek, "Duality in Semi-infinite Programs and Some Works of Haar and Caratheodory," Management Science 9 (1963) 209-228. A. Charnes, P.R. Gribek, and K.O. Kortanek, "Separably Infinite Programs," Z. Operations Research 24 (1980) 33-45. E.V. Denardo, Dynamic Programming: Models and Applications (Prentice-Hall, Englewood Cliffs, NJ, 1982). R.J. Duffin, "Infinite Programs," in: H.W. Kuhn and A.W. Tucker (eds), Linear Inequalities and Related Systems (Princeton University Press, Princeton, NJ, 1956). R.J. Duffin, R.G. Jeroslow, and L.A. Karlovitz, "Duality in Semi-infinite Linear Programming," in: A.V. Fiacco and K.O. Kortanek (eds), Semi-Infinite Programming and Applications (Springer-Verlag, Berlin, 1983). R.J. Duffin and L.A. Karlovitz, "An Infinite Linear Program with a Duality Gap," Management Science 12 (1965) 122-134. J. Evers, Linear Programming over an Infinite Horizon (Tilburg University Press, Tilburg, The Netherlands, 1973). J. Evers, "A Duality Theory for Infinite Horizon Optimization of Concave Input/Output Processes," Mathematics of Operations Research 8 (1983) 479-497. R. Grinold, "Infinite Horizon Programs," Management Science 18 (1971) 157-170. R. Grinold, "Finite Horizon Approximations of Infinite Horizon Linear Programs," Mathematical Programming 12 (1977) 1-17. R. Grinold, "Convex Infinite Horizon Programs," Mathematical Programming 25 (1983) 6482. 19

R. Grinold and D.S.P. Hopkins, "Computing Optimal Solutions for Infinite Horizon Mathematical Programs with a Transient Stage," Operations Research 21 (1972) 179-187. D.S.P. Hopkins, "Infinite Horizon Optimality in an Equipment Replacement and Capacity Expansion Model," Management Science 18 (1971) 145-156. P. Jones, J. Zydiak, and W. Hopp, "Stationary Dual Prices and Depreciation," Mathematical Programming 41 (1988) 357-366. J.F. Karney, "Duality Gaps in Semi-infinite Linear Programming: An Approximation Problem," Mathematical Programming 20 (1981) 129-143. D.G. Luenberger, Optimization by Vector Space Methods (Wiley, New York, NY, 1969). J. Ponstein, Approaches to the Theory of Optimization (Cambridge University Press, Cambridge, 1980). I.E. Schochetman and R.L. Smith, "Infinite Horizon Optimization", Mathematics of Operations Research 14 (1989a) 559-574. I.E. Schochetman and R.L. Smith, "Finite Dimensional Approximation in Infinite Dimensional Programming," Technical Report 89-10, Department of Industrial and Operations Engineering, The University of Michigan (Ann Arbor, MI, 1989b). Submitted to Mathematical Programming. 20

Appendix Lemma 5.1 For the Production Planning Problem (Q), there exist Ti < oo for all i, such that sup B(w, u, v) = sup B(w, u, v). ye7 yEY where Y = {y Y: yi < yi for all i}. Moreover, for all N: sup B(w,u,v;N)= sup B(w,u,v;N). yE7(N) yEY(N) where Y(N) = {y E Y(N): yi < Yi for all i}. Proof We will prove that, for all i, there exist TUs < oo such that for all N > i the following holds: sup B(w, u, v; N) < 0. yEY(N);wi >wi Combining this with sup B(w, u, v; N) = B*(N) >0 yEY(N) we can conclude that sup B(w, u, v;N) sup B(w, u, v; N) yEY(N) yeY(N);wi <wi for all i and N > i. Furthermore, we will have that sup B(w, u, v) = sup B(w, u, v) yEY yEY;wi <wi for all i. Choose some index i. Then, for all N > i: N B(w, u, v;N) = (djwj- Pju,- j-j) j=1 N < (ddjwj - Pjw + Pjwj - juj) j=1 N E ((dj - pj)w + Pi(wi - uj)) j=1 21

N < (di -P 5i)wi + E Pjkjaj-1 j=l < (di - P)wi + E TG(ca7-) j=l < (di - P,)wi + i-' (5) Thus, choosing e.g. PGy' (1- a)(i-di)+1 < we get sup B(w, u, v; N) < (di - Pi) + -, = d - Pi < 0 yEY(N);wij>7 1-7 for i < N. Since inequality (1) holds for all N > i, we also have B(w, u, v) = lim sup B(w, u, v; N) < (di - i)wi + P N- oo 1 -/ and thus sup B(w, u, v) < O. yEY;wi ~wi We can now conclude that for all N: sup B(w, u, v;N) sup B(w, u,v;N) yEY(N);w, <7i yEY(N) and sup B(w, u, v) = sup B(w, u, v). yEY;wi <i YEY Moreover, combining the results for all indices i: sup B(w, u, v; N) = sup B(w, u, v; N) yEY(N);wi <7iVi yEY(N) and sup B(w, u, v) = sup B(w, u, v). yEY;w,<T7iVi yEY 22

Now, observe that in an optimal solution we will have ui = max(O, wi - kai-1) vi = max(O, -wi + w+l - hiai-1) so ui < max(O, ui - ki"i-1) =: Ui vi < max(O,Ti+i - har') =:'i. Combining the results gives: sup B(y;N)= sup B(y; N) yEY(N) yEY(N) for all N, and sup B(y) = sup B(y). * YiY yEY Lemma 5.2 For the Production Planning Problem (Q), suppose y(N) E 7(N) for all N. Suppose further that lim wi(Nk) = Wi k- -oo exists for all i for some subsequence {Nk} of the positive integers. If lim sup wi > 0 then lim inf B(y(N); N) =~o. N- oo Proof By hypothesis, there is a subsequence {ij} such that lim lim wi.(Nk) > 6 > 0. j-+oo k- oo Assume without loss of generality that 8 < oo. This means: 23

UNIVERSITY OF MICHIGAN 111111 11 1l111 il 1 1111111i1iIl 11111111iJ 3 9015 04732 6809 VO < < 6 3 J, such that for all j > Je: (lim wi (Nk) > 6 - > ) and VO < < 6 3 Je such that for all j > J (VO < < 6- 3eK,(j) such that for all k > Kf,(j): w3(Nk) -6-r > 0). Choose some fixed 0 < e < 6, and 0 < r7 < 6 -e. Let / 6 = -e -. Without loss of generality we assume IK,(j + 1) > I~,7(j) for all j. Now define Jk:= {j ~ Jelwij(Nk) >,, ij < Nk}. Choose a positive integer M, arbitrary. Then, for k > IK(Je + M - 1) we have IJkl| > M. Thus, since M was chosen arbitrarily, we can conclude lim IJkI =oo. k- -oo Now we have, for all k: Nk B(y(Nk); Nk) = E (diwi(Nk) - 7u(Nk) - ivi(Nk)) i=l Nk E ((d - Pi)i(Nk) + 7i(wi(Nk) - u(Nk))) i=1 Nk Nk, < Z(di - Pi)w(Nk) + ZE Pki'i-l i=1 i=1 Nk ~PGy < -aZwi(Nk) + 1 - cf7 < - IJkI + PG So: lim inf B(y(N); N) N -oo lim B(y(Nk); Nk) k-I-oo < lim (- ltJkl + PG^) ck- oo( li 1 - c^ U ~PG7 = --- - t lim 7 kl=-oo. = 1 - a k —oo 24