L-SHAPED METHOD FOR TWO STAGE PROBLEMS OF STOCHASTIC CONVEX PROGRAMMING John R. Birge Hengyong Tang Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report 93-22 August 1993

L-shaped Method for Two Stage Problems of Stochastic Convex Programming John R. Birge Department of Industrial and Operations Engineering The University of Michigan Ann Arbor MI 48109 U.S.A. Hengyong Tang Mathematics Department Liaoning University Shenyang Liaoning 110036 P.R. China August 18, 1993 Abstract In this paper we extend directly L-shaped method of Van Slyke and Wets to solving two stage problems of stochastic convex programming. The implement of the algorithm is simple, so less computation work is needed. The algorithm has certain convergence. The result of computation shows that the algorithm is effective. Keywords: L-shaped method, Quadratic programming, Convex programming, Stochastic programming, Two stage problem with recourse. 1 Introduction Van Slyke and Wets [1] have proposed an algorithm for solving L-shaped linear programs which is applicable to linear optimal control problems and two stage problems of stochastic linear programming. J. Birge has extended the two stage L-shaped method of Van Slyke and Wets to solving multistage problems of stochastic linear programming [21. F. V. Louveaux has proposed an algorithm for solving piecewise convex programs which is used to solve two stage stochastic programs [3] [4]. The method of F. V. Louveaux is not direct extension of the method of Van Slyke and Wets, and is not applicable to linear stochastic programming, but has quadratic finite convergence. The algorithm of F. V. Louveaux is complex and has difficulty for solving general convex stochastic programming. 1

Two stage problems of stochastic convex programming are difficult for solving. For solving they are transformed into problems of linear programming by linearization. So the size of the problems is greatly increased. It is not feasible for the problems of large size. We have directly extended L-shaped method of Van Slyke and Wets to solving two stage problems of stochastic convex programs. The method is simple and has certain convergence. In section 2, we formulate mathematical model to be discussed. In section 3 and 4, we discuss the basis of the algorithm. The algorithm is given in section 5. The convergence of the algorithm is discussed in section 6. In section 7, the result of computation is given. In section 8, we do brief summary. 2 Problem formulation We consider following stochastic convex programming mn fi (x) s.t Alx = b Bx = ^(w) x> where x is n-dimensional decision vector, C(w) is mi-dimensional random vector defined on the discrete probability space (Q,.F, P), Al, b, B are matrices of size m x n, m x 1, ml x n respectively. fi(x) is convex function. Two stage problem with recourse of problem (1) is min hi (x) + Q(x) s.t Aix = b (2) x > 0 where Q(x) = EQ(x, w), Q(x,w) = min f2(y, w) s.t A2y = ~(w)-Bx (3) y > 0 y~o where yz is nI-dimensional variable vector, A2 is ml x nl matrix, f2(y, w) is convex function on y for each w E 0. To be conieniente ' K1 =({x Alx=b,x> O}, K2 = {xl for all w E Q, there exists y, such that A2y = C(w) - Bx, y O}. Then feasible set of problem (2) is X = K1 n K2. 2

3 Feasibility cuts The method of getting feasibility cuts is the same as one for stochastic linear programming [1]. Solve- linear programmng Z =m eTy+ +eTy y~>0,y +>O2yr~ 0 where e = 11.. )T, I is an unit matrix. Let a be optimal multiplier vector. If z = 0, X is a feasible point of problem (2), otherwise we get feasibility cut aTBx > oT~(w) (5) 4 Optimality cuts For given wi E 11, we K = {xI there exists y, such that A2y = ~(Wi) - Bx, y ~ O}. Proposition 1 For any Wi E 11 and on all x E K,,, Q(x, wi) is either a finite convex function in x or Q(x, wi) is identically -oo. proof. For all x E K~,, the following convex program is feasible Q(x, wi) =min f2(y, wi) sAt A2y = (wO)- BX (6) Its dual problem is max O(u, v, x, w1i) (7) sA t u>O where O(u, v, x, wi) = inf jf2 (y, wi) - uTe + VT (A2Y - ~(wi) + BX)y YE Rm' If Q(', wi) = -cx, for some X E K,1,,, then O(u, v,T, wi) = -o for each u >: 0 [5]. Thus for ali x EKw,, we have O(u, v, x, w) = -oo for each u ~ 0, and Q(x2 W,) = max{O(u, v, x, W)Iu > 0} = -co. It remains to show that if Q(x, wj) is finite on the convex set K~,,, then it is convex. 3

