Degeneracy in Infinite Horizon Optmization Sarah M. Ran James C. ean Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 January 27, 1987 Revised August 12, 1987 Technical Report 87-5

Degeneracy in Infinite Horizon Optimization t Sarah M. Ryan James C. Bean Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 August 12, 1987 Abstract We consider sequential decision problems over an infinite horizon. The forecast or solution horizon approach to solving such problems requires that the optimal initial decision be unique. We show that multiple optimal initial decisions can exist in general and refer to their existence as degeneracy. We then present a conceptual cost perturbation algorithm for resolving degeneracy and identifying a forecast horizon. We also present a general near-optimal forecast horizon. Key Words and Phrases Sequential decision problems, infinite horizon optimization, forecast or solution horizons, degeneracy, perturbation, near-optimal forecast horizon. 1 Introduction Dynamic sequential decision problems are an important class of optimization problems. Applications include production and inventory control, capacity expansion, and equipment replacement. In some cases the decision variables are continuous, allowing a mathematical programming formulation with a continuous solution space. Often, however, a problem calls for a model with discrete decisions as, for example, in the choice between the various pieces of equipment available to replace one currently in use. A great majority of these problems share tThis material is based on work supported by the National Science Foundation under Grants ECS-8409682 and ECS-8700836. 1

the characteristic of an indefinite horizon. The economy, firm, or government involved has no predetermined moment of extinction. To appropriately model these problems, it is necessary to assume that the problem may continue indefinitely. The traditional and most commonly used solution approach for such problems is to assume some finite horizon, T, and simply proceed as if the world ended there. The hope is that information beyond T will have little or no effect on the optimal solution, for at least the first few decisions, since those first decisions will be implemented immediately. A finite horizon with this guarantee is known as a forecast horizon. This solution method is known as a solution or forecast horizon approach (Lundin and Morton (1975); Charnes, Dreze and Miller (1966); Modigliani and Hohn (1955)). Nearly all forecast horizon existence results require a unique optimal initial decision (see Bean and Smith (1984); Hopp, Bean, and Smith (1984); Bes and Sethi (1986), Schochetman and Smith (1986)). Multiple optima may lead to cases with no forecast horizon. We refer to this as degeneracy. For the problem of minimizing discounted costs, this paper addresses two questions: 1. How often does degeneracy occur? 2. How can degeneracy be resolved? Bean and Smith (1984) showed that forecast horizons exist when every optimal sequence of decisions includes the same initial decision and that uniqueness of the optimal initial decision depends on the interest rate used. We approach the first question by characterizing the interest rates that may allow degeneracy and show that, even in simple problems, every "reasonable" interest rate potentially allows degeneracy. We conclude that degeneracy is a serious theoretical problem and turn to the second question. Recently, Bes and Sethi (1986) found an algorithm for the case of discrete time and discrete decision sets that is guaranteed to identify a forecast horizon when the optimal initial decision is unique. Schochetman and Smith (1986) extended their results to the case of continuous time and continuous decision sets. In this paper, we adapt the Bes and Sethi algorithm to the context of continuous time and discrete decision sets. More important, we present a scheme for perturbing time zero costs which guarantees that the optimal initial decision is unique. We also calculate, for any c, a horizon that yields an initial decision that is part of a strategy with cost within c of the optimal cost. Section 2 includes a mathematical statement of the problem and assumptions. Section 3 is a discussion 2

