Approximating Extreme Points of Infinite Dimensional Convex Sets Willian P. Cross Dept. of Industrild and Operations Engineering University of Michigan Ann Arbor, MI 48109 H. Edwin Roineijn Rotterdain Sch(x)l of Management Er-asnus tIliversity Rotterdaun, Netherlands Robert L. Smith Dept. of Industrial and ()perations Engineering University o' Michigan Ann Arbor, MI 48109 Technicld Report 97-09 June 1997

Approximating extreme points of infinite dimensional convex sets William P. Cross H. Edwin Romeijn Robert L. Smith June 12, 1997 Abstract The property that an optimal solution to the problem of minimizing a continuous concave function over a compact convex set in fRn is attained at an extreme point is generalized by the Bauer Minimum Principle to the infinite dimensional context. The problem of approximating and characterizing infinite dimensional extreme points thus becomes an important problem. Consider now an infinite dimensional compact convex set in the nonnegative orthant of the product space lR~~. We show that the sets of extreme points EN of its corresponding finite dimensional projections onto IRN converge in the product topology to the closure of the set of extreme points E of the infinite dimensional set. As an application, we extend the concept of total unimodularity to infinite systems of linear equalities in nonnegative variables where we show when extreme points inherit integrality from approximating finite systems. An application to infinite horizon production planning is considered. Key words. Infinite dimensional convex sets, extreme points, projections, infinite dimensional total unimodularity. 1 Introduction Many important problems in Operations Research are naturally phrased within the context of an infinite dimensional linear vector space (see Luenberger, 1969). An important instance is the problem of selecting a sequence of decisions over an infinite horizon that minimizes its associated discounted cost (see, for example, Bes and Sethi (1988), Schochetman and Smith (1989)). Included within this class are nonhomogeneous Markov Decision Processes (Hopp, Bean, and Smith, 1987), capacity expansion under nonlinear demand (Bean and Smith, 1985) and equipment replacement under time varying demand or technological change (Bean, Lohmann, and Smith, 1985). By Bauer's Minimum Principle (see Roy, 1987), when the feasible region is a nonempty compact convex subset S C R', and the minimizing objective function is a concave lower semi-continuous function on S, then the optimum is attained at an extreme point of S. The determination of the properties of extreme points of compact convex sets in JR' thereby leads to a characterization of optimal properties. We show in this paper that the extreme points of the finite dimensional projections of S arbitrarily well approximate their 1

infinite dimensional counterparts, thus allowing for the inheritance of finite dimensional properties in the infinite dimensional case whenever such properties are preserved in the limit. We illustrate this principle by showing that the property of integer extreme points is inherited in the infinite horizon case for a classic production planning problem. Now consider a non-empty compact and convex set S in the nonnegative orthant of the product space R~. Our interest in this paper is to approximate, and thereby characterize, the extreme points of this set. We will approximate S by its corresponding projections SN onto IRN (N = 1,2,...). Conditions will be provided that assure that the extreme points EN of SN converge (with respect to the underlying product topology) to the extreme points E of S. Not only does this result allow for the finite computation of approximations of the extreme points of S, but it also, as already noted, provides for the inheritance of all finite dimensional properties of EN that are preserved under componentwise convergence to E. As an illustration, we apply this technique to extending the notion of total unimodularity to an infinite system of linear equalities in nonnegative variables where it is shown that all extreme points must be integer valued. The literature on the extreme point structure of infinite dimensional convex sets goes back to Minkowski (1911) who defined a point of a convex subset of a linear space as an extreme point if the subset remaining after its removal is convex. The subject became an important tool of functional analysis with the publication of the Krein-Milman theorem (Krein and Milman, 1940) which, as later extended by Milman, Kelley, and Bourbaki, established that every compact convex subset of a locally convex topological linear space is the closed convex hull of its extreme points. This result was later extended to locally compact subsets by Klee (1957). These positive results are noteworthy since convex sets can display a disconcerting number of pathological properties in the context of infinite dimensional spaces (Klee, 1951). See also Roy (1987) for an up-to-date survey of the literature. Anderson and Nash (1987) revisited the characterization of extreme points for infinite dimensional linear systems in their path breaking book. Their motivation was to extend the simplex method to infinite dimensional linear programming; however, their task was complicated and their success limited by the pathologies inherent in such problems. For example, such linear programs may have optimal solutions but fail to have optimal basic solutions. Our approach here is indirect, as in Romeijn, Smith, and Bean (1992), in that we establish extreme point properties by demonstrating their inheritance from their finite dimensional projections. Key to this is establishing that the extreme points of these approximating sets converge to the extreme points of the infinite system. In section 2, we establish the mathematical framework for this problem, and in section 3 we demonstrate conditions for this convergence to take place. Section 4 is an application that establishes sufficient conditions for extreme points of linear systems to be integer valued. 2 Mathematical framework 2.1 Extreme points The following will serve as our definition of an extreme point of a convex set: 2