V X1, X2 E K,,,, xA\ = Ax1 + (1 - A)X2, A E [0, 1], let yl, y2 and y~,\ be optimal solution to (6) when x equals X1, X2 and xA\ respectively. Since Ayj ~ (1 - A)y2 is a feasible solution to (6) when x = Ax 1 + (1 - A) X2 Cbut not necessarily optimal, e -g in general y,\ # Ayj ~ (1 - A)Y2) and f2 (y, wi) is a convex function for fixed wi, we have Q(XA,\,W) = f2(YA,\,W) ~ f2(Ayl + (1 - A)Y2,WO) ~ Af2 (yi, wi) + (1 - A) f2 (Y2,WO) = AQ(xj,wj) ~(1 -A)Q(X2,wi). This completes the proof of the proposition. Proposition 2 Let %,, be an optimal solution of following problem Q (7, w) =min f2 (y, wi) s-t A2Y = ~(wi) -BY (8) -9 Ui) is corresponding optimal Lagrangian multipliers, then the linear function is a support of Q(x, C(wi)). proof. Trhe dual problem of the problem (8) is max O(u',v,,Wi) (9) s-t U >0 where O(u, v, 7, w,) = inf If2 (y, wi) - uTe ~ VT(A2Y - ~(wi) ~ BY) Ii yE Rm1 } (10) Since (UwiIUw) is optimal solution of (8), by the duality theory we have that f2 (-Y-~,,w) - e + < A2Fj - v<C(wO ) ~vBY =Q YW) For all x E K (,,,v, is a feasible solution of all problem (7), but is not necessarily an optimal solution. Thus again by duality theory we have Q(x,w,) = max{O(u,v,x,wj)Iu~0} -infff2(y,wi) - Ue ~V~A2Y -vU~(wi) +vjBxly ERm1} -f2 (ya) - <, je + < A2Viwj - v wj~( +V BX.(1 4

last equality is according to arg minyf2(y,w1) — Jge '~2-U,~(i+,B = Arg min71f2(y,wi) -'Ue+v3A2Y-v~~(wi) ~v~B-f. This completes the proof of the proposition. Proposition 1 and proposition 2 are the basis of getting optimality cuts (see following algorithmn). 5 Algorithm Algorithm 1 Step 1. Solve the problem mun fi (x)~O s-t Ajx = b (12.1) 4TBx > (7~ k=1,... Is (12.2) (12) -VT4Bx+ 9 ~ Pk k =1,-...t (12.3) Initially $ and t are zero. If no constraints of the form (12.3) are present, 0 is set equal to -co, is ignored in the computation. Let xi, 0i be an optimal solution of (12). Step 2. Solve the problems Z~j = m eT y+ + eT Yr s-t A2Y +IY+ - Iyr ~ (wj) -Bxj i = 1...,NiN (13) Y~Oly+>~O)YiF 0 If for some z,. > 0, C.= (Wr) and optimal multiplier a,. are used to generate a feasibility cut of the form (12.2) go to step 1, otherwise go to step 3. step 8. Solve the problems unf2 (Y1 w) s. t A2Y = (wi) -Bxg i =1,...N2 (14) y~0 Let yb,, be optimal solution, (u,, v,,,) be co~rresponding optimal Lagrangian multipliers, compute P(wM) = f2(Ywi,,wA) - U Te +vwjA~ywj- V~(Wi), N2 N2 =t Zpi puw), VI = >jPaw,. k_-I k=1 where pi is Probability of wi. 5

If Pt + vITBxj ~ 91, terminate. Otherwise use pi, Vi to generate a new optimality cut of the form (12.3) and odd it to problem (12), go to step 1. 6 Convergence of the algorithm Theorem 1 If for some (xi, 1e), such that Pi + VTBX1 = - V then xi is' an optimal solution to problem (2). proof. Problem (2) is equivalent to min fi(x)+O s.t Q(x) ~ 0 (15) Let K={(x,0)I Q(X)~,XEEK}, K={(x,0)I Aix=b,x~0 lkTBx > oTktk, k = 1,...,s -VkTB + pkk = 1,..., t}, then K C K. According to proposition 2 we have 01 T Xi_ Pt + VB Q(xi), thus (x8i) 01E K. Since, (xi, Oj) is an optimal solution to problem (12) and K c K, then (xi, 0i) is an optimal solution to problem (15) and xi is an optimal solution to problem (2). This completes the proof of the theorem. Theorem 2 9Suppse the agorithnm generates an infinite sequence of (xe, Oi) m e fn) is the imit point of an arbitrary subsequence (x4, 01),and lim Pi + viBx i -Gji. = 0 ita m ioo 2 then Z is an optimal solution to problem (2). 6