of the relationship between degeneracy and the interest rate. Section 4 gives characteristics of the cost function important to the forecast horizon results in Section 5. Section 6 presents our method for degeneracy resolution. Finally, Section 7 contains conclusions. 2 Problem Definition and Assumptions Suppose we are faced with making a sequence of decisions over a continuous or discrete time frame. Each individual decision, denoted 7ri, will be called a policy, and a sequence 7r = (7l, 7r2,...) of policies constitutes a strategy. Let II be the set of policies available after n - 1 decisions have been made. We assume IIn is finite for all n. Let II C x 1IIn be the set of all feasible strategies. Associated with each strategy, ir, is a cumulative net cost function Cr(t). In order to compare costs incurred over time, we continuously discount them to time zero. Hence Cy,(r) = f0' ertdCr,(t) is the resulting infinite horizon discounted cost as a function of the discount rate, r. Also, (C(r, T) = fJ er'dC,(t) is the discounted cost over the finite horizon T. Bean and Smith (1984) showed that infinite horizon discounted costs converge if r is larger than In IC~(t)l 7 = sup lim sup In C(t)I wEn t —oo t The set {rjr > -} is called the range of convergence for interest rates. We keep the assumptions of Bean and Smith (1984); in particular: C,(t) = the cumulative net cost for strategy xr up to time t = K,(t)- R,(t), (1) where 0<K~(t)<Me't A where 0<R O (t) <MeYt Vt > To, M, y,To independent of ir, K, (t), R (t) nondecreasing. The functions K,(t) and Rr(t) represent cumulative pure cost and cumulative pure revenue, respectively. Without loss of generality, we can assume To = 0 (if not, replace M by MeTO~). As in Bean and Smith (1984) we define the metric 00oo p(, ') = Z (nr, n)2, n=l 3

where 1 if the nth policies in ir, 7r' are different, n(, ' ) - 0 if the nth policies in ir, 7r' are the same. This metric has the property that, for any L, any two strategies which agree in the first L policies are closer than any two strategies which do not. This metric induces a topology on II. Given a interest rate, r, the problem we wish to solve is: min C (r). NrEn As shown by Bean and Smith (1984), subject to an assumption that II is complete, the minimum exists since II is compact and C.(r) is continuous in 7r. The forecast horizon approach involves solving finite horizon problems: min Cu (r, T). yEn We define C*(T) to be the minimum finite horizon value and C* to be the minimum infinite horizon value. A strategy i* is termed infinite horizon optimal if it minimizes C.(r) and finite horizon optimal if it minimizes C,(r, T) for some T. Let 11* and II* (T) be the sets of optimal strategies for the infinite horizon and finite horizon problems, respectively. An optimal initial policy is an initial policy included in some optimal strategy. The sets of optimal initial policies for the infinite and finite horizon problems, respectively, are denoted II; and II (T). We formally define a (weak) forecast horizon as a time, T, such that for T > T, l;(T) = II*, with IIT I = 1. As mentioned earlier, Bean and Smith (1984) showed that |* I = 1 is sufficient to ensure existence of a forecast horizon. We define degeneracy in infinite horizon optimization as the case when III* I> 1. 3 Degeneracy and the Interest Rate Whether or not a problem is degenerate is a function of the interest rate chosen. In this section we investigate the interest rate's effect on the number of optimal initial policies. If an interest rate allows multiple optimal initial policies, we call it a degenerate rate. Since C,r(r) is a Laplace-Stieltjes transform, it is analytic (Widder (1946)). From analytic function theory (see Bartle (1964)) we know that for any two strategies 7r1 and 7T2, Ci(r) = C,2(r) for at least countably infinite r in any closed interval in (, oo) if and only if COi(r) = C,2(r) for all r > y. It follows that if 4