Definition 2.1 A point x E S is called an extreme point of S if x is not the midpoint of any line segment contained in S. In other words, if x = ~(u + v), where u, v E S, implies that x = u = v, then x is an extreme point of S. We assume that 1R~ is a product space equipped with the product topology inherited from the underlying Euclidean spaces. This means that a sequence x1, x2,..., where X" E JR0 for all n, converges to some x E JR~ precisely when its components xn converge to Xj in the ordinary Euclidean metric on JR for all j. We will repeatedly use the following result, pertaining to the existence of extreme points: Lemma 2.2 Any nonempty, closed, convex subset of the non-negative orthant of a finitedimensional Euclidean space has an extreme point. Proof: This follows directly from lemma 3.3 in Klee (1957). D 2.2 Projections For each N = 1,2,..., define the projection function PN: R~~00 - RN as PN(X) = (X,...,XN) and the corresponding projections of S onto IRN as SN = {PN(X): x E S}. We will sometimes want to view SN as a set embedded in the infinite dimensional linear space R~~. Therefore, we will at times also let SN = {(PN(x),O): E S} where the precise meaning of SN will be clear from the context. Now let EN be the set of extreme points of SN. (Thus, EN can also be thought of as a set in either JRN or JR0, depending on the context.) The principal objective of this paper is to find conditions under which the sequence of sets of extreme points of SN converges (in the Kuratowski sense to be defined below) to the set of extreme points of S. 2.3 Convergence of sets We begin by defining Kuratowski convergence (Kuratowski, 1966) for a sequence of sets in JR~~. Let KN C JR~~ for N = 1,2,.... Define: (i) lim infyN-vo KN = the set of points x E JR0 for which there exists xN E KN, for N sufficiently large, such that limN-oo N = x. 3

(ii) limsupN_, KN = the set of points x E JR~O for which there exists a subsequence {KNk} of {KN} and a corresponding sequence {xk} such that xk E KNk for all k, and limkoo k = x. In general, lim inf KN C lim sup KN. N —oo N-oo If K C JR00 such that K C lim infN-O, KN and lim SUPN.0oo KN K, i.e. lim infNoo KN =lim supN_,,o KN = K, then we write lim KN= K N-+oo. and say that {KN} Kuratowski converges to K. 3 Convergence of projections We now return to the set S. We will first show that the sequence of projections SN (viewed as subsets of 1R~~ by extension with zeroes) Kuratowski converges to S. Lemma 3.1 The sequence of projections SN converges in the Kuratowski sense to S, i.e. lim SN = S. N —oo Proof: We need to show that (i) S C liminfNoo SN, and (ii) lim supNvo SN C S. The first property follows directly by observing that lim (pN(x),O) = x N ---OO for all x E S. To prove the second property, we introduce, for all N, the set SN = {x E IR: x > 0, pN(x) E SN} i.e. SN can be obtained from SN by arbitrarily extending all elements of SN to nonnegative elements of R~~. We will first show that 00 S= n S (1) N=1 Since S C SN for all N, it is clear that 00 S CN S N=1 4

