GENERATING UPPER BOUNDS ON THE EXPECTED VALUE OF A CONVEX FUNCTION WITH APPLICATIONS TO STOCHASTIC PROGRAMMING John R. Birge Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109 Roger J-B Wets Mathematics University of California Davis, CA 95616 Technical Report 85-14

GENERATING UPPER BOUNDS ON THE EXPECTED VALUE OF A CONVEX FUNCTION WITH APPLICATIONS TO STOCHASTIC PROGRAMMING John R. Birge* Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109 Roger J-B. Wets* Mathematics University of California Davis, CA 95616 ABSTRACT Bounds on the expected value of a convex function are obtained by means of an approximating generalized moment problem. Numerical implementation is discussed in the context of stochastic programming problems. KEYWORDS: Generalized moment problems, stochastic programming, inequalities in probability. *This research has been partially supported by the National Science Foundation. 1

1. INTRODUCTION: THE GENERALIZED MOMENT PROBLEM The (generalized) moment problem: find P: A -— > [0,1] such that (1.1) fJvi() P(dE) < i' i = 1,...,s fvi(S) P(dE) = Bi i = s+1,...,m, and z = vo(S) P(d)) is maximized with A the sigma-field of events defined on 5 — here a subset of RN — is of general interest in statistics, in stochastic optimization, etc. The underlying premise is that some information is available about certain moments, or generalized moments, of an unknown probability distribution. This determines a class P, i.e., the probability measures that satisfy the constraints of (1.1). This limited information is to be used in order to obtain an upper (or/and lower) bound on some other moment of the distributions in this class. This problem has been studied in detail in the classical framework of statistical theory, see for example [9] where the accent is placed on those problems of type (1.1) that can be solved analytically (in the framework provided by Chebyshev systems). The connection between the generalized moment problem and optimization theory has been clarified by Kemperman [81, but so far the computational tools provided by linear or nonlinear programming have only been used sparingly in the development of general solution procedures for generalized moment problems. This paper is one contribution in that direction. Dupacova [2.3] was the first to rely on some (classical) results for the moment problem to obtain bounds for the optimal value of certain stochastic programming problems; the class P is usually determined by first —or possibly second order —moments and vo is a 1-dimensional convex or concave 2

nondifferentiable function. In such cases it is possible to obtain an explicit characterization of the extremal measure that solves the corresponding moment problem. This is not the case in general. Although it is known that if the support of the probability measures S is convex compact, then the linear programming problem (1.1) admits as optimal solution, an extremal measure whose support is concentrated on at most m+1 points of (see [1, Theorem 6.9] for a constructive proof of this result). There is usually no closed form expression that allows us to easily identify this extremal measure. There are no conceptual difficulties in designing solution procedures for solving (1.1), see [1, Section 6], however some of the operations that must be carried out may be in practice extremely onerous. Much depends on the properties of the functions v0 and vi, i = 1,...,m. In this paper we shall be mostly concerned with the case when vo is convex, and the functions v^, i = 1,...,m are linear or piecewise linear. We extend and sharpen the results of Gassmann and Ziemba [4] who were first in developing an implementable procedure for the restricted, but important, case when v0 is convex and there is just one constraint on the expectation (with respect to P). 2. LINEAR CONSTRAINTS Most of the literature devoted to generalized moment problems works with the assumption that 5 is compact [7], [1, Section 6]. Here we drop this assumption. It is possible to do so by relying on an appropriate compactification of Rn, viz. by adding to Rn the space of directions of recession. Let us suppose that E c RN is a nonempty convex set, if not we would work with co the convex hull of 5. Let 3