Proof. Since K is closed convex set [6] and Q(x) is a convex function, then K is a closed convex set too. thus X E K. According to algorithm and proposition 2 we have O4 < Q(X) = pTBxli. Since lim pl, + vT Bxi - 01, = 0, we have 0 = 0(r) Thus (x, 0) is a feasible point to problem (15). Let (x*, 0*) be an optimal solution to problem (15), then fi (xi) + 01i < fl(x*) + 0*. By convexity of fl(x), fi(x) is a continuous function [7], thus fi () + < fl(x*) + 0*. Hence (E, 9) is an optimal solution to problem (15), and X is an optimal solution to problem (2). This completes the proof of theorem. 7 Computational experience To see the feasibility and effect of the algorithm we have computed some sample problems of stochastic convex programming. We consider two stage problem with recourse of stochastic convex quadratic programming min lXTHiX + df + Q(x) s.t Aix = b (16) x >0 where Q(x) = EQ(x, w), Q(x, w) = mrin 2TH2y + da s.t A2y = ~(w)-Bx (17) y > 0 wher.e A AaB, b,4l, da are matrices of size m x n, ml x ni, mi x n, mx x 1, n x 1, n x 1 respectively. H1 is n x n positive semidefinite matrix, H2 is positive definite matrix. ((w) is mi-dimensional random vector defined on the discrete probability space (2, F, P), and has N scenarios. We have computed 3 sample problems which have different size using IBM RS/6000 workstation. We use OSL (Optimization Subroutine Library) to compute the subproblems of linear programming and convex quadratic programming. The code is implemented in Fortran 77 language. 7

n m ni ml N examplel 8 5 6 4 16 example2 36 35 28 23 32 example3 60 53 70 40 64 In all examples, problem (15) has equality constraints and inequality constraints. When pi + vTBxz -- 0 < 0.001, we terminate computing. Theoretically, pi + vTBxi - Q > 0 but sometimes it probably is a negative number which absolute value is very small due to computation error. The result of the computation is following: example NFE NOP NIE CPU ITI HST LST RVT 1 3 3 6 470 78.3 935 847 -0.609280 x 10-5 2 " 2 3 5 918 183.6 2582 1221 0.412843 x 10-6 3 0 10 10 6049 604.9 4737 1723 0.634673 x 10-3 Where NFE: Number of feasibility cuts. NOP: Number of optimality cuts. NIE: Number of iterations. CPU: Average CPU time (microseconds). ITI: Average time of each iteration (microseconds). HST: High storage. LST: Low storage. RVT: pi + vTBxi - Oi. We have together computed N problems (13) (linear programming) and N problems (14) (convex quadratic programming). So the work of the computation is decreased and the units of storage are saved. If A2, d2, H2 are random, computation can also implemented. The result of computation shows that the algorithm is effective for stochastic convex quadratic programming. 8 Summary This paper extends L-shaped method of Van Slyke and Wets to solving stochastic convex programming with recourse. Algorithm is a kind of decomposition method, so it possesses good character of decomposition method. The implement of the algorithm is simple and it has certain convergence. The result of the computing convex quadratic programming shows that algorithm is effective. A number of sample problems of general stochastic convex programming have to be computed to see 8

practical efficiency of the algorithm for general stochastic convex programming. Acknowledgment The author acknowledge the lot of help given by Mr. Dereck Holmes. He has also supplied sample problems in the paper. Mr. Samer Takriti has also given us help when we do computation. References [1] R. Van Slyke and R. J. Wets, "L-shaped linear program with application to optimal control and stochastic linear programming," SIAM Journal and Applied Mathematics 17, 638-663,1969. [2] John R. Birge, 'Decomposition and partitioning methods for multistage stochastic linear programs," Operations Research, 33, 989-1007, 1985. [3] Francois V. Louveaux, "Piecewise convex programs," Mathematical Programming, 15, 53-62, 1978. [4] Francois V. Louveaux, "A solution method for multistage stochastic programs with recourse with application to an energy investment problem," Operations Research, 28, 889-902, 1980. [5] M. S. Bazaraa and C. M. Shetty, Nonlinear Programming, Theory and Algorithm, John Wiley and Sons, New York, 1979. [6] P. Kall, Stochastic Linear Programming, Springer, Berlin, 1974. [7] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970. [8] Richard P. O'neill, "Nested decomposition of multistage convex programs," SIAM J. Control nad Optimization, Vol 14, No 3, 409-418, 1976. 9