It remains to be shown that SN C S. N=1 Let x E SN for all N. For all N, choose yN E S such that pN(yN) = (X1,...,XN) E IRN. Then y = xi for i = 1,..., N. Thus lim yN = X. N-0oo Since S is closed, we have x E S, so (1) follows. Now, by Kuratowski (1966), 00 lim SN n SN N-*0 N=1 since SN+1 D SN for all N. Since S is compact, the sets SN are closed, and thus 00 lim SN= SN =S. N-00 N=1 Property (ii) now follows by observing that lim sup SN C lim sup SN lim SN. N —oo N-,oo N —oo In section 2 we defined PN to be the projection of points in JR~~ onto ERN. Similarly, we can define a projection of points in IRM onto IRN (for M > N). We will denote these projections also by PN, where the appropriate interpretation should be clear from the context. The following lemmas show the relationship between extreme points of the projections SN (regarded as subsets of IRN) and the extreme points of the original set S. Lemma 3.2 For every extreme point x of SN there exists an extreme point of SN+1 which is identical to x in its first N components. Proof: Let x be an extreme point of SN. Then consider T = SN+1 n {y E JR~: pN(y) = x}. Clearly, T is nonempty, since it contains pN+l(z), where z E S is such that x = pN(z). Now let x' be an extreme point of T. (Such a point exists by lemma 2.2.) Then the desired result follows if x' is an extreme point of SN+1 as well. Let u, v E SN+1 such that x' =(u+v). Now note that pN(u),pN(v) E SN, and x = pN((u+v)) = pN(u)+ PN(v). Since x is an extreme point of SN, we have that N(u) = PN(V) = x, so that u,v E T. But now, since ' is an extreme point of T, we have that u = v = x', so ' is an extreme point of SN+1, which proves the lemma. o By invoking lemma 3.2 exactly M - N times for M > N, we conclude 5

Corollary 3.3 For every extreme point x of SN and for every M > N there exists an extreme point of SM which is identical to x in its first N components. Lemma 3.4 For every extreme point xN of SN there exists an extreme point of S which is identical to xN in its first N components. Proof: By lemma 3.2, there exist extreme points xN+1, N+2,... of SN+1, SN+2,... respectively, such that, for all N < i < j, x3 is identical to xi in its first i components. So, by lemma 3.1 the convergent sequence {xT}XN (after extending its elements making them elements of S) converges to some x E S. It remains to be shown that x E E. Suppose not, then there exist u, v E S (u 7 v) such that x = ~(u+v). Now consider the first component in which u and v differ, say M > N. Since x = ~(u + v), pM(X) = 2PM(u) + IPM(v), where PM(X) = xM and pM(u), M( ) E SM. But since xM is an extreme point of SM, PM(U) must be equal to PM(v), implying that the M-th components of u and v are equal, which is a contradiction. Thus x is an extreme point of S. n Lemma 3.5 lim sup EN C E. N —OO Proof: Let x E limsupN,o EN, and let xk E ENk such that limk ook = x. Consider the set {y E S: yi = x for i = 1,... Nk}. By lemma 3.4, this set contains an extreme point of S, say yk. We now have a sequence {yk}_lI in E. This sequence clearly converges to x, so we have x E E. Therefore, lim SUPN.o. EN C E. D We can now prove the first major result of this paper. Theorem 3.6 The sequence of sets of extreme points EN of the projections SN of the compact convex set S converges, i.e. limNo, EN exists. Moreover, lim EN C E. N-.-oo Proof: Let {xNk}01 be a subsequence of points in ENk, k = 1,2,..., respectively, such that lim xNk = x k -oo i.e., x E lim sup EN. N-,oo In order to show that x E lim infNv,,- EN, we need to construct a sequence of points {xN }N=1 such that xN E EN for all N, and such that lim xN = x. N —.o Let Nk < N < Nk+l. We now choose xN as follows: set x^ k= (,~I...,I N~,kYNk+l,...,yN,0) 6

