 American Journal of Computational Mathematics, 2011, 1, 294-302 doi:10.4236/ajcm.2011.14036 Published Online December 2011 (http://www.SciRP.org/journal/ajcm) Copyright © 2011 SciRes. AJCM First Order Convergence Analysis for Sparse Grid Method in Stochastic Two-Stage Linear Optimization Problem Shengyuan Chen Department of Mathematics and Statistics, York University, Toronto, Canada E-mail: chensy@mathsta t.yorku.ca Received August 27, 2011; revised September 20, 2011; accepted Septem b e r 30, 2011 Abstract Stochastic two-stage linear optimization is an important and widely used optimization model. Efficiency of numerical integration of the second stage value function is critical. However, the second stage value function is piecewise linear convex, which imposes challenges for applying the modern efficient spare grid method. In this paper, we prove the first order convergence rate of the sparse grid method for this important stochastic optimization model, utilizing convexity analysis and measure theory. The result is two-folded: it establishes a theoretical foundation for applying the sparse grid method in stochastic programming, and extends the convergence theory of sparse grid integration method to piecewise linear and convex functions. Keywords: Convergence Analysis, Stochastic Optimization, Scenario Generation, Convex Analysis, Measure Theory 1. Introduction Stochastic two-stage linear optimization, also called sto- chastic two-stage linear programming, models a sequen- tial decision structure, where the first stage decisions are made now before the random variable manifests itself; and the second stage decisions are made adaptively to the realized random variable and the first stage decisions. The adaptive decision model has been applied many im- portant application areas. For example, in the introduc- tory farmer’s problem [1], a farmer needs to divide the land for different vegetables in spring. The farmer’s ob- jective is to maximize profit in the harvest season. The profit is related to the market price at that time and the weather dependent yield. Neither the price nor the weather is known at the present time, hence the farmer’s decision in spring has to take into account multiple sce- narios. It is not a simple forecasting problem though, since the farmer’s second stage decision in fall, which adapts to different scenarios, also jointly determines the profit. The second stage decision problem is also called “recourse” problem. [2] collects more recent applications in engineering, manufacture, finance, transportation, tele- communication et al. A stochastic two-stage linear problem with recourse has the following general representation: ,d,and min ,=min ..=,0, T xX T cxx P xsy st QyTxy (1) where is a random vector properly defined on P,,, is a polytope feasible region for the first stage, mn Q , s and are a vector and a matrix of proper sizes, T :, ,X is a real valued function. The high dimensional in tegration in (1) is difficult and is usually approximated by using a set of scenarios and weights ,,1,, kk wk K K as: 1 min, ,and ,min .., 0. Tk k xX k kT k cxw x xdy st QyTxy (2) Under this scenario approximation, the optimal objec- tive value * z of (2) provides an approximation of the optimal objective value of (1). An optimal solution * z * of (2) prov id es an appr ox imation o f an op t imal so lu - tion * of (1). Monte Carlo (MC) method has been widely used in this approximation, where are random ,=1, , kk K  S. Y. CHEN295 sampling points and =1 k wK. The convergence theory of Monte Carlo method has been extensively studied [3-6]. The core result is the epi-convergent theorem: un- der mild assumptions, * z converges to w.p.1 as ; and any clustering po int of the =1 , which is the sequence of optimal solutions to (2), is in the op- timal solution set of the original problem. Quasi Monte- Carlo (QMC) method has also been recently studied [7], and similar convergence result has been achieved. * z * {} KK x K The sparse grid (SP) method is an established high dimensional quadrature rule, which was originally pro- posed by Smolyak [8], and has been studied by many authors in the context of numerical integration [9] (and references therein). Its application in the stochastic two- stage linear optimization is only shown in a recent nu- merical study in [10]. Though [10] shows the superior numerical performance of sparse grid method, compared with both MC and QMC, the convergence analysis is based on an assumption that the recourse function is in a Sobolev space, which only holds for a very narrow sub- set of the two-stage linear problems, i.e., separable prob- lems. The contribution of this paper are 1) establishing the epi-convergence of the sparse grid method for this important decision model; 2) prove the first order con- vergence rate of the method. We first introduce the spare grid approximation error for integrand functions in Sobolev spaces. Let D denote the partial derivative operator = jj f Df xx x Let 1 =,,, dj be a multi-index, and define =1 =1 == dj jd, jj j DD x where 1d . The Sobolev space with smooth- ness parameter is defined as 1r 2 :0,1for all , d r d Df r where r means component-wisely , jr 1, ,j d. Sobolev spaces could also be defin ed using norms, see Evans [11]. The derivatives in the defini- tion of Sobolev space are weak derivatives. Formally, Df is the -derivative of f if for all , 00,1 d vC i.e., infinitely differentiable function on , 0,1 dDf satisfies the following equation: 0,1 [0,1] d 1d d d Dfxvxx . xDvxx For example, = xx defined in 0,1 has the first order weak derivative function Df xsign; but the function is nondifferentiable at 0 in the usual strong sense. It has been shown that weak derivative is essen- tially unique, and coincides with the classical strong de- rivative when it exists. Various properties of strong de- rivatives carry over to weak derivative as well, for ex- ample, DfDDfD Df for all multi- index ,, r . For more calculus rules regard- ing weak derivative, including the extended Leibniz theorem, see Evans ([11], Section 5.2.3). The norm of the defined Sobolev space is 22 , r dr fDf where 2 is the 2-norm of a function, L r component- wisely, 2 is the Euclidian 2-norm of a finite vector: 1/2 2 [0,1] 2d d ffx x 1/2 2 21. k j j hh For , the sparse grid method achieves the fol- lowing convergence rate [12]: r d f 0,1 =1 11 , d log , Kkk dk dr r rd rd fwf Kf K (3) where is the number of function evaluations, ,rd is a constant independent of , increasing with both d and , see Brass [13]. Note that implies rr d f , i d ir . Since the norm r d f and ,dr are non- decreasing in r, and the term 11 ln dr r KK is non-increasing in for large , it is none trivial to tell which space will yield the tightest bound. The prob- lem is called fat rK problem in Wonzniakowski [14]. In this paper, as we shall see, only is relevant for our discussion. =1r The convergence result in (3) only holds for the two- stage stochastic linear programming (1) in the trivial case, i.e., when the integrand function is separable. For example, ,:x 11 1212 1122 , ,,, =min yy xyyy y Copyright © 2011 SciRes. AJCM  S. Y. CHEN 296 1111 = yx 222 =2 yx 1122 ,,, 0yyyy is equivalent to 12121 122 ,,, , xx x where 1 11 1 x , 1 22 1 x and the conver- gence result in (3) can be applied directly. However, in general, , is non-separable piece- wise function, see Birge and Louveaux [1], and does not belong to for any . For example, r d r 1212 , ,,, = min yy xy y 2 121 = yx x ,0yy is equivalent to 121212 1 2 ,,,=, xx x and does not have the (weak) derivative 1,1 12 ,,, xx discon and non-differentiable even in the we 1,11,0 0,1 =DfDDf if nd in (3) can not be applied to two-stage linear problem directly. The major contribution of this paper is to prove the convergence of (2) to (1) in the rate specified in (3) with =1r, i.e., the first order convere rate, even though 1 ,d x . On the other hand, extends the co nvergence theory of sparse grid method to convex multivariate piecewise linear functions since for such a function :: i since istinuous ak sense, while Hence the erro genc this analys (0,1) Df exists. 1,1 Df r bou is dx for i B polyh and 1,, m B partitions presented a =mfx ; each B , could be i isedron res1 B in ,= 1,, . y i y ydxi m The paper is organized as the followings. In Section 2, we introduce a logarithmic mollifier function and prove its various properties. The mollifier function is quite fa- miliar to the optimization community as it is the barrier function used in the Interior Point Method for linear pro- gramming. In Section 3, we use the limiting properties of the mollifier function to prove the uniform convergence and the first order convergence rate for the objective function. We also show the converging behaviour of the optimal solutions * in a subsequence. Finally, Section 4 presents our concions. In the coming sections, we a lus ssume . For a m =0,1 d ith a inveore general continuous distribution wrse cu- mulative function 1:0,1 d F, one can apply trans- formation 0,1 d= d fF f 1dF. The transforma re complexity in the an 2. Mollifier Function We make the followitions of the problem : tion brings in mo ng mild assump alysis without changing our conclusion, hence we as- sume 0,1 d in the following sections and extend the anugh inverse transformation and trunca- tion in the Appendix. alysis thro (1): A1 is compty relative interior; pact with nonem ,,<xX x , , or relative; A2: completeness, and , has nonempty rela- tive interior; A3: =rank Qm ; A4: is a contius random vnuoector with an in- ve cuysis using the In rtiblemulative distribution function. Assumption A1 is necessary for our anal terior Point Method theory. Assumption A2 is for convenience since otherwise we need to discuss the case ,=x , which will drag our analysis to a different ption A3 is implicitly assumed in many analysis of linear programming, since the rows of Q could be preprocessed such that the reduced Q has fu row rank. Assumption A4 facilitates the conversion from a unit cube focus. Assum ll 0,1 d to through the inverse c.d.f. trans- formation. We define a mollifier function ,: : min T , .. = x , y By Tx st Qy =1 =log n i iy . In the (4) where following, we call By , ion, and ,x the recourse funct the molli- fier function. We let 1 11 ,, T n gy Byyy 222 1 11 diag,,. n Hy Byyy (5) is in fact a barrier function widely used in the ()By Interior Point Method for linear programming, and its proper ties ar e well studied. As 0 , the converge n c e of ,x and ** ,, , x yu iin the following theo Theore s stated rem. m 2.1. For any 1 let ,0,xX , ** ,, , x yu e mollifierbe the optimal primal andof th dual solutions 1We thank John Birge for pointing out this elegant argument. Copyright © 2011 SciRes. AJCM  S. Y. CHEN297 function, then , 0=, lim x ** ** ,, 0,, lim xxx uyu , where ** , x yu unctio is an optimal primal and dual pair of the recourse fn , . Proof. Due to thr functioe barrien , the objective fu ()B nction of ,x is strictly convTogether with the relative ceness assumption, it is clear that ,x ex. omplet has an unique optimal solution. Since the pro- non-empty relative interior by assumption, the central path ** yu blem has ,, , xx exists for each , and con- verges to ther of the optimal set, see e analytical cent property of Roos et al. [15] Theorem I.30 and its Definition I.20 for analytic center. The converg ing ** ,, , x yu tant topic in (central path) as ap- pe where . Clearly 0 has been an impor Interior Point Med has been extensive studied by many authors. For interested readers, in addition to the reference given in the proof, we refer the extensive research in Megiddo [16], an early work Fiacco [17], and a survey of degen- eracy and IPM by Güler et al. [18]. For readers interested in the interior point method in general, we refer Nesterov and Nemirovskii [19], Renegar [20] and Wright [21]. The KKT condition of the optimization problem thod, an ared in (4) is ,,, 0, T x sgQu Fyu Qy Tx (1) ,:nm m x F ,,, x F is infinitely dore, ifferentiable. Furtherm *T , , ,0 x x yu yQ FQ , 0, x F (6) where is an identity matrix, , , yu is invertible since () is positive definite. the implicit functioeorem, ** ,, ,Hence by n th x yu are infinitely differentiable functions of . So ** ,,, =T xx sy By is infinitely differtiable. Proposition 2. 1. For a en ny 1, ,0,xX ,(): x .C In the following, we directly derive te (strong) partial de h rivatives of ,x D for all 1 . Note that there are 21 d number of s satisfy1ing . We also prov partial derivatives are finite for all e these 0,1 , X. Finally, we show that their limits are fi nite when 0 <. Hereinafter, a vector <v or a matrix Prop means the inequality holds cnent-wisely. osition 2.2. For all ,0,1xX , ompo * ,,xx u =<. =< xx uFurthe 0, lim * rmore, grangian functi o. ization Proof. The Laptimon of the problem in (4) is ,,Lyu . T syByu uTx TT uQy ,x Since T ** ,,, , ,,= xxxx Lyu , ** ,, ,,,, ** *, *** ,,, *, *, *, =, = = =, xx xx x ,, ** , ,, , xx xx xx T u Lu Qu xx x x x x Ly LLy yu y usgy u Qy Tx u e last equality follows the KKT condition. where th Clearly *,< x u . As 0 , ** , x uu by Theo- rem 2.1. We let ** ,, diag,diag . xxx yy x at the Recall th* 1, refers to the limiting poin t defined in the Theorem 2.not an arbitrary optimal solution of , . Lemma 2.1. Fo y r an ,0,xX 1 , * 1 2 ,, =, T xx uQQ *2 2 ,,, =. TT xxx yQQQ 1 Proof. ,, ,, = xx Fyu ** 0defines implicit functions ** ,, , x , yu . With ,, , x yu F given in (6), 1 , , yu xplicitly cocan be ed as mpute 11 11111 1 11 1 , TT TT TT I Q QHQQHHQQHQ QH QQHQH Q 1 H where is a shorthand notation of *, Hy . Hence by the ilicit function theorem * mp ,1 (,) ,, *, =, x ux x x y F u and the conclusion follows straightforward computation Copyright © 2011 SciRes. AJCM  S. Y. CHEN 298 tion 2.3. For all 1 . Furthermo essentia a 2.1, (7) Hence and (5). Proposi ,0,xX , 1 22T re, ,,xx QQ 2 0,0 lim x Proof. By Propositiolly. n 2.2 and Lemm ,,xx QQ 1 22T 2,<,, . x X By Theorem 2. If the optimal set of 1, 1 22 , 0=0 . lim T xx QQ , ce the a is non-degenerate, 2T xQ is non-singular , henbove limit is zero. If al set is degenerate, then the limit 0 Q the optim is not defined. However, in the following, we shat the degenerated case has zero Lebesgue measure, hence the limit is zero with probability one. Let’s first consider a special case of degeneration. Let the first m columns of Q be an optimal basis B and 12 1 ,,,0, mm n yyyyy be e the set *1 = |=,=0,,,>0EyBTxyyy ow th degene 0 optimal b asic feasible solu rated . Since set 0 has zero a tion. Defin 12 0 Bm m 12 =|=0,,,> m Yyyy y easure in m , and B is both for an arbitrarily d n. Lebes- gue minjective and sur- jective, hence 0mE mBY. Clearly the same argument holdsegenerated optimal basis B with an arbitrarily chosen degenerated basic columFurthermore, there are only finitely many ways to choose basis and degenerated columns. Hence the total measure of the set which leads to a degenerated , is zero. Hence we conclude that the limit is ntially. We continue tca zero esseo lculate higher order partial deriva- tives. Note that 2,x is a mm matrix, and 3 ,2, =. xx ijk kij In general, for any and any set of , kd1,, k ii 2, 3 x ii k s a m im matrix, and ,2, 12 3, 12 =. kxx ii iii kk ii Proposition 2.4. For any ,0,xX , 1 and any set of indices 1,, k ii, , 1 <, k , 01 =0 lim k x ii k essentially. Proof. We first prove the conclusion fr, and extend by induct i on. o =2k 1 22 ,, ()= T xx kk QQ 11 22 2 ,,, * 1, , * 2, , 1 2 , *,, 1 2 , = 00 00 =2 00 0 , TT T xxx k x k x T xk nx k TT x QQ Q QQQ y y QQ Q y QQ Q (8) where *1 ,, *22 ,,, == jx TT xxx jk k k yyQQQ is shown in lemma 2.1. Clearly (8) is finite for >0 . Now taking limit 0 , by Theorem 2.1 and tion 2.3: Proposi- 2, 0= 0essentially. lim x k Furthermore, we prove by induction t hat 2, x ii k 3 ii k x is in the form ,, 2,, x SQ , ere S is an algebraic expression invowhlving multi- plicatiummation claim on and s is true for of 1 2 ,, ,T xx QQ , Q. The 2,x k it is in (8). Suppose true for 2, 31 x ii k , then by the chain rule, the term 2 ,T x QQ 1 panded into multiplica- tion of th ,x Q , Q, hence the will be ex e same terms form 1 2 , ,T x Q ,, 2,, x SQ is established. It is clear that 020 essentially lim by the Theo- ,, , , xx SQ rem 2.1 and Propositionivigher order 2.3. We also dere h partial derivatives explicitly in the Appendix A. Theorem 2.2. For any 1, ,0,xX Copyright © 2011 SciRes. AJCM  S. Y. CHEN299 1 , 21 2 2 ()< ; xn ** 1 ,1 ,, 22 0() ,< . lim xx mx nuu Furthermore, 1 22 2 ** 1, , 22 ,. sup xmx xX uu Proof. follows the definition of the norm 1 n e finite- , Propositions 2.2, 2.3, 2.4, and Theorem 2.1. Th ness of *, x u, =1j, , mption of the . Furthermo m, follows the relative com- pleteness two-stage linear problem and duality thre, assu eory is compt, hence o (1 gence e. ac <. 3. First Order Convergence Rate We first discuss the convergence of the objective func- tion specified in the approximatin model (2) to the ob- jective function of the true model), and the conver- rat Theorem 3.1. For all X, 21 1, 0,1 =1 ,, . kk dd k xd wxK Hence, K log d KK . Proof. For notation convenience, define operators and , K kk w x 0,1 =1 , d k xd uniformly E as 0,1 d, d Ef f =Kkk K Af wf =1k . Th for any ,0,1,xX K , en , ,, , ,, , , K x xKx KxK ExAx Ex E EA AAx Taking limiting on both sides, then the first and third term on tnd side go to zero by Theo- rem 2.1, and the sec is bounded by the classical convergence rategrid method, see (3), Proposi- tion 2.3 and Theorem Let the objective function of the true problem (1) and the approximated problem (2) be 0 he right ha ond term of sparse 2.2. 0,1 =1 =,d, =,, d K Tk k Kk zx cxP zx cxwx Tx an d let the optimal objective value and optimal solution set of the true model and approximated model be *** * ,,, K 3.3 state the resu zXz X respectively. Theorem 3.2 and Theorem lts for the optimal objective value and the optimal sets separately. Theorem 3.2. The optimal objective value converges, i.e., and the rate of convergence is ** limKK zz , 21 ** 1, log . d Kd K zz Proof. For the minimization problem we note that * zx zx for any ** , XxX , and KK K x zx for any *, KK z XxX . Let 2 1, log = d Kd K1 , then ** = KKKKK K z KK K zxz xzxzxzxzx xz x *** * , * * = KKKK K zx zxzx zxx zx x K where the inequalities follow Theorem 3.1. Theorem 3.3. For any K z zx z *** , KK Xx X , 1) is feasible; 2) 21 *1, log 2 d Kd K zx zx ; *of a subsequence 3) For any clust eri ng p oi nt * ,, KK ttt txX , ** X ; furthermore, ** =if x is a singleton, then * =* x . Proof. satisfies the first stage constraints and by the relativmpleteness assumption,e co is feasible. Toow t shhat is also very close to amal solu- tiom 3.1. ny opti n, we apply the similar technique used in Theore ** K KK KK zxz xz xzx 2, 2 , KK since = K zx zx KKK K zxz x by Theorem 3.1, and * KK zx zx by the steps in the proof of Theo * is a clustering point, rem 3.3. Since ** * 0 limtKt zx zxzxzx by the ine- quality above. As a special case, if * = x, then ** = x . tThe.3 is a classical result hird result of Theorem 3 Copyright © 2011 SciRes. AJCM  S. Y. CHEN Copyright © 2011 SciRes. AJCM 300 based the uniform conve bsequal sets are eto, and onxpect op- timality of clustering points. The result h [23,24 onverg cnvergenc K he sparse grid method for the stoch- mming not only converges but order rate. Our constructive proof Mathematics, Philadelphia, 2005. R. J.-B Wets, “Epi-Convergency of Con- Programs,” Stochastic and Stochastic Re- ports, Vol. 34, 1991, pp. 83-92. chastic Pro- rgence, see Römisch [22]. The result is stated in suence since the optim not necessarily singlnse can only e can also be proved by epi-convergence, see Attouc]. Epi- cene is implied by uniform coe, see all [25]. 4. Conclusions The modern sparse grid method is very efficient in nu- merical integration for integrant functions the Sobolev space r d . However, the integrand function in two- stage linear programming does not belong to r. We prove that d astic twot stage linear progra converges in the first also uses a logarithmic mollifier function from interior point method. 5. References [1] J. R. Birge and F. Louveaux, “Introduction to Stochastic Programming,” Springer, New York, 1997. [2] S. W. Wallace and W. T. Ziemba, Eds., “Applications of Stochastic Programming,” Society for Industrial and Ap- plied [3] A. J. King and vex Stochastic [4] A. J. King and R. T. Rockafellar, “Asymptotic Theory for Solutions in Statistical Estimation and Sto gramming,” Mathematics for Operations Research, Vol. 18, No. 1, 1993, pp. 148-162. doi:10.1287/moor.18.1.148 [5] A. Shapiro, “Asymptotic Analysis of Stochastic Programs,” Annals of Operations Resesrch, Vol. 30, No. 1, 1991, pp. 169-186. doi:10.1007/BF02204815 [6] J. Dupacova and R. Wets, “Asymptotic Behavior of Sta- tistical Estimators and of Optimal Solutions of Stochastic Optimization Problems,” Annals of Statistics, Vol. 16, No. 4, 1988, pp. 1517-1549. doi:10.1214/aos/1176351052 [7] T. Pennanen and M. Koivu, “Epi-Convergent Discretiza- tion of Stochastic Programs via Integration Quadratures,” Numerische Mathematik, Vol. 100, No. 1, 2005, pp. 141- 163. doi:10.1007/s00211-004-0571-4 [8] S. A. Smolyak, “Interpolation and Quadrature Formula for the Class a W and a E,” Doklady Akademii Nauk SSSR, Vol. 131, 1960, pp. 1028-1031. (in Russian, Eng- lish Translation: Soviet Mathematica Doklady, Vol. 4, 1963, 9129717644 pp. 240-243). [9] T. Gerstner and M. Griebel, “Numerical Integration Us- ing Sparse Grid,” Numerical Algorithms, Vol. 18, No. 3-4, 1998, pp. 209-232. doi:10.1023/A:101 Cost [10] M. Chen and S. Mehrotra, “Epiconvergent Scenario Gen- eration Method for Stochastic Problems via Sparse Grid,” Stochastic Programming E-Print Series, Vol. 2008, No. 7, 2008. [11] L. C. Evans, “Partial Differential Equations,” American Mathematical Society, Vol. 37, No. 3, 1998, pp. 363-367. [12] G. W. Wasilkowsi and H. Wozniakowski, “Explicit Bounds of Algorithms for Multivariate Tensor Product Problems,” Journal of Complexity, Vol. 11, No. 1, 1995, pp. 1-56. doi:10.1006/jcom.1995.1001 [13] H. Brass and G. H¨ammerlin, Eds., “Bounds for Peano kernels,” Vol. 112, Birkhäuser, Basel, 1993, pp. 39-55. [14] H. Wozniakowski, “Information-Based Complexity,” An- nual Review of Computer Science, Vol. 1, No. 1, 1986, pp. 319-380. doi:10.1146/annurev.cs.01.060186.001535 [15] C. Roos, T. Terlaky and J.-P. Vial, “Interior Point Methods for Linear Optimization,” Springer, New York, 1997. ew De- [16] N. Megiddo, “Progress in Mathematical Programming, Chapter Pathways to the Optimal Set in Linear Program- ming,” Springer-Verlag, New York, 1989, p. 132. [17] A. V. Fiacco, “Int roduction to Se nsitivity and Stab ility Ana- lysis in Nonlinear Programming,” Academic Press, N York, 1983. [18] O. Güler, D. den Hertog, C. Roos and T. Terlaky, “ generacy in Interior Point Methods for Linear Program- ming: A Survey,” Annals of Operations Research, Vol. 46-47, No. 1, 1993, pp. 107-138. doi:10.1007/BF02096259 [19] Y. Nesterov and A. Nemirovskii, “Interior Point Polyno- mial Algorithms in Convex Programming,” Society for 2001. Interior-Point Methods,” Soci- 800 Industrial and Applied Mathematics, Philadelphia, 1994. [20] J. Renegar, “A Mathematical View of Interior-Point Me- thods in Convex Optimization,” Society for Industrial and Applied Mathematics, Philadelphia, [21] S. J. Wright, “Primal-Dual ety for Industrial and Applied Mathematics, Philadelphia, 1997. [22] W. Römisch, “An Approximation Method in Stochastic Optimal Control,” In: Optimization Techniques, Part 1, Lecture Notes in Control and Information Scienc es, Sprin- ger-Verlag, New York, 1980, pp. 169-178. [23] H. Attouch, “Variational Convergence for Functions and Operators,” Pitman (Advanced Publishing Programs), 1984. [24] H. Attouch and R. J.-B. Wets, “Quantitative Stability of Variational Systems: I. The Epigraphical Distance,” Tran- sactions of the American Mathematical Society, Vol. 328, No. 2, 1991, pp. 695-729. doi:10.2307/2001 Vol. 11, No. 1, 1998, pp. 9-18. [25] P. Kall, “Approximation to Optimization Problems: An Elementary Review,” Mathematics of Operations Re- search, doi:10.1287/moor.11.1.9 [26] T.-W. Ma, “Higher Chain Formula Proved by Combina- torics,” The Electronic Journal of Combinatorics, Vol. 16, No. 21, 2009.  S. Y. CHEN301 tion and or a random vector on with invertible cumulative ion om Appendix A. Inverse Transforma Truncation F distribution function 1:0,1 d F, the integrat domain of a mollifier function can be transformed fr to 0,1 d: 1 ,, d= d, xx FF [0,1]d then we apply the sparse grid method to generate scenar- s and weights iofor on the cube. We need to check the properties of the integrand . Its differentiability on ly depends on 0,1 d function 1 ,xF 1()F since ,() xC . Most commonly used invertible cu- mulative distribution functions, for eple, inverse of normal distribution function 1 , is also in C xam . The finiteness of the partial derivatives of 1 ,xF only d also epends on 1 F since partial derivatives of ,x are finite for any multi-index 1 compo- nent-wisely. The higher order partial derivative of aposite function can be calculated exp licitly. For :fg hxXy Yz , we can ap- ply the Faà di Bruno’s formula: com n d==, d nnPB nPBP gxf gxfgxgx x where n is the set of all partit ions of the set n of intege . A partition of rs 1,,nn s of is a family oir- wise dinempty subsetf pa sjoint non whose un ision n . means the cardinality of the set . For a vec- p rm tor comsite function: :, fg hy Yz We apply Tsoy-Wo Ma’s higher chain foula [26]: o x X ,, =1 11 =! !! mk p msk mp k spm kkk z z y mpxy x w here is the set of all decompositions of multi-index with multiplicities Calculat ion involving a multi- x m. inde 1,, follows rules: =1 =1 =,!=!, = . jj jj j z =1 =1 =, j j jj j xz x A multi-index decomposes into parts 1,, pp in with multiplicities 1,, mm in respectively if the decomposition equation 1122 = s mp mpmp holds and all parts are different. The total multiplicity is defined as 12 =. mmmm The list ,, pm ed a is call -decomposition of . nsure all parts are different we may impose 12 0 To e pp p , where means =,,= 111 jj , but < j , for a j . For the problem under discussion, let 1 compo- nent-wisely, i.e., =1r, note that are 21 d number of such (s). Folg the higher c formula, we get lowinhain rule 1 , 11 =. x k F ,! m p msk x mp k ce ,, =1 !! spmkkk mp Furthermore, sin 2 0, mx by Proposi- tion 2.3, the computation of =0 li 1 F 0, lim x can be simplified significantly. In this case, only the de- compositions 1,, i e , -zeros in the i e is the th unit basis of cor- respond to nonula. Otherwise, for i above form d , , 1 = mm , and 0,=0 lim m x m . 2 Hence , 00=1 imdxi iiw 1 ,= lim l xi F * , =1 =. di ii x i uw Hence, 1* ,, 1 0 =< d xi = 1 212 , lim i ix di Fu if and only if < i almost surely 1,=1, ,id . For some distributions, the condi- tion might not hold. For example, the inverse of a cumu- lative function of the normal distribution does not have this property nearby 0 or 1. To remove the singularities, truncation of the cube [0, 1] could be applied: where d 0,1 ,1 ()d d, dhxxhxx 0< <1 han we need t is a small positive number. To com- d siderd sparse grid method,o change the variable to, where pute the right using the standa y Copyright © 2011 SciRes. AJCM  S. Y. CHEN 302 =12:0xy ,1,1 dd 1 . Hence ,1 0,1 d=1212 d. d dd hx xhy y Hence for a two-stage linear problem with an invert- ible but unbounded cumulative distribution function , we shall first generate the standa weights , 1 =12,=12, d kkkk ww finally use the and , kk w in the approximation model (2) The erproximation model is exactly the . ror of this ap sum of truncation error t e, and sparse grid approxima- tion error e. Erro rd grid points and =1 kk w using the sp karse grid method, then scale and transform them to the original random variable by r goes down with t e and error e goes do wng wn ith increasi at der rate sparse gethod. the first or of rid m Copyright © 2011 SciRes. AJCM
|
