First Order Convergence Analysis for Sparse Grid Method in Stochastic Two-Stage Linear Optimization Problem

Shengyuan Chen

.

DOI: 10.4236/ajcm.2011.14036                

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

Conflicts of Interest

The authors declare no conflicts of interest.

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 Applied Mathematics, 2005.
[3]	A. J. King and R. J.-B Wets, “Epi-Convergency of Con- vex Stochastic Programs,” Stochastic and Stochastic Re- ports, Vol. 34, 1991, pp. 83-92.
[4]	A. J. King and R. T. Rockafellar, “Asymptotic Theory for Solutions in Statistical Estimation and Stochastic Pro- 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 and ,” Doklady Akademii Nauk SSSR, Vol. 131, 1960, pp. 1028-1031. (in Russian, Eng- lish Translation: Soviet Mathematica Doklady, Vol. 4, 1963, 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:1019129717644
[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 Cost 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.
[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, “Introduction to Sensitivity and Stability Ana- lysis in Nonlinear Programming,” Academic Press, New York, 1983.
[18]	O. Güler, D. den Hertog, C. Roos and T. Terlaky, “De- 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,” SIAM, Philadelphia, 1994.
[20]	J. Renegar, “A Mathematical View of Interior-Point Me- thods in Convex Optimization,” SIAM, Philadelphia, 2001.
[21]	S. J. Wright, “Primal-Dual Interior-Point Methods,” SIAM, Philadelphia, 1997.
[22]	W. R?misch, “An Approximation Method in Stochastic Optimal Control,” In: Optimization Techniques, Part 1, Lecture Notes in Control and Information Sciences, 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/2001800
[25]	P. Kall, “Approximation to Optimization Problems: An Elementary Review,” Mathematics of Operations Re- search, Vol. 11, No. 1, 1998, pp. 9-18. 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.