where the yj are chosen in such a way that xN is an extreme point of SN, which we can do by corollary 3.3. Thus, a sequence of extreme points xN in EN has been created, which clearly converges to x in the product topology. So we have shown that lim sup EN C lim inf EN. N —OO N-,o The second claim of the theorem now follows from lemma 3.5. o Remark: Note that all the above results remain valid if the assumption that S is compact is replaced by the assumption that S and its projections SN are all closed. Note also that, under compactness, the statement of theorem 3.6 is nontrivial in that lim SUPN0o0 EN #c 0 so that limNse,, EN # 0. Theorem 3.6 then tells us that E # 0, which of course is also concludable from the Krein-Milman theorem since S # 0 by hypothesis. In the remainder of this section we will show that E C lim infNwVo EN, so that limN.o EN = E. In order to prove this result we need the notion of an exposed point, which Klee (1958) defines as follows: Definition 3.7 A point x E S is called an exposed point of S if S is supported at x by a closed hyperplane which intersects S only at x. Let exp(S) denote the set of exposed points of S. We can then prove the following lemma. Lemma 3.8 exp(S) C liminfNoo EN. Proof: Let x E exp(S). Then there exists a continuous linear functional c such that min{c(y): y E S} is attained uniquely by x. Now let, for all N, QN denote the set of points for which min{c(y): y E SN} is attained. Then, since limN.-o SN = S, the Maximum Theorem (see Berge, 1963) says that limsupN_ QN C {x}. Now choose xN E QN such that xN E EN. This is possible since, by Bauer's Minimum Principle, a continuous linear functional has an extreme point optimum when minimized over a compact set (see Roy, 1987). Now, by the compactness of S, every subsequence of {xN} has a convergent subsequence which converges to x. Therefore, limNv,,o N = x, and thus x E lim infN_,o EN. O We are now able to prove the major result of this paper. Theorem 3.9 The sets of extreme points EN of the projections SN of the compact convex set S converges to the closure of the extreme points of S, i.e. lim EN = E. Proof: By the previous lemma, exp(S) C liminf EN. NV —oo Thus, by the first part of theorem 3.6 exp(S) C lim EN. N —+oo 7