rc = cone of the directions of recession of 3. This corresponds to the largest (closed) convex cone such that + (rc f)c c for all i in 3; it is called the recession cone of 2. It is nonempty, in fact 0 E rc _, since by assumption 5 is nonempty. For more about recession cones, consult [10, Section 8]. Let ext: = extreme points of If H has no extreme points, set ext - = {0}, and let ext-rc: = extreme directions of rc-W by which we mean a collection of points in RN such that rcH = pos (ext-rc ), (where pos T denotes the positive hull of the points in T.RN, i.e. q pos T: = { E k t k I k > 0, tk E T, q finite}), k=1 and no element of ext-rc 3 can be obtained as a positive linear combination of other elements of 2. The elements of ext-rc E are positively linearly independent. Since 5 is convex, we have = co(ext3 ) + pos (ext-rcH ). Every point i in s: has at least one representation of the form: 5 = ft eX(e, de) + J rp(, dr) (2.1) ext 3 ext-rc 3 with X(S,') a probability measure on (ext 3, E) and p(S,') a nonnegative measure on (ext-rc 3, R); E and R are the Borel fields. In fact, the theorems of Caratheodory and Steinitz guarantee that for each E there exists one representation involving no more than N+1 points of ext E and 2N points of ext-rc 3, i.e. the measures X(-,') and (-,.) have then finite support. 4

Now, suppose v0: -— > R is a proper convex function, and consider i as as given by (2.1) with i: -= ri(E, dr), ext-rc_ then = / (e + i) X (~, de), (2.2) ext and Vo() < v(e + i) X (5, de). (2.3) /ext 5 By Vo(+tO) - VO(S) Vo(+tr) - Vo(S) rc v0(C): = lim - sup -.-.. (2.4) t —> oo t t>0 t we denote the recession function of v0 in the direction C [10, Section 8]. This is a sublinear function (positively homogeneous and convex). Since v0 is convex, the ratio,I-'(vO(+ C) - vo()) is a monotone nondecreasing function of X (when X>O) and thus the supremum is "attained" at X = 0. This justifies the equivalence of the two formulas in (2.4). It also means that for all e ~ ext 5, vO(e + ) < vO(e) + rc vO(M) and hence (2.3) yields vO(i) < v(e) x(E, de) + rc v0(E). (2.5) ext - Since rc v0 is a sublinear function, this implies that vO() < J v(e) X((, de) + / rc v0(r) W(, dr). (2.6) ext5 rc-ext.' Integrating on both sides with respect to P, we obtain Jvo(~) P(di) < Vo(e) X(de) + / rc V0(r) \(dr) (2.7) extE rc-ext= 5

where X(') =f ( X(S,') P(dS) (2.8) and ((' )-E P(d), -(2.9) (assuming that X and p have been chosen measurable with respect to i). Moreover i-: = ( P(di) = eX(de) + rp(dr), (2.10) exto eext-rc I 1 = f(de) = f P(d)f X(A, de) = flP(d) (2.11) _ ^5 Jext" and both X(defined on E) and P(defined on R) are nonnegative. The inequality (2.7) holds for any nonnegative measures X and p that satisfy (2.8)-(2.11) and (2.1). Given the bound provided by (2.7) one may be tempted to ignore (2.8) and (2.9) —i.e., that it must be possible to "disintegrate" X and 1 in measures X(E,') and U(E,') that satisfy (2.1) - but this would render (2.7) invalid as an easy example will show readily. However, there always exists one pair (A,i) for which it is not necessary to verify if X and p can be "disintegrated" so as to satisfy (2.1): namely, if (X,p) maximizes the right-hand side of (2.7)! We have thus shown 2.1 THEOREM. Suppose CRN is a nonempty convex set, P is a probability measure on (E, A), and v0 is a proper (nowhere - oo and finite-valued somewhere) extended-real valued convex function defined on RN. Then fvo(E) NP(dE)< iSUP(X ) vo(e) X(de) +-f rc vo(r) p (dr) (2.12) J " 9 J xtS- Jxt-rcE where X is a probability measure on (ext E, E), and p is a nonnegative measure on (rc ext 5, R) such that 6

e (de) + r (dr) ='P(d5) = i. (2.13) xt ext-rc This yields an upper bound on the optimal value of (1.1) when the constraints are determined by the linear system J P(dE) = E. It should be emphasized that (2.12) yields in some sense the worst possible bound for fvo(S) P(dE) among all those generated by (2.7)-(2.11), but it may be the only one that is sufficiently easy to compute and to integrate into an approximation scheme for solving stochastic optimization problems. The next result goes even further in that direction. It sharpens and extends [4, Theorem 4] or [1, Section 5(v)] for the case of bounded convex polyhedral support. 2.2 COROLLARY. Suppose CC = co(el,...,eP) + pos(rl,...,rq) and h: RNi -— > R is a convex function such that h > vo on Then Jr P. q Vo(E) P(d0) < suP(,,) Z Xjh(ej) + Z Ui(rc h) (ri) Xj>O, i>O, L J=l t=l p q p Z Xjej + ir = E, X jeJ = 1. (2.14) j-=1 i=1 j-1 PROOF. Note that iVo(i) P(dW) < J h(S) P(dW) = h() P(d~) where P has been (trivially) extended to C. It now suffices to apply Theorem 2.1. U All the results and remarks of this section apply equally well to the case when P is simply a bounded measure, in particular to the case when P is the restriction of some probability to a subset of the space of events, making of course the obvious adjustments. This simple observation yields directly the versions of Theorem 2.1 and Corollary 2.2 with conditional expectations. 7

3. PIECEWISE LINEAR CONSTRAINTS. The extension to the case when the constraints are piecewise linear, or more precisely piecewise affine, is straightforward. Details are worked out in this section. The importance of this case, rests on the potential use of piecewise linear approximations for handling the (general) nonlinear case, see Section 4 for an elementary example. Suppose; is partitioned in L subregions EH, k =1,...,L, and in (1.1) the functions vi, that define the constraints, are piecewise linear: for i=1,...,m, vi(i) = ai' - a i when Ec 5. (3.1) We then have L vi(i) P(dE) = Z | (ai'i - ai) P(d ) (3.2) where -2 = E (g | e e o, Pt = PHThus, the (generalized) moment problem becomes: find Q: A —— > [0,1], a probability measure, such that (3.4) -2 = EQ ={| E E } PE = Q(q) L L Z (P a ) - < i i=1,...,s, =1L L21 -- L L z (p. aie) * ~- - PtiQ = a8i, i=s+1,...,m. 2.=1 l =1 and z = fvo() Q(dE) is maximized. Our objective is to obtain an upper bound on the optimal value of this problem. Let P be any probability measure that satisfies the constraints of 8

(3.4); P could be the measure that we are trying to approximate. Let C., -=1,...,L, be a collection of (nonempty) convex sets such that for all Q, 5C C~. One possibility is to choose for all ~ = 1,...,L, C = co z: = the convex hull of 5. Let X'(,') be probability measures defined on (ext C., E.) and pj(5, ) nonnegative measures on (ext-rc C., R9) such that for all E ~ S = fe e XI (E, de) + f rpr (, dr). (3.5) Jext CZ ext-rc Cj Here Et (R1 resp.) is the Borel field on ext Cn(ext-rc CZ resp.) and we assume that XI and pi are A-measurable with respect to i. For any A c Ek, set X)(A): = f X(, A) P(dE). (3.6) and for any B c RV, set Pn(B): =f ip(S, B) P(d~). (3.7) We have from (3.6): ef XA(de) = X (ext C) = P( )= p. (3.8) Jext C 9 From (3.2), after replacing E by its representation (3.5), and interchanging the summands using the definitions of X and p1, we obtain: f ~ ~ L ~L Jvi(S) P(dE) = ( Z aifeX de + f ai' ri (dr) - apk). (3.9) Z=1 xt C9 ext-rc C~ From the above, by the same arguments as in Section 2, in particular, by the convexity of vo on C., we prove the following generalization of Theorem 2.1. 3.1 THEOREM. Suppose CRN is nonempty, {Ef, { =1,...,L} a partition of, {C, Z=1,...,L} nonempty convex sets such that 3C CC for all Q, P a probability measure, v0 an extended real-valued proper convex function on RN 9

and for i = 1,...,m, vi is a piecewise affine function on RN with vi(i) - ai'S - (li when E c F. Then Jv0() PW(d) < suP( ) [ 1t vo(e) X (de) + xt-rc (rc vO)(r)u (dr (3.10) -ext-rc CZ where for ~=1,...,L, XA and p are nonnegative measures on (ext C,E ) and (ext-rc C, RZ) respectively, such that X (ext CQ) = P( ): p (3.11) and for i=1,...,m, ~ I f^Jl^'S^ + / ^p1o^U' z (poaF)'5~ (3.12): (f ait ceXZ(de) + ai r 1aZidr) )(pa 1 (3.12) -1r \ Jext C xt-rc C=1 Observe that no convexity conditions are necessary on the functions vi, i=1,...,m. Suppose, for example with N=1, that aik = i, aik =0 if 9 A k, the i-th condition of (3.12) would require that the measures be chosen so that eXk (de) + e r Uk(dr) = Pkk. Iext Ck,ext-rc Ck This means that the measures on the extremal structure of Ck must satisfy this conditional expectation condition. Approximation schemes can be built by requiring that the chosen measures satisfy conditional expectation conditions that involve finer and finer partitions of H. Kall and Stoyan [6] and Huang, Vertinsky, and Ziemba [5] have studied constraints'of that type. The constraints (3.7), however, are much more general, in that they allow for tighter restrictions so that sharper bounds may be obtained. The approximations in [5], [6] rely on the extreme points of the for all 9=1,...,L, and therefore require the evaluation of the vi at each of these 10

points. Here only the extreme points of some convex set containing E are needed, indeed simply choose 5. = co - for all -=1,...,L. Restriction of CZ to subsets of 5, however, still imposes additional restrictions on the set of feasible probability measures and can, therefore, improve the bounds. There is also in the piecewise affine case a generalization of Corollary 2.2. We do not need v0 convex, only that it be dominated by a convex function. 3.2 COROLLARY. Suppose 5cC.C: = co(e,...,e ) + pos(r,...,r ),, 9 =1,...,L} is a partition of B, and h: RN -_> R is a proper convex function such that h > vo on B. Then for any probability measure P: A -— > [0,1], we have L rZ qZ vo()P(dE) < sup(r,) z ( EM h(ek )k + Z (rc h)(r )Hk1 (3.13) suP~1PxQ L =i k 1 k r1 L r q L such that Z ( Z aie kXZk + Z a irkHr k)= Z P9ai' ~ 01= k=1 k=1 =1 for i = 1,...,m, rZ Z XZk P=, = 1,...,L k=1 Xk > 0' k > 0 where for 9=1,...,L, pt: = P(5E) and i is the conditional expectation (with respect to P) given that ~ S Of course to obtain this upper bound on fvo(E)P(dE) it is not necessary to -9 know P. It suffices to know the values of pZ and. In fact we do not even need the individual values of the i. It is only necessary to know for each i = 1,...,m, L -a ai: = 1 Pi ai~ i ZR~~=l~ ~11 11

More generally, suppose it is known that ~i vi () P(d) < a but the precise value of this integral (with respect to P) is not known. In this case the constraint (3.12) could be replaced by i < f ai'e X (de) + f ai'r (dr) < (3.14) 9-=1 ext C k ext-rc C 9 This is the case when the generalized moment problem involves inequalities and the vi are piecewise linear. This yields immediately an extension of Theorem 3.1 (to the inequality case) that turns out to be quite useful when dealing with higher order moments approximations. If it is known for example, that j 2 P(dE) < ai' (3.15) then by defining a piecewise affine (lower) approximation vi such that vi(S) < E2, the optimization problem (3.10) with the constraint (3.14) -- defining a: = 0 and a = c. - yields an upper bound on all probability measures satisfying the second moment condition (3.15). The bound can be improved by refining the approximation v,. For other than piecewise linear functions, limited results are still available. Suppose for example vi is concave and Jvi(E) P(dW) < (i. (3.16) We can substitute for its representation (3.5) to obtain z ( i( e X'(S,de) + r P'(, dr) P(dE) < ai 2=1\ 9 \Jext C ext-rc C Now if we use the concavity of vi and the definitions (3.6) of X and (3.7) of 1P, we have L e \ ( | Vi(e)r(de) + r vi(r)U(dr) ) i ~ (3.17) =1 \ ext C ext-rc C 12

Therefore we can replace the constraint (3.16) by (3.17) and again obtain an upper bound on the expectation of vo that satisfies (3.16). Obviously the same technique can also be used if vi is convex and we know a lower bound on the expectation of vi. 4. EXAMPLES. The results of Section 3 can be used to obtain bounds for a variety of lower dimensional cases. In this section we consider two piecewise affine approximations of the second moment function, vi(i) = E2. We take i to be a 1-dimensional random variable distributed on the interval [1, 821] with. < 0 < B2. Let P([( 1 0]) = P P(( = P2 and suppose P({0}) = 0. As upper approximate we define vi( ) = -Y 1, i 0 (4.1) l Y2 El i > 0 with Y1' Y2 > 0. If Y1 = Y2' then vi(S) = 11. In general we define Y1 and Y2 so as to best fit the case at hand, see Figure 1. 62 Figure 1. Upper "absolute value" approximate. With C = co(B1= e1,2=e2) the linear program (3.13) becomes: 13

find X > O, X 12, X21 > 0, 22 > 0 such that (4.2) YaiX1 -Yl + 2X12 21+ X21 + B222 =, X11 + X12 = Pl X21 + X22 = P2 2 2 and w = z Z h(zk)XAk is maximized. Z=l k=l We set 2 d - 2 -: = i(( ) P(d-) = -YI1 P(dE) + Y2 | P(dE) = -Y1P11 + Y2P2E2 1 1 where,1 and Z2 denote conditional expectation with respect to [31, 0] and (0, 32] respectively. Thus we can view (4.2) as finding a probability that assigns weights to the extreme points of [a,' 2], viz. (X11 + X21) to R1 and (X12 + A22) to 62 in such a way that a certain generalized conditional expectation condition is satisfied. There are four possible bases -- each one corresponding to having 1 variable XQ< nonbasic — depending on the values of the coefficients. The following table gives the solution values and optimality conditions when 1 = Y2 > 0, and for 2 of the 4 possible bases ( the other two have X21 and X22 nonbasic resp.): Nonbasic Variable Xll X12 Dual feasibility h(a,2) > h(l) h(2) >h(l) / 2 E 2 \ /a2 - E2 Primal feasibility P1 <P2 I MM. P1 < P2 $2 - ~1 l- C1 Solution: 12 P1 22 P2 X21 = P2 22 X12 = Pi - X11 22 = 1 [[P1(82-1) + P2(B2-i1)] A1 = 2 1 Table 1: Optimality Conditions: Y1 = Y2 > 0 14

The dual feasibility conditions are the same for all Y1 and Y2 positive. The primal feasibility conditions depend on the relative sizes of the slopes. We can also work with a lower approximate for i ~ —> 2, for example with the cup-shaped function: vi(i) = Y1(B1 - ) if 1 i 11 0 if 11 < i < 1'21 if < Y 2( - 21) if B21 < < B2 where B1 < <11 < 0 2 < 2 < 2. See Figure 2.. / approx. \ slpslope = Y2 slope = -v 1.. 811 0 ~21 2@ 2 Figure 2. Cup-shaped approximation for i. If vi is this cup-shaped function, the associated linear program (that yields an upper bound) reads: find X1 >O, 12 >.., 32 > 0 such that (4.3) -Y~11X11 -Y1212 + Y3B1X31 + Y382X32 = a 21 + X2 = PI' p =1,2,3 3 2 and w = Z. h(_k))Xk is maximized, ~=1 k=1 where: = - P1Y1 1 + P3Y3~3~ 15

There are 8 feasible bases, The solutions are of the same type as in Table 1. The solution of (4.6) is useful in conjunction with the solution of (4.2). As we noted earlier, if vi() < E2 then the solution of (3.13) yields an upper bound on fv0(E)P(d)). If, however, vi(i) > E, then the solution of (3.13) yields a lower bound on the supremum over all distributions satisfying the second moment condition. The two bounds can be used to determine how well the second moment condition has been approximated. 5. APPLICATIONS IN STOCHASTIC PROGRAMMING Bounds on the expectation of a convex function can be particularly useful in the solution of stochastic optimization problems. In these problems, it is often necessary to perform an optimization to evaluate a function at a single point. Taking the expectation of such functions presents a formidable task. By limiting the support of the distribution to a finite number of points, as in the development above, the set of problems to optimize is limited, and one can efficiently obtain bounds on the expectation. A typical stochastic optimization problem has the following form: inf c(x) + i Q(x,S) P(dE), (5.1) X~K J5 where Q(x,g) is itself the optimal value of a mathematical program whose coefficients depend on x and i. To solve (5.1), we need to evaluate fQ(x,E) P(dE) for many values of x chosen in an optimization procedure. An upper bound on the integral that is easily calculable may lead to useful bounds on the optimal value of (5.1). 16

As an example, consider Q(x,) = min 5y1 + 10Y2 + 10y3 (5.2) s.t. Y1 + Y2 = -1 - xl Y1 + Y3 = E2 - X2, Y' Y2' Y3 > 0. Note that this problem has the values 10E1 + 5x2 - 5E2 - 10x E - x l x 2 > Q(x,V) = 10E2 + 5x1 - 51 10x2 2 - x2 > x-1 - > 0 + 01 - x1 < 0 or E2 - X2 < 0. S1 Er2 -221 -~22 We wish to consider the case where x = (0,0) and P[S1<iS,2<] =J 2 4e e A ~~~~~A~0 0 di1 d2,, where!1 and d2 are any given nonnegative values of the random variables i1 and E2. In this way, E1 and E2 are independent exponential random variables with means 1/2. We wish to investigate how to find an upper bound on!Q((0,0),9) P(dE) (5.3) without computing the integral exactly. We first note that the exact value is 6.25. The other methods we will try will be Gassmann and Ziemba's approach, a solution using Corollary 3.2 and not exploiting the independence of the random variables, and a solution using Corollary 3.2 and the independence of the random variables. A lower bound on (5.3) is found using Jensen's Inequality as Q((0,0), 5) = 2.5. An upper bound is available using the Gassmann - Ziemba approach which reduces to (3.13) with aiR = en and L=n. Using the extreme directions of, = [0,0) x [0,oo) as (1,0) and (0,1), an extreme point of (0,0), and noting that rc Q((0,0), (1,0)) = re Q((0,0), (0,1)) = 10, the following version of 17

(3.13) is obtained, J Q((0,0), i) P(dS) < sup 10 p1 + 10 12 (5.4) J(X, p) s.t. 0x1 + P1 = 1/2 OX1 + 12 =1/2 X1 =1 X1' ^ 1' W2 > 0 The only feasible solution to (5.4) is p1 = 2 = 1/2, X1 = 1, and the upper bound so obtained is 10. By using the independence of the random variables, we can see that, for any value 2 of i2' Q((0,0),(1, i2)) defined on [0,+oo) has a value of 10o2 at (0,0) and a recession function value of 10 in the direction of increasing i1. A Gassmann-Ziemba bound on the integral over E1' is therefore, 10E2 + 5 for any E2. Using this value, we can then solve the problem in S2 and again obtain a value of 5 at (0,0) and a recession function of 10. The resulting upper bound is again 10, so the use of independence does not improve the bound. To provide a more precise bound on (5.3), we include more constraints in (3.13). Note that E(EI) = E(E22) = 1/2. A function vi (E1' 2) such that vi < i2 is 0 if i < 1/2 (5.5) 2Ei-1 if Ei > 1/2, a cup-shaped function as in Figure 2. This can be used with bounds of 1/2 for i=1,2 to obtain additional constraints to mean value constraints. The region of 5 must then be partitioned into _1,2 -3 and 4 as in Figure 3. In (3.13), 18

52 M_ 1 52 1/2 =3 =4 0 1/2 E1 Figure 3. Partitions of we use h = Q((O,O), i) and C = with constraints on v = e-2' =- 3,14, and vi as in (5.5). The resulting linear program has an optimal value of 8.98. We can improve on this solution value by using the independence of i1 and 2. We consider first j Q((O,O), (E1, 0)) P1(d1) where p1 is the marginal probability distribution of E1. Clearly, this has a value of 10 1 =5 since Q((0,0), (1', 0)) is linear. Next, consider Q((0,0), (~1, 1/2))pl(dS1). For this problem, we use vl(E) as in (5.5) and an upper bound of 1/2 and solve the resulting program (3.13) in E1 only. The result is an upper bound of 6.25. -- i = [09 1/21/, +oo We note here that using the partition = [, 1/2/2, o, ), without the constraint on vl(E) leads to an upper bound of 7.24. The restriction on the second moment therefore allows for a 14% improvement in the bound. The bound on JQ((0,0), (E1, 1/2))Pl(d51) can then be used to bound A (5.3). We use that 5 is a bound at E2 = 0, that 6.25 is a bound at E2 = 1/2 for fQ(O,0), (1' ~2)Pl(dE1) and that the recession function value of fQ((O,0), (S1,~2))p1(d)1) is 10. This yields another problem (3.13) that can be solved with a constraint on v2(l) to yield an overall upper bound of 8.12. 19

This represents a 10% improvement over the bound without using independence, and a 19% improvement over the bound which only considers mean values. The results are summarized in-Table 2. Constraints Independent Upper Bound Computation Means No 10.00 Means Yes 10.00 Means & Second Moments No 8.98 Means & Second Moments Yes 8.12 Table 2. Bounds on fQ((O,O), S)P(dS). This example provides one indication of the usefulness of including constraints on second moments in the solution of stochastic optimization problems. As a second example, we consider a region that is not bounded in any direction and a nonlinear function vO. Let Q(x, )!( - x)2 if - x | 5 (5.6) 10x - 25 if - x > 5 -10x - 25 if - x < 5, where i is normally distributed. We wish to bound jQ(O, )P(dE) where = 0 and E(E2) = 1/4. We use v1 = for the mean value constraint and 2 i- 1 if i > 1/2, (5.7) V2 (i) = 0 if -1/2 < i < 1/2, -2 - 1 if i < -1/2, where v2(E) < E2. The resulting linear program (3.13), with E1 = (-0, -1/2], 2= (-1/2, 1/2], 3 = (1/2, +co), and a bound of 1/4 on fv2(S)P(dE) has an optimal value of 1.5. Without the bound on Jv2(S)P(dS), however, the linear 20

program is unbounded because of the distribution's symmetry. In this case, it is essential to include additional piecewise linear constraints to the mean value constraint. 21

REFERENCES [1] J. Birge and R. Wets, Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse, Mathematical Programming Study, forthcoming. V / / /! / I J [2] J. Dupacova, Minimaxova uloha stochasticheko linearniho programovani a momentovy problem, Ekonomicko - matematicky Obzor, 13(1977), 279-306. [3] J. Dupacova, Minimax approach to stochastic linear programming and the moment problem. Recent results, ZAMM 58(1978), T466-467. [4] H. Gassmann and W. Ziemba, A tight upper bound for the expectation of a convex function of a multi-variate random variable, Mathematical Programming Study, forthcoming. [5] C. Huang, I. Vertinsky and W. Ziemba, Sharp bounds on the value of perfect information, Operations Research 26(1977), 315-325. [6] P. Kall and D. Stoyan, Solving stochastic programming problems with recourse including error bounds, Mathematische Operationsforschung und Statistik, Serie Optimization 13(1982), 431-447. [71 A. Karr, Extreme points of certain sets of probability measures, with applications, Mathematics of Operations Research, 8(1983), 74-85. [8] J. Kemperman, The general moment problem. A geometric approach, Annals of Mathematical Statistics 39(1968), 93-112. [9] M. Krein and A. Nudelman, The Markov Moment Problem and Extermal Problems, Translation Mathematical Monographs 50, American Mathematical Society, Providence, 1977. [10] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970. 22