 Multicut L-Shaped Algorithm for Stochastic ConvexProgramming withFuzzy Probability DistributionMiaomiao HanSchool of Mathematics and PhysicsNorth China Electric Power UniversityBaoding, Hebei Province, ChinaHanmiaomiao_1@163.comXinshun MASchool of Mathematics and PhysicsNorth China Electric Power UniversityBaoding, Hebei Province, Chinaxsma@ncepubd.edu.cnAbstract—Two-stage problem of stochastic convex programming with fuzzy probability distribution is studied in this paper. Multicut L-shaped algorithm is proposed to solve the problem based on the fuzzy cutting and the minimax rule.Theorem of the convergence for the algorithm is proved. Finally, a numerical example about two-stage convex recourse problem shows the essential character and the efficiency.Keywords-stochastic convex programming;fuzzy probability distribution; two-stage problem; multicut L-shaped algorithm1. IntroductionStochastic programming is an important class of mathematical programming with random parameters, and has been widely applied to various fields such as economic management and optimization control. Two-stage stochastic programming is a kind of mathematical programming where the decision variables and the decision process can be decomposed into two stages based on random parameters are observed before and after the specific value. Stochastic linear programming as a basic issue has been studied widely, and many research results have been reported.In , two-stage problem of stochastic linear programming and the basic algorithm were first proposed and applied to the linear optimal control problem. Since then, a large variety of algorithms including Bendersdecomposition, stochastic decomposition, subgradient decomposition, nested decomposition, and disjunctive decomposition for the two-stage stochastic linear programming had been developed. Among these methods, Benders decomposition also called the L-shaped method has become the main approach to deal with stochastic programming problems. The theories and algorithmsobtained before onstochastic linear programming all arebased on a hypothesis that the probability distributions of random parameters have completely information. However, in many situations, due to lack of the date, the probability of a random event is not fully known, and need to get an approximate range with the help of experts’ experience. Recently, model of thestochastic linear program with fuzzy probability distribution was proposed in , and the modified L-shaped algorithmwas presented to solve the model. Stochastic convex programming is an important class of stochastic nonlinear program and has more widely application than stochastic linear programming.As a result, stochastic convex programming with fuzzy probability distribution will havemore useful in many practical situations. In this paper, two-stage stochastic convex programming with fuzzy probability distribution and the solving method are studied, a numerical example shows the essential character and the efficiency.2. Two-stage stochastic convex programming under fuzzy probability distribution Let ,,P:¦be a probability space, sample space ^`1,,NZZ: "is a finite set, and ¦=2:is the V-algebra composed by power set of:,^`.iipPZZ The two-stage stochastic convex programming problem is1 ()(,) . . 0Niiiminfxp Qxst Ax bxZ  t¦ (1) whereˈ (,) (,) . . ()() 0iiiiQx mingyst WyhTxyZZZZ t (2) 1nxand2nyare decision vectors, ()fxis convex function, Ais 11mnumatrix, 1mbis known vector, Wis 22mnurecourse matrix, for each iZ:,(, )igyZis convex function ony,2()mihZis vector, and iTZis Open Journal of Applied Sciences Supplement：2012 world Congress on Engineering and TechnologyCopyright © 2012 SciRes.219 21mnumatrix. Where xandyare the first stage decision variable and the second stage decision variable respectively. The mathematical expected value 1[(,)](,)NiiiEQx pQxZZ ¦. When the random variable obeys fuzzy probability distribution, the scope of ipis as follows ^`1|11 , 1;0,1,,NiiiiiiiNiiiPd lpd lppi NDSDD dd t ¦"(3) where 12,,,TNNPpp p "consisted of probabilities, 1,,TNll l "denotes the vagueness level, and the level value(0 1)iDDddexpresses the DM credibility degree of the partial information on probability distribution. Thefuzzy probability distributions results in that mathematical expectation [(,)]EQxZis uncertain, here, [(,)]pPmax EQxDSZ=1(,)NiiPimaxp QxDSZ ¦will be used to instead of[(,)]EQxZ, and then (1) can be expressed as follows1 ()(,) . . 0NiiPiminfxmaxpQxst Ax bxDSZ  t¦ (4)where (, )iQxZis confirmed by(2).Obviously, for a givenx, there exists12(, ,,)TNPpp p "DS, such that11(, )(, )NNii iiPiipQ xmaxpQ xDSZZ ¦¦. I. MULTICUT L-SHAPED ALGORITHMThe problem(4) is equivalent to:112 (), .. (,),,xNiiPimin f xs tmaxp QxxK KKDSTZT d ¦ (5) where(, ) (,), . . ()(), 0,iiiiyii iiQx min gyst WyhTxyZZZZ t (6) and `^1,0,KxAxbx t`^2 , 0,.. ()().ii iiiKxforallys tWyhTxZZZ :t The standard L-shaped algorithm for solving above problem can be designed under outer linearization (see e.g.). Suppose that 12(, ,,)TNPpp p "is solution of 1(,)NiiPimaxp QxDSZ ¦, problem (5) can be replaced by the following (7)112(, ) () .. ,iNiixiiQxmin f xps tforallixK KKZTT d ¦ (7)because of each constrain in (5) corresponds to Nconstraints in (7).The multicut L-shaped algorithm is defined as follows:S0. Set0,sk 0it for all1, 2,,iN ", and 0xis given. S1. Set 1kk , solve the following master problem: 1() () ()(a1).. ,0,(a2),1,2,,, (a3),()1,2,,, (a4)1, 2,,Niiilllii liimin fxpstAxb xDx dlsExe litiNTT °° t°®t °°t ° ¯¦""" (8) Let 1,,,kk kNxTT"be an optimal solution of problem(8). Note that if no constraint (a4)is presentfor somei,kiTis set equal tof,kiTand iparenot considered in the calculation ofkx. Go to S2.S2. For 1, ,iN ", solve the following linear programming problems . . ()() (a5) 0,0,0TTikiimin zeueus tWyIuIuhTxyu uZZ ° ®°ttt¯ (9) where1, ,1Te ", until, for some i, if the optimal value 0iz!, let kVbe optimal dual variables value, and define 11()()()()kTsikTsiDTdhVZVZ °® °¯, set1ss , add the constraint 11kssDx dtto the set(a3)and return to S1. If for all,0iiz , then go to S3.S3.For1, ,iN ", anda fixedkx, solve the following convex programming problems (,) . . ()() (a6 0 (a7) iikii iimin g yst WyhTxyZZZ° ®°t¯ (10) 220 Copyright © 2012 SciRes. Let(,)ikQxZbe the optimal value, andkiythe optimal solution. Solve the problem1(,)NiPikkimaxp Q xDSZ ¦, and suppose 12(,,,)kk kTNpp p"is the optimal solution, thenupdate the objectivefunction of the master problem. Letkivand kiube the optimal dual variables associatedwithconstrain(a6)and (a7)respectively. Compute 11() (),(,)()() [()()].iikTtiikT kkTktiiiiiiiEvTegy uyvWyhZZZ °® °¯If11iikkit teExTdoes not hold for any1, ,iN ",stop, then1(, ,,)kk kNxTT"is an optimal solution. Otherwise, set1iitt , add the constraint 11iikkit teExTtto the set(a4), return to S1. 3. Theorem of convergence for the algorithm Proposition1. In the algorithm, constraint set(a3) is finite.Proof The proof of this proposition is the same to the standard L-shaped algorithm (see e.g. ).Proposition 2. For any iZ:and on allixKZ,(,)iQxZis either a finite convex function or is identicallyf,where^`, 0,.. ()()iii iiiKxystWyh TxZZZZ :t . Proof (see e.g. ) Proposition3. If (, )iQxZis a finite convex functionfor eachiZ:, then the function11iitteExislinear supporting hyper planes of(, )iQxZ. Proof By the duality theory (see e.g. ), it holdsthat(,( , )()()[( )()()])kTT kii iikkkkkiiiiiQxgyuy vWy hT xZZ ZZ . We know from the convexity of (, )iQxZthat(, )(, )( )()[()()] ()().TTii iTikkkkkiiiiikiQxgyuy vWy hvT xZZ ZZt Thus (,)()()[()()]TTiikkkkkiiiiigyuy vWy hZZ () ()TikivT xZ11iitteEx is a linear support of (, )iQxZ. Theorem. Suppose that the algorithm generates an infinite sequence of1(, ,,)kk kNxTT". If 1(, ,,)NxTT"is the limit point of an arbitrary subsequence1(, ,, )jj jkk kNxTT", and for each,i11lim() 0jjiikktt ijeExTof ,1,, ,iN "then 1(, ,,)NxTT"is an optimal solution of problem(7),xis an optimal solution of problem(4). Proof Since the number of the constraints of type(a3)is finite, we have that jkxKfor jksufficiently large. We also knowKis closed convex set, thenxK.By known, for each,i11(,)jj jiikk kiittQxeExTZt , and11lim() 0jjiikktt ijeExTof Then (, )iiQxTZ for all1, ,iN ". Thus, 1(, ,,)NxTT"is a feasible solution of problem(7). On the other hand, if xis optimal solution to the minimax problem(4), but not necessarily an optimal solution in iterationjk, then *11() (,)() (,).jjNNkkii iiPPiifxmaxp Qxfxmaxp QxDDSSZZ d¦¦By continuity of the convex function we have that *11()(, )()(, )NNiii iPPiifxmaxp Qxfxmaxp QxDDSSZZ d¦¦, then, for a certain value 12(, ,,)TNpp pDS"*11()( )( ,),NNiiiiPiifxpfxmax pQxDSTZ d¦¦Hence,1(, ,,)NxTT"is an optimal solution to problem(7),and xis an optimal solution to problem(4).4. Numerical exampleConsider the following two-stage stochastic convexprogramming 12221212 1212 11122 2112 21212 3 3.552 22. . 25, , 3, 2, ,,, , 0.,xmin xxyyEminyyyystx xyxxxyxxyyyy[[[°½°°®¾°°¿¯°°®t d°d d°°d¯td°° (11) where 1[takes the three values 3.5, 3.8 and 4.0 with probability 1/3, that2[takes the values 0.5, 1.0and 1.5 with probability 1/3, and that 1[and 2[are independent of each other, then 12(,)T[[[ can take the each vector in the set12{(,)|Tkk3 123.5,3.8,4.0,0.5,1.0,1.5}kk with probability 1/9. Under fuzzy probabilitydistribution, assume that [takes the each values in 3with probability around 1/9, i.e. ip#1/9 (1,2,,9)i "ˈit can be confirmed by(3),where1/12id , Copyright © 2012 SciRes.221 1/12il , 1/2iD (1,2,,9)i "ˈthen we get two-stage stochastic convex programming with fuzzy probabilitydistribution. We solve problem (11) by the proposed algorithm and take the initial value01,1Tx .Iterations procedure and outputs are as follows.TABLE I. ITERATIONS PROCEDURE AND OUTPUTS OF MULTICUT L-SHAPED ALGORITHMk.obj valkxP1-20.167(3.000,0.000)(0.153,0.111,0.069,0.153,0.111,0.069,0.153,0.111,0.069)2-15.947 (2.356,0.644)(0.111,0.111,0.111,0.111,0.111,0. 111,0.111 ,0. 11 1,0.111)3-14.454(2.566,0.434) (0.153,0.111,0.069,0.153,0.111,0.069,0.153,0.111,0.069)4-14.020(2.501,0.499) (0.153,0.090,0.090,0.153,0.090,0.090,0.153,0.090,0.090) 5-14.007(2.499,0.501) (0.153,0.090,0.090,0.153,0.090,0.090,0.153,0.090,0.090) 6-14.005(2.500,0.500) (0.153,0.111,0.069,0.153,0.111,0.069,0.153,0.111,0.069)7-14.005(2.500,0.500) (0.153,0.090,0.090,0.153,0.090,0.090,0.153,0.090,0.090) 8-14.005(2.500,0.500) (0.153,0.111,0.069,0.153,0.111,0.069,0.153,0.111,0.069)t(8,8,7,7,8,5,6,8,5)Where obj.val refers to the objective value,19(,, )tt t "is the vector on the number of iterations of each scenario. 5. ConclusionTwo-stage stochastic convex programming with fuzzy probability distribution is proposed in this paper. The multicut L-shaped algorithm for solving the problem ispresented, and the theorem of convergence is given. Finally, a numerical test example demonstrates the essential character and the efficiency of the algorithm.6. AcknowledgmentThis work is supported partially by the Natural Science Foundation of Hebei Province under Grand A2012502061. REFERENCESJ. R. Birge and F. Louveaux, Introduction to Stochastic Programming, M. Berlin: Springer, 1997. R. M. Van Slyke and R. J. Wets, “L-shaped linear programs with applications to optimal control and stochastic programming,” J. Applied. Vol. 17(4), pp.638–663, Math1969. J. F. Benders, “Partitioning procedures for solving mixed-variable programming problems,” J. NumericalMathematics, Vol. 4. 1962, pp.238-252. J. M. Higle and S. Sen, “Stochastic decomposition-an algorithm for 2-stage linear programs with recourse,” J. Mathematics of Operations Research, Vol. 16, 1991, pp. 650-669. S. Sen, “Subgradient decomposition and differentiability of the recourse function of a 2-stage stochastic linear program,” J. Operations Research Letters, Vol. 13, 1993, pp.143-148. S. Sen, Z. Zhou and K. Huang, “Enhancements of two-stage stochastic decomposition,” J. Computers & Operations Research, Vol. 36, 2009, pp. 2434-2439. T. W. Archibald, C. S. Buchanan,K. I. M. Mckinnon and L. C. Thomas, “Nested Benders decomposition and dynamic programming for reservoir optimization,” J. Operational Research Society, Vol. 50,1999, pp.468-479. L. Ntaimo, “Disjunctive decomposition for two-stage stochastic mixed-binary programs with random recourse,” J. Operations Research, Vol. 58,2010, pp. 229-243. F. B. Abdelaziz and H. Masri, “Stochastic programming with fuzzy linear partial information on probability distribution,” J. European Journal of Operational Research, Vol. 162, 2005, pp. 619-629. H.Y. Tang and Y.F. Zhao, “L-shaped algorithm for two stage problems of stochastic convex programming,” J. Applied. Math. & Computing Vol. B, 13(1-2), 2003,pp. 261-275. S. Boyd and L. Vandenberghe, “Convex optimization,” J. Published in the United States of America by Cambridge University Press, New York, Vol. 6, 2004, pp.68-86. 222 Copyright © 2012 SciRes.