Since limN.oo EN is closed (see Kuratowski, 1966), we also have exp(S) C lim EN. N ---oo Klee (1958) proves that, since S is compact, E C exp(S), so E lim EN. -N-.oo Again using the fact that limNvo EN is closed, we obtain EC lim EN. N —+oo Combining this with the second part of theorem 3.6 we conclude lim EN= E. N ---oo D Unfortunately, E may fail to be closed so that theorem 3.9 cannot be strengthened to limN-,, EN = E without additional hypotheses. In fact, there are well-known examples of convex sets in IR3 for which the set of all extreme points is not closed. Consider for example the convex hull of the line segment joining the points (0, 0, -1) and (0, 0, 1) union the unit ball with center at (1,0, 0). For a more interesting example in /R~~, let S be the convex hull of the set 00 E U= j {x E IR: Xj E {0.2},, = 1 for all i# j}. j=1 Clearly, E is the set of extreme points of S, the projections of S are SN = co (U{xE N: x E (0 2 xi = 1 for all i =1,...,N; i j}) j=l and their extreme points are N EN= U{x E IRN:X E {0,2}, x,= 1 for all i = 1,..., N; i j}. j=1 It is easy to see that (1,1,...) E E\E, so that E is not closed. By theorem 3.9, limNv,, EN = E E. This example is striking in that there exists a sequence of extreme points converging to the center of the feasible region. In cases where E is closed, we have E = E, so that theorem 3.9 becomes Corollary 3.10 If E is closed. then lim EN = E. N-0oo 8

4 Extension of total unimodularity to infinite dimensional linear systems 4.1 Lower triangular linear systems In general, the projections SN of S may be difficult to characterize. However, consider the case where S can be expressed as the solution set of an infinite linear system, i.e. 00 S=-{x fIRn:Ax = b,x>0} i=l where A = (Aij) is a doubly infinite lower block-triangular matrix, x E Hf1 IRti, and b E FnHI1 Rmi.- Hence S is the solution set to Aixj = bi i = 1,2,... j=l where Aij is an (mi x nj)-matrix, xj EC Rnj, xj > 0, and bi E?"mi. Now for each N = 1,2,..., consider the algebraic projections TN of S formed by ignoring the (vector) variables and (vector) constraints beyond the N-th one: N i TN= {x EII R:' Aijxj = bi for i = 1,..., N; x > 0}. i=l j=1 The sequence of algebraic projections {TN } is called extendable if, for all N, any solution to the first N linear equalities and nonnegativity constraints has some continuation which satisfies the infinite set of constraints. In this case, SN = TN, N = 1,2,.... In fact, extendability holds if and only if the algebraic projection TN is equal to the ordinary projection SN onto HIN Rni for all N. Note that in the previous sections we only considered explicitly the case where ni = 1 for all i. However, it is easy to see that all results will still hold for arbitrary, but finite, values of ni. 4.2 Total unimodularity Consider the following extension of the concept of total unimodularity: Definition 4.1 A doubly infinite matrix A = (aij)ij=1,2,. is called totally unimodular if every finite square submatrix of A has determinant 0, 1 or -1. For the remainder of this section, we impose the following Assumption 4.2 A is a lower block-triangular matrix, and the set S = {x X: Ax = b, x > 0} is compact and has extendable algebraic projections TN (N = 1,2,...)). Note that a sufficient condition for S to be compact is that we have finite bounds on the variables. We can now prove the following theorem, which is an extension of a corresponding result for the finite dimensional case (see e.g. Schrijver, 1986). 9

Theorem 4.3 Let A be totally unimodular, and let the vector b have integer components. Then, under assumption 4.2, the extreme points of S = {E IR: Ax = b,x > 0} are integer valued. Proof: Since A is totally unimodular and b consists of integers, the extreme points of TN = SN are integer valued (Schrijver, 1986). From theorem 3.9, lim EN= E. N ---oo N I00 Now suppose x E E. Then there exists a sequence of points {xAN}'N= such that xN E EN for all N, and xN - x as N -+ oo. Since all xN are integer valued, x must be integer valued as well. So all points from E are integer valued. But E C E, so all points in E are integer valued. D 4.3 An application in infinite horizon production planning Consider the following infinite horizon production planning problem. 00 min - ' (kj(Pj) + hj(Ij)) j=1 subject to Ij- + Pj- Ij = d j1,2,... Pj < P j=1,2,... Ij < Ij j=,2,. PIj > 0 j=1,2,... where Pj denotes production in period j, Ij denotes net inventory at the end of period j, and dj the demand in period j. We assume that the cost of production kj and the cost of carrying inventory hj are nondecreasing concave functions. Moreover, we require 00 -l' (kkj(Pj) + hj,(I,)) <00 j=1 so that the objective function is well-defined for all feasible solutions. We then have the following result: Theorem 4.4 If in the above production planning problem the demands are integer, they never exceed potential production in a period, and the upper bounds on production and inventory are integers, then there exists an integer valued optimal solution to the problem. Proof: First of all, since demand in a period never exceeds potential production, it is easy to see that the algebraic projections of the system defining the feasible region are extendable, so that the ordinary projection of the feasible region onto nIN=1 R2 is given by the solution set to the first N constraints (and the first N upper bounds). 10

Secondly, it is well-known that the constraint matrix of the feasible region is totally unimodular for any finite horizon version of the problem. But then, by definition 4.1, the constraint matrix of the infinite horizon problem is totally unimodular. Theorem 4.3 now states that the extreme points of the feasible region of the production planning problem are integer valued. Finally, continuity of the objective function, together with compactness of the feasible region, guarantees that one of those (integer valued) extreme points is optimal. o The same argument can be easily applied to more complex planning problems. For example, Jones, Zydiak, and Hopp (1988) introduced an infinite horizon linear programming formulation of an equipment replacement/capacity expansion problem where demand for capacity is nondecreasing over time. Key to the validity of this relaxed LP formulation is the presence of an integer valued optimal solution, which they established directly by verifying the optimality of a constructive integer valued solution. However, one can show that, since machines have finite lifetimes in Jones, Zydiak, and Hopp (1988), all decision variables can be bounded without loss of optimality, so that the feasible region can be restricted to a compact set. Moreover, since there are no a priori bounds on the number of new machines that can be bought or salvaged in any year, the property of extendability holds. Finally, total unimodularity is readily established for the finite horizon versions of the problem. We can therefore conclude from theorem 4.3 that all extreme point solutions, and hence an optimal solution, are integer. This extends the applicability of the model in Jones, Zydiak and, Hopp (1988) to the more general case of arbitrary time varying demand for capacity and time dependent costs arising in the presence of technological change. Acknowledgements This material is based on work supported by the National Science Foundation under Grant No. DDM-9214894. In addition, the work of the second author was supported in part by a NATO Science Fellowship of the Netherlands Organization for Scientific Research (NWO), and the work of the third author was supported in part by the Netherlands Organization for Scientific Research (NWO). References Anderson, E.J., P. Nash (1987). Linear programming in infinite dimensional spaces, Wiley, New York. Bean, J.C., J.R. Lohmann, R.L. Smith (1985). A dynamic infinite horizon replacement economy decision model. The Engineering Economist 30 99-120., R.L. Smith (1985). Optimal capacity expansion over an infinite horizon. Management Science 31 1523-1532. Berge, C. (1963). Topological Spaces, Oliver and Boyd, London, U.K. Bes, C., S.P. Sethi (1988). Concepts of forecast and decision horizons: application to dynamic stochastic optimization problems. Mathematics of Operations Research 13 11

295-310. Hopp, W.J., J.C. Bean, R.L. Smith (1987). A new optimality criterion for non-homogeneous Markov Decision Processes. Operations Research 35 875-883. Jones, P., J. Zydiak, W. Hopp (1988). Stationary dual prices and depreciation. Mathematical Programming 41 357-366. Klee, V. (1951). Convex sets in linear spaces. Duke Mathematical Journal 18 443-466. (1957). Extremal structure of convex sets. Archiv der Mathematik 8 234-240. (1958). Extremal structure of convex sets, II. Mathematische Zeitschrift 69 90-104. Krein, M., D. Milman (1940). On the extreme points of regularly convex sets. Studia Mathematica 9 133-138. Kuratowski, K. (1966). Topology, volume I, Academic Press, New York. Luenberger, D.G. (1969). Optimization by Vector Space Methods, John Wiley & Sons. Minkowski, H. (1911). Gesammelte Abhandlungen, Teubner, Leipzig, Germany. Romeijn, H.E., R.L. Smith, J.C. Bean (1992). Duality in infinite dimensional linear programming. Mathematical Programming 53 79-97. Roy, N.M. (1987). Extreme points of convex sets in infinite dimensional spaces. American Mathematical Monthly 94 409-422. Schochetman, I.E., R.L. Smith (1989). Infinite horizon optimization. Mathematics of Operations Research 14 559-574. Schrijver, A. (1986). Theory of linear and integer programming. Wiley, Chichester. William P. Cross: Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109-2117. H. Edwin Romeijn: Department of Decision and Information Sciences, Rotterdam School of Management, Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands; e-mail: E.Romeijn(fac.fbk.eur.nl. Robert L. Smith: Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109-2117; e-mail: rlsmithOumich.edu. 12