1(^i(r) $ C23(r) for some r > y then C,(r) = C,2(r) for at most finitely many r in every closed interval in (7, oo). Using this fact, Bean and Smith (1984) proved the following: Theorem 1 If the set of potentially optimal strategies is at most countable, then degeneracy can occur for at most a countable number of interest rates in the range of convergence. When Theorem 1 holds, the set of degenerate rates has measure zero. Hence the probability of selecting a degenerate rate is zero. If degenerate rates are also isolated in the range of convergence, then if a degenerate rate is encountered we can apply an arbitrarily small perturbation to the interest rate to find a nondegenerate rate, which will yield a forecast horizon. A special class of problems in which degenerate rates are guaranteed to be isolated is described in Ryan and Bean (1986). Bean and Smith (1984) include a discussion of cases in which the set of potentially optimal strategies is countable. However, in general this set is uncountable. If two policies are available at each policy epoch, each strategy corresponds to an infinite sequence of ones and zeros. The set of all such sequences is uncountable (Rudin (1976)). To examine the case of uncountable strategies, consider a case where decisions are made periodically and each policy incurs a discrete cost at the beginning of the period in which it is implemented. Thus a strategy 7r incurs the sequence of costs {c,,c,...}. Letting a = e-', we can write the discounted cost as C,(a) = n=l. ca'. We further assume that c E {O 1, 2,..., L} for each 7r IE, where L is a large integer. In this case 7 = 0. Let C = {c = {cn}ni=1 0 < Cn < L, Cn integer Vn}. Given a, let f(c) = Cnn. We can show the following: Lemma 2 If I' <. a < 1, then the image of C under the function f is [0, L__]. Proof: Claim (1): If c E C, then f(c) E [0, L] Proof: m m oo r n k —n — n ^k 1-a k=n k=n k=n For every e > 0, 3N such that La < E, Vn > N. Therefore the series converges by the Cauchy criterion. 5

For any c, La O < Ecnan < n=l Claim (2): f: C I- [0, L-a] is onto. Proof: Given x E [O, L],if x; = LC then set Cn = L Vn. f(c)= z. Suppose x < La. Let cl = the largest integer < L such that cla < x. Given Cl, let c2 = the largest integer < L such that cla + c2a2 < x. In general, given c1,c2,...,Ccn-1, let cn = the largest integer < L such that Ek=l Ckck < X. We claim E=1 CnCa = a. Suppose n~=l1 Cnan < x. Note that x < -La =* Cn < L for some n. Suppose that for some k, ck < L and cn = L, Vn > k. Then E Cn^ = ---- > ak since a > L1 -- O~ L+1' n=k+l Then En=i c Cna + (ck + 1)ak > x which contradicts the construction of Ck. Hence for any k, 3n > k with Ck < L. Now, 00 00 Cnan < x = Cna +b =, b>0. n=l n=l There exists n such that ac" < b. Let no be the smallest such n. Let nl be the smallest n > no such that cn < L. Then 00 Z Cnan + anl1 < X, n=l and cn, could be incremented without En1 cncan exceeding x. This contradicts the construction of Cn. Therefore E 1 cn a. Now suppose F =1 Cna" >,. Then n=l Cnc a-d = x, d > 0. Then EN =1 cn ++EZ N+l cna7 - Zn=N+!cncr" LacNaENn > X d = x. But d - E~ =N+I Cna- > d - L1N > 0 for N sufficiently large. Hence ]~ ca= > az for N sufficiently large which contradicts the construction of CN. Hence.~~ = cnan < x. Therefrere n=l Cn an = X. " Theorem 3 If 1 < a < 1 then there exist infinitely many pairs cl'c2 E C such that c\l c2 and f(cl) = f(C2). 6

K Proof: Let cK = {Ic1,0,0,...,O,cK+2,...}, c > O. Then f(cK) E [cia,ci+ L. Let B = {6 E Clbl = cl - 1}. For b E B, f(b) = (cl - 1)a + n=2 bna. By a variation of Lemma 2, {f(b)lb B} = [( (c - 1), l)a + 1 a] Now, 1 La2 a> -—:a < L + 1 1 - a and LaK+2 La2 log (L+l-1 a + - a< for K > - 1. 1-a 1-a loga Hence for K sufficiently large we have La K+2] r( -1 a~ La2 1 c1a,ca h+ 1- cC [(-l)a,(c -l) -a + ' a Hence f(cK) E {f(b)lb E B}. Therefore, 3b E B such that f(b) = f(cK). This holds for each value of K sufficiently large. Therefore there exist at least countably infinitely many such pairs for each value of a > L1 Theorem 3 implies that for any interest rate r, 0 < r < L, infinitely many pairs of strategies can attain the same cost, with disagreement in the initial policy. It remains unknown whether such pairs of strategies can tie for optimal for many interest rates. But at this point, we must asume that degeneracy is a serious theoretical problem in infinite horizon optimization. In the remainder of the paper we develop ways of resolving degeneracy when it occurs. 4 Cost Function Characteristics This section contains results that will be used to derive forecast horizon results in Section 5. They were derived by Bes and Sethi (1986) for the case of discrete time and discrete policy sets and extended to the case of continuous time and continuous policy sets by Schochetman and Smith (1986). We refer the reader to Ryan and Bean (1986) for details on their adaptation to the case of continuous time and discrete policy sets. Using the exponential bound on cumulative costs, we can derive bounds on discounted costs. 7

Definition: a(T) = M e,-(-r)T is an upper bound on ST etdC,,(t) for any ir E II, where M is defined in (1). Note that a(T) -- 0 as T -- oo for r > 7. Lemma 4 For r E II, r > 7, and T > 0, (a) |Cr(r)- C, (r,T)| < a(T). In particular, it follows that as T - oo, C(r) - (r,T)I - 0 uniformly with respect to ir E II. (b) For S > T C,(r, S) - C(r, T) < a(T). (c) IC*(r)- C*(r,T)I < a(T). Lemma 5 Let {Tn} be a sequence of positive times such that Tn -+ oo as n -- oo. For each n = 1,2,3,..., let rn" E n*(Tn). Then 3 a subsequence {irk} of {r"n} and an element r* E 11* with the property that irk -+ rT* as k -+ oo. This property holds for any convergent subsequence of {rn}. 5 Forecast Horizon Results The existence of a forecast horizon and the algorithm for identifying it are based on the bounds on the discounted costs derived in Section 4. Lemma 6 allows us to restrict the set of potentially optimal strategies based on their minimum cost up to a finite time horizon. Theorem 7 expresses a stopping criterion for identifying a forecast horizon. Theorems 8 and 9 state that the stopping criterion will be satisfied if the optimal initial policy is unique. For the remainder of the paper we assume r > y is fixed. Denote the set of initial policies as II1 = {r, 7r,...,7r'} for some k. Let iC*(T) = min{(C(T)I|r E II, 7r1 = -7r} and iC* = min{C, 1r E II, r1 = TrT}. These minima exist since {7r E IIl1 = 7r} is compact. Also, let C(T) = min{iC*(T)Ii: ir\ IIt(T)} be the minimum T-horizon cost given a suboptimal initial policy and C = min{iC* li: r II } be its infinite horizon counterpart. Lemma 6 If for any strategy r, C(T) - C*(T) > 2a(T) then r HI*(S) for all S > T. Proof: For each S > T, and VTr E II, C7(S) < C.(T) + a(T), by Lemma 4(b). 8

Then by taking infimums on the right and then the left, c (s) _ C*(T) + a(T). We also have Ci(S) > C,(T) - a(T) by Lemma 4(c). Then, by subtracting, C*(S) - C*(S) > C*(T) - C*(T) - 2a(T) > 0. u We generalize two theorems of Bes and Sethi (1986) to continuous time. Theorem 7 If C(T) - C*(T) > 2a(T) and II*(T) = {Irt(T)} then IIt(S) = {rr(T)} for all S > T. Proof: Choose S > T, and consider any ir E II with 7i1 0 ir(T). By definition, Cr(T) > C(T). Therefore, C0(T)- C*(T) > 2a(T). Then by Lemma 6, Ir 0 lI*(S). This is true for each ir E II with 71r1 0 Ir(T). Hence II(S) C I*;(T). Theorem 8 If nI = {7r} then 3T such that VS > T, 1(S) = {rt}. Proof: Suppose not. Then 3 a sequence {T,} such that Tn - oo and one can find r"n E II*(Tn) with 7rn 5 Irt. By Lemma 5, 3 a subsequence {irk} of {In"} such that iXk -- * f II*. Then, for k sufficiently large, irk = *l. But *il = 7r*, which is a contradiction.! Now let b(t) be any function satisfying b(t) > 0, for t > 0, and b(t) -+ 0 as t -+ oo. Bes and Sethi (1986) prove the following result for discrete time and discrete policy sets. Schochetman and Smith (1986) extend it to continuous time and continuous policy spaces. The version here applies to continuous time and discrete policy sets. Theorem 9 If I*|I = 1, then there exists T > 0 such that C(T) - C*(T) > b(T). Proof: See Ryan and Bean (1986). We can sum up our results so far: 9

Theorem 10 If lI is a singleton then 3T > 0 such that T is a forecast horizon. Proof: Follows from Theorems 7, 8, 9, with b(t) = a(t). ~ Theorem 10 was also proved by Bean and Smith (1984). But from Theorems 7, 8, and 9 we also get an algorithm, generalized from Bes and Sethi (1986), guaranteed to find a forecast horizon whenever Ilt I = 1: Algorithm (1) Choose any sequence {Tn}0nl such that Tn -- oo as n -- oo. Set n - 1. (2) Solve the Tn-horizon problem to get II*(Tn), C*(Tn), and C(Tn). (3) If Int(Tn)l = 1 and C(T) - C*(Tn) > 2a(T,) then STOP: Tn is a forecast horizon. Else set n - n + 1 and go to (1). Theorem 11 If iH is a singleton then the Algorithm will terminate with an infinite-horizon optimal initial policy for finite Tn. Proof: Follows from Theorems 7, 8, 9. u 6 Degeneracy Resolution The results in Section 5 show that we can find a forecast horizon if the optimal initial policy is unique. Degeneracy can occur if there is more than one optimal initial policy. In this section we present two approaches to resolving degeneracy that follow from the results of the previous section. One is an exact algorithm for finding an optimal initial policy by perturbing costs. Together with the algorithm in Section 5, this constitutes the first method guaranteed to terminate in finite time when solving any of a general class of infinite horizon problems. The second approach is the calculation of a forecast horizon with the guarantee that any finite horizon optimal first policy has infinite horizon discounted cost nearly as small as that of the infinite horizon optimal first policy. We make some additional definitions: Let G = {: 7r E II}, the set of indices for optima l nitial policies. Let e = (e1,e2,...,Ek) be a perturbation vector and set C;(t) = C,(t) + i), t > 0, if r1 = 7ri; that is, add an instantaneous, discrete cost 10

of ci for rx1 at time 0. Define CQ(r), C"*, iCE., Ce as for C,(t). Let II* = {r: r = argminErI C'(r)} be the set of optimal strategies for the perturbed problem and let HI1* be the set of initial policies corresponding to 7r E II*. Set GE = {1: r E ~II *}, the set of indices for optimal policies for the perturbed problem. Finally, let = C - C* be the minimum penalty for choosing a suboptimal initial policy in the original problem. Adjust M if necessary so that K,(t) + < Meft for t > 0. Lemma 12 Let e be such that Ei < e Vi, and ci ej for i A j. Then GE C G and IGIl = 1. Proof: Suppose j 4 G. Then for any i E G, jC* - iC* > c. Then jC - iC = jC* - iC* + ej - Ei > + ej - ei. But 0 < ec < e Vi =: ej -,il < c. Hence, jCE - iC, > 0. Therefore, j V G6. Thus Ge C G. Now suppose i E Go. Suppose j E Ge also. Then i E G and j E G. Hence iC* = jC*. But Ci i ej = iC6*, jC6*. This is a contradiction. ~ Theorem 13 Let costs be perturbed as in Lemma 12. Then the Algorithm will terminate in finite time. Proof: After the perturbation, lH* is a singleton. The result follows from Theorem 11. U Because calculating e requires all the data over the infinite horizon, this perturbation scheme cannot be implemented. We are currently working on an algorithm to implement these ideas without calculating c directly. But as a consequence of Lemma 6, we can find a near-optimal forecast horizon. We say that T is an c-forecast horizon if Cw(s) - C* < e for all S > T and all 7r*(S) E II*(S). Theorem 14 If Te > r7 log 4(M then TE is an e-forecast horizon.. Proof: For any xr, C <~ CO(T) + a(T) by Lemma 4(a). Also, C* > C*(T) - a(T) by Lemma 4(c). For any S > T, let 7rS E II*(S). Then Cs(T)- C*(T) < 2a(T) by Lemma 6. Then Cs - C*' < C,s(T) + a(T) - C*(T) + a(T) < 4a(T) 1 4rM < e if T > - log. r - (r - ) 11

Note that by Lemma 4(c), C* < a(O). Let p = m = '(I) be the error expressed as a proportion of the maximum possible total discounted cost. Then Te = r- log.. Thus the c-forecast horizon length grows proportionally to the log of the accuracy desired and inversely proportionally to the interest rate used. These properties are consistent with those of the c-forecast horizons found by Bean and Smith (1985) for capacity expansion problems and by Bean, Birge, and Smith (1984) for deterministic infinite dynamic programs. 7 Conclusions Forecast horizon existence results have been found for problems with special structure (see Gilmore and Gomory (1966), Morton (1978), and Shapiro and Wagner (1967)). But all general existence results (Bean and Smith (1984), Hopp, Bean, and Smith (1984), Bes and Sethi (1986), Schochetman and Smith (1986)) assume that the optimal initial policy is unique. The results in this paper indicate that this assumption may not be valid. An example is constructed in which every reasonable interest rate may lead to degeneracy. We have therefore turned our attention to resolving degeneracy when it occurs and present the first algorithm guaranteed to stop regardless of degeneracy. Though our method for perturbing time zero costs cannot currently be implemented, it shows that degeneracy resolution is theoretically possible. In some situations a near-optimal initial policy will suffice. Then an c-forecast horizon can be calculated using only the interest rate and parameters of an exponential function that bounds the total cost for any strategy. Stronger near-optimal horizons, as in Bean and Smith (1985), are likely to exist for specific applications. Acknowledgment We would like to thank Professors Robert L. Smith and Hugh L. Montgomery of The University of Michigan for their suggestions and comments. 12

References R. G. Bartle, The Elements of Real Analysis (Wiley, New York, 1964). J. Bean, J. Birge and R. L. Smith, "Aggregation in Dynamic Programming," Technical Report 84-10, Department of Industrial and Operations Engineering, The University of Michigan (Ann Arbor, MI, 1984). J. Bean and R. L. Smith, "Conditions for the Existence of Planning Horizons," Mathematics of Operations Research 9(1984)391-401. J. Bean and R. L. Smith, "Optimal Capacity Expansion Over an Infinite Horizon," Management Science 31(1985)1523-1532. C. Bes and S. Sethi, "Concepts of Forecast and Decision Horizons: Applications to Dynamic Stochastic Optimization Problems," unpublished manuscript, University of Toronto (Toronto, 1986). A. Charnes, J. Dreze and M. Miller, "Decision and Horizon Rules for Stochastic Planning Problems: A Linear Example," Econometrica 34(1966)307-330. P. C. Gilmore and R. E. Gomory, "The Theory and Computation of Knapsack Functions," Operations Research 14(1966)1045-1074. W. Hopp, J. Bean and R. L. Smith, "A New Optimality Criterion for Non-Homogeneous Markov Decision Problems," Technical Report 84-24, Department of Industrial and Operations Engineering, The University of Michigan (Ann Arbor, MI, 1984). To appear in Operations Research. R. A. Lundin and T. E. Morton, "Planning Horizons for the Dynamic Lot Size Model: Zabel vs. Protective Procedures and Computations Results," Operations Research 23(1975)711-734. F. Modigliani and F. Hohn, "Production Planning Over Time and the Nature of the Expectation and Planning Horizon," Econometrica 23(1955)46-66. T. E. Morton, "Universal Planning Horizons for Generalized Convex Production Scheduling," Operations Research 26(1978)1046-1058. W. Rudin, Principles of Mathematical Analysis (McGraw-Hill, New York, 1976). S. M. Ryan and J. Bean, "Cost-Based Means for Resolving Degeneracy in Infinite Horizon Optimization," Technical Report 86-41, Department of Industrial and Operations Engineering, The University of Michigan (Ann Arbor, MI, 1986). I. Schochetman and R. L. Smith, "Infinite Horizon Optimization," Technical Report, Department of Industrial and Operations Engineering, The University of Michigan (Ann Arbor, MI, 1986). J. F. Shapiro and H. M. Wagner, "A Finite Renewal Algorithm for the Knapsack and Turnpike Models," Operations Research 15(1967)319-341. D. V. Widder, The Laplace Transform (Oxford University Press, Oxford, 1946). 13